계산이론

교과목 구분: 
전공선택
교과목 번호: 
M1522.002900
학년: 
대학원
학점: 
3

계산이론은 컴퓨터공학의 기초학문이며, 중요한 문제에 대한 효율적인 알고리즘들을 소개하고, 그런 알고리즘의 복잡도 분석을 다룬다. 이 교과목에서는 먼저 알고리즘의 성능을 분석하는 기법, 특히 amortized analysis에 대해 배운다. 그리고, 계산이론 분야에서 중요한 알고리즘과 그 응용에 대해 배운다. 구체적으로, (스트링 매칭, 2차원 패턴 매칭, 근사 매칭, suffix trees, 데이터 압축 문제에 대한) 스트링 알고리즘과 bioinformatics에의 응용, (선택 문제, 다항식 확인 문제에 대한) randomized 알고리즘과 그 영향, (페이지 교체 문제, k 서버 문제에 대한) online 알고리즘과 금융문제(일방향 거래와 portfolio 선택 문제)에의 응용을 배운다.