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

รุ่นแก้ไขปัจจุบันเมื่อ 14:32, 4 กันยายน 2552

เนื้อหา

1 ข้อ 1
2 ข้อ 2
3 ข้อ 3
4 ข้อ 4
5 ข้อ 5
6 ข้อ 6
7 ข้อ 7
8 ข้อ 8
9 ข้อ 9

ข้อ 1

[ดัีดแปลงจาก Dasgupta, Papadimitriou, Vazirani 2.16] คุณได้รับอะเรย์ $A[\cdot ]\,$ ซึ่งมีจำนวนช่องเท่ากับจำนวนของจำนวนเต็มทั้งหมด (สมาชิกของอะเรย์นี้คือ $A[1],A[2],A[3],\ldots \,$ ) อะเรย์นี้มีคุณสมบัติว่าสมาชิก $n\,$ ตัวแรกของมันจะมีค่าเท่ากับ 0 (กล่าวคือ $0=A[1]=A[1]=\dotsb =A[n]\,$ ) โดยที่ $n\,$ เป็นจำนวนเต็มหนึ่งตัว และสมาชิกที่เหลือมีค่าเท่ากับ 1 (กล่าวคือ $1=A[n+1]=A[n+2]=A[n+3]=\dotsb \,$ )

คุณไม่ทราบค่า $n\,$ จงหาอัลกอริทึมที่หาค่า $n\,$ ได้ในเวลา $O(\log n)\,$

เฉลย

ข้อ 2

[Dasgupta, Papadimitriou, Vazirani 2.17] กำหนดอะเรย์ $A[\cdot ]\,$ ที่มีขนาด $n\,$ ช่องที่เรียงจากน้อยไปหามาก นอกจากนี้เลขในอะเรย์ทุกตัวจะมีค่าไม่เท่ากัน คุณอยากจะทราบว่ามีจำนวนเต็ม $i\,$ ที่ทำให้ $A[i]=i\,$ หรือไม่ จงหาอัลกอริทึมที่สามารถหาค่า $i\,$ ดังกล่าวมาหนึ่งค่าหรือตอบว่าไม่มีค่า $i\,$ ดังกล่าวเลยได้ในเวลา $O(\log n)\,$

เฉลย

ข้อ 3

[Dasgupta, Papadimitriou, Vazirani 2.19] สมมติว่าคุณมีอะเรย์ที่เรียงแล้วอยู่ $k\,$ อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ $n\,$ ตัว คุณต้องการรวมอะเรย์ทั้งหมดเป็นอะเรย์ที่เรียงแล้วขนาด $kn\,$ ช่อง

นี่เป็นวิธีการหนึ่งที่คุณสามารถจะทำได้ ใช้อัลกอริทีม merge ที่เรียนไปในชั้นเรียนทำการรวมอะเรย์สองอะเรย์แรก เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สาม เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สี่ เช่นนี้ไปเรื่อยๆ วิธีการนี้มีเวลาการทำงานเป็นเท่าใดในรูปของ $n\,$ และ $k\,$ ?
จงออกอัลกอริทึมที่มีประสิทธิภาพกว่านี้โดยใช้เทคนิค divide and conquer

เฉลย

ข้อ 4

[Dasgupta, Papadimitriou, Vazirani 2.22] กำหนดอะเรย์ $A[\cdot ]\,$ ที่เรียงแล้วขนาด $m\,$ ช่อง และกำหนดอะเรย์ $B[\cdot ]\,$ ที่เรียงแล้วขนาด $n\,$ ช่อง โดยที่ไม่มีจำนวนสองตัวใดๆ ในอะเรย์ทั้งสองตัวที่ซ้ำกัน จงออกแบบอัลกอริทึีมเพื่อหาสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ $k\,$ ของเซตของตัวเลขที่เกิดจากการนำเอาตัวเลขในอะเรย์ทั้งสองตัวมารวมกัน อัลกอริทึีมของคุณควรจะทำงานได้ในเวลา $O(\log n+\log m)\,$

เฉลย

ข้อ 5

