DD771 계산이론

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


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

수업시간

  • Class A (1176): 목요일 123 (09:00-12:00)
  • Class B (1823): 금요일 123 (09:00-12:00)

강의실

  • Class A (1176): 종합강의동 407호
  • Class B (1823): 종합강의동 407호

평가

  • 출석: 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/15) 계산이론 교과목 학기초 설문을 진행합니다. KUTIS에서 9/30까지 설문 응답하세요. 설문하지 않은 자는 감점할 수 있습니다.
  • (8/24) 계산이론(DD771) 홈페이지가 개설되었습니다.
공지사항은 수시로 확인해주세요.

과제물

제출시 주의사항
- 표지에 분반(목 혹은 금), 학번, 이름 명시
- 손으로 쓰거나 워드프로세스하거나 알아볼 수 있게
- 제출은 수업시간 시작 전에
  • Homework#1: Ex. 1.2, 1.4, 1.6, 1.7 ([3주] 수업까지)
    혹시나 해서 한국어 번역
    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개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어있게 된다. 왜?

  • Homework#2: ([5주] 수업까지)
    Ex. (2.1의 1, 2, 3, 4, 5, 6, 10), (2.2의 1, 2, 3번), (2.3의 1, 3번), 2.4 ~ 2.6
    아래의 설명과 힌트를 참고하세요.
    2.1 다음 language를 accept하는 DFA를 만드세요. Alphabet은 {0, 1}입니다.
      2.1.1 {w | w의 길이는 3의 배수}
      2.1.2 {w | w는 110을 포함하지 않음} (substring은 부분 string이라는 의미)
      2.1.3 {w | w는 적어도 5개의 1을 포함함}
      2.1.4 {w | w는 1011을 포함함}
      2.1.5 {w | w는 적어도 두개의 1과 최대 두개의 0을 포함함}
      2.1.6 {w | w는 홀수개의 1을 포함하거나 2개의 0을 포함함}
      2.1.10 {epsilon, 0}
    2.2 다음 language를 accept하는 주어진 조건에 맞는 NFA를 만드세요. Alphabet은 {0, 1}입니다.
      2.2.1 {w | w는 10으로 끝난다}를 accept하는 3개의 state를 갖는 NFA
      2.2.2 {w | w는 1011을 포함한다}를 accept하는 5개의 state를 갖는 NFA
      2.2.3 {w | w는 홀수개의 1을 포함하거나 2개의 0을 포함함}를 accept하는 6개의 state를 갖는 NFA
    2.3 다음 language를 accept하는 NFA를 만드세요. Alphabet은 {0, 1}입니다.
      2.3.1 {w | w는 11001을 포함한다}
      2.3.3 {w | w는 1로 시작하고 0으로 끝남}
    2.4~2.6 각 state diagram이 표현하는 NFA를 DFA로 바꾸세요(convert).

강의자료

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

그 밖에 도움이 될 만한 자료


일정

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

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


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



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