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

Cardcaptor: /* ความถูกต้อง */

2009-09-02T13:19:30Z

ความถูกต้อง

Cardcaptor: /* ข้อความที่ 1 */

2009-09-02T13:17:40Z

ข้อความที่ 1

Cardcaptor เมื่อ 13:13, 2 กันยายน 2552

2009-09-02T13:13:49Z

158.108.183.136: QU

2009-09-02T12:42:18Z

หน้าใหม่

== อัลกอริทึม ==
เราออกแบบอัลกอริทึมที่ใช้แก้ปัญหาโจทย์ข้อนี้ด้วยเทคนิค divide and conquer ในขั้นแรก เราจะสมมติว่าเรามีอัลกอริทึมที่สามารถแก้ปัญหานี้ได้อยู่แล้ว และเราจะเรียกชื่อมันว่า <math>\mathrm{Majority} \,</math> โดยมันจะรับบัตร ATM <math>c_1, c_2, \ldots, c_n \,</math> เป็นอินพุต และจะส่งข้อมูลออกตามเงื่อนไขดังต่อไปนี้
* ถ้าหากในกลุ่มของบัตร ATM ที่ให้ไม่มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า <math>n/2 \,</math> แล้ว <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) = \mathrm{NONE} \,</math> โดยที่ <math>\mathrm{NONE} \,</math> เป็นค่าพิเศษค่าหนึ่งที่ไม่ตรงกับบัตร ATM ใดๆ เลย
* ถ้าหากในกลุ่มของบัตร ATM ที่ให้มีเซตของบัีตร ATM ที่สมมูลกันที่มีขนาดใหญ่กว่า <math>n/2 \,</math> แล้ว <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n) = x \,</math> เมื่อ <math>x \,</math> เป็นบัตร ATM บัตรหนึ่งในกลุ่มของบัตรนั้น

เมื่อได้สมมติเช่นนั้นแล้ว รายละเอียดของ <math>\mathrm{Majority}(c_1, c_2, \ldots, c_n)\,</math> จะเป็นดังต่อไปนี้

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

* '''CONQUER:''' เรียก <math>\mathrm{Majority}(c_1, c_2, \ldots, c_h) \,</math> และสมมติให้ผลลัพธ์ของมันเป็น <math>x_1 \,</math> หลังจากนั้นเรียก <math>\mathrm{Majority}(c_{h+1}, c_{h+2}, \ldots, c_n) \,</math> และสมมติให้ผลลัพธ์เป็น <math>x_2 \,</math>

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

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:19, 2 กันยายน 2552
แถว 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:17, 2 กันยายน 2552
แถว 78:		แถว 78:

	ดังนั้นเมื่อเรานำ <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>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 เท่านั้น

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:13, 2 กันยายน 2552
แถว 50:		แถว 50:
	}		}
	</geshi>		</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> เป็นจริง