전체 글
-
운영체제의 프로세스운영체제 2020. 10. 19. 12:52프로세스 프로세스는 디스크에 저장되어 있는 실행 파일이 실행되어 메모리에 올라오면 이를 프로세스라 함 프로세스의 메모리 Text : 코드 Stack : 지역변수, 파라미터 Data : 전역변수, static 변수 Heap : 동적할당 프로세스의 상태 new : 프로스세스가 갓 생성됨 running : Instruction(명령어)가 실행 중임 waiting : 대기 중 ready : 프로세서에 할당되기를 기다리는 중 terminated : 프로세스가 실행을 마침 PCB(Process Control Block) OS가 프로세스를 관리하기 위한 자료구조로, 프로세스 1개당 PCB 1개가 할당 PCB를 Task Control block 이라고도 부름 하드웨어와 프로세스의 맵핑을 용이하게 하기 위해 필요함 구성..
-
운영체제 기본지식과 리눅스운영체제 2020. 10. 18. 18:48OS 구성도 OS User Interface GUI, Shell 등 다양한 형태로 제공 역할 명령어 해석 커널에 명령어 전달 (실행) 결과 출력 시스템 콜 주로 high level language (c, c++)로 작성되며, OS는 이를 사용자에게 제공하기 위해 API(Application Programming Interface)를 제공합니다. 시스템 함수가 호출되면 Software interrupt 가 발생하고, 인터럽트 별로 어떻게 대응할지는 IDT(Interrupt Descriptor Table)에 저장되어 있습니다. system_call()의 경우에는 entry.S에 가서 사용자가 호출한 시스템 함수의 인덱스를 찾습니다. 이후 sys_call_table 이라는 시스템콜을 정리해둔 테이블에 해당 인..
-
Local search, Hill-climbing search인공지능 2020. 10. 17. 22:29Local search 오직 현재 state 만을 저장하여 검색하는 탐색법입니다. 과거나 미래의 state sequence 를 저장하지 않기 때문에 메모리를 적게 사용합니다. Loacl search 는 goal 까지의 path 를 알아내는 것이 불가능합니다. 따라서 8-puzzle 처럼 답은 쉽지만 과정을 알아내는 문제에는 적합하지 않고, N-queen 문제처럼 과정은 몰라도 되고 답 자체를 알아내는 것에 집중되는 문제나 최적화 문제에 적합합니다. Hill-climbing search function HILL-CLIMBING(problem) returns a state that is a local maximum current ← MAKE-NODE(problem.INITIAL-STATE) loop do n..
-
Heuristic 과 Relaxed problem인공지능 2020. 10. 17. 20:50Heuristic 8-퍼즐을 푸는데 보통 22 step 정도가 필요하며 branching factor 는 평균 3이 됩니다. 가운데에 있을 때는 상하좌우 다 갈 수 있지만 구석에 있을 때는 Action 의 방향에 제약이 생기기 때문입니다. tree search 의 경우 3 ^ 22 개의 노드를 방문해야하며 이는 10 ^ 10에 달하는 큰 수입니다. 그래프 서치에도 170,000개 정도 되며 15퍼즐만 되어도 10^13 개가 됩니다. 두 개의 Admissible heuristics 를 제시합니다. h1 = 잘못 위치된 타일의 수 h2 = 잘못 위치된 타일의 위치와 정상 위치와의 맨해튼 거리의 합 위 사진에서 start state 의 h1 = 8, h2 = 18 입니다. 비교 IDS와 A*(h1), A*(h..
-
AI Informed search, Greedy Best-first Search, A* Serach인공지능 2020. 10. 17. 17:37Informed search 지금까지의 Uninformed search 와는 달리 문제 정의 이외의 정보를 활용하여 더 효율적인 검색을 하는 방법입니다. Best-first search 트리 내 노드에서 evaluation function f(n)에 의해 cost가 가장 적은 노드를 판별하여 해당 노드를 먼저 탐색합니다. f(n) 은 heuristic function h(n)을 포함하고 있습니다. h(n)은 n에서부터 goal state 까지의 최소 비용을 예측하는 함수입니다. 가령 예를 들어 Romania 문제에서 도시간의 비용이 지도에 주어졌지만 h(n)으로는 도시 n에서부터 goal 도시까지의 직선거리를 사용할 수 있을 것입니다. 지금부터 이를 hSLD라고 부르겠습니다. (SLD = Straight..
-
Iterative deepening DFS, Bidirectional Search인공지능 2020. 10. 17. 17:00Iterative Deppening DFS (IDS) Depth limit 를 조금 씩 늘려나가는 Depth limited Search 방식으로, goal state를 찾을 때까지 반복해나갑니다. function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure for depth = 0 to INFINITE do result ← DEPTH-LIMITED-SEARCH(problem, depth) if result != cutoff then return result 평가 Complete : yes ( BFS 와 같은 원리 ) Optimal : yes ( BFS 와 같은 원리 ) Time complexity : O(b^d) (BFS와 같은 ..
-
AI DFS, Depth-Limited-Search인공지능 2020. 10. 17. 16:40Depth-first search 가장 깊은 노드부터 expand 하는 기법으로, 일반 알고리즘에서 동작하는 방식과 동일합니다. AI에서는 frontier 를 LIFO 큐로 구성하여 Grpah search 하는 방식입니다. BFS = FIFO, Uniform-Cost Search = Priority queue, DFS = LIFO(Stack) 평가 Completeness Grpah search : Yes : 단 state space 이 유한한 크기일 때 Tree search : No : 방문했던 노드를 재방문 가능하므로 cycle 이 생길 수 있기 때문 Optimality No : 항상 최적은 아님 Time complexity Graph search : state space의 최대 사이즈 Tree sea..