3. 강의목표
This course introduces fundamental ideas and models which can answer some core questions in computer science:
(1) what is computation and algorithm?;
(2) what can and what cannot be computed?;
(3) when should an algorithm be considered practically feasible?
Topics that we discuss in this course include finite automata, regular languages, context-free languages, pushdown automata, and Turing machines. Undecidability and intractability are also briefly introduced.
This course sets a foundation for theoretical computer science, AI, PL, and compiler.
5. 성적평가
quiz (5-6 times): 25%
midterm exam: 35%
final exam: 40%
7. 참고문헌 및 자료
Primary: Introduction to Automata Theory, Languages, and Computation, 3rd edition (by J. E. Hopcroft, R. Motwani, and J. D. Ullman)
Secondary: Introduction to the Theory of Computation (by M. Sipser)
8. 강의진도계획
week 1: introduction
week 2: finite automata
week 3: regular languages
week 4: regular languages
week 5: regular languages
week 6: context-free languages
week 7: context-free languages
week 8: context-free languages
week 9: midterm exam
week 10: Turing machines
week 11: Turing machines
week 12: undecidabillity
week 13: undecidability
week 14: intractable problems
week 15: intractable problems
week 16: final exam
9. 수업운영
- COVID로 인한 온라인 강의
- 이론수업
11. 장애학생에 대한 학습지원 사항
- 수강 관련: 문자 통역(청각), 교과목 보조(발달), 노트필기(전 유형) 등
- 시험 관련: 시험시간 연장(필요시 전 유형), 시험지 확대 복사(시각) 등
- 기타 추가 요청사항 발생 시 장애학생지원센터(279-2434)로 요청