ผลต่างระหว่างรุ่นของ "204512-53/lecture1"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 13 รุ่นระหว่างกลางโดยผู้ใช้ 4 คน)
แถว 3: แถว 3:
 
Algorithm Lecture #1
 
Algorithm Lecture #1
  
Course Information
+
=Course Information=
 +
รายละเอียดวิชาสามารถดูได้ที่ http://www.cpe.ku.ac.th/~jtf/wiki/doku.php?id=01204512-53
  
    * Homework    15%
+
==เกณฑ์การให้คะแนน==
    * Project        15%
+
* Homework    15%
    * Scribe note   5%
+
* Project        15%
    * Mid-Term 2 Times 20x2%
+
* Scribe Note   5%
    * Final            25%
+
* Mid-Term 2 Times 20*2%
 +
* Final            25%
  
URL    http://www.cpe.ku.ac.th/~jtf/wiki/doku.php?id=01204512-53
+
=Introduction to Algorithm=
  
Introduction to Algorithm
+
==ทำไมเราต้องวิเคราะห์อัลกอริทึม==
  
??. ทำไมเราต้องวิเคราะห์อัลกอริทึม
+
* เพื่อความถูกต้องของอัลกอริทึม - ต้องการความแน่ใจ
 +
* เพื่อประสิทธิภาพของอัลกอริทึม
 +
** เวลา (time)
 +
** พื้นที่ (space)
 +
** คุณภาพคำตอบ (quality)
  
    * เพื่อความถูกต้องของอัลกอริทึม - ต้องการความแน่ใจ
+
==เนื้อหาแต่ละบทที่จะสอน ตามลำดับ==
    * เพื่อประสิทธิภาพของอัลกอริทึม - ทั้งด้าน เวลา (time), พื้นที่ (space), คุณภาพคำตอบ (quality)
 
  
 +
# Data Structure
 +
# Graph Algorithm
 +
# Dynamic Programming
 +
# Linear Programming
 +
# Randomize Algorithm
  
เนื้อหาแต่ละ บทที่จะสอนตามลำดับ
+
===Data Structure===
  
  1.    data structure
+
====ตัวอย่างปัญหาที่ 1====
  2.    graph algorithm
+
การจองอาเรย์ให้เหมาะสมกับขนาดข้อมูลที่บรรจุ โดยกำหนดให้มีขั้นตอน การทำงานดังนี้
  3.    dynamic programming
 
  4.    linear programming
 
  5.    randomize algorithm
 
  
 +
# จองพื้นที่สำหรับใส่ของ
 +
# นำของไปใส่จนเต็ม
 +
# จองพื้นที่เพิ่มสำหรับใส่ของ
  
1. Data Structure
+
=====กรณี 1: จองแบบเพิ่มทีละ 1 ที่=====
    ตัวอย่างปัญหาที่ 1 ของ data structure เช่นการจองอาเรย์ให้เหมาะสมกับขนาดข้อมูลที่บรรจุ
 
โดยกำหนดให้มีขั้นตอน การทำงานดังนี้
 
1. จองพื้นที่สำหรับใส่ของ 2. นำของไปใส่จนเต็ม 3. จองพื้นที่เพิ่มสำหรับใส่ของ
 
