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

รุ่นแก้ไขปัจจุบันเมื่อ 13:19, 2 กันยายน 2552

เนื้อหา

1 อัลกอริทึม
2 ความถูกต้อง
- 2.1 ข้อความที่ 1
- 2.2 ข้อความที่ 2
3 ประสิทธิภาพ

อัลกอริทึม

เราออกแบบอัลกอริทึมที่ใช้แก้ปัญหาโจทย์ข้อนี้ด้วยเทคนิค divide and conquer ในขั้นแรก เราจะสมมติว่าเรามีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้อยู่แล้ว และเราจะเรียกชื่อมันว่า $\mathrm {Majority} \,$ โดยมันจะรับบัตร ATM $c_{1},c_{2},\ldots ,c_{n}\,$ เป็นอินพุต และจะส่งข้อมูลออกตามเงื่อนไขดังต่อไปนี้

ถ้าหากในกลุ่มของบัตร ATM ที่ให้ไม่มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})=\mathrm {NONE} \,$ โดยที่ $\mathrm {NONE} \,$ เป็นค่าพิเศษค่าหนึ่งที่ไม่ตรงกับบัตร ATM ใดๆ เลย
ถ้าหากในกลุ่มของบัตร ATM ที่ให้มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})=x\,$ เมื่อ $x\,$ เป็นบัตร ATM บัตรหนึ่งในกลุ่มของบัตรนั้น

เมื่อได้สมมติเช่นนั้นแล้ว รายละเอียดของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะเป็นดังต่อไปนี้

DIVIDE: แบ่งบัตร ATM ที่ได้รับมาออกเป็นสองกลุ่ม ได้แก่ $c_{1},c_{2},\ldots ,c_{h}\,$ และ $c_{h+1},c_{h+2},\ldots ,c_{n}\,$ เมื่อ $h=\lfloor n/2\rfloor \,$
พึงระลึกว่า เราจะไม่สามารถแบ่งปัญหาออกเป็นปัญหาย่อยเช่นนี้ได้ถ้า $n=1\,$ ในกรณีนี้เราจะืคืนค่า $c_{1}\,$ กลับไป กล่าวคืือ $\mathrm {Majority} (c_{1})=c_{1}\,$

CONQUER: เรียก $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{h})\,$ และสมมติให้ผลลัพธ์ของมันเป็น $x_{1}\,$ หลังจากนั้นเรียก $\mathrm {Majority} (c_{h+1},c_{h+2},\ldots ,c_{n})\,$ และสมมติให้ผลลัพธ์เป็น $x_{2}\,$

COMBINE: ตรวจสอบว่าระหว่าง $x_{1}\,$ กับ $x_{2}\,$ ตัวใดกันแน่ที่เป็นมีกลุ่มบัตร ATM ที่สมมูลกับมันมากกว่า $n/2\,$ ใบ ซึ่งการตรวจสอบสามารถทำได้โดยการนำเอา $x_{1}\,$ ไปตรวจเช็คความสมมูลกับบัตร ATM อื่นๆ ทุกบัตร แล้วนับว่ามีบัตรที่สมมูลกับมันกี่บัตร แล้วจึงทำเช่นเดียวกันกับ $x_{2}\,$ หลังจากนั้นเราจึงคืนบัตรที่มีจำนวนบัตรที่สมมูลกับมันมากกว่า $n/2\,$ กลับไป (จะมีบัตรนี้ได้เพียงบัตรเดียวเท่านั้น)

อัลกอริืทึมที่อธิบายมาข้างบนสามารถเขียนเป็น 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 สองบัตรสมมูลกันหรือไม่

ความถูกต้อง

การพิูสูจน์ว่าอัลกอริทึมข้างบนทำงานได้ถูกต้อง เราจะต้องพิสูจน์ข้อความสองข้อความต่อไปนี้

ถ้าใน $c_{1},c_{2},\ldots ,c_{n}\,$ มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา
ถ้าใน $c_{1},c_{2},\ldots ,c_{n}\,$ ไม่มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนั้นมีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนค่า NONE

ข้อความที่ 1

ให้ $P(n)\,$ เป็นประพจน์เปิด " $c_{1},c_{2},\ldots ,c_{n}\,$ มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า $n/2\,$ แล้ว $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา"

เราจะพิสูจน์ $P(n)\,$ ด้วย induction บน $n\,$ แต่ก่อนที่เราจะพิสูจน์เราจะพิสูจน์ lemma ต่อไปนี้

lemma: ให้บัตร $x\,$ เป็นบัตร ATM บัตรหนึ่งใน $c_{1},c_{2},\ldots ,c_{n}\,$ ที่มีบัตรสมมูลกับมันมากกว่า $n/2\,$ ใบ และให้ $h=n/2\,$ แล้วอย่างน้อยข้อความใดข้อความหนึ่งต่อไปนี้จะเป็นจริิง

มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $h/2\,$ ใบ
มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $(n-h)/2\,$ ใบ

พิสูจน์: สมมติเพื่อให้เกิดข้อขัดแย้งว่าข้อความทั้งสองเป็นเท็จ ดังนั้นเราจะได้ว่ามีบัตรที่สมมูลกับ $x\,$ ไม่เกิืน $h/2+(n-h)/2=n/2\,$ ใบ เกิดข้อขัดแย้งกับความจริงที่ว่ามีบัตรสมมูลกับ $x\,$ มากกว่า $n/2\,$ ฉะนั้นจะต้องมีอย่างน้อยข้อความหนึ่งที่เป็นจริง

พิสูจน์ $P(n)\,$ : (Base Case) ในกรณีนี้ $n=1\,$ ซึ่งเราทราบว่า $\mathrm {Majority} (c_{1})=c_{1}\,$ และ $c_{1}\,$ เป็นบัตรที่มีบัตรสมมูลกับมัน 1 ใบ (ตัวมันเอง) ซึ่งจำนวนบัตรนี้มากกว่า $1/2=0.5\,$

(Induction Case) สมมติให้ $P(1),P(2),\ldots ,P(n-1)\,$ เป็นจริงสำหรับจำนวนเต็ม $n>1$ บางตัว พิจารณาเซตของบัตร ATM $c_{1},c_{2},\ldots ,c_{n}\,$ และสมมติให้ $x\,$ เป็นบัตร ATM ที่มีบัตรสมมูลกับมัน (รวมตัวมันเองด้วย) มากกว่า $n/2\,$ ใบ จาก lemma เราจะได้ว่า

มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $h/2\,$ ใบ หรือไม่ก็
มีบัตรสมมูลกับ $x\,$ ใน $c_{1},c_{2},\ldots ,c_{h}\,$ มากกว่า $(n-h)/2\,$ ใบ

ฉะนั้นจะมีบัตรอย่างน้อยหนึ่งใบใน $x_{1}=\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{h})\,$ และ $x_{2}=\mathrm {Majority} (c_{h+1},c_{h+1},\ldots ,c_{n})\,$ ที่สมมูลกับ $x\,$

ดังนั้นเมื่อเรานำ $x_{1}\,$ และ $x_{2}\,$ ไปตรวจว่ามีบัตร ATM ที่สมมูลกับมันกี่ตัว จะมีบัตรหนึ่งทีมีบัตรสมมูลกับมันมากกว่า $n/2\,$ ใบ และ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะคืนบ้ัตรนั้นออกมา ฉะนั้นเราสรุปได้ว่า $P(n)\,$ เป็นจริง

ดังนั้นเราสามารถสรุปว่า $P(n)\,$ เป็นจริงสำหรับจำนวนเต็มบวก $n\,$ ทุกตัวด้วย (strong) induction

ข้อความที่ 2

พิสูจน์: พิจารณาการทำงานของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ เราจะได้ว่าไม่ว่า $x_{1}\,$ และ $x_{2}\,$ จะมีค่าเป็นอะไรก็ตาม จะมีบัตร ATM ที่สมมูลกับมันไม่เกิน $n/2\,$ เสมอ ฉะนั้น $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ จะตอบค่า NONE เท่านั้น

ประสิทธิภาพ

ให้ $T(n)\,$ เป็นเวลาการทำงานของ $\mathrm {Majority} (c_{1},c_{2},\ldots ,c_{n})\,$ แล้วเราจะได้ว่า

T(n)={\begin{cases}O(1)&n=1\\2T(n/2)+O(n)&n>1\end{cases}}\,

ฉะนั้นด้วย Master Theorem เราจะได้ว่า $T(n)=O(n\log n)\,$

@@ แถว 50: / แถว 50: @@
 }
 </geshi>
