ผลต่างระหว่างรุ่นของ "01204512 ภาคต้น 2555"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 51: | แถว 51: | ||
* '''สัปดาห์ที่ 9''' On-line bipartite matching, AdWords | * '''สัปดาห์ที่ 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. | ** [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] | ||
== วิดีทัศน์ประกอบการเรียน == | == วิดีทัศน์ประกอบการเรียน == |
รุ่นแก้ไขเมื่อ 15:03, 27 สิงหาคม 2555
ใน วิชาอัลกอริทึมระดับบัณฑิตศึกษา เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี
เนื้อหา
ประกาศ
- สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ Group 01204512/55 Graduate algorithms บน facebook
การวัดผล
- การบ้าน: 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
วิดีทัศน์ประกอบการเรียน
การบ้าน
- การบ้าน 1 กำหนดส่ง 8 ส.ค. 2555
- ส่วนที่ 1: ไฟล์:01204512-55-hw01.pdf
- ส่วนที่ 2: .pdf, .ps
ลิงก์อื่น ๆ
- วิกิรายวิชาปี 2555 มีสรุปของแต่ละการบรรยายโดยนิสิต