ลองวิเคราะห์การจองที่ใส่ของเพิ่มที่ละ 1 ที่
 
  
[[ไฟล์:http://docs.google.com/File?id=dc5nr7ts_23d32375g4_b]]
+
[[Image:204512-53-01-malloc-table-1.png]]
 +
 
 +
จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า
 +
* การจองใช้เวลา 1 หน่วย
 +
* การคัดลอกต้องคัดลอก i - 1 ตัวดังนั้นใช้เวลา i - 1 หน่วย
 +
* การนำข้อมูลใหม่ไปใส่ใช้เวลาอีก 1 หน่วย
 +
 
 +
จะเห็นได้ว่าในการสร้างอาเรย์เก็บข้อมูล n ตัวจะต้องใช้เวลาทั้งหมด
 +
 
 +
= <math>2 + 3 + 4 + ... + n + n + 1</math> หน่วย
 +
= <math>2 + 3 + 4 + ... + n + n + 1</math> หน่วย
 +
= <math>(1 + 2 + 3 + ... + n) + n</math> หน่วย
 +
 
 +
ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้  <math>\frac{n*(n+1) + n}{2}</math> หน่วย หรือ O(<math>n^2</math>)
 +
 
 +
=====กรณี 2: จองแบบเพิ่มทีละ 3 ที่=====
 +
 
 +
[[Image:204512-53-01-malloc-table-2.png]]
 +
 
 +
จากภาพการเก็บ สามารถวิเคราะห์ได้ว่าจะยังได้ผลลัพธ์ไม่ต่างจากเดิมมาก คือ O(<math>n^2</math>) โดย n ในที่นี้เทียบได้กับ <math>\frac{n}{3}</math> ของตัวอย่างบน มาจาก <math>n + 3*\frac{n*(n+1)}{2} + 3*n</math> ซึ่งมี factor 3 เพิ่มเข้ามา
 +
 
 +
=====กรณี 3: จองแบบเพิ่มทีละ <math>2^k</math> ที่=====
 +
 
 +
ต่อมามีคนเสนอว่าถ้าลองจองเป็นแบบ <math>2^k</math> โดยที่ k หมายถึงการจองครั้งที่ k และค่า k เริ่มต้นจาก 0 เพื่อเป็นการตัดปัญหา ว่ากรณ๊ถ้าจองไม่เต็มจะทำอย่างไร เราจึงสมมุติไปเลยว่าการจองที่ n นั้นจะต้องจอง <math>n = 2^k</math> โดย k นั้นคือเลขจำนวนเต็มใดๆที่มากกว่า 0 ซึ่งถ้า <math>n < 2^k</math> อาจหมายถึงการแถมเวลาให้เต็ม <math>n = 2^k</math> เลยก็ได้
 +
 
 +
[[Image:204512-53-01-malloc-table-3.png]]
 +
 
 +
จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า
 +
* จะได้ว่ามีการจองข้อมูลเกิดขึ้นทั้งหมด k ครั้ง
 +
* มีการเขียนข้อมูล <math>n(2^{k})</math> ครั้ง
 +
* มีการคัดลอกข้อมูล <math>1+2+4+8+...+2^{k-1} = (2^k)-1</math> (มองง่ายๆให้มองเป็นการบวกเลข binary)
 +
 
 +
ดังนั้นจะได้ k<math> + 2^{k} + 2^{k} -1 = O(n)</math>
 +
 
 +
====ตัวอย่างปัญหาที่ 2====
 +
 
 +
ในแต่ละ Network (เครือข่าย) ประกอบไปด้วยส่วนหลักๆ คือ Router, Client และ Routing table  เราต้องการเรียนรู้การเชื่อมต่อของ Router แต่ละตัวเพื่อบันทึกใน Routing table การคิดวิธีการเพื่อแก้ปัญหา เราจะต้อง Assume (สมมติ) อย่างน้อยว่าการทำงานของระบบจะสำเร็จในสักวัน, ระบบมีความก้าวหน้า, ก้าวหน้ามากพอที่จะสำเร็จในช่วงเวลาที่รับได้ และสมมติฐานในปัจจัยอื่นๆ
 +
 
 +
การ ออกแบบ Routing table แบบ RIP
 +
 
 +
* Assume ว่า Router ทุกตัวทำการ Broadcast (กระจายสัญญาณไปหาทุกตัว) พร้อมกัน และ Router ทุกตัวรู้จักตัวเอง ในที่นี้ให้ค่าระยะของเส้นเชื่อม (edge) เท่ากับ 1 หน่วย
 +
* RIP เป็นการหาเส้นเชื่อมระหว่าง Router เพื่อให้สื่อสารถึงกันได้ทั้งหมด โดยมีค่าระยะทางน้อยที่สุด
 +
* ในการคิดครั้งนี้จะคิดโดยใช้ Router A เป็นโหนดตั้งต้น แล้วค้นหา Router ตัวอื่นที่อยู่รอบๆ
 +
 
 +
กำหนดให้
 +
 
 +
* Set ของโหนด ทั้งหมด แทนด้วย V จะได้ว่า V = {A, B, C, ..., H}
 +
* Set ของเส้นเชื่อม ทั้งหมด แทนด้วย E จะได้ว่า E = {(A,D), (A,B), (A,E), ..., (F,H)}
 +
* Set ของโหนด ที่อยู่ในชั้น n (ติดต่อกับ A ด้วยระยะทาง n หน่วย) แทนด้วย Ln
 +
 
 +
จะได้ว่า
 +
 
 +
L0 = {A}, L1 = {v e V-L0 | มี node u ที่ u e L0 และ (u,v) e E}
 +
 
 +
ดังนั้นสำหรับค่า i ใดๆ ที่ i > 0, Li = {v e V - (ตั้งแต่ L0 จน Li - 1) | มี node u ที่ u e Li - 1 และ (u,v) e E} โดย กำหนดให้ L0={A}
 +
 
 +
====ตัวอย่างปัญหาที่ 3====
 +
 
 +
สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math>"
 +
 
 +
การพิสูจน์โดยใช้วิธี Induction นั้นแบ่งเป็น 2 ส่วนคือ
 +
 
 +
# Basic step (Base case) ซึ่งเป็นจุดกำหนิดของตัวแรกของการคิด ส่วนใหญ่คือค่า 0 หรือ 1 โดยส่วนมากมักจะมีค่าจริงอยู่แล้ว
 +
# Inductive step โดยจะสมมติให้ P(i) มีค่าเป็นจริง แล้วต้องพิสูจน์ให้ได้ว่า P(i + 1) นั้นมีค่าเป็นจริง
 +
 
 +
วิธีการแก้ปัญหาในตัวอย่างนี้
 +
 
 +
=====Basic Step=====
 +
 
 +
<math>P(1) = 1 =1^2</math> มีค่าเป็นจริง
 +
 
 +
=====Inductive Step=====
 +
 
 +
ถ้าให้ P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math> เป็นจริงแล้ว ต้องพิสูจน์ว่า <math>P(i+1)</math> ที่ <math>1+3+5+9+...+(2(i+1)-1) = (i+1)^2</math> เป็นจริง
 +
 
 +
<math>P(i+1) = P(i) + (2(i+1) - 1) = P(i) + 2i + 1</math>
 +
 
 +
แทนค่า <math>P(i) = i^2</math> จะได้ <math>P(i+1) = i^2 + 2i + 1 = (i+1)^2</math>
 +
 
 +
แสดงว่า <math>P(i+1)</math> ที่ <math>1+3+5+9+...+(2(i+1)-1) = (i+1)^2</math> เป็นจริง
 +
 
 +
เพราะฉะนั้นพิสูจน์ ได้ว่า สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math>" เป็นจริง โดยใช้วิธีพิสูจน์แบบ induction
 +
 
 +
[[Image:Tree.png]]
 +
 
 +
====ตัวอย่างปัญหาที่ 4====
 +
 
 +
ปัญหาการระบายสี Planar Graph ให้แต่ละเมืองแทนด้วยโหนด และเมืองที่มีอาณาเขตติดกันให้ลากเส้นเชื่อมติดต่อกัน
 +
* ทฤษฎีบท 4 สี - สามารถระบายสีโดยใช้สีไม่เกิน 4 สีบน Planar Graph
 +
* ทฤษฎีบท 5 สี - สามารถระบายสีโดยใช้สีไม่เกิน 5 สีบน Planar Graph
 +
 
 +
=====การพิสูจน์ทฤษฎีบท 5 สี=====
 +
 
 +
กำหนดให้
 +
 
 +
* n แทนจำนวนโหนดในกราฟ
 +
* m แทนจำนวนเส้นเชื่อมในกราฟ
 +
* f แทนจำนวนหน้า (face)
 +
* degree(v) แทนดีกรีของโหนด v (ดีกรีของโหนด = จำนวนเส้นเชื่อมที่เชื่อมกับโหนดอื่นๆ ไม่นับเส้นเชื่อมวกกลับเข้าหาตัวเอง)
 +
 
 +
จากความจริงที่ว่า E(v &isin; G) degree(v) = 2*m (ค่ารวมของค่าดีกรีของทุกโหนด จะเป็นสองเท่าของจำนวนเส้นเชื่อมทั้งหมดในกราฟ)
 +
 
 +
* Assume: n-m+f = 2
 +
* ลองให้ f = 3; <math>3 * f <= 2m</math>, <math>f <= \tfrac{2*m}{3}</math>, <math>n - m - 2 <= 2*m</math>

รุ่นแก้ไขปัจจุบันเมื่อ 01:03, 21 มีนาคม 2555

บันทึกคำบรรยายวิชา 204512-53 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย) Algorithm Lecture #1

Course Information

รายละเอียดวิชาสามารถดูได้ที่ http://www.cpe.ku.ac.th/~jtf/wiki/doku.php?id=01204512-53

เกณฑ์การให้คะแนน

  • Homework 15%
  • Project 15%
  • Scribe Note 5%
  • Mid-Term 2 Times 20*2%
  • Final 25%

Introduction to Algorithm

ทำไมเราต้องวิเคราะห์อัลกอริทึม

  • เพื่อความถูกต้องของอัลกอริทึม - ต้องการความแน่ใจ
  • เพื่อประสิทธิภาพของอัลกอริทึม
    • เวลา (time)
    • พื้นที่ (space)
    • คุณภาพคำตอบ (quality)

เนื้อหาแต่ละบทที่จะสอน ตามลำดับ

  1. Data Structure
  2. Graph Algorithm
  3. Dynamic Programming
  4. Linear Programming
  5. Randomize Algorithm

Data Structure

ตัวอย่างปัญหาที่ 1

การจองอาเรย์ให้เหมาะสมกับขนาดข้อมูลที่บรรจุ โดยกำหนดให้มีขั้นตอน การทำงานดังนี้

  1. จองพื้นที่สำหรับใส่ของ
  2. นำของไปใส่จนเต็ม
  3. จองพื้นที่เพิ่มสำหรับใส่ของ
กรณี 1: จองแบบเพิ่มทีละ 1 ที่

204512-53-01-malloc-table-1.png

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า

  • การจองใช้เวลา 1 หน่วย
  • การคัดลอกต้องคัดลอก i - 1 ตัวดังนั้นใช้เวลา i - 1 หน่วย
  • การนำข้อมูลใหม่ไปใส่ใช้เวลาอีก 1 หน่วย

จะเห็นได้ว่าในการสร้างอาเรย์เก็บข้อมูล n ตัวจะต้องใช้เวลาทั้งหมด

=  หน่วย
=  หน่วย
=  หน่วย

ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้ หน่วย หรือ O()

กรณี 2: จองแบบเพิ่มทีละ 3 ที่

204512-53-01-malloc-table-2.png

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่าจะยังได้ผลลัพธ์ไม่ต่างจากเดิมมาก คือ O() โดย n ในที่นี้เทียบได้กับ ของตัวอย่างบน มาจาก ซึ่งมี factor 3 เพิ่มเข้ามา

กรณี 3: จองแบบเพิ่มทีละ ที่

ต่อมามีคนเสนอว่าถ้าลองจองเป็นแบบ โดยที่ k หมายถึงการจองครั้งที่ k และค่า k เริ่มต้นจาก 0 เพื่อเป็นการตัดปัญหา ว่ากรณ๊ถ้าจองไม่เต็มจะทำอย่างไร เราจึงสมมุติไปเลยว่าการจองที่ n นั้นจะต้องจอง โดย k นั้นคือเลขจำนวนเต็มใดๆที่มากกว่า 0 ซึ่งถ้า อาจหมายถึงการแถมเวลาให้เต็ม เลยก็ได้

204512-53-01-malloc-table-3.png

จากภาพการเก็บ สามารถวิเคราะห์ได้ว่า

  • จะได้ว่ามีการจองข้อมูลเกิดขึ้นทั้งหมด k ครั้ง
  • มีการเขียนข้อมูล ครั้ง
  • มีการคัดลอกข้อมูล (มองง่ายๆให้มองเป็นการบวกเลข binary)

ดังนั้นจะได้ k

ตัวอย่างปัญหาที่ 2

ในแต่ละ Network (เครือข่าย) ประกอบไปด้วยส่วนหลักๆ คือ Router, Client และ Routing table เราต้องการเรียนรู้การเชื่อมต่อของ Router แต่ละตัวเพื่อบันทึกใน Routing table การคิดวิธีการเพื่อแก้ปัญหา เราจะต้อง Assume (สมมติ) อย่างน้อยว่าการทำงานของระบบจะสำเร็จในสักวัน, ระบบมีความก้าวหน้า, ก้าวหน้ามากพอที่จะสำเร็จในช่วงเวลาที่รับได้ และสมมติฐานในปัจจัยอื่นๆ

การ ออกแบบ Routing table แบบ RIP

  • Assume ว่า Router ทุกตัวทำการ Broadcast (กระจายสัญญาณไปหาทุกตัว) พร้อมกัน และ Router ทุกตัวรู้จักตัวเอง ในที่นี้ให้ค่าระยะของเส้นเชื่อม (edge) เท่ากับ 1 หน่วย
  • RIP เป็นการหาเส้นเชื่อมระหว่าง Router เพื่อให้สื่อสารถึงกันได้ทั้งหมด โดยมีค่าระยะทางน้อยที่สุด
  • ในการคิดครั้งนี้จะคิดโดยใช้ Router A เป็นโหนดตั้งต้น แล้วค้นหา Router ตัวอื่นที่อยู่รอบๆ

กำหนดให้

  • Set ของโหนด ทั้งหมด แทนด้วย V จะได้ว่า V = {A, B, C, ..., H}
  • Set ของเส้นเชื่อม ทั้งหมด แทนด้วย E จะได้ว่า E = {(A,D), (A,B), (A,E), ..., (F,H)}
  • Set ของโหนด ที่อยู่ในชั้น n (ติดต่อกับ A ด้วยระยะทาง n หน่วย) แทนด้วย Ln

จะได้ว่า

L0 = {A}, L1 = {v e V-L0 | มี node u ที่ u e L0 และ (u,v) e E}

ดังนั้นสำหรับค่า i ใดๆ ที่ i > 0, Li = {v e V - (ตั้งแต่ L0 จน Li - 1) | มี node u ที่ u e Li - 1 และ (u,v) e E} โดย กำหนดให้ L0={A}

ตัวอย่างปัญหาที่ 3

สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ "

การพิสูจน์โดยใช้วิธี Induction นั้นแบ่งเป็น 2 ส่วนคือ

  1. Basic step (Base case) ซึ่งเป็นจุดกำหนิดของตัวแรกของการคิด ส่วนใหญ่คือค่า 0 หรือ 1 โดยส่วนมากมักจะมีค่าจริงอยู่แล้ว
  2. Inductive step โดยจะสมมติให้ P(i) มีค่าเป็นจริง แล้วต้องพิสูจน์ให้ได้ว่า P(i + 1) นั้นมีค่าเป็นจริง

วิธีการแก้ปัญหาในตัวอย่างนี้

Basic Step

มีค่าเป็นจริง

Inductive Step

ถ้าให้ P(i) ที่ เป็นจริงแล้ว ต้องพิสูจน์ว่า ที่ เป็นจริง

แทนค่า จะได้

แสดงว่า ที่ เป็นจริง

เพราะฉะนั้นพิสูจน์ ได้ว่า สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ " เป็นจริง โดยใช้วิธีพิสูจน์แบบ induction

Tree.png

ตัวอย่างปัญหาที่ 4

ปัญหาการระบายสี Planar Graph ให้แต่ละเมืองแทนด้วยโหนด และเมืองที่มีอาณาเขตติดกันให้ลากเส้นเชื่อมติดต่อกัน

  • ทฤษฎีบท 4 สี - สามารถระบายสีโดยใช้สีไม่เกิน 4 สีบน Planar Graph
  • ทฤษฎีบท 5 สี - สามารถระบายสีโดยใช้สีไม่เกิน 5 สีบน Planar Graph
การพิสูจน์ทฤษฎีบท 5 สี

กำหนดให้

  • n แทนจำนวนโหนดในกราฟ
  • m แทนจำนวนเส้นเชื่อมในกราฟ
  • f แทนจำนวนหน้า (face)
  • degree(v) แทนดีกรีของโหนด v (ดีกรีของโหนด = จำนวนเส้นเชื่อมที่เชื่อมกับโหนดอื่นๆ ไม่นับเส้นเชื่อมวกกลับเข้าหาตัวเอง)

จากความจริงที่ว่า E(v ∈ G) degree(v) = 2*m (ค่ารวมของค่าดีกรีของทุกโหนด จะเป็นสองเท่าของจำนวนเส้นเชื่อมทั้งหมดในกราฟ)

  • Assume: n-m+f = 2
  • ลองให้ f = 3; , ,