418531 ภาคต้น 2552/โจทย์ปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก - ประวัติรุ่นแก้ไข

Aoy: /* ข้อ 10 */

2009-08-21T08:56:41Z

ข้อ 10

Aoy: /* ข้อ 10 */

2009-08-18T06:59:31Z

ข้อ 10

Aoy: /* ข้อ 9 */

2009-08-18T06:59:19Z

ข้อ 9

Aoy: /* ข้อ 8 */

2009-08-18T06:59:07Z

ข้อ 8

Aoy: /* ข้อ 7 */

2009-08-18T06:58:55Z

ข้อ 7

Aoy: /* ข้อ 6 */

2009-08-18T06:58:41Z

ข้อ 6

Aoy: /* ข้อ 5 */

2009-08-18T06:58:26Z

ข้อ 5

Aoy: /* ข้อ 4 */

2009-08-18T06:58:10Z

ข้อ 4

Aoy: /* ข้อ 3 */

2009-08-18T06:57:59Z

ข้อ 3

Aoy: /* ข้อ 2 */

2009-08-18T05:37:08Z

ข้อ 2

@@ แถว 133: / แถว 133: @@
 == ข้อ 10 ==
-[Traveling Salesman Problem] กำหนดจุดมาให้ <math>n \,</math> ในระนาบสองมิติ ให้จุด <math>n \,</math> จุดเหล่ามีสัญลักษณ์ <math>(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \,</math>
+[Traveling Salesman Problem] กำหนดจุดมาให้ <math>n \,</math> ในระนาบสองมิติ ให้จุด <math>n \,</math> จุดเหล่านี้มีสัญลักษณ์ <math>(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \,</math>
 คุณต้องการเดินทางโดยเริ่มจากจุด <math>(x_1, y_1) \,</math> แล้วไปผ่านจุดอื่นทุกจุด โดยคุณจะเดินเข้าหาจุดแต่ละจุดเพียงครั้งเดียว และออกจากจุดแต่ละจุดเพียงครั้งเดียวเท่านั้น แล้วให้ท้ายที่สุดคุณกลับไปอยู่ที่จุด <math>(x_1, y_1) \,</math> อีกครั้ง การเดินแบบนี้เรียกว่า Hamiltonian Cycle ยกตัวอย่างเช่นตามรูปข้างล่างนี้ (จุด <math>(x_1, y_1) \,</math> จะเป็นจุดใดก็ได้ในจุดหลายๆ จุดข้างล่างนี้)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:59, 18 สิงหาคม 2552
แถว 142:		แถว 142:

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:59, 18 สิงหาคม 2552
แถว 129:		แถว 129:

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

	== ข้อ 10 ==		== ข้อ 10 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:59, 18 สิงหาคม 2552
แถว 103:		แถว 103:

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:58, 18 สิงหาคม 2552
แถว 92:		แถว 92:

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

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

@@ แถว 79: / แถว 79: @@
 # จงออกแบบอัลกอริืึทึมดังกล่าว อัลกอริทึมของคุณควรทำงานด้วยเวลา <math>\Theta(N^3 M^3 K^2) \,</math>
 # จงออกแบบอัลกอริืึทึมดังกล่าว อัลกอริทึมของคุณควรทำงานด้วยเวลา <math>\Theta(N^3 M^3) \,</math>
 == ข้อ 7 ==

@@ แถว 50: / แถว 50: @@
 # จงออกแบบอัลกอริทึมที่แก้ปัญหาข้างต้นที่มีเวลาการทำงานเท่ากับ <math>\Theta(n^3) \,</math>
 # จงออกแบบอัลกอริทึมที่แก้ปัญหาข้างต้นที่มีเวลาการทำงานเท่ากับ <math>\Theta(n) \,</math>
 == ข้อ 6 ==

@@ แถว 38: / แถว 38: @@
 # จงออกแบบอัลกอริทึมที่ตอบคำถามดังกล่าวข้างต้นที่มีเวลาการทำงานเท่ากับ <math>\Theta(n^2) \,</math>
 # จงแสดงว่าถ้าสามารถตอบคำถามว่ามีจำนวนเต็ม <math>y \,</math> อยู่ในเซต <math>A \,</math> หรือไม่ ได้ในเวลา <math>O(f(n)) \,</math> แล้วเราสามารถแก้ปัญหานี้ในเวลา <math>O( n \cdot f(n) ) \,</math>
 == ข้อ 5 ==

@@ แถว 28: / แถว 28: @@
 # จงออกแบบอัลกอริทึมที่ตอบคำถามดังกล่าวข้างต้นที่มีเวลาการทำงานเท่ากับ <math>\Theta(n^3) \,</math>
 # จงแสดงว่าถ้าเราสามารถเรียงจำนวนที่อยู่ในเซต <math>A \,</math> ในเวลา <math>O(f(n)) \,</math> แล้วเราสามารถแก้ปัญหานี้ในเวลา <math>O(f(n) + n) \,</math>
 == ข้อ 4 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:37, 18 สิงหาคม 2552
แถว 20:		แถว 20:

	'''หมายเหตุ:''' มีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้ในเวลา <math>O(nk 2^k) \,</math>		'''หมายเหตุ:''' มีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้ในเวลา <math>O(nk 2^k) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 2\|เฉลย]]

	== ข้อ 3 ==		== ข้อ 3 ==