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

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

2009-09-19T07:59:38Z

การพิสูจน์ความถูกต้องของอัลกอริทึม

Aoy: /* อัลกอริทึม */

2009-09-19T07:56:18Z

อัลกอริทึม

Aoy: /* อัลกอริทึม */

2009-09-19T07:37:56Z

อัลกอริทึม

Aoy: /* อัลกอริทึม */

2009-09-19T07:37:42Z

อัลกอริทึม

Aoy: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== ให้สตริงใน $S' \,$ จับคู่กับสตริงใ…'

2009-09-19T07:37:14Z

หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== ให้สตริงใน <math> S' \, </math> จับคู่กับสตริงใ…'

หน้าใหม่

==''อัลกอริทึม''==
ให้สตริงใน <math> S' \, </math> จับคู่กับสตริงใน <math> S \, </math> ตัวแรกสุดที่เหมือนกัน ถ้าสตริงทุกตัวใน <math> S' \, </math> ถูกจับคู่ได้หมดให้ตอบ "ใช่" ไม่เช่นั้นให้ตอบ "ไม่ใช่"

ให้ <math> i \, </math> เป็นตัวแปรที่ชี้ไปยังสตริงที่กำลังพิจารณาในสตริง <math> S \,</math>

ให้ <math> j \, </math> เป็นตัวแปรที่ชี้ไปยังสตริงที่กำลังพิจารณาในสตริง <math> S' \,</math>

