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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 64 รุ่นระหว่างกลางโดยผู้ใช้ 3 คน)
แถว 1: แถว 1:
−
'''วิชาอัลกอริทึมระดับบัณฑิตศึกษา'''  
+
ใน '''วิชาอัลกอริทึมระดับบัณฑิตศึกษา''' เราจะศึกษาเนื้อหาในเชิงวิเคราะห์มากขึ้น และเป็นเนื้อหาที่มีความทันสมัยมากกว่าเนื้อหาที่เรียนในระดับปริญญาตรี
  
−
* เราจะทดลองใช้ระบบถามตอบสำหรับการเรียนการสอนที่ชื่อว่า [http://piazza.com Piazza]  กรุณาสมัครเข้าส่วนของรายวิชา [http://www.piazza.com/ku.ac.th/fall2012/01204512
+
== ประกาศ ==
−
ที่นี่] (ต้องใช้อีเมล์ @ku.ac.th)
+
* สำหรับการติดต่อและปรึกษาทั่วไป เราจะใช้ [https://www.facebook.com/groups/345828848821452/ Group 01204512/55 Graduate algorithms] บน facebook
  
−
== เนื้อหา ==
+
== ตารางนัด present ==
−
* สัปดาห์ที่ 1: Introduction, matrix multiplication, divide and conquer
+
* วันพฤหัสที่ 18 ต.ค.
−
* สัปดาห์ที่ 2:  
+
** บ่าย
 +
*** 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 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani (ดาวน์โหลดดราฟต์ของบทดังกล่าวได้จากลิงก์)
 +
 
 +
* '''สัปดาห์ 2.''' Dynamic programming
 +
** เอกสาร บทที่ 6 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani
 +
 
 +
* '''สัปดาห์ 3.''' Review of shortest path and maximum flow problems.  Dueling subroutines.
 +
** สามารถอ่านเนื้อหาละเอียดในส่วน shortest paths จากบทที่ 4 และเนื้อหาส่วน maximum flows จากส่วนที่ 7.2 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani
 +
** ส่วนของ Congestion minimization ดูจาก [[01204512/congestion1|ปัญหา congestion minimization]] หรือเอกสาร lecture note จากเว็บ [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] หัวข้อ Introduction and Routing/Toll Games.
 +
 
 +
* '''สัปดาห์ 4.''' Maximum flow algorithms, Congestion minimization (cont.), Intro to Games
 +
** [[01204512/congestion2|การวิเคราะห์ปัญหา congestion minimization]]
 +
 
 +
* '''สัปดาห์ 5.''' Two-player Games.  Expert's algorithm.
 +
** lecture note จากเว็บ [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ 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/ 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 จากหนังสือ [http://www.cs.berkeley.edu/~vazirani/algorithms.html Algorithms] โดย Dasgupta, Papadimitriou, Vazirani
 +
** 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

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

ประกาศ

ตารางนัด 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.
  • สัปดาห์ที่ 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

ลิงก์อื่น ๆ

ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=01204512_ภาคต้น_2555&oldid=36727"