ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาอัลกอริทึมแบบแบ่งแยกแล้วเอาชนะ/เฉลยข้อ 9"
Cardcaptor (คุย | มีส่วนร่วม) |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 83: | แถว 83: | ||
=== ข้อความที่ 2 === | === ข้อความที่ 2 === | ||
'''พิสูจน์:''' พิจารณาการทำงานของ <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> เราจะได้ว่าไม่ว่า <math>x_1 \,</math> และ <math>x_2 \,</math> จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน <math>n/2 \,</math> เสมอ ฉะนั้น <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> จะตอบค่า NONE เท่านั้น | '''พิสูจน์:''' พิจารณาการทำงานของ <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> เราจะได้ว่าไม่ว่า <math>x_1 \,</math> และ <math>x_2 \,</math> จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน <math>n/2 \,</math> เสมอ ฉะนั้น <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> จะตอบค่า NONE เท่านั้น | ||
| + | |||
| + | == ประสิทธิภาพ == | ||
| + | ให้ <math>T(n) \,</math> เป็นเวลาการทำงานของ <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> แล้วเราจะได้ว่า | ||
| + | |||
| + | : <math>T(n) = \begin{cases} O(1) & n = 1 \\ 2T(n/2) + O(n) & n > 1 \end{cases} \,</math> | ||
| + | |||
| + | ฉะนั้นด้วย Master Theorem เราจะได้ว่า <math>T(n) = O(n \log n) \,</math> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 13:19, 2 กันยายน 2552
อัลกอริทึม
เราออกแบบอัลกอริทึมที่ใช้แก้ปัญหาโจทย์ข้อนี้ด้วยเทคนิค divide and conquer ในขั้นแรก เราจะสมมติว่าเรามีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้อยู่แล้ว และเราจะเรียกชื่อมันว่า โดยมันจะรับบัตร ATM เป็นอินพุต และจะส่งข้อมูลออกตามเงื่อนไขดังต่อไปนี้
- ถ้าหากในกลุ่มของบัตร ATM ที่ให้ไม่มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า แล้ว โดยที่ เป็นค่าพิเศษค่าหนึ่งที่ไม่ตรงกับบัตร ATM ใดๆ เลย
- ถ้าหากในกลุ่มของบัตร ATM ที่ให้มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า แล้ว เมื่อ เป็นบัตร ATM บัตรหนึ่งในกลุ่มของบัตรนั้น
เมื่อได้สมมติเช่นนั้นแล้ว รายละเอียดของ จะเป็นดังต่อไปนี้
- DIVIDE: แบ่งบัตร ATM ที่ได้รับมาออกเป็นสองกลุ่ม ได้แก่ และ เมื่อ
- พึงระลึกว่า เราจะไม่สามารถแบ่งปัญหาออกเป็นปัญหาย่อยเช่นนี้ได้ถ้า ในกรณีนี้เราจะืคืนค่า กลับไป กล่าวคืือ
- CONQUER: เรียก และสมมติให้ผลลัพธ์ของมันเป็น หลังจากนั้นเรียก และสมมติให้ผลลัพธ์เป็น
- COMBINE: ตรวจสอบว่าระหว่าง กับ ตัวใดกันแน่ที่เป็นมีกลุ่มบัตร ATM ที่สมมูลกับมันมากกว่า ใบ ซึ่งการตรวจสอบสามารถทำได้โดยการนำเอา ไปตรวจเช็คความสมมูลกับบัตร ATM อื่นๆ ทุกบัตร แล้วนับว่ามีบัตรที่สมมูลกับมันกี่บัตร แล้วจึงทำเช่นเดียวกันกับ หลังจากนั้นเราจึงคืนบัตรที่มีจำนวนบัตรที่สมมูลกับมันมากกว่า กลับไป (จะมีบัตรนี้ได้เพียงบัตรเดียวเท่านั้น)
อัลกอริืทึมที่อธิบายมาข้างบนสามารถเขียนเป็น pseudocode ได้ดังต่อไปนี้ <geshi lang="c"> Majority(c[1], c[2], ..., c[n]) {
if n = 1 then
return c[1]
else
{
h = n/2
x1 = Majority(c[1], c[2], ..., c[h])
x2 = Majority(c[h+1], c[h+2], ..., c[n])
x1count = 0
if x1 != NONE then
{
for i = 1 to n do
if TEST_EQUIVALENCE(x1, c[i]) = true then
x1count = x1count + 1
}
x2count = 0
if x2 != NONE then
{
for i = 1 to n do
if TEST_EQUIVALANCE(x2, c[i]) = true then
x2count = x2count + 1
}
if x1count > n/2 then
return x1
else if x2count > n/2 then
return x2
else
return NONE
}
}
</geshi>
ใน pseudocode ข้างบนนี้ TEST_EQUIVALANCE คือการเช็คว่าบัตร ATM สองบัตรสมมูลกันหรือไม่
ความถูกต้อง
การพิูสูจน์ว่าอัลกอริทึมข้างบนทำงานได้ถูกต้อง เราจะต้องพิสูจน์ข้อความสองข้อความต่อไปนี้
- ถ้าใน มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า แล้ว จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา
- ถ้าใน ไม่มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนั้นมีขนาดมากกว่า แล้ว จะคืนค่า NONE
ข้อความที่ 1
ให้ เป็นประพจน์เปิด " มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า แล้ว จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา"
เราจะพิสูจน์ ด้วย induction บน แต่ก่อนที่เราจะพิสูจน์เราจะพิสูจน์ lemma ต่อไปนี้
lemma: ให้บัตร เป็นบัตร ATM บัตรหนึ่งใน ที่มีบัตรสมมูลกับมันมากกว่า ใบ และให้ แล้วอย่างน้อยข้อความใดข้อความหนึ่งต่อไปนี้จะเป็นจริิง
- มีบัตรสมมูลกับ ใน มากกว่า ใบ
- มีบัตรสมมูลกับ ใน มากกว่า ใบ
พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่าข้อความทั้งสองเป็นเท็จ ดังนั้นเราจะได้ว่ามีบัตรที่สมมูลกับ ไม่เกิืน ใบ เกิดข้อขัดแย้งกับความจริงที่ว่ามีบัตรสมมูลกับ มากกว่า ฉะนั้นจะต้องมีอย่างน้อยข้อความหนึ่งที่เป็นจริง
พิสูจน์ : (Base Case) ในกรณีนี้ ซึ่งเราทราบว่า และ เป็นบัตรที่มีบัตรสมมูลกับมัน 1 ใบ (ตัวมันเอง) ซึ่งจำนวนบัตรนี้มากกว่า
(Induction Case) สมมติให้ เป็นจริงสำหรับจำนวนเต็ม บางตัว พิจารณาเซตของบัตร ATM และสมมติให้ เป็นบัตร ATM ที่มีบัตรสมมูลกับมัน (รวมตัวมันเองด้วย) มากกว่า ใบ จาก lemma เราจะได้ว่า
- มีบัตรสมมูลกับ ใน มากกว่า ใบ หรือไม่ก็
- มีบัตรสมมูลกับ ใน มากกว่า ใบ
ฉะนั้นจะมีบัตรอย่างน้อยหนึ่งใบใน และ ที่สมมูลกับ
ดังนั้นเมื่อเรานำ และ ไปตรวจว่ามีบัตร ATM ที่สมมูลกับมันกี่ตัว จะมีบัตรหนึ่งทีมีบัตรสมมูลกับมันมากกว่า ใบ และ จะคืนบ้ัตรนั้นออกมา ฉะนั้นเราสรุปได้ว่า เป็นจริง
ดังนั้นเราสามารถสรุปว่า เป็นจริงสำหรับจำนวนเต็มบวก ทุกตัวด้วย (strong) induction
ข้อความที่ 2
พิสูจน์: พิจารณาการทำงานของ เราจะได้ว่าไม่ว่า และ จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน เสมอ ฉะนั้น จะตอบค่า NONE เท่านั้น
ประสิทธิภาพ
ให้ เป็นเวลาการทำงานของ แล้วเราจะได้ว่า
ฉะนั้นด้วย Master Theorem เราจะได้ว่า
