ผลต่างระหว่างรุ่นของ "01204512 ภาคต้น 2555"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 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

ใน วิชาอัลกอริทึมระดับบัณฑิตศึกษา เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี

ประกาศ

การวัดผล

  • การบ้าน: 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.
  • สัปดาห์ที่ 6 Applications of the Expert's algorithm: solving two-player zero-sum games, AdaBoost, congestion minimization.
  • สัปดาห์ที่ 8 Linear programming duality, weighted bipartite matching
  • สัปดาห์ที่ 9 On-line bipartite matching, AdWords
  • สัปดาห์ที่ 10 Randomized algorithms pdf

วิดีทัศน์ประกอบการเรียน

การบ้าน

ลิงก์อื่น ๆ