2. 강의교수 정보
|
이름 |
배경민 |
학과(전공) |
컴퓨터공학과 |
| 이메일 주소 |
kmbae@postech.ac.kr
|
Homepage |
|
| 연구실 |
054-279-2256 |
전화 |
054-279-2256 |
| Office Hours |
|
3. 강의목표
This course provides an in-depth exploration of the theoretical foundations of computation. It focuses on formal models of computation, complexity classes, and the relationships between computational problems. The course covers fundamental topics such as Turing machines, undecidability, and computational complexity, along with advanced topics such as the complexity of logical theories, interactive proofs, and probabilistic complexity.
4. 강의선수/수강필수사항
Algorithms
Automata & Formal Languages
6. 강의교재
| 도서명 |
저자명 |
출판사 |
출판년도 |
ISBN |
|
Theory of Computation
|
Dexter C. Kozen
|
Springer
|
2006
|
|
7. 참고문헌 및 자료
Dexter C. Kozen, Automata and computability. Springer, 2012.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
8. 강의진도계획
- Turing machines
- Undecidability and Reducibility
- Arithmetic Hierarchy
- Time and Space Complexity Classes
- NL and P
- PSPACE and Polynomial Time Hierarchy
- Undecidability of First-Order Logic
- Complexity of Decidable Theories
- Descriptive Complexity
- Parallel Complexity
- Probabilistic Complexity
- Interactive Proofs
- Probabilistically Checkable Proofs
11. 장애학생에 대한 학습지원 사항
- 수강 관련: 문자 통역(청각), 교과목 보조(발달), 노트필기(전 유형) 등
- 시험 관련: 시험시간 연장(필요시 전 유형), 시험지 확대 복사(시각) 등
- 기타 추가 요청사항 발생 시 장애학생지원센터(279-2434)로 요청