L.O.K

경험적인 탐색 방법 정보를 기반으로 탐색하는 알고리즘이다. 휴리스틱 정보(Heuristic Information)를 이용하여 휴리스틱 탐색 방법으로도 불린다. ( * 휴리스틱 정보 : 사람이 유용할거라 판단한 정보 ) 휴리스틱 정보(Heuristic Information) 현재상태와 목표상태가 주어졌다. 여기서 휴리스틱 정보를 뽑아보자. h1(N) : 현재상태를 목표 상태와 비교했을 때, 목표상태와 일치하지 않은 현재상태의 타일의 개수 2, 1, 8, 4 타일은 목표상태와 위치가 다른 타일이다. 그러므로 h1(N)은 4가 된다. h2(N) : 각 타일의 목표 위치간 거리 2, 1, 8, 4 타일이 목표 위치와 얼마나 떨어져 있는지 계산해야 한다. 2 와 1은 한 칸, 8 과 4는 두 칸이므로 h2(N)은..

맹목적 탐색 ( 목적없이 탐색 ) - 깊이 우선 탐색 - 너비 우선 탐색 - 균일 비용 탐색 넓이 우선 탐색 ( BFS; Breadth First Search ) 루트 노드의 모든 자식 노드를 탐색한 다음 해가 없으면 다음 레벨로 넘어가 탐색하는 알고리즘 탐색 대상인 '노드(Node)'는 동적으로 생성된다. ( 미리 생성 X ) OPEN-CLOSED 리스트 확장이 가능한 상태(노드)는 동적으로 생성된다. 동적으로 생성된 노드 중 이미 탐색했던 상태와 동일한 상태가 존재할 수 있다. 동일한 상태를 검사하는 오버헤드를 줄이기 위해 두 가지 리스트를 사용한다. - OPEN 리스트 : 확장은 되었으나 탐색되지 않은 상태 리스트 - CLOSED 리스트 : 탐색이 끝난 상태 리스트 BFS 알고리즘 1. OPEN 리..

알파고는 딥러닝으로 가장 가능성 높은 몇 개의 수를 추려낸 후 탐색기법을 적용하여 다음 수를 읽었다. 361! 개의 경우의 수에서 가능성 있는 1000가지를 추리고 1000가지에 탐색기법을 적용한다. 이번 포스팅에서는 탐색기법을 다루어 보겠다. 탐색(Search)이란, 상태공간에서 초기상태에서 목표상태까지의 경로를 찾는 것이 탐색이다. 연산자는 다음 상태를 생성한다. 맹목적 탐색 ( 목적없이 탐색 ) - 깊이 우선 탐색 - 너비 우선 탐색 - 균일 비용 탐색 깊이 우선 탐색 ( DFS; Deep First Search ) 해가 존재할 가능성이 있는 한 앞으로 계속 전진하여 탐색하는 방법 탐색 대상인 '노드(Node)'는 동적으로 생성된다. ( 미리 생성 X ) OPEN-CLOSED 리스트 확장이 가능한 ..

인공지능의 태동 1943년 Warren Mculloch와 Walter Pitts는 뉴런들의 간단한 네트워크를 분석 생물학적 개념인 뉴런을 컴퓨터적 컨셉으로 제시 튜링테스트 1950년, 영국의 수학자 앨런 튜링은 기계와 사람을 구분할 수 없다면 인공지능이 구현되었다고 판단 퍼셉트론(Perceptron) 컨셉과 개념으로만 제시되었던 인공신경망을 수학적 모델과 알고리즘으로 제시 범용성이 없고 제한적인 영역만 가능 첫번째 AI 겨울 ( 1970년대 ) 범용적 인공지능을 원하던 시대의 요구를 퍼셉트론이 충족하지 못하면서 인공지능에 대한 관심이 떨어짐 1970년대는 충분한 컴퓨팅 파워가 부족 ( CPU 처리속도, 메모리 용량 ) 방대한 정보를 다룰 만한 데이터베이스를 만들지 못하고 어떻게 학습해야 하는지도 모름 A..

인공지능(Artificial Intelligence)란, 인간의 인지적 기능을 흉내내어 문제를 해결하기 위하여 학습하고 이해하는 기계 인간의 지능 - 학습 ( Learning ) : 과거의 패턴들로부터 학습할 수 있는 능력 - 추론 ( Reasoning ) : 주위 상황으로부터 추론할 수 있는 능력 - 문제해결 ( Problem Solving ) : 복잡한 문제를 분석하고 해결할 수 있는 능력 - 빅데이터 ( Big data ) : 큰 용량의 변화하는 데이터 처리 가능 학습과 추론이 선행되면 문제해결이 가능해지고 빅데이터는 학습과 추론 및 문제해결의 근간이 된다. 인공지능의 종류 - 약인공지능 : 특정 영역에 국한된 인공지능 ( 체스, 바둑, 일기예보 ) - 강인공지능 : 일반적인 영역에서 문제를 해결하..

