204512-53/lecture1 - ประวัติรุ่นแก้ไข

Jittat: /* Inductive Step */

2012-03-21T01:03:01Z

Inductive Step

203.113.85.18: /* ตัวอย่างปัญหาที่ 3 */

2010-07-22T02:28:33Z

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

203.113.85.18: /* Basc Step */

2010-07-19T08:10:56Z

Basc Step

Rtsp เมื่อ 13:30, 1 กรกฎาคม 2553

2010-07-01T13:30:43Z

Rtsp: /* ตัวอย่างปัญหาที่ 2 */

2010-07-01T13:28:59Z

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

Rtsp: /* Data Structure */

2010-07-01T12:36:47Z

Data Structure

Rtsp: /* ตัวอย่างปัญหาที่ 1 */

2010-07-01T12:33:11Z

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

Rtsp เมื่อ 12:08, 1 กรกฎาคม 2553

2010-07-01T12:08:11Z

Rtsp: /* ตัวอย่างปัญหาที่ 1 */

2010-07-01T12:07:46Z

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

Rtsp เมื่อ 10:16, 1 กรกฎาคม 2553

2010-07-01T10:16:45Z

@@ แถว 115: / แถว 115: @@
 =====Inductive Step=====
-ถ้าให้ P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math> เป็นจริงแล้ว ต้องพิสูจน์ว่า <math>P(i+1) ที่ 1+3+5+9+...+(2(i+1)-1) = (i+1)^2</math> เป็นจริง
+ถ้าให้ 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>
@@ แถว 121: / แถว 121: @@
 แทนค่า <math>P(i) = i^2</math> จะได้ <math>P(i+1) = i^2 + 2i + 1 = (i+1)^2</math>
-แสดงว่า <math>P(i+1) ที่ 1+3+5+9+...+(2(i+1)-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

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

@@ แถว 109: / แถว 109: @@
 วิธีการแก้ปัญหาในตัวอย่างนี้
-=====Basis Step=====
+=====Basic Step=====
 <math>P(1) = 1 =1^2</math> มีค่าเป็นจริง

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:30, 1 กรกฎาคม 2553
แถว 124:		แถว 124:

	เพราะฉะนั้นพิสูจน์ ได้ว่า สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math>" เป็นจริง โดยใช้วิธีพิสูจน์แบบ induction		เพราะฉะนั้นพิสูจน์ ได้ว่า สำหรับลำดับจำนวนเต็ม i ใดๆ "P(i) ที่ <math>1+3+5+9+...+(2i-1) = i^2</math>" เป็นจริง โดยใช้วิธีพิสูจน์แบบ induction
		+
		+	[[Image:Tree.png]]

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:28, 1 กรกฎาคม 2553
แถว 77:		แถว 77:

	====ตัวอย่างปัญหาที่ 2====		====ตัวอย่างปัญหาที่ 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 ส่วนคือ
		+
		+	# Basis step (Base case) ซึ่งเป็นจุดกำหนิดของตัวแรกของการคิด ส่วนใหญ่คือค่า 0 หรือ 1 โดยส่วนมากมักจะมีค่าจริงอยู่แล้ว
		+	# Inductive step โดยจะสมมติให้ P(i) มีค่าเป็นจริง แล้วต้องพิสูจน์ให้ได้ว่า P(i + 1) นั้นมีค่าเป็นจริง
		+
		+	วิธีการแก้ปัญหาในตัวอย่างนี้
		+
		+	=====Basis 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) ที่ 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) ที่ 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
		+
		+	====ตัวอย่างปัญหาที่ 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; <math>3 * f <= 2m</math>, <math>f <= \tfrac{2m}{3}</math>, <math>n - m - 2 <= 2m</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:36, 1 กรกฎาคม 2553
แถว 76:		แถว 76:
	ดังนั้นจะได้ k<math> + 2^{k} + 2^{k} -1 = O(n)</math>		ดังนั้นจะได้ k<math> + 2^{k} + 2^{k} -1 = O(n)</math>

