แผนการสอน CSC610 ทฤษฎีการคำนวณขั้นสูง
CSC610 Advanced Theory of Computation
ภาคการศึกษาที่ 2 (ระบบไตรภาค)
ห้อง 702 วันอาทิตย์เวลา 9:00-12:00 น.
ผู้สอน
(Lecturer) |
ผศ. ดร. กรุง สินอภิรมย์สราญ
ภาควิชาคณิตศาสตร์, คณะวิทยาศาสตร์, จุฬาลงกรณ์มหาวิทยาลัย
โทรศัพท์: 02-218-5162, โทรสาร: 02-255-2287
อีเมล์: Krung.S@chula.ac.th
|
|---|
| คำอธิบายเนื้อหาวิชา (ภาษาไทย) |
เครื่องนามธรรมและการคณนา ออโตมาตาจำกัด ภาษาปรกติ ออโตมาตากดลง ภาษาไม่พึ่งบริบท เครื่องทัวริง ฟังก์ชันรีเคอร์ซีฟ
ปัญหาที่ตัดสินได้และปัญหาที่ตัดสินไม่ได้ และความซับซ้อนของคณนา
|
|---|
| Course description (English) |
The abstract of machines and computing, finite automata, regular language, push down automata, context-free languages,
Turing machines, Recursive function, Decidability and undecidability, and computational complexity.
|
|---|
ตำราเรียน
(Text) |
เอกสารคำสอนได้จาก http://pioneer.netserv.chula.ac.th/~skrung/csc610/
|
|---|
หนังสืออ้างอิง
(References) |
Brookshear, J. G., Theory of computation, Benjamin/Cummings Publishing Company, Inc., California, 1989.
Cohen, D. I. A., Introduction to computer theory, revised edition, John Wiley & Sons, New York, 1991.
Denning, P. J., J. B. Dennis and J. E. Qualitz, Machines, Languages, and Computation, Prentice-Hall, N.J., 1978.
Martin, J. C., Introduction to languages and the theory of computation, second edition, McGraw-Hill Companies, Singapore, 1997.
Minsky, M. L., Computation: Finite and Infinite Machines, Prentice-Hall, N.J., 1967.
Wood, D., Theory of computation, John Wiley & Sons, New York, 1987.
สุวิมล (ก่อเกิดวิบูลย์) ฮอล์, ทฤษฎีการคณนา (Theory of Computation),
ห้างหุ้นส่วนพิทักษ์การพิมพ์, 2542
|
|---|
การวัดผล
(Evaluation) |
| สอบย่อย (4 ครั้ง) | |
20% |
| สอบกลางภาค วันที่ 7 พฤศจิกายน 2547 | | 40% |
| สอบปลายภาค วันที่ 26 ธันวาคม 2547 | | 40% |
หมายเหตุ: สอบย่อยเริ่มเวลา 8:30 น. ใช้เวลา 30 นาที 4 ครั้งจะตัดเอาคะแนน 2 ครั้งที่ต่ำที่สุดออก
- สอบย่อยครั้งที่ 1 (10 ตุลาคม 2547) เรื่องออโตมาตาแบบจำกัดเชิงกำหนด และออโตมาตาแบบจำกัดเชิงไม่กำหนดที่ใช้กับไม่ใช้
 -moves
- สอบย่อยครั้งที่ 2 (24 ตุลาคม 2547) เรื่องนิพจน์ปรกติ ภาษาปรกติ และทฤษฎีบทตั้งการปั๊มสายอักขระของเอฟเอ และการใช้เอฟเอ
- สอบย่อยครั้งที่ 3 (21 พฤศจิกายน 2547) เรื่องภาษาไม่พึ่งบริบท (CFL) การสมมูลกันของ PDA กับ CFL
รูปแบบบรรทัดฐานชอมสกีและกรายบาค (CNF and GNF)
- สอบย่อยครั้งที่ 4 (12 ธันวาคม 2547) เรื่องเครื่องทัวริง
|
|---|
ตารางการเรียน
(Schedule) |
| 26 | กันยายน | 2547 |
ทบทวนความรู้เบื้องต้น คือ เซต กราฟ สายอักขระ ภาษา การให้เหตุผล การพิสูจน์เซต อุปนัยเชิงคณิตศาสตร์
(Review the fundamental backgrounds: set, graph, string, language, logical reasoning, set proof and induction) |
| 3 | ตุลาคม | 2547 |
ออโตมาตาจำกัดเชิงกำหนด (DFA) ออโตมาตาจำกัดเชิงไม่กำหนด (NFA)
ออโตมาตาจำกัดเชิงไม่กำหนดที่มีการย้ายโดย-
(Deterministic Finite Automata, Nondeterministic Finite Automata, NFA w/-moves)
|
| 10 | ตุลาคม | 2547 |
[สอบย่อยครั้งที่ 1] นิพจน์ปรกติ ภาษาปรกติ ทฤษฎีบทตั้งการปั๊มสายอักขระของเอฟเอ
[QUIZ I] (Regular expression, regular language, pumping lemma for FA)
|
| 17 | ตุลาคม | 2547 |
การสมมูลกันของเอฟเอต่าง ๆ กับภาษาปรกติ และการนำไปใช้
(Equivalent of all FAs with Regular language, their applications)
|
| 21 | ตุลาคม | 2547 |
(ย้ายจาก 24 ตุลาคม 2547 เรียนที่ห้อง 703) [สอบย่อยครั้งที่ 2] ออโตมาตาแบบกดลง (PDA) ลักษณะ PDA และ DPDA
[QUIZ II] (Pushdown automata with nondeterministic and deterministic)
|
| 31 | ตุลาคม | 2547 |
ไวยากรณ์ไม่พึ่งบริบท (CFG) และภาษาไม่พึ่งบริบท (CFL)
(Context-Free Grammar and Context-Free language)
|
| 7 | พฤศจิกายน | 2547 |
สอบกลางภาค (MIDTERM)
|
| 14 | พฤศจิกายน | 2547 |
รูปแบบบรรทัดฐานชอมสกีและกรายบาค (CNF and GNF) การสมมูลกันของ PDA กับ CFL
(Chomsky and Greibach's normal form, Equivalent of PDA and CFL)
|
| 21 | พฤศจิกายน | 2547 |
[สอบย่อยครั้งที่ 3] เครื่องทัวริง (TMs)
[QUIZ III] (Turing Machines)
|
| 28 | พฤศจิกายน | 2547 |
การสมมูลกันของเครื่องทัวริง และเครื่องทัวริงครอบจักรวาล
(Equivalent of Turing machines and Universal Turing Machine)
|
| 12 | ธันวาคม | 2547 |
[สอบย่อยครั้งที่ 4] ฟังก์ชันรีเคอร์ซีฟปฐมฐาน ฟังก์ชันรีเคอร์ซีฟ
[QUIZ IV] (Primitive recursive function, Recursive function)
|
| 19 | ธันวาคม | 2547 |
เซตรีเคอร์ซีฟ เซตอาร์อี ปัญหาที่ตัดสินได้และปัญหาที่ตัดสินไม่ได้ ลำดับชั้นชอมสกี และความซับซ้อนของคณนา
(Recursive set, R.E. set, Decidable and undecidable problems, Chomsky hierarchy and computational complexity)
|
| 26 | ธันวาคม | 2547 |
สอบปลายภาค (Final exam)
|
|
|
|
CSC610 ทฤษฎีการคำนวณขั้นสูง
