이번 시간에는 A* algorithm, heuristics, forward search 등을 배운다. Heuristic Search Strategies FIFO 나 LIFO 는 와 달리 heuristic algorithm 은 search space 에 대한 정보를 이용한다. heuristic function h: state space -> R 은, problem-specific knowledge 를 problem-independent way 로 표현한다. best-first search 알고리즘은 general tree search 알고리즘의…
What is a general-purpose computer? Are there limits on the power of digital computers? Are there limits on the power of machines we can build? 컴퓨터 과학자들이 computation 에 관해 질문해 온 것들이다. 이 문제에 답하기 위해 computation model 을 좀 살펴보자. 긴 테이프가 있고, 기계는 테이프를 하나씩 읽어 0인지…
linear programming: problem-solving model for optimal allocation of scarce resources, among a number of competing activities that encompasses maxflow, MST, shortest paths, assigment, Ax = b, 2-person zero-sum games 등이 있다. 다시 말해서, constraints 를 지키면서 특정 값을 maximize 하는 문제다. 따라서 주어진 문제를 아래의 형태로 reduction 해야 한다. (http://www.…
앞으로 남은 3챕터에서 배울 내용은 reduction, linear programming, intractability 이다. 따라서 지금까지의 관심에서 좀 벗어나 from individual problems to problem-solving models from linear / quadratic to polynomial / exponential scale from details of implementation to conceptual framework Intro to Reduction reduction 챕터에서는 다음의 내용을 다룬다. design algorithms estabilish lower bounds classify problems…
Data Compression 주된 이유는 전송 시간과 저장 공간을 절약하기 위해서다. 무어의 법칙이 말해주듯이 제품의 성능은 점점 좋아지는데, 그럼에도 불구하고 사람들이 만들어 내는 데이터의 양은 더 급격히 증가한다. 그래서 압축이 필요하다. 이번시간에 배울 기법은 3 가지다. Run-length Huffman LZW data compression 응용은 generic file compression GZIP 같은 파일 압축이나, PKZIP 같은…