ผลต่างระหว่างรุ่นของ "01204512 ภาคต้น 2555"
ไปยังการนำทาง
ไปยังการค้นหา
(minor updates) |
Jittat (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 22 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) | |||
| แถว 3: | แถว 3: | ||
== ประกาศ == | == ประกาศ == | ||
* สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ [https://www.facebook.com/groups/345828848821452/ Group 01204512/55 Graduate algorithms] บน facebook | * สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ [https://www.facebook.com/groups/345828848821452/ Group 01204512/55 Graduate algorithms] บน facebook | ||
| + | |||
| + | == ตารางนัด present == | ||
| + | * วันพฤหัสที่ 18 ต.ค. | ||
| + | ** บ่าย | ||
| + | *** 1 | ||
| + | *** 2 | ||
| + | *** 3 | ||
| + | ** เย็น | ||
| + | *** 1 | ||
| + | *** 2 | ||
| + | *** 3 | ||
| + | * วันจันทร์ที่ 22 ต.ค. | ||
| + | ** เย็น | ||
| + | *** 1: Pisit Makpaisit | ||
| + | *** 2: Atikan Muang-ngeon | ||
| + | *** 3: Narongsak Thipjoy | ||
| + | * วันพุธที่ 24 ต.ค. | ||
| + | ** บ่าย | ||
| + | *** 1: Sasithorn Suchaiya | ||
| + | *** 2: Pasakorn Tiwatthanont | ||
| + | *** 3 | ||
| + | ** เย็น | ||
| + | *** 1: KaoPoon Pabo | ||
| + | *** 2: Suphamit Plathong | ||
| + | *** 3: Natapon Aom Saengtaiyarak | ||
== การวัดผล == | == การวัดผล == | ||
| แถว 43: | แถว 68: | ||
** Lecture 5-6 จากเว็บ [http://theory.stanford.edu/~trevisan/cs261/ http://theory.stanford.edu/~trevisan/cs261/] | ** Lecture 5-6 จากเว็บ [http://theory.stanford.edu/~trevisan/cs261/ http://theory.stanford.edu/~trevisan/cs261/] | ||
| − | + | * '''สัปดาห์ที่ 8''' Linear programming duality, weighted bipartite matching | |
| + | ** [[01204512/weight bipartite matching]] | ||
| + | ** เอกสารประกอบ: | ||
| + | *** lecture 10 Primal-Dual Algorithm for Weighted Bipartite Matching จากวิชา [http://www.cs.illinois.edu/class/sp10/cs598csc/ CS 598, UIUC] | ||
| + | *** lecture notes on bipartite matching จากวิชา [http://math.mit.edu/~goemans/18433S07/18433.html 18.433, MIT] | ||
| − | + | * '''สัปดาห์ที่ 9''' On-line bipartite matching, AdWords | |
| + | ** [http://www.cs.brown.edu/~claire/Publis/sigactnews08.pdf On-line bipartite matching made simple] Benjamin Birnbaum and Claire Mathieu, ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87. | ||
| − | * | + | * '''สัปดาห์ที่ 10''' Randomized algorithms [http://theory.cpe.ku.ac.th/wiki/images/Randomized-short.pdf pdf] |
| − | |||
| − | |||
| − | + | * '''สัปดาห์ที่ 11''' Sparsest cuts, eigenvalues, eigenvectors | |
| − | * | ||
| − | + | * '''สัปดาห์ที่ 12''' Cheeger's Inequality | |
| − | + | * '''สัปดาห์ที่ 13''' NP-Completeness | |
| + | ** เอกสาร บทที่ 8 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์) | ||
| − | + | * '''สัปดาห์ที่ 14''' NP-Completeness (ต่อ) และวิธีการจัดการ | |
| + | ** เอกสาร บทที่ 8 และ 9 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์) | ||
| − | + | * '''สัปดาห์ที่ 15''': Streaming algorithms | |
| + | ** เอกสารหัวข้อ Streaming และ Streaming: Frequency Estimation จากเว็บ [http://www.cs.berkeley.edu/~satishr/cs270/sp11/index.html http://www.cs.berkeley.edu/~satishr/cs270/sp11/index.html] | ||
| − | == | + | == วิดีทัศน์ประกอบการเรียน == |
| − | + | == การบ้าน == | |
| − | + | * การบ้าน 1 กำหนดส่ง 8 ส.ค. 2555 | |
| + | ** ส่วนที่ 1: [[ไฟล์:01204512-55-hw01.pdf]] | ||
| + | ** ส่วนที่ 2: [http://www.cpe.ku.ac.th/~jtf/204512-46/hw1.pdf .pdf], [http://www.cpe.ku.ac.th/~jtf/204512-46/hw1.ps .ps] | ||
| − | + | * การบ้าน 2 กำหนดส่ง 22 ต.ค. 2555 [http://theory.cpe.ku.ac.th/wiki/images/512-55-hw02.pdf .pdf] | |
| − | == | + | == ลิงก์อื่น ๆ == |
| − | + | * [[204512 ภาคต้น 2550|วิกิรายวิชาปี 2555]] มีสรุปของแต่ละการบรรยายโดยนิสิต | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | [[ | ||
รุ่นแก้ไขปัจจุบันเมื่อ 14:16, 17 ตุลาคม 2555
ใน วิชาอัลกอริทึมระดับบัณฑิตศึกษา เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี
เนื้อหา
ประกาศ
- สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ Group 01204512/55 Graduate algorithms บน facebook
ตารางนัด present
- วันพฤหัสที่ 18 ต.ค.
- บ่าย
- 1
- 2
- 3
- เย็น
- 1
- 2
- 3
- บ่าย
- วันจันทร์ที่ 22 ต.ค.
- เย็น
- 1: Pisit Makpaisit
- 2: Atikan Muang-ngeon
- 3: Narongsak Thipjoy
- เย็น
- วันพุธที่ 24 ต.ค.
- บ่าย
- 1: Sasithorn Suchaiya
- 2: Pasakorn Tiwatthanont
- 3
- เย็น
- 1: KaoPoon Pabo
- 2: Suphamit Plathong
- 3: Natapon Aom Saengtaiyarak
- บ่าย
การวัดผล
- การบ้าน: 20%
- สอบ: กลางภาค 30%, ปลายภาค 30%
- โครงงานกลุ่ม: 20% (ในส่วนโครงงานนี้อาจจะเป็นการนำเนื้อหาที่เรียนมาประยุกต์ใช้ในหัวข้อที่นิสิตสนใจ หรืออาจจะเป็นการช่วยกันอ่านเปเปอร์ทางอัลกอริทึมที่เกี่ยวข้องกับหัวข้อวิจัยและนำเสนอกับอาจารย์ผู้สอน)
เนื้อหาโดยรวม
- Divide-and-conquer method
- Dynamic programming
- Multiplicative weights update method and applications
- Graph algorithms: shortest paths and maximum flows
- Linear programming
- Randomized algorithms
- Algorithms in machine learning: perceptron, SVM, dimension reduction techniques
เนื้อหาแยกละเอียดเป็นสัปดาห์
- สัปดาห์ 1. Introduction, divide-and-conquer method, matrix multiplication, FFT
- เอกสาร บทที่ 2 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)
- สัปดาห์ 2. Dynamic programming
- เอกสาร บทที่ 6 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani
- สัปดาห์ 3. Review of shortest path and maximum flow problems. Dueling subroutines.
- สามารถอ่านเนื้อหาละเอียดในส่วน shortest paths จากบทที่ 4 และเนื้อหาส่วน maximum flows จากส่วนที่ 7.2 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani
- ส่วนของ Congestion minimization ดูจาก ปัญหา congestion minimization หรือเอกสาร lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Introduction and Routing/Toll Games.
- สัปดาห์ 4. Maximum flow algorithms, Congestion minimization (cont.), Intro to Games
- สัปดาห์ 5. Two-player Games. Expert's algorithm.
- lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Game examples และ Expert's algorithm.
- สัปดาห์ที่ 6 Applications of the Expert's algorithm: solving two-player zero-sum games, AdaBoost, congestion minimization.
- lecture note จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp12/ หัวข้อ Expert's algorithms Application to Min-Max for Games and Boosting
- สัปดาห์ที่ 7 Linear programming and duality
- เอกสาร บทที่ 7 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani
- Lecture 5-6 จากเว็บ http://theory.stanford.edu/~trevisan/cs261/
- สัปดาห์ที่ 8 Linear programming duality, weighted bipartite matching
- 01204512/weight bipartite matching
- เอกสารประกอบ:
- lecture 10 Primal-Dual Algorithm for Weighted Bipartite Matching จากวิชา CS 598, UIUC
- lecture notes on bipartite matching จากวิชา 18.433, MIT
- สัปดาห์ที่ 9 On-line bipartite matching, AdWords
- On-line bipartite matching made simple Benjamin Birnbaum and Claire Mathieu, ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.
- สัปดาห์ที่ 10 Randomized algorithms pdf
- สัปดาห์ที่ 11 Sparsest cuts, eigenvalues, eigenvectors
- สัปดาห์ที่ 12 Cheeger's Inequality
- สัปดาห์ที่ 13 NP-Completeness
- เอกสาร บทที่ 8 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)
- สัปดาห์ที่ 14 NP-Completeness (ต่อ) และวิธีการจัดการ
- เอกสาร บทที่ 8 และ 9 จากหนังสือ Algorithms โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)
- สัปดาห์ที่ 15: Streaming algorithms
- เอกสารหัวข้อ Streaming และ Streaming: Frequency Estimation จากเว็บ http://www.cs.berkeley.edu/~satishr/cs270/sp11/index.html
วิดีทัศน์ประกอบการเรียน
การบ้าน
- การบ้าน 1 กำหนดส่ง 8 ส.ค. 2555
- ส่วนที่ 1: ไฟล์:01204512-55-hw01.pdf
- ส่วนที่ 2: .pdf, .ps
- การบ้าน 2 กำหนดส่ง 22 ต.ค. 2555 .pdf
ลิงก์อื่น ๆ
- วิกิรายวิชาปี 2555 มีสรุปของแต่ละการบรรยายโดยนิสิต
