418531 ภาคต้น 2553

ขอต้อนรับเข้าสู่ 418531: โครงสร้างข้อมูลและการวิเคราะห์อัลกอริทึม ประจำภาคการศึกษาที่ 1 ปีัการศึกษา 2553

ประกาศ

• 1 กรกฎาคม 2553: เฉลยข้อสอบย่อยครั้งที่ 1 ของปีนี้ (PDF)
• 21 มิถุนายน 2553: ข้อสอบย่อยครั้งที่ 1 ของปีที่แล้ว (PDF) ข้อสอบชุดเดียวกันพร้อมเฉลย (PDF)
• 14 มิถุนายน 2553
  • การสอบย่อยครั้งแรกจะมีในวันพุธที่ 23 มิถุนายน 2553 เวลา 18.00 น. - 20.00 น. ณ ห้อง 114
  • ติวสอบย่อยครั้งแรกในวันอังคารที่ 22 มิถุนายน 2553 เวลา 18.00 น. - 20.00 น. ณ ห้อง 114
• 7 พฤษภาคม 2553: เริ่มสร้างเวบไซต์

เกี่ยวกับรายวิชา

• เนื้อหา

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

• เวลาและสถานที่
  • ภาคปกติ: วันอังคาร 13.00 น. - 16.00 น. SMC 101
  • ภาคพิเศษ: วันอาทิตย์ 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

การเรียนการสอน

วันที่	หัวข้อ	เอกสาร
ภาคปกติ: 1 มิ.ย. 2553 ภาคพิเศษ: 6 มิ.ย. 2553	ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน I	อ่าน Logic โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน I
ภาคปกติ: 8 มิ.ย. 2553 ภาคพิเศษ: 13 มิ.ย. 2553	ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน II	อ่า่น Binary Relations หน้า 1-7 Mathematical Data Types หน้า 8-15 โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน II
ภาคปกติ: 15 มิ.ย. 2553 ภาคพิเศษ: 20 มิ.ย. 2553	งดการเรียนการสอน (ปฐมนิเทศ ป.โท)	ไม่มี
ภาคปกติ: 22 มิ.ย. 2553 ภาคพิเศษ: 27 มิ.ย. 2553	การพิสูจน์ I	อ่าน Proofs โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการพิสูจน์ I
ภาคปกติ: 29 มิ.ย. 2553 ภาคพิเศษ: 4 ก.ค. 2553	การพิสูจน์ II	อ่าน Induction Recursive Definition and Structural Induction โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการพิสูจน์ II
ภาคปกติ: 6 ก.ค. 2553 ภาคพิเศษ: 11 ก.ค. 2553	การวิเคราะห์เชิงการจัด (Combinatorics)	อ่าน Counting I Counting II โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการวิเคราะห์เชิงการจัด
ภาคปกติ: 13 ก.ค. 2553 ภาคพิเศษ: 18 ก.ค. 2553	การวิเคราะห์เชิงเส้นกำกัับ (Asymtotic Analysis)	อ่าน Kleinberg & Tardos 2.2 และ 2.4 สไลด์ อัลกอริทึมและการวิเคราะห์เวลาทำงาน Running Time Analysis Asymptotic Notations & Recurrences Application of Recurrences โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการวิเคราะห์เชิงเส้นกำกับ
ภาคปกติ: 20 ก.ค. 2553 ภาคพิเศษ: 25 ส.ค. 2553	ความน่าจะเป็น I	อ่าน Introduction to Probability Random Variables, Distributions and Expectation โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาความน่าจะเป็น I
ภาคปกติ: 27 ก.ค. 2553 ภาคพิเศษ: 8 ส.ค. 2553	ความน่าจะเป็น II	อ่าน Missed Expectations? โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาความน่าจะเป็น II
ภาคปกติ: 10 ส.ค. 2553 ภาคพิเศษ: 15 ส.ค. 2553	การค้นหาด้วยพละกำลังเยี่ยงควายถึก (Brute Force Search)	สไลด์ การค้นหาข้อมูล: PDF PPT PPTX การค้นหาข้อมูล (ต่อ): PDF PPT PPTX โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก
ภาคปกติ: 17 ส.ค. 2553 ภาคพิเศษ: 22 ส.ค. 2553	อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ (Divide and Conquer)	อ่าน Kleinberg & Tardos บทที่ 5.1 - 5.4 สไลด์ PDF PPT Merge Demo Merge and Count Demo เนื้อหาสำหรับเรื่อง closest pair and quicksort ที่จดในห้องไม่ทัน โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ
ภาคปกติ: 24 ส.ค. 2553 ภาคพิเศษ: 29 ส.ค. 2553	อัลกอริทึมเกี่ยวกับกราฟ	อ่าน Kleinberg & Tardos บทที่ 3 สไลด์ Graph (printable version) สไลด์ Graph (with animation, not recommended for printing) Demo on BFS Demo on DAG โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ
ภาคปกติ: 31 ส.ค. 2553 ภาคพิเศษ: 5 ก.ย. 2553	อัลกอริทึมแบบตะกละ I (Greedy Algorithm)	อ่าน Kleinberg & Tardos 4.1 - 4.4 สไลด์ PDF PPT Interval Scheduling Demo Dijkstra's Algorithm Demo โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาอัลกอริทึมแบบตะกละ I
ภาคปกติ: 7 ก.ย. 2553 ภาคพิเศษ: 12 ก.ย. 2553	อัลกอริทึมแบบตะกละ II (Greedy Algorithm)	อ่าน Kleinberg & Tardos 4.5 - 4.7 สไลด์ PDF PPT Prim's MST Demo (Slides 27-39) Union-Find โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาอัลกอริทึมแบบตะกละ II
ภาคปกติ: 14 ก.ย. 2553 ภาคพิเศษ: 19 ก.ย. 2553	การโปรแกรมพลวัต I (Dynamic Programming)	อ่าน Kleinberg & Tardos บทที่ 6.1 - 6.5 สไลด์ Dynamic Programming: PDF PPT Matrix Chain Multiplication: PDF โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการโปรแกรมพลวัต I
ภาคปกติ: 21 ก.ย. 2553 ภาคพิเศษ: 26 ก.ย. 2553	การโปรแกรมพลวัต II (Dynamic Programming)	อ่าน Kleinberg & Tardos บทที่ 6.6 - 6.10 สไลด์ PDF PPT โจทย์ปัญหาพร้อมเฉลย โจทย์ปัญหาการโปรแกรมพลวัต II

การสอบ

การสอบ	วันที่	หัวข้อ
สอบย่อยครั้งที่ 1	23 มิ.ย. 2553	ตรรกศาสตร์, เซต, ความสัมพันธ์, ฟังก์ชัน
สอบย่อยครั้งที่ 2	16 ก.ค. 2553	การพิสูจน์
สอบกลางภาค	5 ส.ค. 2553	การพิสูจน์, การวิเคราะห์เชิงเส้นกำกับ, ความน่าจะเป็น
สอบย่อยครั้งที่ 3	9 ก.ย. 2553	อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ
สอบย่อยครั้งที่ 4	23 ก.ย. 2553	อัลกอริทึมแบบตะกละ
สอบปลายภาค	7 ต.ค. 2553	อัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ, อัลกอริทึมแบบตะกละ, การโปรแกรมพลวัต

ลิงก์ภายนอก

• MIT 6.042: Mathematics for Computer Science