강 의 소 개
모국어 강의 본 강의는 모국어로 이루어진다.
강 의 개 요 Finite Automata의 여러 가지 형태 및 각종 finite automata로 인식될 수 있는 언어 클래스의 성질, context-free 문법과 pushdown automata, 그리고 Turing machine과 computablity, 마지막으로 complexity의 문제를 간단히 다룬다.
추가로 context free grammar의 deterministic parsing에 관해서 다룬다.
선 수 과 목 CS204 Discrete Mathematics homepage
담 당 교 수 최광무, 전산학동 2427호, choe@kaist.ac.kr
강 의 교 재
  • 주교재
    • 교재명 : Introduction to Automata Theory, Language, and Computation (third edition)
    • 저자 : John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman
    • 출판사 : Addison Wesley
    • Homepage : http://www-db.stanford.edu/~ullman/ialc.html
  • 부교재
    • 1. Introduction to Automata Theory, Language, and Computation, John E. Hopcroft and Jeffery D. Ullman(second edition) → 예전 교재로 잘 쓰여진 책이다.
    • 2. Introduction to Languages and the Theory of Computation, John Martin (forth editon) → TP가 잘 정리되어 있다.
    • 3. Problem solving in automata, language, and complexity, Ding-zhu Du, Ker-i Ko, Wiley interscience. → 좋은 연습문제가 많다.
  • 강 의 시 간 화, 목 13:00 ~ 14:15
    강 의 장 소 (E11)창의학습관 311호

    강 의 계 획
  • 최종 성적(숙제, 프로젝트, 시험, 출석 등)
  • 성 적
    출 석
    숙제 & 프로젝트
    중간고사
    기말고사
    합 계
    25%
    25%
    25%
    25%
    100%
    강 의 일 정
    주제
    강의 기간
    교재 범위
    Ⅰ. Mathematical Preview
    2주
    chap1
    Ⅱ. Finite Automata, Regular expression, Pumping Lemma for Regular Languages, minimal DFA
    4주
    chap2, chap3, chap4
    Ⅲ. CFG, Pushdown Automata, Left/Right Parser, CNF, and CYK Algorithm
    4주
    chap5, chap6, chap7
    Ⅳ. Turing Machine, non-Recursively Enumerable and Church’s thesis
    3주
    chap8, chap9
    Ⅴ. Complexity Theory
    1주
    chap10

    ※공휴일과 강의 상황에 따라 약간 바뀔 수 있습니다.

    시 험
    • 중간고사 : 10월 20일 화요일 오후 1:00 - 3:45 ***전산동 1501호(제 1공동 강의실)***문제와 정답 중간고사 성적
      중간고사 점수와 채점 기준은 위 링크들을 참고하기 바랍니다.
      중간고사 채점 결과에 대해서 "실수로 잘못 채점된 부분"에 대한 클레임을 아래와 같이 받습니다.
      문제별 담당 조교
      1번: 박현지
      2번: 이의현
      3번: 김성훈
      4번: 황진환
      5번: 신동환
      6번: 이정준

      11월 10일 화요일 18:30~20:00 --> 1번, 2번, 4번, 5번, 6번 클레임 가능
      11월 12일 목요일 18:30~20:00 --> 2번, 3번, 5번, 6번 클레임 가능

      본인의 답안지는 본인이 방문한 경우에 한해서 확인할 수 있습니다, (나눠주지는 않습니다)
      위에 명시된 시간에 부득이하게 방문하기 어려운 경우, 개별적으로 문제 담당 조교에게 연락하여 클레임을 진행하기 바랍니다.

    • 기말고사 : 12월 15일 화요일 오후 1:00 - 2:30 ***전산동 1501호(제 1공동 강의실)*** 문제와 정답 최종 성적(숙제, 프로젝트, 시험, 출석 등)

      기말고사(+출석/숙제/플젝) 클레임은 12월 22일(화요일) 오후 6:30-8:00에 N1 422호에서 진행될 예정입니다.

    강 의 자 료
    • TP와 한글강의노트는 강의 전에 미리 올라옵니다. 미리 읽어보고 인쇄하여 강의에 반드시 들고 오시길 바랍니다.
    • 강의 필기는 수업이 끝난 직후 제공됩니다.
    • 이전 년도 강의 자료들을 참고하셔서 공부하시길 권장드립니다. 2007 2008 2009 2011 2012 2014

  • 강의 필기와 영상 ( cf. 2014 CS322 Homepage)
    파트 챕터 강의순서 강의일 제목 강의영상
    Part I
    Chapter 1
    제 1강
    2015-09-01(화)
    제 2강
    2015-09-03(목)
    제 3강
    2015-09-08(화)
    제 4강
    2015-09-10(목)
    Part II
    Chapter 2
    제 5강
    2015-09-15(화)
    제 6강
    2015-09-17(목)
    제 7강
    2015-09-22(화)
    Chapter 3
    제 8강
    2015-09-24(목)
    Chapter 4
    제 9강
    2015-10-01(목)
    제 10강
    2015-10-06(화)
    제 11강
    2015-10-08(목)
    Part III
    Chapter 5
    제 12강
    2015-10-13(화)
    제 13강
    2015-10-15(목)
    Chapter 6
    제 14강
    2015-10-27(화)
    제 15강
    2015-10-29(목)
    Chapter 7
    제 16강
    2015-11-03(화)
    제 17강
    2015-11-05(목)
    제 18강
    2015-11-10(화)
    제 19강
    2015-11-12(목)
    Part IV
    Chapter 8
    제 20강
    2015-11-17(화)
    제 21강
    2015-11-19(목)
    제 22강
    2015-11-24(화)
    Chapter 9
    제 23강
    2015-12-01(화)
    제 24강
    2015-12-03(목)
    제 25강
    2015-12-08(화)
    Part V
    Chapter 10
    제 26강
    2015-12-10(목)

  • 교과서 TP ( cf. 2014 CS322 Homepage)
    파트 챕터 보조 TP 제목 쪽수 최종수정일
    Part I
    Chapter 0
    Introduction to Automata Theory, Languages, and Computation : v1 v2 v3
    2
    2016-08-31
    Chapter 1
    Automata - The Methods and the Madness : v1
    18
    2016-08-31
    1
    Reviews on Discrete Mathmatics : v1 v2
    25
    2016-08-31
    Part II
    Chapter 2
    Finite Automata : v1 v2 v3 v4
    27
    2016-08-31
    1
    Repeated Composition of Functions : v1
    4
    2016-08-31
    2
    Examples of Deterministic Finite Automata : v1 v2
    6
    2016-08-31
    2-1
    Examples of DFA in Du & Ko's Book(부교재 3번) : v1
    4
    2016-08-31
    3
    한글오토마타 : v1
    5
    2016-08-31
    4
    FA with Output : v1
    2
    2016-08-31
    Chapter 3
    Regular Expressions and Languages : v1 v2
    16
    2016-08-31
    Chapter 4
    Properties of Regular Languages : v1 v2 v3 v4
    24
    2016-08-31
    1
    The Myhill-Nerode Theorem and Minimization of Finite Automata : v1
    3
    2016-08-31
    Part III
    Chapter 5
    Context-free Grammars : v1 v2
    16
    2016-08-31
    1
    Examples for Context-Free Grammars and Regular grammar : v1
    15
    2016-08-31
    1-1
    Examples of CFG in Du & Ko's Book(부교재 3번) : v1
    10
    2016-08-31
    Chapter 6
    Pushdown Automata : v1 v2
    12
    2016-08-31
    1
    Rewriting Systems : v1 v2 v3
    13
    2016-08-31
    Chapter 7
    Properties of Context-free Languages : v1 v2
    24
    2016-08-31
    1
    Loop Invariance and Terminating Conditions : v1
    7
    2016-08-31
    1-1
    Guarded Commands, Nondeterminacy and Formal Derivation of Programs : v1
    5
    2016-08-31
    2
    CYK Algorithm, revisited : v1
    4
    2016-08-31
    Part IV
    Chapter 8
    Introduction to Turing Machine : v1 v2 v3 v4
    14
    2016-08-31
    Chapter 9
    Undecidability : v1 v2
    21
    2016-08-31
    1
    Computability : v1 v2
    45
    2016-08-31
    2
    Partial Recursive Functions : v1
    34
    2016-08-31
    Part V
    Chapter 10
    Intractable Problem : v1
    20
    2016-08-31
    1
    NP complete 문제는 수학인가 : v1
    8
    2016-08-31
    Chapter X
    2012 SIGPL 겨울학교 : v1 v2
    62
    2016-08-31
    446

  • 한글 보조 자료 ( cf. 2014 CS322 Homepage)
    파트 챕터 섹션 제목 PDF 쪽수 최종수정일
    Part I
    Chapter 1
    1
    강의개요 : v1
    v1
    4
    2016-08-31
    2
    수학기초 : v1
    v1
    6
    2016-08-31
    3
    증명 : v1
    v1
    7
    2016-08-31
    4
    Recursion 혹은 수학적 귀납법과 무한집합 : v1
    v1
    4
    2016-08-31
    5
    언어이론(Language Theory) 기초 : v1 v2
    v1 v2
    3
    2016-08-31
    Part II
    Chapter 2
    1
    Deterministic Finite Automata : v1
    v1
    4
    2016-08-31
    2
    DFA의 확장 - Partial function 과 NFA : v1
    v1
    4
    2016-08-31
    3
    DFA의 확장(2) - ε-NFA와 Extended FA : v1
    v1
    3
    2016-08-31
    4
    한글 모아쓰기 오토마타 : v1
    v1
    3
    2016-08-31
    Chapter 3
    1
    Regular Expression과 Regular Language : v1
    v1
    3
    2016-08-31
    2
    Regular expression의 연립방정식을 이용한 해법 : v1 v2
    v1 v2
    3
    2016-08-31
    Chapter 4
    1
    정규(Regular) 언어를 위한 Pumping Lemma : v1
    v1
    4
    2016-08-31
    2
    정규(Regular) 언어에 관하여 닫혀있는 성질(closure property)과 대수계(algebraic system) : v1
    v1
    3
    2016-08-31
    3
    Myhill-Nerode Theorem and Minimization of DFA : v1
    v1
    3
    2016-08-31
    Part III
    Chapter 5
    1
    문맥자유 문법(Context-Free Grammar) : v1 v2
    v1 v2
    6
    2016-08-31
    2
    문맥자유문법과 문법나무 그리고 유도순서 : v1
    v1
    3
    2016-08-31
    Chapter 6
    1
    Pushdown Automata : v1
    v1
    4
    2016-08-31
    Chapter 7
    1
    쓸모 있게(Useful) 줄인 문법(Reduced Grammar) : v1
    v1
    3
    2016-08-31
    2
    Chomsky Normal Form : v1
    v1
    4
    2016-08-31
    3
    Loop Invariance and Termination(보충) : v1
    v1
    3
    2016-08-31
    4
    Context-Free 언어를 위한 Pumping Lemma : v1
    v1
    3
    2016-08-31
    5
    CYK 알고리즘 : v1
    v1
    2
    2016-08-31
    Part IV
    Chapter 8
    1
    Turing Machine : v1
    v1
    2
    2016-08-31
    Chapter 9
    1
    Undecidability : v1
    v1
    3
    2016-08-31
    2
    Primitive Recursive Function : v1
    v1
    3
    2016-08-31
    3
    mu-Recursive Partial Function : v1
    v1
    2
    2016-08-31
    Part V
    Chapter 10
    1
    NP-compleness : v1
    v1
    3
    2016-08-31
    2
    Satisfiability Problem : v1
    v1
    2
    2016-08-31
    97
  • 숙 제
    • Homework
      • 공 지
        숙제는 일주일에 한 번씩, 매주 화요일에 홈페이지에 공지될 예정입니다.
      • 마감
        공지한 다음 주 화요일 오후 11:59까지 입니다.
      • Delay
        Due 이후에 제출된 숙제는 일체 받지 않습니다.
      • 제출 방식
        제출 장소는 N1 403호 앞 숙제함입니다.
      • 숙제 Return
        숙제 Due에서 2주 후 월요일 숙제함 근처에 채점된 숙제를 모아 놓을 테니 찾아가시면 됩니다.
  • 필기숙제
    출제일 제출일 숙제 풀이 담당조교
    2015/09/08
    2015/09/15(화)
    황진환, 박현지, 이의현
    2015/09/15
    2015/09/22(화)
    김성훈, 이의현
    2015/09/22
    2015/10/01(목)
    김성훈, 이의현
    2015/10/06
    2015/10/13(화)
    김성훈, 이의현
    2015/10/13
    2015/10/20(화) 시험 전
    신동환, 이정준
    2015/11/03
    2015/11/10(화)
    신동환, 이정준
    2015/11/10
    2015/11/19(목)
    신동환, 이정준
    2015/11/21
    2015/12/01(화)
    신동환, 이정준
    2015/12/01
    2015/12/08(화)
    이정준
    2015/12/08
    2015/12/15(화) 시험 종료 전
    김성훈

  • 프로젝트-> CS322 2015 프로젝트 점수
    출제일 제출일 프로젝트 HWP PDF 출제자 채점 기준 담당조교
    2015/09/16
    2015/09/23(수)
    예비프로젝트1-1
    HWP
    PDF
    최광무
    신동환, 박현지
    2015/09/22
    2015/10/01(목)
    예비프로젝트1-2
    HWP
    PDF
    최광무
    신동환, 박현지
    2015/09/22
    2015/10/14(수)
    본프로젝트 1
    HWP
    PDF
    최광무
    이의현, 김성훈
    2015/10/01
    2015/11/11(수)
    예비프로젝트2-1
    HWP
    PDF
    최광무
    이정준, 황진환
    2015/10/01
    2015/11/25(수)
    본프로젝트 2
    HWP
    PDF
    최광무
    이정준, 황진환
    2015/10/01
    2015/12/09(수)
    본프로젝트 3
    HWP
    PDF
    최광무
    이의현, 김성훈
    • 권장하는 프로그래밍 언어는 C/C++/Python/Java 입니다. 이외의 언어를 사용하셔도 되지만, 조교들이 해당 언어에 능숙하지 않아서 발생하는 불이익이 있을 수 있습니다.
    • 제출물: 소스코드 (라이브러리 포함), 실행가능파일, 간단한 메뉴얼(실행법(입/출력 예시), 프로그램 설명, 실행 결과 스크린샷 포함)
    • 제출 방법: 모든 제출물을 [프로젝트이름].zip으로 압축하여 KLMS로 제출 바랍니다.(Google 메일에서 실행파일을 받을 수 없는 문제가 발생하여 부득이하게 방법을 바꾸게 되었습니다.) ex) [예비프로젝트1-1].zip


  • 프로젝트 참고자료
    등록일 파일 이름 제목
    2014/10/20
    Bison과 Flex의 소개 및 사용법
    2012/10/20
    Lex & Yacc의 소개 및 사용법
  • 조 교 정 보
    • 조교 Office Hour: (화, 목) 18:30~20:00, N1 #403

    이 름 연 구 실 이 메 일 담 당
    신동환
    N1 524
    donghwan@se.kaist.ac.kr
    조교장
    이정준
    E3 2422
    j2in2o@kaist.ac.kr
    숙제
    이의현
    E3 2422
    luh0907@kaist.ac.kr
    출석, 홈페이지
    김성훈
    E3 2422
    shkim0604@kaist.ac.kr
    숙제
    황진환
    -
    jinkrkrkr@kaist.ac.kr
    숙제
    박현지
    -
    hyunjip@kaist.ac.kr
    출석

    출 석
    • 사진을 보고 링크에 들어가 출석 체크를 해 주십시오. 되도록이면 빨리 해 주시면 좋겠습니다.
    • 3번 결석 까지는 봐주지만, 그 이상 결석하면 점수에 영향을 주게 됩니다.
  • 출석사진
    날짜 요일 사진 출석체크
    2015-09-08
    2
    1 2 3
    2015-09-10
    2
    1 2 3
    2015-09-15
    3
    1 2 3
    2015-09-17
    3
    1 2 3
    2015-09-22
    4
    1 2 3
    2015-09-24
    4
    1 2 3
    2015-10-01
    5
    1 2 3
    2015-10-06
    6
    1 2 3
    2015-10-08
    6
    1 2 3
    2015-10-13
    7
    1 2 3
    2015-10-15
    7
    1 2 3
    2015-10-27
    9
    1 2 3
    2015-10-29
    9
    1 2 3
    2015-11-03
    10
    1 2 3
    2015-11-05
    10
    1 2 3
    2015-11-10
    11
    1 2 3
    2015-11-12
    11
    1 2 3
    2015-11-17
    12
    1 2 3
    2015-11-19
    12
    1 2 3
    2015-11-24
    13
    1 2 3
    2015-12-01
    14
    1 2 3
    2015-12-03
    14
    1 2 3
    2015-12-08
    15
    1 2 3
    2015-12-10
    15
    1 2 3

  • CS322 2015 출석표 → 클라우드 저장소에 저장된 최신 정보 반영 정보입니다.
  • 부교재 Martin책의 TP
    Chapter 제목 쪽수
    Chapter 1
    Mathematical Tools and Techniques
    56
    Chapter 2
    Finite Automata and the Languages They Accept
    42
    Chapter 3
    Regular Expressions, Nondeterminism, and Kleene’s Theorem
    25
    Chapter 4
    Context-Free Languages
    31
    Chapter 5
    Pushdown Automata
    39
    Chapter 6
    Context-Free and Non-Context-Free Languages
    23
    Chapter 7
    Turing Machine
    42
    Chapter 8
    Recursively Enumerable Languages
    35
    Chapter 9
    Undecidable Problem
    30
    Chapter 10
    Computable Functions
    42
    Chapter 11
    Introduction to Computational Complexity
    27

    CS322, http://adamant.kaist.ac.kr/cs322, Webmaster: luh0907 [at] kaist.ac.kr