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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 7 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน)
แถว 19: แถว 19:
  
 
== ข้อ 4 ==
 
== ข้อ 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|เฉลย]]
 
[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 4|เฉลย]]
แถว 30: แถว 30:
 
== ข้อ 6 ==
 
== ข้อ 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 \\ 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+1} & f_n \\ f_n & f_{n-1}  \end{bmatrix} </math> สำหรับจำนวนเต็มบวก <math>n \,</math> ทุกจำนวน
 
# จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>
 
# จงออกแบบอัลกอริืทึมเพื่อหาค่า <math>f_n \,</math> ที่มีเวลาการทำงาน <math>O(\log n) \,</math>
  
แถว 46: แถว 46:
  
 
== ข้อ 8 ==
 
== ข้อ 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>
 
จงออกแบบอัลกอริทึมเพื่อนับอินเวอร์ชันสำคัญในอะเรย์ อัลกอริทึมนี้ควรทำงานได้ในเวลา <math>O(n \log n) \,</math>
 +
 +
[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 8|เฉลย]]
  
 
== ข้อ 9 ==
 
== ข้อ 9 ==
แถว 60: แถว 62:
  
 
สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น
 
สมมติว่าสิ่งที่คุณทำได้คือการเลือกบัตรสองใบไปเช็คกับเครื่องตรวจสอบความสมมูลเท่านั้น จงแสดงว่าคุณสามารถตอบคำถามข้างบนของธนาคารได้ด้วยการใช้เครื่องตรวจสอบความสมมูลเพียง <math>O(n \log n) \,</math> ครั้งเท่านั้น
 +
 +
[[418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9|เฉลย]]

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

ข้อ 1

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

คุณไม่ทราบค่า จงหาอัลกอริทึมที่หาค่า ได้ในเวลา

เฉลย

ข้อ 2

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

เฉลย

ข้อ 3

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

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

เฉลย

ข้อ 4

[Dasgupta, Papadimitriou, Vazirani 2.22] กำหนดอะเรย์ ที่เรียงแล้วขนาด ช่อง และกำหนดอะเรย์ ที่เรียงแล้วขนาด ช่อง โดยที่ไม่มีจำนวนสองตัวใดๆ ในอะเรย์ทั้งสองตัวที่ซ้ำกัน จงออกแบบอัลกอริทึีมเพื่อหาสมาชิกตัวที่น้อยที่สุดเป็นอันดับที่ ของเซตของตัวเลขที่เกิดจากการนำเอาตัวเลขในอะเรย์ทั้งสองตัวมารวมกัน อัลกอริทึีมของคุณควรจะทำงานได้ในเวลา

เฉลย

ข้อ 5

ใำห้ และ เป็นจำนวนเต็มที่ไม่เป็นลบ จงออกแบบอัลกอริทึมเพื่อทำการคำนวณ ซึ่งทำงานได้ในเวลา โดยสมมติว่าเราสามารถคูณเลขสองตัวได้ในเวลา

เฉลย

ข้อ 6

เลขฟิโนนักชีมีนิยามดังต่อไปนี้

  1. จงพิสูจน์ว่า สำหรับจำนวนเต็มบวก ทุกจำนวน
  2. จงออกแบบอัลกอริืทึมเพื่อหาค่า ที่มีเวลาการทำงาน

เฉลย

ข้อ 7

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

กำหนดอะเรย์ ขนาด ช่อง แต่ละช่องมีจำนวนเต็มบรรจุอยู่หนึ่งตัว เราต้องการหาลำดับย่อย โดยที่ ที่ทำให้ มีค่ามากที่สุด

จงออกแบบอัลกอริทึีมเพื่อแก้ปัญหานี้ซึ่งทำงานในเวลา

เฉลย

ข้อ 8

[Kleinberg & Tardos 5.2] กำหนดอะเรย์ ขนาด ช่อง นิยามอินเวอร์ชันสำััคัญว่าเป็นคู่ลำดับ ที่ และ

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

เฉลย

ข้อ 9

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

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

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

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

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

เฉลย