상호배제를 보장받기 위한 요구조건이 있다. 1) 단 하나의 프로세스만이 임계영역에 진입되어야 한다. 2) 임계 영역이 아닌 곳에서 수행이 멈춘 프로세스는 다른 프로세스 수행을 간섭해서는 안된다. 3) 임계 영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안된다. 4) 임계 영역이 비어있으면 즉시 임계영역에 들어갈 수 있다. 5) 프로세서 개수나 상대적 프로세스 수행속도에 대한 가정은 없어야 한다. ( 독립적 ) 6) 임계 영역에 들어간 프로세스는 일정시간 내에 나와야 한다. 상호배제 보장 요구조건 만족을 위한 하드웨어 지원 1) 인터럽트 금지 단일처리기에서의 병행처리는 오버래핑(Overlapping)이 아닌 인터리빙(Interleaving)이 일어난다. 그러므로 임계영역에 들어간 프로세스의 ..

프로세스간 관계는 3가지가 있다. 1. 경쟁관계 독립적인 프로세스는 다른 프로세스를 인식하지 못하면 경쟁(competition)에 놓인다. 주로 '타이밍'에 영향을 받는다. 디스크, 파일, 프린터를 동시에 사용하려는 경쟁이 발생하므로 OS는 이를 제어해야한다. - 상호배제 두 개의 프로세스가 동시에 접근할 수 없는 자원을 임계자원(critical resource)라 한다. 임계자원이 존재하는 코드를 임계영역(critical section)이라 한다. 상호배제란 한 프로세스만이 임계영역에 들어갈 수 있음을 의미한다. 상호배제가 보장되지 않으면 여러 프로세스가 자원에 동시에 접근하게 된다. 그러므로 OS는 상호배제를 보장해주어야 한다. 그러나 상호배제 방식은 상황에 따라 다르며 OS가 모든 상호배제 요구사항..

OS는 한정된 자원을 최대한 사용하기 위해 병렬처리를 한다. 병렬처리를 위한 기법으로 인터리빙(Interleaving)과 오버래핑(Overlapping)이 있다. 인터리빙은 멀티프로그래밍을 구현한다. 처리기가 하나여도 여러 개의 프로세스를 번갈아 실행하면서 마치 병렬적으로 처리되고 있는 듯 보이게 한다. 오버래핑은 멀티프로세싱을 구현한다. 여러 개의 처리기로 동시에 여러 작업을 처리한다. 한 처리기로 프로세스A를 처리하면서 다른 처리기로 프로세스B를 처리하는 것과 같다. 병렬처리를 통해 구현된 성질을 병행성이라고 부른다. 병행성에는 한 가지 문제점이 있다. 각각의 프로세스의 속도를 예측할 수 없다는 것이다. 예측할 수 없는 프로세스들이 동일한 자원을 두고 경쟁하다보니 많은 문제를 야기한다. 1. 전역 자..

멀티 코어 구조에서 잠재적인 성능 향상은 응용 프로그램이 병렬자원을 얼마나 효율적으로 이용할 수 있느냐에 달려있다. 여기서 성능 향상이란 처리 속도의 향상을 의미한다. Amdal의 법칙 Amdal의 법칙은 멀티코어시스템에서 수행되는 단일 응용 프로그램의 속도 향상을 구하는 공식이다. f : 전체 코드 중 병렬화 비중 1 - f : 전체 코드 중 순차동작 비중 N : 코어의 개수 1 : 단일 처리기 상에서 프로그램 실행 시간 ( 1 - f ) : 전체 코드 중 순차 코드 처리 시간 f/N : f의 병렬 코드를 N개의 코어로 나누어 처리한 시간 10%가 순차 동작하는 코드라면 f = 0.9이다. 8개의 처리기로 구성된 멀티코어 시스템이라면 속도 향상은 4.7이 나온다. 그렇다면 코어의 개수를 무한히 늘리면 ..

쓰레드는 두 가지 유형으로 나뉜다. 1) 유저 수준 쓰레드 ( ULT ; Uerser Level Thread ) 2) 커널 수준 쓰레드 ( KLT ; Kerner Level Thread ) 유저 수준 쓰레드 ( UTL ) OS 커널은 PCB를 통해 프로세스를 제어한다. 디스패처 프로그램으로 처리기 인터리빙을 구현하여 스케줄링을 제어하기도 한다. 이처럼 프로세스는 커널 영역 메모리에서 제어가 이루어진다. 그러나 쓰레드는 유저 영역 메모리 안에서도 충분히 제어를 할 수 있다. 스레드 API 라이브러리는 스레드를 제어할 자료구조와 알고리즘을 담고 있다. 라이브러리가 유저영역 메모리 안에 존재하므로 커널 모드로 전환되지 않아도 스레드를 제어할 수 있다. 커널영역에는 스레드 제어 블록을 포함한 제어 알고리즘이 존..