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

ข้อ 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\,$ ช่อง

1. นี่เป็นวิธีการหนึ่งที่คุณสามารถจะทำได้ ใช้อัลกอริทีม merge ที่เรียนไปในชั้นเรียนทำการรวมอะเรย์สองอะเรย์แรก เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สาม เสร็จแล้วเอาผลลัพธ์ไปรวมกับอะเรย์ที่สี่ เช่นนี้ไปเรื่อยๆ วิธีการนี้มีเวลาการทำงานเป็นเท่าใดในรูปของ $n\,$ และ $k\,$?
2. จงออกอัลกอริทึมที่มีประสิทธิภาพกว่านี้โดยใช้เทคนิค 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}}\,$

1. จงพิสูจน์ว่า ${\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}f_{n+1}&f_{n}\\f_{n}&f_{n-1}\end{bmatrix}}$ สำหรับจำนวนเต็มบวก $n\,$ ทุกจำนวน
2. จงออกแบบอัลกอริืทึมเพื่อหาค่า $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)\,$ ครั้งเท่านั้น

เฉลย