01204512 ภาคต้น 2555

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

ประกาศ

ตารางนัด present

  • วันพฤหัสที่ 22 ต.ค.
    • บ่าย
      • 1
      • 2
      • 3
    • เย็น
      • 1
      • 2
      • 3
  • วันจันทร์ที่ 22 ต.ค.
    • เย็น
      • 1
      • 2
      • 3
  • วันพุธที่ 24 ต.ค.
    • บ่าย
      • 1
      • 2
      • 3
    • เย็น
      • 1
      • 2
      • 3

การวัดผล

  • การบ้าน: 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
  • สัปดาห์ที่ 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 (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)

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

การบ้าน

  • การบ้าน 2 กำหนดส่ง 22 ต.ค. 2555 .pdf

ลิงก์อื่น ๆ