2025년도 2학기 특론: 매개변수 알고리즘 (CSED701A-01) 강의계획서

1. 수업정보

학수번호 CSED701A 분반 01 학점 3.00
이수구분 전공선택 강좌유형 강의실 강좌 선수과목
포스테키안 핵심역량
강의시간 화, 목 / 14:00 ~ 15:15 / 제2공학관 강의실 [109호] 성적취득 구분 G

2. 강의교수 정보

오은진 이름 오은진 학과(전공) 컴퓨터공학과
이메일 주소 jin9082@postech.ac.kr Homepage https://sites.google.com/view/eunjinoh/
연구실 알고리즘 연구실 전화 054-279-2389
Office Hours

3. 강의목표

매개변수 복잡도 이론 (parameterized complexity) 는 고전적인 알고리즘 분석법에서 벗어나 고전적인 방법보다 더 정밀하게 알고리즘의 수행 시간을 분석하기 위해 도입된 이론이다. 고전적인 분석법은 알고리즘의 수행 시간을 입력 값의 크기에 대한 함수로 표현한다. 반면에 매개변수 복잡도 이론에서는 새로운 하나 이상의 파라미터를 도입하여 알고리즘의 수행 시간을 이 파라미터와 입력 값의 크기의 함수로 표현한다. 이를 통해 고전적인 분석법보다 더 정교하게 알고리즘의 퍼포먼스를 분석할 수 있다.
본 과목에서는 효율적인 매개변수 알고리즘과 이를 설계하기 위한 몇가지 테크닉을 공부한다. 또한 W-hierarchy 등 매개변수 복잡도 이론 (parameterized complexity) 의 중요한 개념도 다룬다.

4. 강의선수/수강필수사항

(추천 선수) CSED 331알고리즘

5. 성적평가

중간고사(30%), 기말고사(20%), 과제(30%) 발표(20%)

6. 강의교재

도서명 저자명 출판사 출판년도 ISBN
Parameterized Algorithms Marek Cygan, Fedor V.Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk Michal Pilipczuk, Saket Saurabh Springer Cham 2015 978-3-319-21274-6

7. 참고문헌 및 자료

8. 강의진도계획

1주차: Introduction to parameterized algorithms
2주차: Kernelization
3주차: Bounded search trees
4주차: Iterative compression
5주차: Randomized methods in parameterized algorithms
6주차: Graph minor theory
7주차: Treewidth I
8주차: 중간고사
9주차: Treewidth II
10주차: Treewidth III
11주차: W-hierarchy
12주차: Lower bounds based on ETH I
13주차: Lower bounds based on ETH II
14주차: Presentation
15주차: 기말고사

9. 수업운영

이론강의, 발표

10. 학습법 소개 및 기타사항

11. 장애학생에 대한 학습지원 사항

- 수강 관련: 문자 통역(청각), 교과목 보조(발달), 노트필기(전 유형) 등

- 시험 관련: 시험시간 연장(필요시 전 유형), 시험지 확대 복사(시각) 등

- 기타 추가 요청사항 발생 시 장애학생지원센터(279-2434)로 요청

강의계획서 복사
번호 학기명 학수번호 분반 강좌명