−		+	====ตัวอย่างปัญหาที่ 2====
−	~~[[Image:Tree.png]]~~

@@ แถว 39: / แถว 39: @@
 # นำของไปใส่จนเต็ม
 # จองพื้นที่เพิ่มสำหรับใส่ของ
-จากภาพการเก็บวิเคราะห์ได้ว่า การเก็บข้อมูลตัวที่ i
+=====กรณี 1: จองแบบเพิ่มทีละ 1 ที่=====
 * การจองใช้เวลา 1 หน่วย
 * การคัดลอกต้องคัดลอก i - 1 ตัวดังนั้นใช้เวลา i - 1 หน่วย
@@ แถว 53: / แถว 55: @@
   = <math>(1 + 2 + 3 + ... + n) + n</math> หน่วย
-ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้  <math>\tfrac{n*(n+1) + n}{2}</math> หน่วย
+ดังนั้นการถ้ามีข้อมูล n ตัวจะได้ว่าต้องใช้  <math>\frac{n*(n+1) + n}{2}</math> หน่วย หรือ O(<math>n^2</math>)
-[[ไฟล์:Tree.png]]
+[[Image:Tree.png]]

@@ แถว 3: / แถว 3: @@
 Algorithm Lecture #1
-==Course Information==
+=Course Information=
 รายละเอียดวิชาสามารถดูได้ที่ http://www.cpe.ku.ac.th/~jtf/wiki/doku.php?id=01204512-53
-===เกณฑ์การให้คะแนน===
+==เกณฑ์การให้คะแนน==
 * Homework    15%
 * Project         15%

@@ แถว 35: / แถว 35: @@
 ====ตัวอย่างปัญหาที่ 1====
 การจองอาเรย์ให้เหมาะสมกับขนาดข้อมูลที่บรรจุ โดยกำหนดให้มีขั้นตอน การทำงานดังนี้
 # จองพื้นที่สำหรับใส่ของ
 # นำของไปใส่จนเต็ม
@@ แถว 41: / แถว 42: @@
 จากภาพการเก็บวิเคราะห์ได้ว่า การเก็บข้อมูลตัวที่ i
 * การจองใช้เวลา 1 หน่วย
 * การคัดลอกต้องคัดลอก i - 1 ตัวดังนั้นใช้เวลา i - 1 หน่วย
 * การนำข้อมูลใหม่ไปใส่ใช้เวลาอีก 1 หน่วย
-จะเห็นได้ว่าในการสร้างอาเรย์เก็บข้อมูล n ตัวจะต้องใช้เวลาทั้งหมด 2+3+4+...+n+n+1 หน่วย
+จะเห็นได้ว่าในการสร้างอาเรย์เก็บข้อมูล n ตัวจะต้องใช้เวลาทั้งหมด
-เท่ากับ 2+3+4+...+n+n+1 = (1+2+3+..+n) +n
 [[ไฟล์:Tree.png]]

@@ แถว 4: / แถว 4: @@
 ==Course Information==
 * Homework    15%
 * Project         15%
@@ แถว 10: / แถว 12: @@
 * Mid-Term 2 Times 20*2%
 * Final            25%
 =Introduction to Algorithm=
@@ แถว 18: / แถว 18: @@
 * เพื่อความถูกต้องของอัลกอริทึม - ต้องการความแน่ใจ
-* เพื่อประสิทธิภาพของอัลกอริทึม - ทั้งด้าน เวลา (time), พื้นที่ (space), คุณภาพคำตอบ (quality)
+* เพื่อประสิทธิภาพของอัลกอริทึม
 ==เนื้อหาแต่ละบทที่จะสอน ตามลำดับ==
@@ แถว 36: / แถว 39: @@
 # จองพื้นที่เพิ่มสำหรับใส่ของ
 # ลองวิเคราะห์การจองที่ใส่ของเพิ่มที่ละ 1 ที่
 [[ไฟล์:Tree.png]]