204451

This is an old revision of the document!

204451 การออกแบบและการวิเคราะห์อัลกอริทึม (ALGORITHM DESIGN AND ANALYSIS)

หน่วยกิตกระบวนวิชา 3(3-0-6)

เงื่อนไขที่ต้องผ่านก่อน 204251 or 204252; and 206183 or 206281

ประกาศ

Facebook Group : 21S1-204451

วัน-เวลาเรียน ห้องเรียนและผู้สอน

วันอังคารและศุกร์ เวลา 08:00 - 09:30 น.

ตอน 001 ห้องเรียน  CSB 207
ชื่อผู้สอน ผศ.เบญจมาศ ปัญญางาม		
ห้องทำงาน : CSB 110 email : bpanyangam@yahoo.com

ตอน 002 ห้องเรียน  CSB 209
  ชื่อผู้สอน ผศ.ดร.จักริน  ชวชาติ	
ห้องทำงาน : CSB 107 email : jakarin.c@cmu.ac.th

ทั้งนีจนถึงเดือนกรกฏาคม เรียนทาง Online ประกาศ

วัตถุประสงค์ของกระบวนวิชา

เพื่อให้นักศึกษาสามารถ

ประเมินความซับซ้อนของอัลกอริทึมและมีความสามารถออกแบบใหม่
อธิบายความรู้เทคนิคอัลกอริทึมขั้นพื้นฐาน
นำเทคนิคเหล่านี้ไปประยุกต์ใช้งานได้

สัดส่วนการให้คะแนน

การวัดผล อิงเกณฑ์และกลุ่ม

คะแนนสอบย่อย 15%
คะแนนงานโปรแกรม 10%
วินัยในการส่งงาน 5%
คะแนนสอบกลางภาค 35%
คะแนนสอบปลายภาค 35%

กำหนดส่งงาน (download ไฟล์งานบน FB กระบวนวิชา)

การตั้งชื่อไฟล์ assign_xx_id โดยที่ xx หมายถึงลำดับงาน เช่น assign_01_id เป็นต้น

ลำดับงาน	กำหนดส่งงาน
Assignment#01 : Time Complexity	TBA
Assignment#02 : Asymptotic notation I	TBA
Assignment#03 : Asymptotic notation II	TBA
Assignment#04 : Solving Recurrence Relation I	TBA
Assignment#05 : Solving Recurrence Relation II	TBA
Assignment#06 : Network Flow	TBA
Assignment#07 : NP I	TBA
Assignment#08 : NP II	TBA
Assignment#09 : Automata I	TBA
Assignment#10 : Automata II	TBA

กำหนดส่งงานโปรแกรม ส่งบนระบบ Grader

ลำดับงาน	กำหนดส่งงาน
Problem#01 :	TBA
Problem#02 :	TBA
Problem#03 :	TBA
Problem#04 :	TBA

เนื้อหากระบวนวิชา

สัปดาห์ที่	เนื้อหา-บรรยาย
0	* ชี้แจงแนวทางการเรียนการสอน นัดสอบกลางภาค
1	* บทที่ 1 ทบทวนคณิตศาสตร์ (Math Reviews) Download * บทที่ 2 ความสำคัญของอัลกอริทึมที่มีประสิทธิภาพ (The importance of efficient algorithms) Download
2	* บทที่ 3 สัญลักษณ์แสดงขีดจำกัด (Asymptotic notation) Download Download1 Download2
3-4	วันอังคารที่ 27 ก.ค. 64 หยุดพิเศษ(ครม.) * บทที่ 4 การแก้ปัญหาความสัมพันธ์แบบเวียนเกิด (Solving recurrence relations) Download1 Download2 * บทที่ 5 อัลกอริทึมแบบแบ่งแยกและเอาชนะ (Divide and conquer algorithms) Download1
5	* บทที่ 5 อัลกอริทึมแบบแบ่งแยกและเอาชนะ (Divide and conquer algorithms) Download2 Download3
6	* บทที่ 6 ต้นไม้การตัดสินใจและขอบเขตล่าง (Decision trees and lower bounds) Download * บทที่ 7 ปัญหาเกี่ยวกับสายอักขระ (String related problem) Download
7-8	* บทที่ 8 อัลกอริทึมเชิงละโมบ (Greedy algorithms)Download1 Download2 Download3
ช่วงสัปดาห์สอบกลางภาค วันจันทร์ที่ 16 - อาทิตย์ที่ 22 สิงหาคม 2564 สอบกลางภาค วันที่ 12 ก.ย. 63 เวลา 15.30 -18.30 น.(นัดหมายในวันแรกของการเรียน)
9-10	* บทที่ 9 การโปรแกรมแบบพลวัต (Dynamic programming) DP1 DP2 DP3 DP4
11-12	* บทที่ 10 การไหลในเครือข่าย (Network flow) NetFlow1 NetFlow2 NetFlow3
12-13	* บทที่ 11 เอ็นพีบริบูรณ์ (NP-Completeness) วันอังคารที่ 13 ต.ค. 63 หยุด วันคล้ายวันสวรรคตของพระบาทสมเด็จพระบรมชนกาธิเบศร มหาภูมิพลอดุลยเดชมหาราช บรมนาถบพิตร NP1 NP2 NP3
14-15	* บทที่ 12 ออโตมาตา (Automata) วันศุกร์ที่ 23 ต.ค. 63 หยุด วันปิยมหาราช AutoMata1 AutoMata2 AutoMata3

21 และอังคารที่ 26 - ศุกร์ที่ 29 ตุลาคม 2564
สอบปลายภาควันพฤหัสบดี ที่ 21 ต.ค. 64 เวลา 12:00 - 15:00 น. (ตามประกาศของมหาวิทยาลัย) ||

หนังสือ/วารสารประกอบการเรียนการสอน

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms
สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม (Online Book ที่ http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/)