DD771 계산이론

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


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

수업시간 및 강의실

  • Class A (1322): 목요일 678 (14:00-17:00), 종합강의동 206호
  • Class B (1954): 금요일 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/15) 중간고사 범위는 교재의 1장~3장 중 [7주]까지의 수업에서 다룬 내용입니다.
  • (10/15) 중간고사에서는 A4 용지 2장(4면)에 직접 작성한 노트만을 참조할 수 있습니다. 이 노트는 시험 후에 제출합니다.
  • (10/15) 중간고사는 10월 22일(월) 17:00~, 8509호(8강의동, 5층 세미나실) 에서 합니다
  • (10/4) Homework#3가 게시되었습니다. [7주] 수업시간에 제출하세요.
  • (9/27) Homework#2가 게시되었습니다. [5주] 수업시간에 제출하세요.
  • (9/13) 계산이론 교과목 학기초 설문을 진행합니다. KUTIS에서 9/28까지 설문 응답하세요. 설문하지 않은 자는 감점할 수 있습니다.
  • (9/13) Homework#1이 게시되었습니다. [3주] 수업시간에 제출하세요.
  • (9/7) 목요일 분반(1322) 강의실이 종합강의동 206 호로 변경되었습니다.
  • (8/17) 계산이론(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, 2012

그 밖에 도움이 될 만한 자료


일정

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

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


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



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