ใำห้ $x\,$ และ $k\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ จงออกแบบอัลกอริทึมเพื่อทำการคำนวณ $x^{k}\,$ ซึ่งทำงานได้ในเวลา $O(\log k)\,$ โดยสมมติว่าเราสามารถคูณเลขสองตัวได้ในเวลา $O(1)\,$

เฉลย

ข้อ 6

เลขฟิโนนักชีมีนิยามดังต่อไปนี้ $f_{n}={\begin{cases}0&n=0\\1&n=1\\f_{n-1}+f_{n-2}&n\geq 2\end{cases}}\,$

จงพิสูจน์ว่า ${\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}f_{n+1}&f_{n}\\f_{n}&f_{n-1}\end{bmatrix}}$ สำหรับจำนวนเต็มบวก $n\,$ ทุกจำนวน
จงออกแบบอัลกอริืทึมเพื่อหาค่า $f_{n}\,$ ที่มีเวลาการทำงาน $O(\log n)\,$

เฉลย

ข้อ 7

พิจารณาปัญหาการหาลำดับย่อยที่มีผลบวกสูงสุด (ซึ่งเราเคยเรียนกันในชั้นเรียนแล้ว) ดังต่อไปนี้

กำหนดอะเรย์ $A[\cdot ]\,$ ขนาด $n\,$ ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว เราต้องการหาลำดับย่อย $A[i],A[i+1],\ldots ,A[j]\,$ โดยที่ $1\leq i\leq j\leq n\,$ ที่ทำให้ $A[i]+A[i+1]+A[i+2]+\dotsb +A[j]\,$ มีค่ามากที่สุด

จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา $O(n\log n)\,$

เฉลย

ข้อ 8

[Kleinberg & Tardos 5.2] กำหนดอะเรย์ $A[\cdot ]\,$ ขนาด $n\,$ ช่อง นิยามอินเวอร์ชันสำััคัญว่าเป็นคู่ลำดับ $(i,j)\,$ ที่ $i<j\,$ และ $A[i]>2A[j]\,$

จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา $O(n\log n)\,$

เฉลย

ข้อ 9

[Kleinberg & Tardos 5.3] คุณให้คำปรึกษาธนาคารแห่งหนึ่งเกี่ยวกับการตรวจสอบการฉ้อโกง ขณะนี้ธนาคารมีปัญหาดังต่อไปนี้

ธนาคารได้ยึดบัตร ATM จำนวน $n\,$ ใบมา บัตร ATM แต่ละใบจะมีหมายเลขบัญชีธนาคารฝังอยู่ในไมโครชิป โดยบัตรหลายๆ ใบอาจมีหมายเลขบัญชีธนาคารเดียวกันก็ได้ เรากล่าวว่าบัตร ATM สองใบใดๆ จะสมมูลกันมันตรงกับบัญชีธนาคารเดียวกัน

การอ่านเลขบัญชีออกมาจากบัตร ATM เป็นเรื่องที่ทำยาก (สมมตินะครับ) แต่ธนาคารมีเครื่อง "ตรวจสอบความสมมูล" ที่คุณสามารถเอาบัตร ATM สองใบไปเสียบ แล้วมันจะบอกว่าบัตรสองใบนี้สมมูลกันหรือไม่

ธนาคารต้องการตอบคำถามต่อไปนี้: ในบัตร $n\,$ ใบนี้ั มีกลุ่มของบัตรที่มีจำนวนมากกว่า $n/2\,$ สักกลุ่มหรือไม่ที่บัตรทุกใบในกลุ่มนี้สมมูลกันทั้งหมด?

สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง $O(n\log n)\,$ ครั้งเท่านั้น

เฉลย

@@ แถว 1: / แถว 1: @@
 == ข้อ 1 ==
