DD771 계산이론

2019년 2학기
경기대학교 컴퓨터과학과


공지사항은 수시로 체크! | 과제물, 강의자료 | 일정

수업시간 및 강의실

  • Class A (1383): 월요일 678 (14:00-17:00), 종합강의동 305호
  • Class B (1713): 화요일 123 (09:00-12:00), 종합강의동 302호
  • Class C (1714): 수요일 123 (09:00-12:00), 종합강의동 308호

평가

  • 출석: 20%
  • 중간고사: 30%
  • 기말고사: 30%
  • 과제물, 참여도 및 기타: 20%

교재

  • [MS] Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012
    Download free ebook
  • [L] Introduction to Formal Languages and Automata, 6th ed., Peter Linz
  • [Sip] Introduction to the theory of computation, M. Sipser, PWS Publishing Company, 1997

담당교수

  • 배상원
  • 연구실: 8309
  • 전화: 9677
  • 홈페이지: 링크
  • 이메일:
  • 상담 환영

공지사항

  • (9/9) 월요일 분반(1383) 강의실이 종합강의동 305 호로 변경되었습니다.
  • (8/30) 계산이론(DD771) 홈페이지가 개설되었습니다.
공지사항은 수시로 확인해주세요.

과제물

제출시 주의사항
- 표지에 분반(목 혹은 금), 학번, 이름 명시
- 손으로 쓰거나 워드프로세스하거나 알아볼 수 있게
- 제출은 수업시간 시작 전에
  • Homework#1: Ex. 1.1, 1.2, 1.4, 1.6, 1.7 ([3주] 수업까지)
    혹시나 해서 한국어 번역
    1.1 Induction을 이용하여, 2 이상의 자연수는 소수들의 곱으로 표현할 수 있음을 증명하시오.
    1.2 임의의 소수(prime number) p에 대해, (루트 p)는 무리수임을 증명하시오.
    1.4 Induction을 이용하여, 모든 1이상의 정수 n에 대해 n4-4n2는 3의 배수임을 증명하시오.
    1.6 0이상의 임의의 정수 n에 대해, n3 + (n+1)3 + (n+2)3은 항상 9의 배수임을 증명하시오.
    1.7 {1, 2, ..., 2n} 중에서 임의로 n+1개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어있게 된다. 왜?

강의자료

  1. 주교재: [MS] Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2019

그 밖에 도움이 될 만한 자료


일정

강의 관련자료 과제
1주 (9/2-9/4) 과목소개 --- ---
2주 (9/9-9/11) 기본 수학 지식 [MS] Chap. 1, [Sip] Chap. 0 HW#1 게시
3주 (9/16-9/18) Finite Automata and Regular Languages [MS] Chap. 2, [Sip] Chap. 1 HW#1 제출
4주 (9/23-9/25) Finite Automata and Regular Languages [MS] Chap. 2, [Sip] Chap. 1 HW#2 게시
5주 (9/30-10/2) Finite Automata and Regular Languages [MS] Chap. 2, [Sip] Chap. 1 HW#2 제출
HW#3 게시
6주 (10/7-10/9) Finite Automata and Regular Languages [MS] Chap. 2, [Sip] Chap. 1
7주 (10/14-10/16) Context-Free Languages [MS] Chap. 3, [Sip] Chap. 2 HW#3 제출
중간고사 (10/17(목): 17:00~) 중간고사
8주 (10/21-10/23) 중간고사 리뷰
9주 (10/28-10/30) Context-Free Languages [MS] Chap. 3, [Sip] Chap. 2 HW#4 게시
10주 (11/4-11/6) Context-Free Languages
Formal Grammars and Chomsky Hierarchy
[MS] Chap. 3, [Sip] Chap. 2
11주 (11/11,-11/13) Turing Machines [MS] Chap. 4, [Sip] Chap. 3 HW#4 제출
HW#5 게시
12주 (11/18-11/20) Turing Machines [MS] Chap. 4, [Sip] Chap. 3 HW#5 제출
13주 (11/25-11/27) Decidability and Enumerability [MS] Chap. 5, [Sip] Chap. 4
14주 (12/2-12/4) Decidability and Enumerability [MS] Chap. 5, [Sip] Chap. 4
기말고사 (12/6(금): 17:00~) 기말고사
15주 (12/12 17:00~) 기말고사 리뷰

일정은 변동될 수 있으며 변동될 경우 사전에 공지합니다.


공지사항은 수시로 체크! | 과제물, 강의자료 | 일정



Managed by Sang Won Bae
Associate Professor
Dept. Computer Science, Kyonggi University
Suwon, Korea.