คำอธิบายรายวิชา Course description

(ภาษาไทย) ความเป็นมาและภาพรวมของขั้นตอนวิธี การวิเคราะห์ขั้นตอนวิธีแบบพื้นฐาน การวิเคราะห์ความซับซ้อนขอบบนและระดับเฉลี่ย บิ๊กโอ แนะนำกลยุทธ์ขันตอนวิธีขั้นตอนวิธีแบบถี่ถ้วน ขั้นตอนวิธีเชิงละโมบ หลักการแบ่งแยกเพื่อเอาชนะ การย้อนรอย ขั้นตอนวิธีการคำนวณ ขั้นตอนวิธีเชิงตัวเลขอย่างง่าย การเรียงลำดับ การค้นหา ตารางแฮช กราฟ ขั้นตอนวิธีหาทางที่สั้นที่สุด ขั้นตอนวิธีแบบกระจาย ความซับซ้อนของขั้นตอนวิธี ปัญหาแทร็กเทเบิล และปัญหาอินแทร็กเทเบิล กลุ่มปัญหาแบบพีเอ็นพี และ เอ็นพีสมบูรณ์ ปัญหามาตรฐานแบบเอ็นพีสมบูรณ์

(ภาษาอังกฤษ)  History and overview of algorithms; basic algorithmic analysis, analysis of upper and average complexity bound, big O; introduction to algorithmic strategies, brute-force algorithm, greedy algorithm, divide-and-conquer, backtracking; computing algorithms, simple numerical algorithms, sorting, searching, hash table, graph, shortest-path algorithms; distributed algorithms; algorithmic complexity; tractable and intractable problems; class P, class NP, NP-completeness; standard NP-complete problems 

จุดประสงค์รายวิชา
  รายวิชานี้ เป็นการแนะนำให้ผู้เรียนได้รู้จักอัลกอริทึม(หรือขั้นตอนวิธี) การวิเคราะห์และออกแบบอัลกอริทึม โดยศึกษาจากตัวอย่างการวิเคราะห์และอัลกอริทึมพื้นฐาน ประเภทต่างๆ ให้รู้จักการเปรียบเทียบประสิทธิภาพและความซับซ้อนของอัลกอริทึมได้ และแนะนำการจัดแบ่งประเภทของกลุ่มปัญหาพี/เอ็นพี

รายวิชาที่ต้องเรียนมาก่อน (Pre-requisites)

  ผู้เรียนต้องเรียนผ่าน วิชา 242-207 มีความรู้พื้นฐานที่ดีเกี่ยวกับโครงสร้างข้อมูลและ discrete math

การให้คะแนน Scoring คะแนนรวม 100%

สอบกลางภาค Midterm exam   35%

สอบปลายภาค Final exam  35% 

Assignment   20%

Quiz และเข้าห้องเรียน    10%

หนังสืออ้างอิง Reference

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

[1] สมชาย ประสิทธิจูตระกูล. อัลกอริทึม การออกแบบและวิเคราะห์, พิมพ์ครั้งที่ 4, จุฬาลงกรณ์มหาวิทยาลัย ภาควิชาวิศวกรรมคอมพิวเตอร์, 2553.

[2] S. S. Skeina. The Algorithm Design Manual, 2^nd ed, Spriger-Verlag, 2008.

หนังสือแนะนำ

[3] J. Kleinberg and E. Tardos. Algorithm Design, Addison-Wesley, 2005.

[4] Shi-Kuo Chang, et al. Data Structures and Algorithms, World Scientific Publishing, 2003.

[5]R. Sedgewick and K.Wayne. Algorithms, Addison-Wesley, 2011.

[6] M. A. Weiss, Data Structures and Algorithm Analysis in C++, 4^th ed, Printice-Hall, 2013.

[7]T. H. Cormen, C. E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3rd ed, MIT Press,2009.

[8]R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996.

[9] C.A. Shaffer. Data Structures and Algorithm Analysis (C++ version), electronic edition 3.2, 2012.

[10] ณัฐพงษ์ วารีประเสริฐ, สุธี พงศาสกุลชัย. โครงสร้างข้อมูลและอัลกอริทึม, เคทีพี คอมพ์แอนด์คอนซัลท์,  2552.