正規語言概論(英文授課)
Introduction to Formal Language
學期
109-2
學分
3
學分
當期課號
1186
永久課號
DCP3122
開課單位
資訊學院共同課程
授課教師
曾文貴
校區
光復
類別
選修
上課時間表
| 節 | 週二 | 週四 |
|---|---|---|
3 10:10–11:00 | 正規語言概論(英文授課) EC122 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 正規語言概論(英文授課) EC122 |
* 根據陽明交大上課時間表所列
概述
(1) To teach formalization of computation problems and and abstraction of modern computers. (2) To study the computing power of modern computers (3) To classify the hardness levels of computing problems.
先修科目
(1) Discrete mathematics (2) Basic programming
教學方式
Class lectures
評分方式
1. Homework 25% 2. Midterm (twice) 50% 3. Final 25%
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction |
| 第 2 週 | Finite automata (I) |
| 第 3 週 | Finite automata (II) |
| 第 4 週 | Regular languages and regular grammars |
| 第 5 週 | Properties of regular languages |
| 第 6 週 | Midterm I |
| 第 7 週 | Context-free languages (I) |
| 第 8 週 | Context-free languages (II) |
| 第 9 週 | Simplification of context-free grammars and normal forms |
| 第 10 週 | Pushdown automata |
| 第 11 週 | Properties of context-free grammars |
| 第 12 週 | Midterm II |
| 第 13 週 | Turing machines |
| 第 14 週 | Other models of Turing machines |
| 第 15 週 | Limit of algorithmic computation (I) |
| 第 16 週 | Limits of algorithmic computation (II) |
| 第 17 週 | An overview of computational complexity |
| 第 18 週 | Final |
教科書
Peter Linz, An Introduction to Formal Languages and Automata (6th ed.), Jones & Bartlett Learning. (Previous editions are ok.)
Office Hours
- 地點
- Teacher: EC238 TA: EC 131A (PLAS lab)
- 時間
- Teacher:(1)Tu: 2:30-4:00pm; (2)Th:10:00-11:30am TA (Zi-Xuan Chen, 陳子軒): (1) Mon: 1:00-2:30pm; (2) Tu: 1:00-2:30pm
- 聯絡方式
- Teacher: wgtzeng@cs.nctu.edu.tw TA: dici86.chen@gmail.com