การออกแบบและวิเคราะห์ขั้นตอนวิธี
ภาคเรียนต้น 2545
วันจันทร์ พุธ ศุกร์เวลา 9:00-10:00 น. ตึก SCI25 M02
ชั่วโมงให้คำปรึกษา: พฤหัส ศุกร์ 12:00-13:00 น.
ผู้สอน
(Lecturer) |
อ.ดร. กรุง สินอภิรมย์สราญ
ภาควิชาคณิตศาสตร์, คณะวิทยาศาสตร์, จุฬาลงกรณ์มหาวิทยาลัย
โทรศัพท์: 218-5158(ที่ทำงาน)
อีเมล์: Krung.S@chula.ac.th
เว็บ: http://pioneer.netserv.chula.ac.th/~skrung
|
หนังสือเรียน
(Text) |
Brassard, G. and Bratley P., Fundamentals of Algorithmics, Prentice-Hall, 1996
|
หนังสืออ้างอิง
(References) |
Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
Even, S., Graph Algorithms, Computer Science Press, 1979
Heileman, G. L., Data structures, algorithms, and object-oriented programming, McGraw-Hill Companies, 1996
Horowitz, E. and Sahni, S., Fundamentals of Computer Algorithms, Computer Science Press, 1978
Manber, U., Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989
|
การวัดผล
(Evaluation) |
| สอบย่อย | 30% |
| สอบกลางภาค | 35% |
| สอบปลายภาค | 35% |
หมายเหตุ: สอบย่อยใช้เวลา 40 นาที 6 ครั้ง
- สอบกลางภาค วันที่ 29 กรกฎาคม 2545, 8:30-11:30 น.
- สอบปลายภาค วันที่ 25 กันยายน 2545, 13:00-16:00 น.
|
เนื้อหารายวิชา
(Course Description) |
การวัดความซับซ้อน ขั้นตอนวิธีเลขคณิต ขั้นตอนวิธีเมตริกซ์ ขั้นตอนวิธีความน่าจะเป็น ขั้นตอนวิธีเรียงลำดับ
ขั้นตอนวิธีการค้น ขั้นตอนวิธีการจับคู่แบบ ขั้นตอนวิธีการย้อนรอย
|
เนื้อหาที่ครอบคลุม
(Course topics)
| สัปดาห์ที่ 1: | 3-7 มิถุนายน | 2545 |
ทบทวนความรู้พื้นฐานทางคณิตศาสตร์: การพิสูจน์โดย contradiction, induction การนับ ลำดับ อนุกรมและความน่าจะเป็น
|
| สัปดาห์ที่ 2: | 10-14 มิถุนายน | 2545 |
ทบทวนความรู้พื้นฐานทางวิทยาการคอมพิวเตอร์: โครงสร้างข้อมูลและการดำเนินการบนโครงสร้างข้อมูล
ได้แก่ โครงสร้างข้อมูลแถวลำดับ (Array) โครงสร้างข้อมูลกองซ้อน (Stack) โครงสร้างข้อมูลแถวคอย (Queue)
โครงสร้างข้อมูลรายการโยง (Linked List) โครงสร้างข้อมูลต้นไม้ (Tree) โครงสร้างข้อมูลฮีป (Heap) โครงสร้างข้อมูลแฮช (Hash table)
|
| สัปดาห์ที่ 3: | 17-21 มิถุนายน | 2545 |
สอบย่อย I, นิยามขั้นตอนวิธี รหัสลำลอง (Pseudocode) และการวัดความซับซ้อน: O (big-O), o (small-O),
 (big-Omega),  (small-Omega),
 (Theta),
|
| สัปดาห์ที่ 4: | 24-28 มิถุนายน | 2545 |
การวิเคราะห์ขั้นตอนวิธี: barometer, recursion โดยใช้ความสัมพันธ์เวียนเกิด (recurrence relation)
|
| สัปดาห์ที่ 5: | 1-5 กรกฎาคม | 2545 |
สอบย่อย II, การวิเคราะห์ขั้นตอนวิธี: การวิเคราะห์กรณีที่แย่ที่สุด (Worst-case analysis) การวิเคราะห์ในกรณีที่ดีที่สุด
(Best-case analysis) การวิเคราะห์ในกรณีเฉลี่ย (Average-case analysis) การวิเคราะห์ในกรณีใช้งานจริง(Amortized analysis)
|
| สัปดาห์ที่ 6: | 8-12 กรกฎาคม | 2545 |
ประเภทของขั้นตอนวิธี: ขั้นตอนวิธีประเภทละโมภ (Greedy)
|
| สัปดาห์ที่ 7: | 15-19 กรกฎาคม | 2545 |
สอบย่อย III, ประเภทของขั้นตอนวิธี: ขั้นตอนวิธีประเภทละโมภ (Greedy) ต่อ
|
| สัปดาห์ที่ 8: | 22-26 กรกฎาคม | 2545 |
สอบกลางภาค
|
| สัปดาห์ที่ 9: | 29 กรกฎาคม | 2545 |
สอบกลางภาค
|
| สัปดาห์ที่ 10: | 5-9 สิงหาคม | 2545 |
ประเภทของขั้นตอนวิธี: ขั้นตอนวิธีประเภทการแบ่งเพื่อชนะ (Divide-and-conquer)
|
| สัปดาห์ที่ 11: | 12-16 สิงหาคม | 2545 |
สอบย่อย IV, ประเภทของขั้นตอนวิธี: ขั้นตอนวิธีประเภทกำหนดการพลวัต (Dynamic Programming)
|
| สัปดาห์ที่ 12: | 19-23 สิงหาคม | 2545 |
ประเภทของขั้นตอนวิธี: ขั้นตอนวิธีประเภทศึกษาสำนึก (Heuristic)
|
| สัปดาห์ที่ 13: | 26-30 สิงหาคม | 2545 |
สอบย่อย V, ปัญหาทางขั้นตอนวิธี: Number-Theoretic Algorithms
|
| สัปดาห์ที่ 14: | 2-6 กันยายน | 2545 |
ปัญหาทางขั้นตอนวิธี: RSA algorithm
|
| สัปดาห์ที่ 15: | 9-13 กันยายน | 2545 |
สอบย่อย VI, ปัญหาทางขั้นตอนวิธี: Sorting
|
| สัปดาห์ที่ 16: | 16-20 กันยายน | 2545 |
ปัญหาทางขั้นตอนวิธี: String matching
|
| สัปดาห์ที่ 17: | 25 กันยายน | 2545 |
สอบปลายภาค
|
|
|
2301372 การออกแบบและวิเคราะห์ขั้นตอนวิธี
