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

58.136.1.145: /* Polynomial Multiplication */

2010-08-12T14:48:03Z

Polynomial Multiplication

58.136.1.145: /* Review Quick Sort */

2010-08-12T14:40:20Z

Review Quick Sort

58.136.1.145: /* Review Merge Sort */

2010-08-12T14:34:12Z

Review Merge Sort

58.136.1.145: /* Red-Black Tree (Cont.) */

2010-08-12T14:27:24Z

Red-Black Tree (Cont.)

58.136.1.145: /* Red-Black Tree (Cont.) */

2010-08-12T14:26:15Z

Red-Black Tree (Cont.)

Meenkaza เมื่อ 13:47, 12 สิงหาคม 2553

2010-08-12T13:47:54Z

Meenkaza เมื่อ 13:36, 12 สิงหาคม 2553

2010-08-12T13:36:57Z

Meenkaza เมื่อ 13:17, 12 สิงหาคม 2553

2010-08-12T13:17:40Z

Meenkaza เมื่อ 11:43, 12 สิงหาคม 2553

2010-08-12T11:43:29Z

Meenkaza เมื่อ 11:06, 12 สิงหาคม 2553

2010-08-12T11:06:23Z

@@ แถว 178: / แถว 178: @@
   ดังนั้น T(n) = 4T(n/2) + Cn
-จะอธิบายโดยรูปได้ว่า
+จะอธิบายโดยรูปได้ว่า หากเราทำการแบ่งข้อมูลในแต่ละครั้งออกเป็น 4 ส่วน จะได้ออกมาดังรูป
   [[ไฟล์:Polynomial_Multiplication_cr1.jpg]]
-แต่ปัญหาของการใช้ Divide and Conqure ก็คือ ถึงแม้แต่ละชั้นจะใช้ O(n) ก็ตาม แต่ชั้นสุดท้ายมีลูกมากเกินไป จึงได้ค่าออกมาเป็น O(n^2) = 2^(log n) Cn
+แต่ปัญหาของการใช้ Divide and Conqure ก็คือ ถึงแม้แต่ละชั้นจะใช้เวลา O(n) ก็ตาม แต่ชั้นสุดท้ายมีลูกมากเกินไป จึงได้ค่าออกมาเป็น O(n^2) = 2^(log n) Cn
   [[ไฟล์:Polynomial_Multiplication_cr2.jpg]]
-ดังนั้น จะได้ O(n log n)
+ดังนั้น จากรูปข้างบน หากเราแบ่งแต่ละชั้นออกเป็น 2 ส่วน จะได้เวลาเท่ากับ O(n log n)
   [[ไฟล์:Polynomial_Multiplication_cr3.jpg]]
-ดังนั้น จะได้ O(n)
+และถ้าเราอยากให้เร็วขึ้นอีก เราก็จะให้แต่ละชั้นมีเพียงส่วนเดียว เราก็จะได้เวลาเท่ากับ O(n)

@@ แถว 89: / แถว 89: @@
 ==Review Quick Sort==
+จากรูปเป็นตัวอย่างของข้อมูลที่จะทำการ Quick Sort โดยเริ่มต้น เราหาตัว pivot ก่อน
    [[ไฟล์:Quick_sort_cr1.jpg]]
-เมื่อแยกตัว pivotแล้ว จะได้
+เมื่อเราได้ตัว pivot แล้ว ก็แยกตัว pivot ออกมา เราจะได้ ข้อมูลเป็น 2 ส่วน คือ ข้อมูลที่อยู่ฝั่งซ้ายและฝั่งขวา
    [[ไฟล์:Quick_sort_cr2.jpg]]
-เมื่อทำการ Quick Sort แล้ว จะได้
+แล้วเมื่อทำการ Quick Sort ในแต่ละฝั่ง จะได้ ข้อมูลที่เรียงแล้วในฝั่งของตนเอง
    [[ไฟล์:Quick_sort_cr3.jpg]]