<geshi lang="c">
FindSubString(S,m,S',n)
{
j = 1
for i = 1 to m do
{
if S[i] = S'[j] then
j = j + 1
}
if j > n then
return 1
else
return 0
}
</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:59, 19 กันยายน 2552
แถว 23:		แถว 23:

	==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==		==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
−	จะทำการพิสูจน์โดยใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> Y_i \, </math> คือตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ให้ <math> Y_i^G \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม greedy algorithm ข้างต้น ส่วน math> Y_i^A \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม algorithm อื่น ๆ จะพิสูจน์ว่า <math> Y_i^G \leq Y_i^A \, </math> เสมอ นั่นคือถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \,</math> ตำแหน่งที่เรากำลังพิจารณาแล้ว greedy algorithm จะสามารถจับคู่ได้เสมอ จะพิสูจน์โดยใช้ strong induction กรณี base case ให้ <math> i=1 \,</math> เนื่องจาก greedy algorithm จะจับคู่สตริงใน <math> S \, </math> ตัวแรกสุดที่เหมือนกัน ดังนั้นถ้ามีสตริงใน <math> S \,</math> ที่เหมือนกับสตริงตัวแรกใน <math> S' \, </math> แล้ว <math> Y_1^G \leq Y_1^A \,</math> เสมอ กรณี indutive step สมมติให้ <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> พิจารณากรณีที่กำลังจับคู่ให้กับสตริงตัวที่ <math> m \,</math> ใน <math> S' \, </math> ถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \, </math> ตำแหน่งที่ <math> m \, </math> แล้ว เนื่องจาก greedy algorithm จะจับตัวแรกที่เหมือนกัน ซึ่ง ถ้ามีแค่ตัวเดียวจะได้ว่า <math> ~~Y_m~~^G = ~~Y_m~~^A \,</math> แต่ถ้ามีตัวที่เหมือนกันมากกว่าหนึ่งตัวแล้ว <math> ~~Y_m~~^G < ~~Y_m~~^A \,</math> เนื่องจาก <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> และ <math> ~~Y_m~~^G \leq ~~Y_m~~^A \,</math> ดังนั้น <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i \leq n \, </math> จะได้ว่าสำหรับสตริง <math> m \, </math> ตัวใน <math> S \, </math> ถ้ามีสตริงที่เหมือนกันในสตริง <math> S \, </math> แล้ว greedy algorithm จะตอบ "ใช่" เสมอ	+	จะทำการพิสูจน์โดยใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> Y_i \, </math> คือตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ให้ <math> Y_i^G \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม greedy algorithm ข้างต้น ส่วน <math> Y_i^A \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม algorithm อื่น ๆ จะพิสูจน์ว่า <math> Y_i^G \leq Y_i^A \, </math> เสมอ นั่นคือถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \,</math> ตำแหน่งที่เรากำลังพิจารณาแล้ว greedy algorithm จะสามารถจับคู่ได้เสมอ จะพิสูจน์โดยใช้ strong induction กรณี base case ให้ <math> i=1 \,</math> เนื่องจาก greedy algorithm จะจับคู่สตริงใน <math> S \, </math> ตัวแรกสุดที่เหมือนกัน ดังนั้นถ้ามีสตริงใน <math> S \,</math> ที่เหมือนกับสตริงตัวแรกใน <math> S' \, </math> แล้ว <math> Y_1^G \leq Y_1^A \,</math> เสมอ กรณี indutive step สมมติให้ <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> พิจารณากรณีที่กำลังจับคู่ให้กับสตริงตัวที่ <math> n \,</math> ใน <math> S' \, </math> ถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \, </math> ตำแหน่งที่ <math> n \, </math> แล้ว เนื่องจาก greedy algorithm จะจับตัวแรกที่เหมือนกัน ซึ่ง ถ้ามีแค่ตัวเดียวจะได้ว่า <math> Y_n^G = Y_n^A \,</math> แต่ถ้ามีตัวที่เหมือนกันมากกว่าหนึ่งตัวแล้ว <math> Y_n^G < Y_n^A \,</math> เนื่องจาก <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> และ <math> Y_n^G \leq Y_n^A \,</math> ดังนั้น <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i \leq n \, </math> จะได้ว่าสำหรับสตริง <math> n \, </math> ตัวใน <math> S \, </math> ถ้ามีสตริงที่เหมือนกันในสตริง <math> S \, </math> แล้ว greedy algorithm จะตอบ "ใช่" เสมอ

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:56, 19 กันยายน 2552
แถว 21:		แถว 21:
	}		}
	</geshi>		</geshi>
		+
		+	==''การพิสูจน์ความถูกต้องของอัลกอริทึม''==
		+	จะทำการพิสูจน์โดยใช้เทคนิค greedy algorithm นำหน้าเสมอ ดังนี้ ให้ <math> Y_i \, </math> คือตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ให้ <math> Y_i^G \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม greedy algorithm ข้างต้น ส่วน math> Y_i^A \, </math> คือ ตำแหน่งของสตริงใน <math> S \, </math> ที่ถูกจับคู่กับสตริงตัวที่ <math> i \, </math> ของ <math> S' \, </math> ที่ถูกจับคู่ตาม algorithm อื่น ๆ จะพิสูจน์ว่า <math> Y_i^G \leq Y_i^A \, </math> เสมอ นั่นคือถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \,</math> ตำแหน่งที่เรากำลังพิจารณาแล้ว greedy algorithm จะสามารถจับคู่ได้เสมอ จะพิสูจน์โดยใช้ strong induction กรณี base case ให้ <math> i=1 \,</math> เนื่องจาก greedy algorithm จะจับคู่สตริงใน <math> S \, </math> ตัวแรกสุดที่เหมือนกัน ดังนั้นถ้ามีสตริงใน <math> S \,</math> ที่เหมือนกับสตริงตัวแรกใน <math> S' \, </math> แล้ว <math> Y_1^G \leq Y_1^A \,</math> เสมอ กรณี indutive step สมมติให้ <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> พิจารณากรณีที่กำลังจับคู่ให้กับสตริงตัวที่ <math> m \,</math> ใน <math> S' \, </math> ถ้ามีสตริงใน <math> S \, </math> ที่เหมือนกับสตริงใน <math> S' \, </math> ตำแหน่งที่ <math> m \, </math> แล้ว เนื่องจาก greedy algorithm จะจับตัวแรกที่เหมือนกัน ซึ่ง ถ้ามีแค่ตัวเดียวจะได้ว่า <math> Y_m^G = Y_m^A \,</math> แต่ถ้ามีตัวที่เหมือนกันมากกว่าหนึ่งตัวแล้ว <math> Y_m^G < Y_m^A \,</math> เนื่องจาก <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i < n \, </math> และ <math> Y_m^G \leq Y_m^A \,</math> ดังนั้น <math> Y_i^G \leq Y_i^A \,</math> สำหรับ <math> 1 \leq i \leq n \, </math> จะได้ว่าสำหรับสตริง <math> m \, </math> ตัวใน <math> S \, </math> ถ้ามีสตริงที่เหมือนกันในสตริง <math> S \, </math> แล้ว greedy algorithm จะตอบ "ใช่" เสมอ

@@ แถว 7: / แถว 7: @@
 <geshi lang="c">
-FindSubString(S,m,S^',n)
+FindSubString(S,m,S',n)
+     {
       j = 1

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

Aoy: /* การพิสูจน์ความถูกต้องของอัลกอริทึม */

Aoy: /* อัลกอริทึม */

Aoy: /* อัลกอริทึม */

Aoy: /* อัลกอริทึม */

Aoy: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== ให้สตริงใน S' \, จับคู่กับสตริงใ…'

Aoy: หน้าที่ถูกสร้างด้วย '==''อัลกอริทึม''== ให้สตริงใน $S' \,$ จับคู่กับสตริงใ…'