-คุณได้รับอะเรย์ <math>A[\cdot] \,</math> ซึ่งมีจำนวนช่องเท่ากับจำนวนของจำนวนเต็มทั้งหมด (สมาชิกของอะเรย์นี้คือ <math>A[1], A[2], A[3], \ldots \,</math>) อะเรย์นี้มีคุณสมบัติว่าสมาชิก <math>n \,</math> ตัวแรกของมันจะมีค่าเท่ากับ 0 (กล่าวคือ <math>0 = A[1] = A[1] = \dotsb = A[n]\,</math>) โดยที่ <math>n \,</math> เป็นจำนวนเต็มหนึ่งตัว และสมาชิกที่เหลือมีค่าเท่ากับ 1 (กล่าวคือ <math>1 = A[n+1] = A[n+2] = A[n+3] = \dotsb \,</math>)
+[ดัีดแปลงจาก Dasgupta, Papadimitriou, Vazirani 2.16] คุณได้รับอะเรย์ <math>A[\cdot] \,</math> ซึ่งมีจำนวนช่องเท่ากับจำนวนของจำนวนเต็มทั้งหมด (สมาชิกของอะเรย์นี้คือ <math>A[1], A[2], A[3], \ldots \,</math>) อะเรย์นี้มีคุณสมบัติว่าสมาชิก <math>n \,</math> ตัวแรกของมันจะมีค่าเท่ากับ 0 (กล่าวคือ <math>0 = A[1] = A[1] = \dotsb = A[n]\,</math>) โดยที่ <math>n \,</math> เป็นจำนวนเต็มหนึ่งตัว และสมาชิกที่เหลือมีค่าเท่ากับ 1 (กล่าวคือ <math>1 = A[n+1] = A[n+2] = A[n+3] = \dotsb \,</math>)
 คุณไม่ทราบค่า <math>n \,</math> จงหาอัลกอริทึมที่หาค่า <math>n \,</math> ได้ในเวลา <math>O(\log n) \,</math>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 1|เฉลย]]
 == ข้อ 2 ==
-กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่มีขนาด <math>n \,</math> ช่องที่เรียงจากน้อยไปหามาก คุณอยากจะทราบว่ามีจำนวนเต็ม <math>i \,</math> ที่ทำให้ <math>A[i] = i\,</math> หรือไม่ จงหาอัลกอริทึมที่สามารถหาค่า <math>i \,</math> ดังกล่าวมาหนึ่งค่าหรือตอบว่าไม่มีค่า <math>i \,</math> ดังกล่าวเลยได้ในเวลา <math>O(\log n) \,</math>
+[Dasgupta, Papadimitriou, Vazirani 2.17] กำหนดอะเรย์ <math>A[\cdot] \,</math> ที่มีขนาด <math>n \,</math> ช่องที่เรียงจากน้อยไปหามาก นอกจากนี้เลขในอะเรย์ทุกตัวจะมีค่าไม่เท่ากัน คุณอยากจะทราบว่ามีจำนวนเต็ม <math>i \,</math> ที่ทำให้ <math>A[i] = i\,</math> หรือไม่ จงหาอัลกอริทึมที่สามารถหาค่า <math>i \,</math> ดังกล่าวมาหนึ่งค่าหรือตอบว่าไม่มีค่า <math>i \,</math> ดังกล่าวเลยได้ในเวลา <math>O(\log n) \,</math>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 2|เฉลย]]
 == ข้อ 3 ==
-สมมติว่าคุณมีอะเรย์ที่เรียงแล้วอยู่ <math>k \,</math> อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ <math>n \,</math> ตัว คุณต้องการรวมอะเรย์ทั้งหมดเป็นอะเรย์ที่เรียงแล้วขนาด <math>kn \,</math> ช่อง
+[Dasgupta, Papadimitriou, Vazirani 2.19] สมมติว่าคุณมีอะเรย์ที่เรียงแล้วอยู่ <math>k \,</math> อะเรย์ แต่ละอะเรย์มีสมาชิกอยู่ <math>n \,</math> ตัว คุณต้องการรวมอะเรย์ทั้งหมดเป็นอะเรย์ที่เรียงแล้วขนาด <math>kn \,</math> ช่อง
 # นี่เป็นวิธีการหนึ่งที่คุณสามารถจะทำได้ ใช้อัลกอริทีม <code>merge</code> ที่เรียนไปในชั้นเรียนทำการรวมอะเรย์สองอะเรย์แรก เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สาม เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สี่ เช่นนี้ไปเรื่อยๆ วิธีการนี้มีเวลาการทำงานเป็นเท่าใดในรูปของ <math>n \,</math> และ <math>k \,</math>?
 # จงออกอัลกอริทึมที่มีประสิทธิภาพกว่านี้โดยใช้เทคนิค divide and conquer
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 3|เฉลย]]
 == ข้อ 4 ==