-ต่างจาก Merge Sort ตรงที่ Merge Sort จะเริ่มจากจุดกึ่งกลาง แต่ Quick Sort จะต้องเริ่มหาตัว pivot ก่อน
+ซึ่ง Quick Sort จะต่างจาก Merge Sort ตรงที่ Merge Sort จะเริ่มจากจุดกึ่งกลาง แต่ Quick Sort จะต้องเริ่มหาตัว pivot ก่อน
    [[ไฟล์:Quick_sort_cr4.jpg]]

@@ แถว 29: / แถว 29: @@
 == Review Merge Sort ==
-#จิ้มไปที่กิ่งกลางจะได้ array 2 ส่วน คือ Array Aขนาด n และ Array B ขนาด m
+#จิ้มไปที่กึ่งกลางจะได้ array 2 ส่วน คือ Array A ขนาด n และ Array B ขนาด m
 #ซึ่ง array แต่ละส่วนจะทำการ Sort ใน Array ของตัวเอง เรียกว่า Merge Sort
 #หลังจากนั้นทำการ เปรียบค่าแต่ละค่า ในแต่ละ Index ระหว่าง array ได้ค่าไหนที่น้อยกว่าก็ทำการ Add เข้าไปใน array ใหม่ ชื่อว่า C และทำไปเรื่อยๆ จนครบ เรียกว่า การ Merge
@@ แถว 63: / แถว 63: @@
 [[ไฟล์:Loop_invariant_cr2.png]]
-จะได้ว่า Z เป็นค่าใหญ่ที่สุดใน array Aที่ตำแหน่ง i แต่ปัญหาอยู่ที่จะทำอย่างไรให้เห็นว่า Z มีค่ามากที่สุดใน array B ในตำแหน่ง j
+จะได้ว่า Z เป็นค่าใหญ่ที่สุดใน array A ที่ตำแหน่ง i แต่ปัญหาอยู่ที่ จะทำอย่างไรให้เห็นว่า Z มีค่ามากที่สุดใน array B ในตำแหน่ง j
 [[ไฟล์:Loop_invariant_cr3.png]]
@@ แถว 74: / แถว 74: @@
 ===Merge Sort Algorithm===
-    Merge Sort(A) ให้  n = ขนาดของ A                      <math>\Rightarrow</math> ใช้เวลา T(n)
+    Merge Sort(A) ให้  n = ขนาดของ A                                                 <math>\Rightarrow</math> ใช้เวลา T(n)
     A(left) <math>\Leftarrow</math> A[1…(n/2)]          	                         <math>\Rightarrow</math> ใช้เวลา O(n)
     A(right) <math>\Leftarrow</math> A[(n+1)/2 …n] 			         <math>\Rightarrow</math> ใช้เวลา O(n)

@@ แถว 10: / แถว 10: @@
 *Tree ใดๆ จะเป็น Red-Black Tree ได้ต้องมีคุณสมบัติ 5 ข้อ ได้แก่
-#โหนดใดๆ เป็นได้เพียง 2 สี คือ แดง หรือ ดำ
+#โหนดแต่ละโหนด เป็นได้เพียงสีใดสีหนึ่งเท่านั้น ระหว่าง สีแดง หรือ สีดำ
 #Root ต้องเป็นสีดำ
 #Leaf ปลายสุดทั้งหมดต้องเป็นสีดำ

@@ แถว 10: / แถว 10: @@
 *Tree ใดๆ จะเป็น Red-Black Tree ได้ต้องมีคุณสมบัติ 5 ข้อ ได้แก่
-#โหนดเป็นได้ 2 สี คือ แดง กับ ดำ
+#โหนดใดๆ เป็นได้เพียง 2 สี คือ แดง หรือ ดำ
 #Root ต้องเป็นสีดำ