+ใน pseudocode ข้างบนนี้ <code>TEST_EQUIVALANCE</code> คือการเช็คว่าบัตร ATM สองบัตรสมมูลกันหรือไม่
+== ความถูกต้อง ==
+การพิูสูจน์ว่าอัลกอริทึมข้างบนทำงานได้ถูกต้อง เราจะต้องพิสูจน์ข้อความสองข้อความต่อไปนี้
+# ถ้าใน <math>c_1, c_2, \ldots, c_n \,</math> มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า <math>n/2 \,</math> แล้ว <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา
+# ถ้าใน <math>c_1, c_2, \ldots, c_n \,</math> ไม่มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนั้นมีขนาดมากกว่า <math>n/2 \,</math> แล้ว <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> จะคืนค่า NONE
+=== ข้อความที่ 1 ===
+ให้ <math>P(n) \,</math> เป็นประพจน์เปิด "<math>c_1, c_2, \ldots, c_n \,</math> มีเซตของบัตร ATM ที่สมมูลกัน โดยเซตนี้มีขนาดมากกว่า <math>n/2 \,</math> แล้ว <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) \,</math> จะคืนบัตร ATM หนึ่งใบในบัตร ATM เซตนั้นมา"
+เราจะพิสูจน์ <math>P(n) \,</math> ด้วย induction บน <math>n \,</math> แต่ก่อนที่เราจะพิสูจน์เราจะพิสูจน์ lemma ต่อไปนี้
+'''lemma:''' ให้บัตร <math>x \,</math> เป็นบัตร ATM บัตรหนึ่งใน <math>c_1, c_2, \ldots, c_n \,</math> ที่มีบัตรสมมูลกับมันมากกว่า <math>n/2 \,</math> ใบ และให้ <math>h = n/2 \,</math> แล้วอย่างน้อยข้อความใดข้อความหนึ่งต่อไปนี้จะเป็นจริิง
+# มีบัตรสมมูลกับ <math>x \,</math> ใน <math>c_1, c_2, \ldots, c_h \,</math> มากกว่า <math>h/2 \,</math> ใบ
+# มีบัตรสมมูลกับ <math>x \,</math> ใน <math>c_1, c_2, \ldots, c_h \,</math> มากกว่า <math>(n-h)/2 \,</math> ใบ
+'''พิสูจน์:''' สมมติเพื่อให้เกิดข้อขัดแย้งว่าข้อความทั้งสองเป็นเท็จ ดังนั้นเราจะได้ว่ามีบัตรที่สมมูลกับ <math>x \,</math> ไม่เกิืน <math>h/2 + (n-h)/2 = n/2 \,</math> ใบ เกิดข้อขัดแย้งกับความจริงที่ว่ามีบัตรสมมูลกับ <math>x \,</math> มากกว่า <math>n/2 \,</math> ฉะนั้นจะต้องมีอย่างน้อยข้อความหนึ่งที่เป็นจริง
+'''พิสูจน์ <math>P(n) \,</math>:''' (Base Case) ในกรณีนี้ <math>n = 1 \,</math> ซึ่งเราทราบว่า <math>\mathrm{Majority}(c_1) = c_1 \,</math> และ <math>c_1 \,</math> เป็นบัตรที่มีบัตรสมมูลกับมัน 1 ใบ (ตัวมันเอง) ซึ่งจำนวนบัตรนี้มากกว่า <math>1/2 = 0.5 \,</math>
+(Induction Case) สมมติให้ <math>P(1), P(2), \ldots, P(n-1) \,</math> เป็นจริงสำหรับจำนวนเต็ม <math>n > 1</math> บางตัว พิจารณาเซตของบัตร ATM <math>c_1, c_2, \ldots, c_n \,</math> และสมมติให้ <math>x \,</math> เป็นบัตร ATM ที่มีบัตรสมมูลกับมัน (รวมตัวมันเองด้วย) มากกว่า <math>n/2 \,</math> ใบ จาก lemma เราจะได้ว่า
+* มีบัตรสมมูลกับ <math>x \,</math> ใน <math>c_1, c_2, \ldots, c_h \,</math> มากกว่า <math>h/2 \,</math> ใบ หรือไม่ก็
+* มีบัตรสมมูลกับ <math>x \,</math> ใน <math>c_1, c_2, \ldots, c_h \,</math> มากกว่า <math>(n-h)/2 \,</math> ใบ
+ฉะนั้นจะมีบัตรอย่างน้อยหนึ่งใบใน <math>x_1 = \mathrm{Majority}(c_1, c_2, \ldots, c_h) \,</math> และ <math>x_2 = \mathrm{Majority}(c_{h+1}, c_{h+1}, \ldots, c_n) \,</math> ที่สมมูลกับ <math>x \,</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> จะคืนบ้ัตรนั้นออกมา ฉะนั้นเราสรุปได้ว่า <math>P(n) \,</math> เป็นจริง
+ดังนั้นเราสามารถสรุปว่า <math>P(n) \,</math> เป็นจริงสำหรับจำนวนเต็มบวก <math>n \,</math> ทุกตัวด้วย (strong) induction
+=== ข้อความที่ 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>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>

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

รุ่นแก้ไขปัจจุบันเมื่อ 13:19, 2 กันยายน 2552

เนื้อหา

อัลกอริทึม

ความถูกต้อง

ข้อความที่ 1

ข้อความที่ 2

ประสิทธิภาพ

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