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
  • 홈페이지: 링크
  • 이메일:
  • 상담 환영

공지사항

  • (10/11) 중간고사 시험은 closed book으로 진행합니다.
  • (10/11) 중간고사 범위는 교재의 1장~3장 중 [7주]까지의 수업에서 다룬 내용입니다.
  • (10/11) 중간고사는 10월 17일(목) 17:00~, 8509호(8강의동, 5층 세미나실) 에서합니다
  • (9/29) 수요일 분반(1714)의 [6주] 수업은 한글날 공휴일 대신 10월 7일 오후 5시부터 보강 진행합니다.
  • (9/29) HW#3이 게시되었습니다. 제출 기한은 [7주]까지입니다.
  • (9/23) HW#2가 게시되었습니다. 제출 기한은 [5주]까지입니다.
  • (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개의 수를 고르면 그중에는 꼭 연속된 두 수가 들어있게 된다. 왜?

  • 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).

  • Homework#3: ([7주] 수업까지)
    Ex. 2.11, 2.12, (2.13의 1, 2, 4, 6번), 2.14, (2.20의 1, 3번), 2.21, 2.22
    아래의 설명과 힌트를 참고하세요.
    2.11 이 문제는 지금까지 배운 내용 중에서도 Theorem 2.6.1~2.6.4를 이용해서 쉽게 증명할 수 있습니다.
    2.12 각 regular expression에 속하는 string 두개와 속하지 않는 string 두 개를 제시하시오.
    2.13 다음 language를 describe하는 regular expresssion을 써보세요.
      2.13.1 {w | w는 적어도 3개의 1을 포함한다.}
      2.13.2 {w | w는 최소 2개의 1과 최대 1개의 0을 포함한다.}
      2.13.4 {w | w는 정확히 2개의 0과 최소 2개의 1을 포함한다.}
      2.13.6 {w | w의 모든 홀수 번째 자리는 1이 위치한다.}
    2.14 다음 regular expression을 같은 language를 accept하는 NFA로 변환(convert)하시오.
    2.20 Pumping Lemma를 이용하여 각 language가 regular language가 아님을 증명하시오.
    2.21 {ambn | m과 n은 0이상의 서로 다른 정수}가 regular하지 않음을 증명하시오.
      (힌트) {anbn | n >= 0}이 regular하지 않은 사실과 2.6절에서 배운 regular operation을 이용하면 간단~
    2.22 다음과 같은 language A와 B의 실례를 찾아보세요.
      2.22.1 A는 regular이고 B는 regular가 아니면서 B가 A를 포함하는 경우
      2.22.2 A는 regular가 아니고 B는 regular이면서 B가 A를 포함하는 경우

강의자료

  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.