-#Leaf ทั้งหมดต้องเป็นสีดำ
+#Leaf ปลายสุดทั้งหมดต้องเป็นสีดำ
-#โหนดสีแดงมีโหนดลูกเป็นสีดำ ทั้ง 2 โหนด
+#โหนดที่มีสีแดง จะต้องมีโหนดลูกเป็นสีดำ ทั้ง 2 โหนด
 #จากโหนดใดๆ ไปหา Leaf ที่เป็นลูกหลานของตัวเอง จะต้องมีจำนวนโหนดสีดำเท่ากันหมด

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:47, 12 สิงหาคม 2553
แถว 1:		แถว 1:
		+	{{หัวคำบรรยาย\|204512-53}}
		+	'''จดบันทึกคำบรรยายโดย:'''
		+	:<table border='0'>
		+	<tr><td>นายดลวัฒน์ งามภักดิ์</td><td>5314550075</td></tr>
		+	<tr><td>นายณรงค์ศักดิ์ ทิพย์จ้อย</td><td>5314552230</td></tr>
		+	<tr><td>นายปริตร หมึ่นคง</td><td>5314552248</td></tr>
		+	</table>
		+
	=Red-Black Tree (Cont.)=		=Red-Black Tree (Cont.)=

@@ แถว 99: / แถว 99: @@
 การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median
-===SELECTION===
+===Selection===
   ให้ข้อมูล x1, x2, x3, … , xn และจำนวนเต็ม k ให้หาข้อมูลตัวที่น้อยที่สุด เป็นอันดับที่ k
