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

Aoy: /* ข้อ 5 */

2009-09-30T06:51:17Z

ข้อ 5

Cardcaptor: /* ข้อ 7 */

2009-09-18T15:13:06Z

ข้อ 7

Cardcaptor: /* ข้อ 6 */

2009-09-18T15:12:58Z

ข้อ 6

Cardcaptor: /* ข้อ 5 */

2009-09-18T15:12:50Z

ข้อ 5

Cardcaptor: /* ข้อ 4 */

2009-09-18T15:12:42Z

ข้อ 4

Cardcaptor: /* ข้อ 3 */

2009-09-18T15:12:33Z

ข้อ 3

Cardcaptor: /* ข้อ 2 */

2009-09-18T15:12:26Z

ข้อ 2

Cardcaptor: /* ข้อ 2 */

2009-09-18T15:12:12Z

ข้อ 2

Cardcaptor: /* ข้อ 1 */

2009-09-18T15:12:05Z

ข้อ 1

Cardcaptor: /* ข้อ 6 */

2009-09-18T15:09:47Z

ข้อ 6

@@ แถว 33: / แถว 33: @@
 == ข้อ 5 ==
-[Kleinberg & Tardos 4.10] ให้ <math>G = (V,E)\,</math> เป้นกราฟต่อเนื่องแบบไม่มีทิศทางที่ cost <math>c_e \geq 0 \,</math> สำหรับทุก edge <math>e \,</math> สมมติว่าคุณได้รับ minimum spanning tree <math>T \,</math> ของ <math>G \,</math> มาหนึ่งต้น
+[Kleinberg & Tardos 4.10] ให้ <math>G = (V,E)\,</math> เป็นกราฟต่อเนื่องแบบไม่มีทิศทางที่ cost <math>c_e \geq 0 \,</math> สำหรับทุก edge <math>e \,</math> สมมติว่าคุณได้รับ minimum spanning tree <math>T \,</math> ของ <math>G \,</math> มาหนึ่งต้น
 ต่อมาสมมติว่าเราเพิ่ม edge edge หนึ่งเข้าไปใน <math>G \,</math> โดย edge นี้ต่อ vertex <math>v \,</math> เข้ากับ vertex <math>w \,</math> และมี cost <math>c \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:13, 18 กันยายน 2552
แถว 49:		แถว 49:
	== ข้อ 7 ==		== ข้อ 7 ==
	[Dasgupta, Papadimitriou, Vazirani 4.3] กำหนดกราฟแบบไม่มีทิศทาง <math>G = (V,E) \,</math> มาให้ จงออกแบบอัลกอริทึมเพื่อหาว่าใน <math>G \,</math> มี'''สี่เหลี่ยม''' หรือไม่ เมื่อสี่เหลี่ยมคือ simple cycle ที่มีความยาวเท่ากับ 4 พอดี อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา <math>O(\|V\|^3) \,</math>		[Dasgupta, Papadimitriou, Vazirani 4.3] กำหนดกราฟแบบไม่มีทิศทาง <math>G = (V,E) \,</math> มาให้ จงออกแบบอัลกอริทึมเพื่อหาว่าใน <math>G \,</math> มี'''สี่เหลี่ยม''' หรือไม่ เมื่อสี่เหลี่ยมคือ simple cycle ที่มีความยาวเท่ากับ 4 พอดี อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา <math>O(\|V\|^3) \,</math>
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 7\|เฉลย]]

@@ แถว 44: / แถว 44: @@
 == ข้อ 6 ==
 [Dasgupta, Papadimitriou, Vazirani 4.12] กำหนดกราฟแบบไม่มีทิศทาง <math>G = (V,E) \,</math> ซึ่ง edge ทุก edge มีความยาวเป็นบวก และกำหนด edge <math>e \in E \,</math> ให้ จงออกแบบอัลกอริทึมเพื่อหา cycle ที่สั้นที่สุดใน <math>G \,</math> ที่มี edge <math>e \,</math> เป็นส่วนประกอบ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O((|V| + |E|) \log |V|) \,</math>
 == ข้อ 7 ==
 [Dasgupta, Papadimitriou, Vazirani 4.3] กำหนดกราฟแบบไม่มีทิศทาง <math>G = (V,E) \,</math> มาให้ จงออกแบบอัลกอริทึมเพื่อหาว่าใน <math>G \,</math> มี'''สี่เหลี่ยม''' หรือไม่ เมื่อสี่เหลี่ยมคือ simple cycle ที่มีความยาวเท่ากับ 4 พอดี อัลกอริึทึมของคุณควรจะทำงานได้ในเวลา <math>O(|V|^3) \,</math>

