ผลต่างระหว่างรุ่นของ "01204213"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
(ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
แถว 115: | แถว 115: | ||
* [https://www.youtube.com/watch?v=i5VbWY0NmDU&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=40 11-3: นิยามคลาส P และคลาส NP] | * [https://www.youtube.com/watch?v=i5VbWY0NmDU&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=40 11-3: นิยามคลาส P และคลาส NP] | ||
|| | || | ||
+ | |- | ||
+ | | - || คลิปทบทวนเนื้อหาจากปี 2564 || | ||
+ | || | ||
+ | คลิป: | ||
+ | * [https://www.youtube.com/watch?v=Dl7_s-VuY9c&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=41 12-1: ทบทวน Turing recognizability และ (Turing) decidability] | ||
+ | * [https://www.youtube.com/watch?v=fYjYn58T-X0&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=42 12-2: ทบทวน undecidability และ reduction] | ||
+ | || | ||
+ | |- | ||
| 12 || NP-completeness || | | 12 || NP-completeness || | ||
[https://gitlab.com/jittat/01204213-theory-of-computation-slides/-/raw/master/lect13/lect13.pdf handout12 (draft)] | [https://gitlab.com/jittat/01204213-theory-of-computation-slides/-/raw/master/lect13/lect13.pdf handout12 (draft)] | ||
|| | || | ||
คลิป: | คลิป: | ||
+ | * [https://www.youtube.com/watch?v=e8bA_yFhneo&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=43 13-1: นิยามคลาส NP] | ||
+ | * [https://www.youtube.com/watch?v=HiEuXBBRLwY&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=44 13-2: คลาส NP, แนะนำปัญหา CLIQUE, VERTEX-COVER, และ 3SAT] | ||
+ | * [https://www.youtube.com/watch?v=vi8SDMwxXXU&list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG&index=45 13-3: Polynomial-time reduction] | ||
|| | || | ||
|} | |} |
รุ่นแก้ไขปัจจุบันเมื่อ 04:04, 28 กันยายน 2565
ภาพรวม
- กรุณาเข้ากลุ่ม discord
- Youtube Playlist เนื้อหาจากปี 2564: https://www.youtube.com/playlist?list=PLii-CvAgf-8iQcIS1ChsK3HDRrl2kOCBG
เอกสารและคลิป
Week | Topics | Handouts | Links | Homework |
---|---|---|---|---|
1 | Introduction, Review |
คลิป:
|
ไม่มี | |
2 | Finite automata & Regular languages |
คลิป: |
||
3 | Nondeterministic finite automata, Regular expressions, Equivalence |
คลิป: |
การบ้าน: hw02.pdf | |
4 | Nonregular languages, the Pumping lemma, and Context-free grammars |
คลิป: |
||
5 | Context-free grammars and Pushdown automata |
คลิป: |
||
6 | Pumping Lemma for CFG, Turing machines |
คลิป: |
||
7 | Turing machines and their variants |
คลิป: |
||
8 | Church-Turing thesis, diagonalization |
คลิป: |
||
9 | Undecidable languages, reducibility |
คลิป: |
||
10 | Reduction (2), แนะนำ Time complexity |
คลิป: |
||
11 | Time complexity, class P, and class NP |
คลิป: |
||
- | คลิปทบทวนเนื้อหาจากปี 2564 |
คลิป: |
||
12 | NP-completeness |
คลิป: |
ลิงก์
- เว็บวิชา: ปีการศึกษา 2564 ปีการศึกษา 2551