|
|
| แถว 1: |
แถว 1: |
| − | ขอต้อนรับเข้าสู่ '''418531: โครงสร้างข้อมูลและการวิเคราะห์อัลกอริทึม''' ประจำภาคการศึกษาที่ 1 ปีัการศึกษา 2553
| |
| | | | |
| − | == ประกาศ ==
| |
| − | * 7 พฤษภาคม 2553: เริ่มสร้างเวบไซต์
| |
| − |
| |
| − | == เกี่ยวกับรายวิชา ==
| |
| − | * เนื้อหา
| |
| − | : วิชานี้ทบทวบเนื้อหาเกี่ยวกับคณิตศาสตร์ดิสครีต โครงสร้างข้อมูล การวิเคราะห์และออกแบบอัลกอริทึม ซึ่งเป็นความรู้ที่มึความจำเป็นยิ่งในการศึกษาวิทยาการคอมพิวเตอร์ และการทำวิจัยในระดับบัณฑิตศึกษา
| |
| − | * เวลาและสถานที่
| |
| − | ** ภาคปกติ: วันอังคาร 12.30 น. - 15.30 น. SMC 126
| |
| − | ** ภาคพิเศษ: วันอาทิตย์ 13.00 น. - 16.00 น. SMC 126
| |
| − | * การให้คะแนน
| |
| − | ** สอบย่อย 4 ครั้ง ครั้งละ 15% รวม 60%
| |
| − | ** สอบกลางภาค 20%
| |
| − | ** สอบปลายภาค 20%
| |
| − | * ผู้สอน
| |
| − | ** อ.ประมุข ขันเงิน
| |
| − | *** อีเมล์: pramook at gmail dot com หรือ fscipmk at ku dot ac dot th
| |
| − | *** มือถือ: ศูนย์ แปด ห้า สี่ ห้า สาม ห้า แปด ห้า เจ็ด
| |
| − | *** เวลาเข้าพบ: วันพุธและวันศุกร์ 13.00 น. - 16.00 น. หรือนัดหมายล่วงหน้า
| |
| − | *** ออฟฟิศ: ห้องไม่มีเบอร์เยื้องสำนักงานภาีควิชา
| |
| − | * หนังสือ
| |
| − | ** Kenneth H. Rosen. '''Discrete Mathematics and Its Applications.''' McGraw-Hill, 2006.
| |
| − | ** Jon Kleinberg and Eva Tardos. '''Algorithm Design.''' Addison Wesley, 2005.
| |
| − | **: ซื้อได้ที่ศูนย์หนังสือเกษตร แต่ยังไม่ใช่จนกว่าจะถึงสัปดาห์ที่ 6
| |
| − |
| |
| − | == การเรียนการสอน ==
| |
| − | <table border="1" cellpadding="5">
| |
| − | <tr>
| |
| − | <td>'''วันที่'''</td>
| |
| − | <td>'''หัวข้อ'''</td>
| |
| − | <td>'''เอกสาร'''</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 8 มิ.ย. 2552
| |
| − | * ภาคพิเศษ: 13 มิ.ย. 2552
| |
| − | </td>
| |
| − | <td>ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน I</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-01/l1_logic.pdf Logic]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน I|โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน I]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 15 มิ.ย. 2552
| |
| − | * ภาคพิเศษ: 20 มิ.ย. 2552
| |
| − | </td>
| |
| − | <td>ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน II</td>
| |
| − | <td>
| |
| − | อ่า่น
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-02/ln4.pdf Binary Relations] หน้า 1-7
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-02/ln2.pdf Mathematical Data Types] หน้า 8-15
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน II|โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน II]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 22 มิ.ย. 2552
| |
| − | * ภาคพิเศษ: 27 มิ.ย. 2552
| |
| − | </td>
| |
| − | <td>การพิสูจน์ I</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-03/l2_proofs.pdf Proofs]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ I|โจทย์ปัญหาการพิสูจน์ I]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 29 มิ.ย. 2552
| |
| − | * ภาคพิเศษ: 4 ก.ค. 2552
| |
| − | </td>
| |
| − | <td>การพิสูจน์ II</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-04/ln2.pdf Induction]
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-04/ln6.pdf Recursive Definition and Structural Induction]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II|โจทย์ปัญหาการพิสูจน์ II]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 6 ก.ค. 2552
| |
| − | * ภาคพิเศษ: 11 ก.ค. 2552
| |
| − | </td>
| |
| − | <td>การวิเคราะห์เชิงการจัด (Combinatorics)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-05/ln9.pdf Counting I]
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-05/ln10.pdf Counting II]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด|โจทย์ปัญหาการวิเคราะห์เชิงการจัด]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 13 ก.ค. 2552
| |
| − | * ภาคพิเศษ: 18 ก.ค. 2552
| |
| − | </td>
| |
| − | <td>การวิเคราะห์เชิงเส้นกำกัับ (Asymtotic Analysis)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos 2.2 และ 2.4
| |
| − | สไลด์
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-06/lecture06.pdf อัลกอริทึมและการวิเคราะห์เวลาทำงาน]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture03/lecture03-runtime-analysis.ppt Running Time Analysis]
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-06/mit6046jf05_demaine_lec02_01.pdf Asymptotic Notations & Recurrences]
| |
| − | * [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-04/lec3.pdf Application of Recurrences]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ|โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 20 ก.ค. 2552
| |
| − | * ภาคพิเศษ: 25 ส.ค. 2552
| |
| − | </td>
| |
| − | <td>ความน่าจะเป็น I</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-07/ln12.pdf Introduction to Probability]
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-07/ln13.pdf Random Variables, Distributions and Expectation]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น I|โจทย์ปัญหาความน่าจะเป็น I]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 27 ก.ค. 2552
| |
| − | * ภาคพิเศษ: 8 ส.ค. 2552
| |
| − | </td>
| |
| − |
| |
| − | <td>ความน่าจะเป็น II</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-08/ln14.pdf Missed Expectations?]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาความน่าจะเป็น II|โจทย์ปัญหาความน่าจะเป็น II]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 10 ส.ค. 2552
| |
| − | * ภาคพิเศษ: 15 ส.ค. 2552
| |
| − | </td>
| |
| − | <td>การค้นหาด้วยพละกำลังเยี่ยงควายถึก (Brute Force Search)</td>
| |
| − | <td>
| |
| − | สไลด์
| |
| − | * การค้นหาข้อมูล: [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching.pdf PDF] [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching.ppt PPT] [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching.pptx PPTX]
| |
| − | * การค้นหาข้อมูล (ต่อ): [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching-2.pdf PDF] [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching-2.ppt PPT] [http://theory.cpe.ku.ac.th/~pramook/418531/lecture-09/searching-2.pptx PPTX]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418531 ภาคต้น 2552/โจทย์ปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก|โจทย์ปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 17 ส.ค. 2552
| |
| − | * ภาคพิเศษ: 22 ส.ค. 2552
| |
| − | </td>
| |
| − | <td>อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ (Divide and Conquer)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos บทที่ 5.1 - 5.4
| |
| − | สไลด์
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture09/05divide-and-conquer.pdf PDF] [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture09/05divide-and-conquer.ppt PPT]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture09/05demo-merge.ppt Merge Demo]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture09/05demo-merge-invert.ppt Merge and Count Demo]
| |
| − | *[[เนื้อหาสำหรับเรื่อง closest pair and quicksort ที่จดในห้องไม่ทัน]]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ|โจทย์ปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 24 ส.ค. 2552
| |
| − | * ภาคพิเศษ: 29 ส.ค. 2552
| |
| − | </td>
| |
| − | <td>อัลกอริทึมเกี่ยวกับกราฟ</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos บทที่ 3
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture05/lecture05-graphs-print-bw.pdf สไลด์ Graph (printable version)]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture05/lecture05-graphs.ppt สไลด์ Graph (with animation, not recommended for printing)]
| |
| − | * [http://www.cs.princeton.edu/~wayne/cs423/lectures/demo-bfs.ppt Demo on BFS]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture05/demo-dag.ppt Demo on DAG]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมเกี่ยวกับกราฟ|โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 31 ส.ค. 2552
| |
| − | * ภาคพิเศษ: 5 ก.ย. 2552
| |
| − | </td>
| |
| − | <td>อัลกอริทึมแบบตะกละ I (Greedy Algorithm)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos 4.1 - 4.4
| |
| − | สไลด์
| |
| − | * [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-06/04greed.pdf PDF] [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-06/04greed.ppt PPT]
| |
| − | * [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-06/04demo-interval-scheduling.ppt Interval Scheduling Demo]
| |
| − | * [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-06/04demo-dijkstra.ppt Dijkstra's Algorithm Demo]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมแบบตะกละ I|โจทย์ปัญหาอัลกอริทึมแบบตะกละ I]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 7 ก.ย. 2552
| |
| − | * ภาคพิเศษ: 12 ก.ย. 2552
| |
| − | </td>
| |
| − | <td>อัลกอริทึมแบบตะกละ II (Greedy Algorithm)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos 4.5 - 4.7
| |
| − | สไลด์
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture07/04mst.pdf PDF] [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture07/04mst.ppt PPT]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture07/lec16-slide27.pdf Prim's MST Demo (Slides 27-39)]
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture07/union-find.ppt Union-Find]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริืทึมแบบตะกละ II|โจทย์ปัญหาอัลกอริทึมแบบตะกละ II]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 14 ก.ย. 2552
| |
| − | * ภาคพิเศษ: 19 ก.ย. 2552
| |
| − | </td>
| |
| − | <td>การโปรแกรมพลวัต I (Dynamic Programming)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos บทที่ 6.1 - 6.5
| |
| − | สไลด์
| |
| − | * Dynamic Programming: [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-10/06dynamic-programming.pdf PDF] [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-10/06dynamic-programming.ppt PPT]
| |
| − | * Matrix Chain Multiplication: [http://access.cs.sci.ku.ac.th/~pramook/418531/first2008/lecture-10/matrix-chain.pdf PDF]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I|โจทย์ปัญหาการโปรแกรมพลวัต I]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>
| |
| − | * ภาคปกติ: 21 ก.ย. 2552
| |
| − | * ภาคพิเศษ: 26 ก.ย. 2552
| |
| − | </td>
| |
| − | <td>การโปรแกรมพลวัต II (Dynamic Programming)</td>
| |
| − | <td>
| |
| − | อ่าน
| |
| − | * Kleinberg & Tardos บทที่ 6.6 - 6.10
| |
| − | สไลด์
| |
| − | * [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture11/06bellman-ford.pdf PDF] [http://access.cs.sci.ku.ac.th/~usa/418531/2008-1/lecture11/06bellman-ford.ppt PPT]
| |
| − | โจทย์ปัญหาพร้อมเฉลย
| |
| − | * [[418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II|โจทย์ปัญหาการโปรแกรมพลวัต II]]
| |
| − | </td>
| |
| − | </tr>
| |
| − |
| |
| − | </table>
| |
| − |
| |
| − | == การสอบ ==
| |
| − | <table border="1" cellpadding="5">
| |
| − | <tr>
| |
| − | <td>'''การสอบ'''</td>
| |
| − | <td>'''วันที่'''</td>
| |
| − | <td>'''หัวข้อ'''</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบย่อยครั้งที่ 1</td>
| |
| − | <td>24 มิ.ย. 2552</td>
| |
| − | <td>ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบย่อยครั้งที่ 2</td>
| |
| − | <td>16 ก.ค. 2552</td>
| |
| − | <td>การพิสูจน์</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบกลางภาค</td>
| |
| − | <td>5 ส.ค. 2552</td>
| |
| − | <td>การพิสูจน์, การวิเคราะห์เชิงเส้นกำกับ, ความน่าจะเป็น</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบย่อยครั้งที่ 3</td>
| |
| − | <td>9 ก.ย. 2552</td>
| |
| − | <td>อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบย่อยครั้งที่ 4</td>
| |
| − | <td>23 ก.ย. 2552</td>
| |
| − | <td>อัลกอริทึมแบบตะกละ</td>
| |
| − | </tr>
| |
| − |
| |
| − | <tr>
| |
| − | <td>สอบปลายภาค</td>
| |
| − | <td>7 ต.ค. 2552</td>
| |
| − | <td>อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ, อัลกอริทึมแบบตะกละ, การโปรแกรมพลวัต</td>
| |
| − | </tr>
| |
| − |
| |
| − | </table>
| |
| − |
| |
| − | == ลิงก์ภายนอก ==
| |
| − | * [http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-042JSpring-2005/CourseHome/index.htm MIT 6.042: Mathematics for Computer Science]
| |