@@ แถว 39: / แถว 39: @@
 # จงออกแบบอัลกอริทึมที่ทดสอบว่าหลังจากเพิ่ม edge ดังกล่าวเข้าไปใน <math>G \,</math> แล้ว <math>T \,</math> ยังเป็น minimum spanning tree อยู่หรือไม่? อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(|E|) \,</math> คุณสามารถทำให้มันทำงานในเวลา <math>O(|V|) \,</math> ได้หรือไม่? เวลาตอบจงบอกว่าอัลกอริทึมของคุณแทนกราฟและ spanning tree ด้วยโครงสร้างข้อมูลแบบใดด้วย
 # สมมติว่าหลังจากเพิ่ม edge ดังกล่าวเข้าไปใน <math>G \,</math> แล้ว <math>T \,</math> ไม่เป็น minimum spanning tree จงออกแบบอัลกอริทึมที่ทำการปรับปรุง <math>T \,</math> ให้กลายเป็น minimum spanning tree ใหม่อีกครั้ง อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(|E|) \,</math>
 == ข้อ 6 ==

@@ แถว 29: / แถว 29: @@
 # ถ้า <math>T \,</math> minimum-bottleneck spanning tree ของ <math>G \,</math> แล้ว <math>T \,</math> เป็น minimum spanning tree ด้วยหรือไม่? จงพิสูจน์หรือไม่ก็ให้ตัวอย่างขัดแย้ง
 # ถ้า <math>T \,</math> minimum spanning tree ของ <math>G \,</math> แล้ว <math>T \,</math> เป็น minimum-bottleneck spanning tree ด้วยหรือไม่? จงพิสูจน์หรือไม่ก็ให้ตัวอย่างขัดแย้ง
 == ข้อ 5 ==

@@ แถว 17: / แถว 17: @@
 == ข้อ 3 ==
 [Kleinberg & Tardos 4.8] ให้ <math>G \,</math> เป็น connected graph ที่ไม่มี cost ของ edge สอง edge ใดๆ เท่ากันเลย จงแสดงว่า <math>G \,</math> มี minimum spanning tree เพียงแค่ต้นเดียวเท่านั้น (กล่าวคือ ไม่มี tree สองต้นที่แตกต่างกัน ที่มี cost รวมเท่ากับ cost ของ minimum spanning tree)
 == ข้อ 4 ==

@@ แถว 13: / แถว 13: @@
 #: จริงหรือไม่ ที่ <math>P \,</math> ยังเป็น shotest path จาก <math>s \,</math> ไปยัง <math>t \,</math> อยู่
-[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 1|เฉลย]]
+[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ II/เฉลยข้อ 2|เฉลย]]
 == ข้อ 3 ==

@@ แถว 2: / แถว 2: @@
 [Kleinberg & Tardos 4.1] จงตัดสินใจว่าข้อความต่อไปนี้เป็นความจริงหรือไม่ ถ้าเป็นจริงให้พิสูจน์็ ถ้าเป็นเท็จให้หาตัวอย่างขัดแย้ง
 : สมมติว่า <math>G \,</math> เป็น connected graph ที่มี edge <math>e \,</math> แต่ละ edge มี cost <math>c(e) \,</math> ถ้า edge <math>e^* \,</math> เป็น edge ที่มี cost ต่ำที่สุด ใน <math>G \,</math> (กล่าวคือ <math>c(e^*) < c(e) \,</math> สำหรับ edge <math>e \,</math> อื่นๆ ที่ <math>e \neq e^* \,</math>) แล้วจะมี minimum spanning tree <math>T  \,</math> ที่มี edge <math>e^* \,</math> เป็นส่วนประกอบ
 == ข้อ 2 ==