오토메타 형식언어 2003년도 제 2학기.

Presentation on theme: "오토메타 형식언어 2003년도 제 2학기."— Presentation transcript:

1 오토메타 형식언어 2003년도 제 2학기

2 강의진 소개 담당 교수 조성배 (공대 C515;  2123-2720; sbcho@cs.yonsei.ac.kr)
웹 페이지 : 강의 시간(장소) : 월 4, 5 목 5 (C040) 면담 시간 : 월 7, 8 실습시간 : 금 11 (A222, A417, A505, A542) 담당 조교 : 4803 : 3877

3 데이터 프로그램 알고리즘 데이터 구조 화일처리 데이터베이스 프로그래밍 언어구조론 소프트웨어 공학 컴파일러 컴퓨터 그래픽스
운영체제 정보통신 입문 이산구조 오토메타 형식언어 알고리즘 분석 인공지능 컴퓨터 시스템 디지털 논리회로 컴퓨터 구조 마이크로 프로세서

4 왜 배우나? 이 과목은 컴퓨터과학의 바탕이 되는 기본 개념들(fundamentals of computing)을 가르쳐 준다.
이들 기본 개념을 이해함으로 말미암아 다양한 software system 과 hardware system 및 이와 관련된 문제들을 이해할 수 있는 안목 (perspective)을 갖출 수 있으며, 이러한 안목은 문제를 해결하기 위한 새로운 방안을 효율적으로 찾을 수 있게 하고, 컴퓨터과학을 하나의 학문으로 바라볼 수 있게 하여 관련 지식의 응용능력과 흥미를 높인다.

5 Generation: Grammars) Recognition: Machines)
뭘 배우나? G M aaba acba 언어 발생 모델: 문법 (Models of Language Generation: Grammars) 언어 인식 모델:계산기 Recognition: Machines)

6 Recursively enumerable
구체적으로 뭘 배우나? Automata Formal Language Grammar 계산이론 Finite automata Regular language Chomsky Hierarchy Regular grammar Pushdown automata Context free language Context free grammar Linear bounded automata Context sensitive language Turing machine Recursively enumerable Unrestricted grammar

7 진짜로 뭘 배우나? Computer Science  Practical discipline
Theory  Concepts & Principles Applications (digital design, PL, Compiler, OS, PR, AI, …) Fun Abstract model with simple notations o Alphabet o Strings : finite sequence of symbols from alphabet o Language : a subset of alphabet set

8 어디에 쓰이는 물건인고? R 2 1 1/ 0 0/ 0 0/ 1 0/ - (a) 회로이론(switching circuits): state diagram Running Blocked Ready block wakeup dispatch timer run out (b) 운영체제(operating systems) : process state transition (c) Web browsing: pattern matching for “cup” [c] [cu] [cup] c u p any not (c or p) not (c or u) start not(c) stmt if expr then E1 else E2 S1 S2 (d) Compiler: constructing a parse tree

9 뭘로 배우나? 주교재 P. Linz, An Introduction to Formal Languages and Automata (3rd Ed), Jones and Bartlett Publishers, 2001 P. Linz, An Introduction to Formal Languages and Automata (2nd Ed), D.C. Heath and Company, 1996 참고 서적 J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979 J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd Ed, Addison Wesley, 2001 D.Z. Du and K.I. Ko, Problem Solving in Automata, Languages, and Complexity, Wiley Inter-Science, 2001

10 어떤 순서로 배우나? 1. 9/1, 4 : 사전준비(1장) 2. 9/8 : Finite Automata (2장)
3. 9/15, 18 : Regular Languages & Grammars (3장), Program-1 4. 9/22, 25 : 정규언어의 특성(4장) 5. 9/29 : 1차 시험 6. 10/6, 9 : Context Free Languages (5장), Program-2 7. 10/13, 15 : Context Free 문법의 변환(6장) 8. 10/20~25 : 중간시험 기간 9. 10/27, 30 : Pushdown 오토메타(7장) 10. 11/3, 6 : Context Free 언어의 특성(8장) 11. 11/10 : 2차 시험, Program-3 12. 11/17, 20 : Turing Machines (9장) 13. 11/24, 27 : TM의 다양한 모델(10장), 정규언어 총정리(11장) 14. 12/1, 4 : 계산이론 소개(12장, 13장) 15. 12/8 : 3차 시험 16. 12/15~20 : 기말시험 기간

11 평가는 어떻게 하나? 시험 : 60% (20% * 3회) 프로그래밍 과제 : 25% (3회) 수업참여 : 15%
시험 : 60% (20% * 3회) 프로그래밍 과제 : 25% (3회) 수업참여 : 15% 출석 및 수업 참여 연습 및 실습 참여

12 마지막 잔소리 1. 이 과목 사전에 휴강이란 없다. 2. 컨닝하다 걸리면 끝장이다. 3. 모든 마감일에 예외란 없다.