01204213

ภาพรวม

• กรุณาเข้ากลุ่ม discord
• Youtube Playlist เนื้อหาจากปี 2564: https://www.youtube.com/playlist?list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG

เอกสารและคลิป

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
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
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
6	Pumping Lemma for CFG, Turing machines	handout6	คลิป: 06-1: Pumping Lemma สำหรับ CFL 06-2: แนวคิดในการพิสูจน์ Pumping lemma สำหรับ CFL, แนะนำ Turing machine
7	Turing machines and their variants	handout7	คลิป: 07-1: นิยามการคำนวณของ Turing machine 07-2: ตัวอย่าง Turing machine และ variants ของ Turing machine
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
9	Undecidable languages, reducibility	handout9	คลิป: 09-1: ทบทวน Diagonalization 09-2: พิสูจน์ว่าภาษา Acceptance ของ Turing machine เป็น undecidable language
10	Reduction (2), แนะนำ Time complexity	handout10 (draft)	คลิป: 09-3: Reduction (1) 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
-	คลิปทบทวนเนื้อหาจากปี 2564		คลิป: 12-1: ทบทวน Turing recognizability และ (Turing) decidability 12-2: ทบทวน undecidability และ reduction
12	NP-completeness	handout12 (draft)	คลิป: 13-1: นิยามคลาส NP 13-2: คลาส NP, แนะนำปัญหา CLIQUE, VERTEX-COVER, และ 3SAT 13-3: Polynomial-time reduction

ลิงก์

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