รายละเอียด

การวิเคราะห์และออกแบบขั้นตอนวิธี / Analysis and Design of Algorithms

  • 17 สัปดาห์
  • จำนวนนักศึกษา 36 คน
  • อาจารย์ผู้สอน 1 คน

ข้อมูลรายวิชา

  • รหัสรายวิชา : BSCCS404
  • ชื่อรายวิชา(TH) : การวิเคราะห์และออกแบบขั้นตอนวิธี
  • ชื่อรายวิชา (EN) : Analysis and Design of Algorithms
  • เทอม / ปีการศึกษา : 2/2563

รายละเอียด

รายวิชา - การวิเคราะห์และออกแบบขั้นตอนวิธี

บทที่ 1 บทนำ
• การหาค่าน้อยที่สุดในแถวลำดับ
• การออกแบบอัลกอริทึม
• เนื้อหาที่จะเรียน
• พื้นฐานที่ต้องมี
กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 2 ปัญหาและอัลกอริทึม
• ปัญหา
• ตัวอย่างปัญหา
• ขนาดของตัวอย่างปัญหา
• อัลกอริทึม

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 3 การเติบโตของฟังก์ชัน
• อัตราการเติบโต
• สัญกรณ์เชิงเส้นกำกับ
• โอเล็ก
• โอเมกาเล็ก
• ทีตาใหญ่
• โอใหญ่
• โอเมกาใหญ่
• คุณสมบัติของสัญกรณ์เชิงเส้นกำกับ
• การใช้สัญกรณ์เชิงเส้นกำกับในสมการ
• การใช้สัญกรณ์เชิงเส้นกำกับ

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 4 การวิเคราะห์อัลกอริทึม
• คำสั่งมูลฐาน
• คำสั่งมาตรเวลา
• การวิเคราะห์รูปแบบการทำงาน
• การทำงานแบบลำดับ
• คำสั่ง if…then…else
• วงวนแบบ for
• วงวนแบบ while
• การเรียกแบบเวียนเกิด
• ประเภทของการวิเคราะห์

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 5 การวิเคราะห์ถัวเฉลี่ย
• กองซ้อนแบบมี multipop
• วิธีการวิเคราะห์กรณีถัวเฉลี่ย
• กองซ้อนขนาดไม่จำกัด
• การค้นหาทวิภาคแบบพลวัต

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 6 การแบ่งแยกและเอาชนะ
• การค้นแบบทวิภาค
• การเรียงลำดับแบบผสาน
• การเรียงลำดับแบบเร็ว
• ปัญหาการเลือก
• การคูณเมทริกซ์

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 7 กำหนดการพลวัต
• ปัญหาการหาค่าเหมาะที่สุด
• ลักษณะเฉพาะของปัญหา
• ขั้นตอนการออกแบบด้วยกำหนดการพลวัต
• การคูณลูกโซ่เมทริกซ์

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

สอบกลางภาค
กิจกรรม :

บทที่ 8 อัลกอริทึมเชิงละโมบ
• ปัญหาถุงเป้
• ลักษณะเฉพาะของปัญหา
• อัลกอริทึมการแก้ปัญหา

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 9 การค้นคำตอบ
• รูปแบบของผลเฉลย
• การแจงกรณีและตรวจสอบผลเฉลย
• การค้นตามแนวลึก แนวกว้าง และต้นทุนน้อยสุด

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 10 อัลกอริทึมเชิงสุ่ม (ตอนที่ 1)
• อัลกอริทึมแบบมอนติคาร์โล
o การทวนสอบการคูณเมทริกซ์
o ส่วนตัดน้อยที่สุด
o การทดสอบความเป็นจำนวนเฉพาะ
o การจับคู่สตริง

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 10 อัลกอริทึมเชิงสุ่ม (ตอนที่ 2)
• อัลกอริทึมแบบลาสเวกัส
o อัลกอริทึมแบบลาสเวกัสที่ไม่ต้องเรียกซ้ำ
o อัลกอริทึมแบบลาสเวกัสที่อาจต้องเรียกซ้ำ
o ปัญหาการเลือก
o การจับคู่สตริง

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 11 เอ็นพีบริบูรณ์ (ตอนที่ 1)
• อัลกอริทึมที่มีและที่ไม่ประสิทธิภาพ
• ปัญหาง่ายและยาก
• ปัญหาการตัดสินใจ
• กลุ่มปัญหาพี
• กลุ่มปัญหาเอ็นพี

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

บทที่ 11 เอ็นพีบริบูรณ์ (ตอนที่ 2)
• การลดรูปปัญหา
• กลุ่มปัญหาเอ็นพีบริบูรณ์
• อัลกอริทึมสำหรับปัญหาเอ็นพีแบบยาก

กิจกรรม : - บรรยายประกอบสื่อ
นำเสนอ พร้อมยกตัวอย่างประกอบ
- ซักถามประเด็นสงสัย

นำเสนอรายงาน
กิจกรรม : - ฟังการนำเสนอและให้ข้อเสนอแนะ

ทบทวน
กิจกรรม : - ฟังการนำเสนอและให้ข้อเสนอแนะ

สอบปลายภาค
กิจกรรม :

อาจารย์ผู้สอน