-กำหนดอะเรย์ <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|เฉลย]]
+== ข้อ 5 ==
+ใำห้ <math>x \,</math> และ <math>k \,</math> เป็นจำนวนเต็มที่ไม่เป็นลบ จงออกแบบอัลกอริทึมเพื่อทำการคำนวณ <math>x^k \,</math> ซึ่งทำงานได้ในเวลา <math>O(\log k) \,</math> โดยสมมติว่าเราสามารถคูณเลขสองตัวได้ในเวลา <math>O(1) \,</math>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 5|เฉลย]]
+== ข้อ 6 ==
+เลขฟิโนนักชีมีนิยามดังต่อไปนี้
+<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 & f_{n-1}  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
+# จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 6|เฉลย]]
+== ข้อ 7 ==
+พิจารณาปัญหาการหาลำดับย่อยที่มีผลบวกสูงสุด (ซึ่งเราเคยเรียนกันในชั้นเรียนแล้ว) ดังต่อไปนี้
+กำหนดอะเรย์ <math>A[\cdot] \,</math> ขนาด <math>n \,</math> ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว เราต้องการหาลำดับย่อย <math>A[i], A[i+1], \ldots, A[j] \,</math> โดยที่ <math>1 \leq i \leq j \leq n \,</math> ที่ทำให้ <math>A[i] + A[i+1] + A[i+2] + \dotsb + A[j] \,</math> มีค่ามากที่สุด
+จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา <math>O(n \log n) \,</math>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 7|เฉลย]]
+== ข้อ 8 ==
+[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>
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 8|เฉลย]]
+== ข้อ 9 ==
+[Kleinberg & Tardos 5.3] คุณให้คำปรึกษาธนาคารแห่งหนึ่งเกี่ยวกับการตรวจสอบการฉ้อโกง ขณะนี้ธนาคารมีปัญหาดังต่อไปนี้
+ธนาคารได้ยึดบัตร ATM จำนวน <math>n \,</math> ใบมา บัตร ATM แต่ละใบจะมีหมายเลขบัญชีธนาคารฝังอยู่ในไมโครชิป โดยบัตรหลายๆ ใบอาจมีหมายเลขบัญชีธนาคารเดียวกันก็ได้ เรากล่าวว่าบัตร ATM สองใบใดๆ จะ<i>สมมูล</i>กันมันตรงกับบัญชีธนาคารเดียวกัน
+การอ่านเลขบัญชีออกมาจากบัตร ATM เป็นเรื่องที่ทำยาก (สมมตินะครับ) แต่ธนาคารมีเครื่อง "ตรวจสอบความสมมูล" ที่คุณสามารถเอาบัตร ATM สองใบไปเสียบ แล้วมันจะบอกว่าบัตรสองใบนี้สมมูลกันหรือไม่
+ธนาคารต้องการตอบคำถามต่อไปนี้: ในบัตร <math>n \,</math> ใบนี้ั มีกลุ่มของบัตรที่มีจำนวนมากกว่า <math>n/2 \,</math> สักกลุ่มหรือไม่ที่บัตรทุกใบในกลุ่มนี้สมมูลกันทั้งหมด?
+สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น
+[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9|เฉลย]]

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

รุ่นแก้ไขปัจจุบันเมื่อ 14:32, 4 กันยายน 2552

เนื้อหา

ข้อ 1

ข้อ 2

ข้อ 3

ข้อ 4

ข้อ 5

ข้อ 6

ข้อ 7

ข้อ 8

ข้อ 9

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