418341 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ - ประวัติรุ่นแก้ไข

Cardcaptor: /* ข้อ 8 */

2009-09-04T14:32:18Z

ข้อ 8

Cardcaptor: /* ข้อ 6 */

2009-09-04T14:23:46Z

ข้อ 6

Cardcaptor: /* ข้อ 6 */

2009-09-04T14:19:07Z

ข้อ 6

Cardcaptor: /* ข้อ 6 */

2009-09-04T14:17:15Z

ข้อ 6

Aoy: /* ข้อ 8 */

2009-09-04T08:04:43Z

ข้อ 8

Cardcaptor: /* ข้อ 4 */

2009-09-02T13:43:06Z

ข้อ 4

Aoy: /* ข้อ 9 */

2009-09-02T07:11:31Z

ข้อ 9

Aoy: /* ข้อ 8 */

2009-09-02T07:11:21Z

ข้อ 8

Aoy: /* ข้อ 7 */

2009-09-02T07:11:08Z

ข้อ 7

Aoy: /* ข้อ 6 */

2009-09-02T07:10:57Z

ข้อ 6

@@ แถว 46: / แถว 46: @@
 == ข้อ 8 ==
-[Kleinberg & Tardos 5.2] กำหนดอะเรย์ <math>A[.]</math> ขนาด <math>n \,</math> ช่อง นิยาม<b>อินเวอร์ชันสำััคัญ</b>ว่าเป็นคู่ลำดับ <math>(i,j)\,</math> ที่ <math>i < j \,</math> และ <math>A[i] > 2A[j] \,</math>
+[Kleinberg & Tardos 5.2] กำหนดอะเรย์ <math>A[\cdot] \,</math> ขนาด <math>n \,</math> ช่อง นิยาม<b>อินเวอร์ชันสำััคัญ</b>ว่าเป็นคู่ลำดับ <math>(i,j)\,</math> ที่ <math>i < j \,</math> และ <math>A[i] > 2A[j] \,</math>
 จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>

@@ แถว 30: / แถว 30: @@
 == ข้อ 6 ==
 เลขฟิโนนักชีมีนิยามดังต่อไปนี้
-<math>f_n = \begin{cases}1 & n = 1 \\ 1 & n = 2 \\ f_{n-1} + f_{n-2} & n \geq 2 \end{cases} \,</math>
+<math>f_n = \begin{cases}0 & n = 0 \\ 1 & n = 1 \\ f_{n-1} + f_{n-2} & n \geq 2 \end{cases} \,</math>
-# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & 0  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
+# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1}  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
 # จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>

@@ แถว 31: / แถว 31: @@
 เลขฟิโนนักชีมีนิยามดังต่อไปนี้
 <math>f_n = \begin{cases}1 & n = 1 \\ 1 & n = 2 \\ f_{n-1} + f_{n-2} & n \geq 2 \end{cases} \,</math>
-# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_n & f_{n+1} \\ f_n & 0  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
+# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & 0  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
 # จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>

@@ แถว 31: / แถว 31: @@
 เลขฟิโนนักชีมีนิยามดังต่อไปนี้
 <math>f_n = \begin{cases}1 & n = 1 \\ 1 & n = 2 \\ f_{n-1} + f_{n-2} & n \geq 2 \end{cases} \,</math>
-# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} f_n & f_{n+1} \\ 0 & f_n \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
+# จงพิสูจน์ว่า <math>\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_n & f_{n+1} \\ f_n & 0  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
 # จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>

@@ แถว 46: / แถว 46: @@
 == ข้อ 8 ==
-[Kleinberg & Tardos 5.2] กำหนดอะเรย์ <math>A[.]</math> ขนาด <math>n \,</math> ช่อง นิยาม<b>อินเวอร์ชันสำััคัญ</b>ว่าจำเป็นคู่ลำดับ <math>(i,j)\,</math> ที่ <math>i < j \,</math> และ <math>A[i] > 2A[j] \,</math>
+[Kleinberg & Tardos 5.2] กำหนดอะเรย์ <math>A[.]</math> ขนาด <math>n \,</math> ช่อง นิยาม<b>อินเวอร์ชันสำััคัญ</b>ว่าเป็นคู่ลำดับ <math>(i,j)\,</math> ที่ <math>i < j \,</math> และ <math>A[i] > 2A[j] \,</math>
 จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>

@@ แถว 19: / แถว 19: @@
 == ข้อ 4 ==
-[Dasgupta, Papadimitriou, Vazirani 2.22] กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่เรียงแล้วขนาด <math>m \,</math> ช่อง และกำหนดอะเรย์ <math>B[\cdot] \,</math> ที่เรียงแล้วขนาด <math>n \,</math> ช่อง จงออกแบบอัลกอริทึีมเพื่อหาสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ของเซตของตัวเลขที่เกิดจากการนำเอาตัวเลขในอะเรย์ทั้งสองตัวมารวมกัน อัลกอริทึีมของคุณควรจะทำงานได้ในเวลา <math>O(\log n + \log m) \,</math>
+[Dasgupta, Papadimitriou, Vazirani 2.22] กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่เรียงแล้วขนาด <math>m \,</math> ช่อง และกำหนดอะเรย์ <math>B[\cdot] \,</math> ที่เรียงแล้วขนาด <math>n \,</math> ช่อง โดยที่ไม่มีจำนวนสองตัวใดๆ ในอะเรย์ทั้งสองตัวที่ซ้ำกัน จงออกแบบอัลกอริทึีมเพื่อหาสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ <math>k \,</math> ของเซตของตัวเลขที่เกิดจากการนำเอาตัวเลขในอะเรย์ทั้งสองตัวมารวมกัน อัลกอริทึีมของคุณควรจะทำงานได้ในเวลา <math>O(\log n + \log m) \,</math>
 [[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4|เฉลย]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:11, 2 กันยายน 2552
แถว 62:		แถว 62:

	สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น		สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น
		+
		+	[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9\|เฉลย]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:11, 2 กันยายน 2552
แถว 49:		แถว 49:

	จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>		จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 8\|เฉลย]]

	== ข้อ 9 ==		== ข้อ 9 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:11, 2 กันยายน 2552
แถว 42:		แถว 42:

	จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา <math>O(n \log n) \,</math>		จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา <math>O(n \log n) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7\|เฉลย]]

	== ข้อ 8 ==		== ข้อ 8 ==