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

공지사항

  • (11/20) 기말고사는 12월 4일(월) 17:00~, 6405호(6강의동, 4층) 에서 합니다
  • (11/20) 계산이론 교과목 학기말 설문을 진행합니다. KUTIS에서 12/8까지 설문 응답하세요. 설문하지 않은 자는 감점할 수 있습니다.
  • (10/25) 중간고사 결과 공개
  • (10/25) 10/26, 10/27 [9주] 수업합니다.
  • (10/18) 중간고사 범위는 교재의 1장~3장 중 [8주]까지의 수업에서 다룬 내용입니다.
  • (10/18) 중간고사는 10월 23일(월) 17:00~, 8509호(8강의동, 5층 세미나실) 에서 합니다
  • (10/12) 10/16 17시 부터 8509호(8강의동, 5층 세미나실)에서 보강을 합니다.
  • (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).
  • Homework#3: ([8주] 수업까지)
    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를 포함하는 경우

  • Homework#4: ([11주] 수업까지)
    Ex. 3.1, 3.4, 3.5, (3.8의 1,3,5)
    아래의 설명과 힌트를 참고하세요.
    3.1 각 language에 해당하는 CFG를 구하시오. Alphabet은 {0, 1}입니다.
      + {02n1n | n >=0 }
      + {w | w는 최소 3개의 1을 포함한다.}
      + {w | w의 길이는 홀수이며 정 가운데의 symbol은 0이다.}
      + {w | w는 palindrome이다.}
        Palindrome이란 왼쪽부터 읽으나 오른쪽부터 읽으나 같게 읽히는 string을 말한다.
      + {w | w의 첫 symbol과 마지막 symbol이 같다.}
      + {w | w의 첫 symbol과 마지막 symbol이 다르다.}
    3.4 A와 B가 각각 CFL(context-free language)일 때에
    아래의 세 가지 연산을 해도 결과물이 역시 CFL임을 보이라는 이야기.

    3.5 다음 두 language A와 B에 대하여 아래의 문제를 푸세요.
        A = {ambncn | m >=0, n>=0}, B = {ambmcn | m >=0, n>=0}

      + A와 B를 정의하는 CFG를 만들어서, A와 B가 CFL임을 보이세요.
      + 3.8.2절을 통해 {anbncn | n>=0}이 CFL이 아님을 알 수 있습니다.
       이 사실을 통해 두 CFL의 교집합(intersection)이 늘 CFL이 되지는 않는다는 것을 설명하세요.
      + 어떤 CFL의 complement가 반드시 CFL이 되지 않을 수 있다는 것을 보이세요. (드모르간 법칙을 이용)
    3.8 다음의 language를 accept하는 PDA(pushdown automata)를 만드세요. Alphabet은 {0, 1}입니다.
      3.8.1 {02n1n | n >=0 }
      3.8.3 {w | w는 1의 개수가 0의 개수보다 많다.}
      3.8.5 {w | w는 palindrome이다.}

  • Homework#5: ([13주] 수업까지)
    Ex. 4.1, 4.2, 4.4, 4.5(옵션)
    아래의 설명과 힌트를 참고하세요.
    이번 문제는 모두 특정 language를 accept하는 Turing Machine을 작성하는 것입니다.
    아래의 유의사항에 따라 답안을 작성하세요.

    4.1번: 문제에서 요구하는 대로 one-tape Turing machine을 만든다.
      먼저 대략적인 idea를 한국어 혹은 영어로 서술한다. (각 state의 의미라던지 어떤 단계로 TM이 동작하는지)
      이후, TM의 instruction들을 기술한다.
    4.2번: {w | w는 0의 개수가 1의 개수의 두배이다.}
      문제에서는 one-tape Turing machine을 요구하지만 필요하다면 multi-tape Turing machine을 만들어도 좋다.
      먼저 대략적인 idea를 한국어 혹은 영어로 서술한다. (각 state의 의미라던지 어떤 단계로 TM이 동작하는지)
      이후, TM의 instruction들을 기술한다.
    4.4번: 자연수 x가 이진수 형식으로 (즉, 0과 1로 이루어진 string) tape에 기록되어 있을 때,
      이것을 x+1로 변환하여 기록하는 one-tape Turing machine을 만드시오.
      이 문제의 TM은 accept state 혹은 reject state가 따로 존재하지 않고 "종료 state"인 q1을 갖는다.
      4.1, 4.2번과 마찬가지로 대략적인 idea를 먼저 한국어 혹은 영어로 서술한다.
    4.5번: 4.4번에서 만든 TM을 이용하여 두 자연수 x와 y가 주어질 때에 x+y를 계산하는 TM을 만들어라.
      이 문제는 옵션(보너스 문제)입니다.
      당신의 TM이 어떻게 동작하는지를 한국어로 서술하십시오.
      instruction을 모두 기술할 필요는 없습니다.

강의자료

  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 제출
HW#3 게시
추석연휴 (10/5,10/6) --- ---
6주 (10/12, 10/13) Finite Automata and Regular Languages [MS] Chap. 2, [Sip] Chap. 1
7주 (10/16(월) 17시~) 보강 (장소: 8509) [MS] Chap. 2, [Sip] Chap. 1
8주 (10/19, 10/20) Context-Free Languages [MS] Chap. 3, [Sip] Chap. 2 HW#3 제출
중간고사 (10/23(월): 17:00~) 중간고사
9주 (10/26, 10/27) 중간고사 리뷰
Context-Free Languages
[MS] Chap. 3, [Sip] Chap. 2 HW#4 게시
10주 (11/2, 11/3) Context-Free Languages
Formal Grammars and Chomsky Hierarchy
[MS] Chap. 3, [Sip] Chap. 2
11주 (11/9, 11/10) Turing Machines [MS] Chap. 4, [Sip] Chap. 3 HW#4 제출
HW#5 게시
12주 (11/16, 11/17) Turing Machines
Decidability
[MS] Chap. 4, [Sip] Chap. 3
[MS] Chap. 5, [Sip] Chap. 4
13주 (11/23, 11/24) Decidability and Enumerability [MS] Chap. 5, [Sip] Chap. 4 HW#5 제출
14주 (11/30, 12/1) Decidability and Enumerability [MS] Chap. 5, [Sip] Chap. 4
기말고사 (12/4(월): 17:00~) 기말고사 (장소: 6405)
15주 (12/7, 12/8) 기말고사 리뷰

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


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



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