@@ แถว 157: / แถว 157: @@
 =Polynomial Multiplication=

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:17, 12 สิงหาคม 2553
แถว 98:		แถว 98:
	จะใช้เวลา T(n) = O(n) + T(k) + T(n-k-1) โดยที่ในกรณีที่แย่ที่สุดนั้น จะได้ T(n) = O(n) + T(n-1)		จะใช้เวลา T(n) = O(n) + T(k) + T(n-k-1) โดยที่ในกรณีที่แย่ที่สุดนั้น จะได้ T(n) = O(n) + T(n-1)
	การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median		การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median
		+
		+	===SELECTION===
		+
		+	ให้ข้อมูล x1, x2, x3, … , xn และจำนวนเต็ม k ให้หาข้อมูลตัวที่น้อยที่สุด เป็นอันดับที่ k
		+	ได้เวลา O(n log n) โดยใช้การ Merge Sort และหยิบตัวที่ k ซึ่งหากต้องการทำให้ได้ O(n) จะใช้การ Quick Selection
		+
		+	การ Quick Selection
		+
		+	ใช้เวลาเลือกตัว Pivot = O(x) [[ไฟล์:Quick_selection_cr1.jpg]]
		+
		+	ใช้เวลาตรวจสอบว่าอยู่ฝั่งซ้ายหรือขวา = O(n) [[ไฟล์:Quick_selection_cr2.jpg]]
		+
		+	จะได้ว่า T(n) = O(x) + O(n) + T(n/2) เมื่อ T(n/2) เป็นเวลาที่ใช้ในการ recursive ฝั่งใดฝั่งหนึ่ง
		+
		+	ดังนั้น เมื่อ T(1) = 1
		+	T(n) = Cn + ((Cn/2) + T(n/4))
		+	= Cn + (Cn/2) + (Cn/4) + T(n/8)
		+	<= Cn[1+(1/2)+(1/4)+(1/8)+…]
		+
		+	ซึ่ง [1+(1/2)+(1/4)+(1/8)+…] มีค่าได้ไม่เกิน 2
		+	ดังนั้น <= 2Cn = O(n)
		+
		+	จากตัวอย่างนี้ โชคดีตรงที่ว่า ได้ค่าตรงกลางพอดี แต่ถ้าหากแบ่งได้ 1/10 แล้ว จะได้ใหม่ว่า
		+	T(1) = 1
		+	T(n) = Cn + T(9n/10)
		+	= Cn + (Cn(9/10) + T(n(9/10)^2))
		+	= Cn + Cn(9/10) + Cn(9/10)^2 + T(n(9/10)^3)
		+	<= 2Cn = O(n)
		+
		+
		+	===Finding medians in linear time===
		+
		+	เป็นอีกอัลกอริทึมหนึ่งสำหรับหาค่ากลางเหมือนกัน
		+
		+	*ในแต่ละแถว Sort ใช้เวลา C1
		+	เนื่องจากมี n/5 แถว จึงใช้เวลา ((C1n)/5)
		+	*หลัง Sort แล้วเอาข้อมูลตรงแถวกลางมาเป็นค่า Median
		+	[[ไฟล์:Finding_median_in_linear_time_cr.jpg]]
		+
		+	====algorithm====
		+
		+	[[ไฟล์:Select_cr1.jpg]]
		+
		+	ดังนั้น ใช้เวลาทั้งหมด T(n) = Cn + T(n/5) + T(max(l, n-l))
		+
		+	จาก [[ไฟล์:Select_cr2.jpg]]
		+
		+	ค่า Medium ที่เราได้ จะมากกว่าสมาชิกในช่องที่ 1 จำนวณ n/4 ตัว และจะน้อยกว่าช่อง 2 จำนวน n/4 ตัว
		+	ดังนั้น T(n) <= Cn + T(n/5) + T(3n/4)
		+
		+	==Conclusion==
		+	Base Case: T(1) = 1
		+	Merge Sort: T(n) = Cn + 2T(n/2)
		+	Quick Sort: T(n) = Cn + T(1) + T(n-1)
		+	<= Cn + T(n-1)
		+	Selection: T(n) <= Cn + T(n/5) + T(3n/4)
		+	Binary Search: T(n) = 1+ T(n/2)
		+
		+	=Polynomial Multiplication=

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:43, 12 สิงหาคม 2553
แถว 61:		แถว 61:
	จากรูปข้างบนแสดงให้เห็นว่า เงื่อนไขใน Loop Invariants ยังไม่แข็งแกร่งพอ โดยจะเพิ่มเงื่อนไขใหม่ได้เป็น		จากรูปข้างบนแสดงให้เห็นว่า เงื่อนไขใน Loop Invariants ยังไม่แข็งแกร่งพอ โดยจะเพิ่มเงื่อนไขใหม่ได้เป็น
	จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ (เพิ่ม และข้อมูลทุกตัวใน C[1…k] น้อยกว่าหรือเท่ากับ A[i] และ B[j]		จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ (เพิ่ม และข้อมูลทุกตัวใน C[1…k] น้อยกว่าหรือเท่ากับ A[i] และ B[j]
		+
		+	'''Trick''' หากเงื่อนไขของ Loop Invariants แรกยังไม่แข็งแกร่งพอ ก็ให้หาเงื่อนไขเพิ่มเติมที่รัดกุมกว่าเดิมใส่เข้าไปจนกว่าจะพิสูจน์ได้
		+	ทำให้ได้ว่าอัลกอริทึมนี้ จะได้ Big O = O(m+n) ซึ่งวนลูปทั้งหมด m+n รอบ ซึ่งหลักๆแล้วเราจะดูที่เวลาการทำงานมากกว่า
		+
		+	===Merge Sort Algorithm===
		+	Merge Sort(A) ให้ n = ขนาดของ A <math>\Rightarrow</math> ใช้เวลา T(n)
		+	A(left) <math>\Leftarrow</math> A[1…(n/2)] <math>\Rightarrow</math> ใช้เวลา O(n)
		+	A(right) <math>\Leftarrow</math> A[(n+1)/2 …n] <math>\Rightarrow</math> ใช้เวลา O(n)
		+
		+	Assume ว่า n เป็นกำลังของ 2
		+
		+	S(left) <math>\Leftarrow</math> Merge Sort(A(left)) <math>\Rightarrow</math> ใช้เวลา T(n/2)
		+	S(right) <math>\Leftarrow</math> Merge Sort(A(right)) <math>\Rightarrow</math> ใช้เวลา T(n/2)
		+	S <math>\Leftarrow</math> Merge Sort(S(left), S(right)) <math>\Rightarrow</math> ใช้เวลา O(n)
		+	Return S
		+
		+	ให้ T(n) เป็นเวลาการทำงานที่แย่ที่สุด เมื่อ input ขนาด n โดยที่ O(n)+O(n) = O(n) ดังนั้น จะได้ T(n) = 2T(n/2) + O(n)
		+	ปัญหาอยู่ที่อัลกอริทึมนี้ยังผิดอยู่ เพราะเนื่องจากยังไม่มี Base Case จึงไม่รู้ว่าจะต้องเริ่มทำ Loop เมื่อไร โดยในที่นี้ จะให้ Base Case เป็น T(1) = O(1) และให้ T(n) เป็น recurrence แต่เนื่องจาก O(n)+O(n)=O(n) นั้น ค่าคงที่บางส่วนจะหายไป ดังนั้นจึงเปลี่ยน T(n) ใหม่เป็น T(n) <= 2T(n/2) +Cn
		+
		+	==Review Quick Sort==
		+
		+	[[ไฟล์:Quick_sort_cr1.jpg]]
		+
		+	เมื่อแยกตัว pivotแล้ว จะได้
		+
		+	[[ไฟล์:Quick_sort_cr2.jpg]]
		+
		+	เมื่อทำการ Quick Sort แล้ว จะได้
		+
		+	[[ไฟล์:Quick_sort_cr3.jpg]]
		+
		+	ต่างจาก Merge Sort ตรงที่ Merge Sort จะเริ่มจากจุดกึ่งกลาง แต่ Quick Sort จะต้องเริ่มหาตัว pivot ก่อน
		+
		+	[[ไฟล์:Quick_sort_cr4.jpg]]
		+
		+	จะใช้เวลา T(n) = O(n) + T(k) + T(n-k-1) โดยที่ในกรณีที่แย่ที่สุดนั้น จะได้ T(n) = O(n) + T(n-1)
		+	การหาค่า pivot จะง่าย ก็ต่อเมื่อตัว pivot อยู่ตรงกลาง ซึ่งเราจะใช้วิธี Selection หาค่า Median

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:06, 12 สิงหาคม 2553
แถว 44:		แถว 44:
	*ถ้า array B เรียงจากน้อยไปหามาก แล้ว		*ถ้า array B เรียงจากน้อยไปหามาก แล้ว
	*Array C จะเป็น array ที่มาจาก array A และ array B ที่เรียงจากน้อยไปหามาก		*Array C จะเป็น array ที่มาจาก array A และ array B ที่เรียงจากน้อยไปหามาก
		+
		+	====Loop Invariants====
		+	จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ
		+
		+	[[ไฟล์:Loop_invariant_cr1.png]]
		+
		+	จะพิสูจน์ว่า array ชุดใหม่ มาจาก
		+
		+
		+	[[ไฟล์:Loop_invariant_cr2.png]]
		+
		+	จะได้ว่า Z เป็นค่าใหญ่ที่สุดใน array Aที่ตำแหน่ง i แต่ปัญหาอยู่ที่จะทำอย่างไรให้เห็นว่า Z มีค่ามากที่สุดใน array B ในตำแหน่ง j
		+
		+	[[ไฟล์:Loop_invariant_cr3.png]]
		+
		+	จากรูปข้างบนแสดงให้เห็นว่า เงื่อนไขใน Loop Invariants ยังไม่แข็งแกร่งพอ โดยจะเพิ่มเงื่อนไขใหม่ได้เป็น
		+	จาก C[1…k] มีข้อมูลของ A[1…i+1] และ B[1…j-1] และเรียงลำดับ (เพิ่ม และข้อมูลทุกตัวใน C[1…k] น้อยกว่าหรือเท่ากับ A[i] และ B[j]