01204213-64

หน้านี้เป็นหน้าเก็บเอกสาร ลิงก์ และวิดีโอของวิชา Theory of Computation ภาคต้น ปีการศึกษา 2564

ประกาศ

• รูปแบบการเรียน: ออนไลน์ บรรยายและทำกิจกรรมหรือการบ้าน 3 ชม.
• สนทนาและกิจกรรมกลุ่ม discord
• ส่งการบ้านทาง google classroom: https://classroom.google.com/c/MzY1OTc4MTE5Nzg0?cjc=opnp4y6

เนื้อหา

Week	Topics	Handouts	Links	Homework
1	Introduction, Review	handout1	คลิป: 01-1 Introduction 01-2 ทบทวนพื้นฐาน (แบบเร็ว ๆ) อย่าลืมดู 01-A1 01-A2 ต่อ 01-A1 ทบทวนพื้นฐานคณิตศาสตร์ 01-A2 ทบทวนการพิสูจน์	ไม่มี
2	Finite automata & Regular languages	handout2	คลิป: 02-1 แนะนำ finite automata 02-2 นิยาม finite automata 02-3 Regular operations (union) 02-4 แนะนำ nondeterministic finite automata	การบ้าน: hw01.pdf กำหนดส่ง 12 ก.ค. 2564
3	Nondeterministic finite automata, Regular expressions, Equivalence	handout3	คลิป: 03-1: Formal definition ของ NFA 03-2: Equivalence ของ NFA กับ DFA 03-3: Regular Expressions และ Equivalence กับ FA (part 1) 03-4: Equivalence ระหว่าง Regular Expressions กับ FA (part 2)	การบ้าน: hw02.pdf กำหนดส่ง 19 ก.ค. 2564
4	Nonregular languages, the Pumping lemma, and Context-free grammars	handout4	คลิป: 04-1: ทบทวนการแปลง NFA ไปยัง reg ex, แนะนำ non-regular language และแนะนำ pumping lemma 04-2: ตัวอย่างการใช้ pumping lemma ในการแสดงว่าภาษาไม่เป็น regular (1) 04-3: การใช้ pumping lemma ในการแสดงว่าภาษาไม่เป็น regular (2), บทพิสูจน์ pumping lemma 04-4: แนะนำ context-free grammars	การบ้าน: hw03.pdf โจทย์ข้อ 4 ผิด ขยายกำหนดส่ง กำหนดส่ง 2 ส.ค. 2564 26 ก.ค. 2564
5	Context-free grammars and Pushdown automata	handout5	คลิป: 05-1: ทบทวน Context-free grammar, Chomsky normal form 05-2: แนะนำ Pushdown automata 05-extra: ตัวอย่างการใช้งานเว็บ automatonsimulator.com 05-3: นิยาม Pushdown automata และตัวอย่าง 05-4: Equivalence ระหว่าง CFG และ PDA	การบ้าน: hw04.pdf กำหนดส่ง 2 ส.ค. 2564
6	Pumping Lemma for CFG, Turing machines	handout6	คลิป: 06-1: Pumping Lemma สำหรับ CFL 06-2: แนวคิดในการพิสูจน์ Pumping lemma สำหรับ CFL, แนะนำ Turing machine	การบ้าน: hw05.pdf กำหนดส่ง 9 ส.ค. 2564
7	Turing machines and their variants	handout7	คลิป: 07-1: นิยามการคำนวณของ Turing machine 07-2: ตัวอย่าง Turing machine และ variants ของ Turing machine	ข้อสอบเก่าประกาศทาง discord
8	Church-Turing thesis, diagonalization	handout8	คลิป: 08-1: การพิสูจน์แบบ diagonalization 08-2: ทบทวน Turing machine, nondeterministic Turing machine, แนะนำ Enumerator 08-3: การพิสูจน์ว่าภาษาที่ Turing-enumerable สมมูลกับภาษาที่ Turing-recognizable 08-4: Church-Turing thesis, decidable problems, แนะนำปัญหาที่ undecidable A_TM	การบ้าน: hw06.pdf กำหนดส่ง 30 ส.ค. 2564
9	Undecidable languages, reducibility	handout9	คลิป: 09-1: ทบทวน Diagonalization 09-2: พิสูจน์ว่าภาษา Acceptance ของ Turing machine เป็น undecidable language 09-3: Reduction (1)
10	Reduction (2), แนะนำ Time complexity	handout10 (draft)	คลิป: 10-1: Reduction (2) 10-2: ทบทวนแนวคิด reduction 10-3: พิสูจน์ว่า E_TM undecidable, นิยาม mapping reducibility 10-4: ภาษาที่ไม่เป็น Turing-recognizable 10-5: Time complexity - นิยามและตัวอย่างที่เวลาการทำงานขึ้นกับโมเดล
11	Time complexity, class P, and class NP	handout11 (draft)	คลิป: 11-1: ทบทวน mapping reduction 11-2: โมเดลการคำนวณกับเวลาการทำงาน 11-3: นิยามคลาส P และคลาส NP

ลิงก์

• เว็บวิชา: ปีการศึกษา 2551