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 같은…
Regular Expression 이전까지 배웠던 패턴매칭 기법들은 모두 단일 패턴만을 찾았었. (e.g substring search) 일치하는 집합 을 원한다면 어떻게 해야할까? 예를 들어 유전자 분석에서는 Fragile X syndrome 은 GCG(CGG|AGG)*CTG 패턴에서 더 많이 반복될수록 fragile x 신드롬일 확률이 높다. 이 경우에는 하나가 아니라 몇번 일치하는지가 중요한 결과값이 된다…