Google    Youtube      Psv     สพม.11

หน่วยที่8อัลกอริทึม

อัลกอริทึม

    การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบทที่1มี 2 ส่วนที่สำคัญคือการเลือกใช้โครงสร้างข้อมูลและการออกแบบอัลกอริทึม (Algorithm) ซึ่งที่ผ่านมาได้กล่าวถึงโครงสร้างข้อมูลพื้นฐานแบบต่างๆ และในบทนี้จะกล่าวถึงรายละเอียดของอัลกอริทึมโดยพิจารณาวิธีการตรวจสอบการทำงานของอัลกอริทึมว่ามีความถูกต้องมากน้อยเพียงใดซึ่งใช้เทคนิคแบบการตรวจสอบความจริง (Verification) นอกจากมีการพิจารณาเปรียบเทียบหลายๆ อัลกอริทึมที่ใช้แก้ปัญหาเรื่องเดียวกันว่ามีประสิธิภาพต่างกันอย่างไรซึ่งมีเทคนิคที่นำมาใช้ตรวจวัดว่าอัลกอริทึมไหนดีกว่ากัน

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

การเรียกให้โปรแกรมหรือระบบทำงานแบบเบื้องต้นเพื่อทดสอบกับข้อมูลที่หลากหลาย ยังไม่มีประสิทธิภาเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏจะไม่สามารถทราบได้จึงนำการตรวจสอบแบบการอนุมาน (Deductive) มาใช้เพื่อรับประกันว่าผลลัพธ์มีความถูกต้อง

การตรวจสอบอัลกอริทึมเพื่อใช้แก้ไขปัญหาว่ามีความถูกต้องจึงใช้การอนุมานซึ่งแสดงขั้นตอนการประมวลผลของอัลกอริทึมถูกต้องหรือไม่ตั้งแต่มีการรับข้อมูลเข้ามาและแก้ปัญหาจนถุงผลลัพธ์ที่ได้ออกมาดังนั้นการตรวจสอบความถูกต้องของอัลกอริทึม Aเริ่มต้นด้วยการวินิจฉัยIเป็นการสมมุติข้อมูลที่จะรับเข้ามาใช้งาน (Input Assertion)เรียกกว่าเงื่อนไขตอนต้น(Precondition)และการวินิจฉัยOเป็นการสรุปผลลัพธ์ที่ได้ออกมา (OutputAssertion)เรียกว่าเงื่อนไขตอนท้าย ( post condition)ได้เป็นข้อพิสูจน์ทางตรรกะแสดงให้ทราบว่า Oจะเกิดขึ้นตามI และได้เป็น

I=>O(“IImpliesO”)

ได้หลักเกณฑ์คือ เมือกำหนดเงื่อนไขต้นI หลังจากอัลกอริทึมA ทำงานจนถึงจุดสิ้นสุด (Terminate)จะต้องได้เงื่อนไขตอนท้ายOโดยพิจารณาจากตัวอย่างอัลกอริทึมหาค่าเฉลี่ยของค่าทั้งหมดที่เก็บไว้อาร์เรย์ดังในตารางที่8.1

ตารางที่ 8.1อัลกอริทึมการทึมการคำนวณหาค่าเฉลี่ย

1. กำหนดค่าเริ่มต้นให้ตัวแปร sum =02. กำหนดค่าเริ่มต้นให้ตัวแปรดัชนี i=03. วนลูปwhile i<n ให้ทพดังนี้

a. นำค่าของอาร์เรย์X[i] บวกกับตัวแปร sum

b. เพิ่มค่าให้กับตัวแปร I หนึ่งค่า

4. คำนวณหาค่าเฉลี่ย sum/n และส่งคืนกลับ

เมื่อวินิจฉัยการรับค่า Iจะได้คำอธิบายดังนี้

I: ค่าที่รับเข้ามาประกอบด้วยตัวเลข n ≤ 1 และอาร์เรย์ Xที่เก็บค่าเลขทศนิยมเมื่อวินิจฉัยผลลัพธ์ oออกมาจะได้คำอธิบาย

O: อัลกอริทึมทำงานเสร็จค่าที่ส่งคอนกลับมาให้เป็นค่าเฉลี่ยของX [0],…, X[n-11]

การแสดงผลการทำงานจะได้ว่าเงื่อนไขตอนท้าย O จะเกิดขึ้นได้ตามเงื่อนไขตอนต้น I และมีหลายช่วงของอัลกอริทึมซึ่งเป็นการวินิจฉัยซึ่งเป็นการวินิจฉัยตอนกลาง (Intermediate Assertion) โดยเกี่ยวกับสถานะของการประมวลผลเมื่อทำงานถึงในช่วงนั้น ๆ จากตัวอย่างอัลกอริทึมที่ผ่านมามีการวินิจฉัยตอนกลาง L ในส่วนท้ายของการวนลูป while ซึ่งจะเป็นจริงทุกครั้งเมื่อการทำงานมาถึงช่วงนี้และการวินิจฉัยตอนกลางเรียกว่าการวนลูปสม่ำเสมอ (LoopInvariant)จะได้ว่า

I: ค่าที่รับเข้ามาประกอบด้วยตัวเลขn ≥1 และอาร์เรย์ X ที่เก็บค่าเลขทศนิยม

1 .กำหนดค่าเริ่มต้นให้ตัวแปร sum =0

2.กำหนดค่าเริ่มต้นให้แปรดัชนี i=0

3.whilei<n ให้ทำดังนี้

a. นำค่าของอาร์เรย์ X [i] บวกให้กับตวแปร Sum

b. เพิ่มค่าให้กับตัวแปร I หนึ่งค่า

L : ค่าของตัวแปร I เป็นจำนวนครั้งในการทำงานที่ถึงในแต่ละช่วงและตัวแปร sum เป็นผลรวมของแต่ละสมาชิก I ในอาร์เรย์X

4.คำนวณหาค่าเฉลี่ย Sum /nและส่งค่ากลับ

O: อัลกอริทึมทำงานเสร็จค่าที่ส่งคืนกลับมาให้เป็นค่าเฉลี่ยของ X[0],…,X[n-1]

การตรวจสอบจึงประกอบด้วยการแสดงคำอธิบายใหทราบว่าการวินิจฉัยLได้โดยสมติให้ k เป็นจำนวนครั้งในการทำงานที่ถึงส่วนล่งของการวนลูปให้ikและ sumเป็นค่าของตัวแปร i และ sumตาม่ลำดับของแตละครั้งทีทำงานมาถึงเมี่อk=1เป็นการผ่นรอบแรกในลูปค่าของ iมีค่าเป็น 0 จากค่าเริ่มต้นกับ0(บรรทัด 1) ตัวแปร sum มีค่าเทากับ X[0] (บรรทัด3a)ซึ่งค่าเริ่มต้นเท่ากับ 0(บรรทัด 1) จากนั้นเพิ่ค่าให้กับตัวแปร I หนึ่งค่าจได้i=1 (บรรทัด3b)ดังนั้นจะได้ว่าตัวแปร I และ sum มีค่าที่ถูกวินิจฉัยของL เมื่อ k=1หากสมมุติให้การทำงานเมื่อไปถึงส่วนล่างของการวนลูปสำหรับครั้งที่ k การวนลูปสม่ำเสมอของ Lได้เป็นดังนี้

Ik =kและ sumk =X[0] +….+X[k-1]

ซึ่งสามารถตรวจสอบได้ว่า l เป็นรจริงเช่นกันเมื่อการทำงานต่อไปผ่านไปถึงการวนลูปในครั้งที่ k+1 ซึ่งได้เป็น

Ik+1 =k+1และ sumk+1 = X[0] +….+X[k-1]

ในรอบที่k +1 เมื่อผ่นการวนลูปค่าของ I มีความถูกต้งเพื่อใช้งานดงนี้

Sumk+1 =sumk +X[k](บรรทัดที่3a )

=X[0]+…+X[k](การอนุมานสมมุติ)

และค่าของI จะเพิ่มขึ้นหึ่งค่าดังนี้

Ik+1=ik+1(บรรทัดที่3b)

=k+1(การอนุมานสมมุติ)

จากนี้เมื่อทำค่อเนื่องโดยการอนุมานไปแต่ละครั้งการทำงานไปถึงส่วนล่างของการวนลูปค่าของตัวแปร I และ sum จะถูกวินิจฉัยในการวนลูปสม่ำเสมอ หลังจากการวนลูปทำงานผ่านนิพจน์ i<nซึ่งคบคุการทำงานซ้ำในลูปเป็นเท็จลูปwhile จึงหยุดการทำงานและทำต่อที่ บรรทัด 4 เป็นการคานวณหาค่าฉลี่ยของสมาชิกในอาร์เรย์จากนั้นการทำงานถึงจุดสิ้นสุดของอัลกอริทึมและนำการวินิจฉัยผลลัพธ์มาใช้ดังนั้นการตรวจสอบความถูกต้องของอัลกอริทึมจึงเสร็จสิ้นสมบูรณ์

การตรวจสอบดังกล่าวมีสักษระเรยบง่ายซึ่งมีการวินิจฉับตอนกลางLเพียงตอนเดียว และอยู่ในรูปแบบต่อไปนี้

I=>L=> O

แต่สักหรับอัลกอริทึมที่ซับซอ้นมากขึ้นจำเป็นต้องมีการวินิจฉัยตอนกลางหลายๆ ตอน คือL1,L2,…,Lnดังนั้นอัลกอริทึมหรือโปรแกรมจึงถ฿กแตกออกมาเป็นส่วน ๆ เรียกว่าเซ็กต์เม้นท์ (Segment)ซึ่งอาจเป็นประโยคคำสั่งเดีวบล็อกการวนลูป หรือทั้งโปรแกรม โด่ยแต่ละเซ็กต์เม้นท์จะมีLi หรือ I เป็นเงื่อนไขตอนต้นและมี Li+1 หรือ O เป็นเงื่อนไขตอนท้ายดังในรูปที่8.1

Li

Li+1

รูปที่ 8.1 เซ็กต์เม้นนท์กับเงงื่อนไขตอนต้น และเงื่อนไขตอนท้าย

ถ้าให้Li+1 เกิดขึ้นมาตาม Li สำหรับแต่ละ i=1,…,n-1ใจได้โครงสร้างของการตรวจ สอยความถูกตอ้งเป็นดังนี้

I=> L=> L2=>…=>Ln=> O

หากเซ็กต์เม้นท์ของโปรแกรมมีโครงสร้างการทำงานแบบเรียงลำดับ (Sequential)การตรวจสอบความถูกตอ้งจะทำทีละประโยคคำสั่งตามลำดับถ้ามีโครงสร้างการทำงานเป็ทางเลือกหรือเงื่อนไข (if)ก็จะมีหลายเส้นทางการทำงานเป็นไปได้เดระหว่างจาก LiไปยังLi+1

และมีความจะเป็นจะต้องตรวจสอบเส้นทางการทำงานทั้งหมดทำให้การตรวจสอบความถูกต้องมีความซับซ้อนมากขึ้นซึ่งต้งใช้เวลาและความพยายามเพื่อตรวจสอบอย่างอลเอียดเพื่อให้เกดตวามถูกต้องหากโครงสร้างการทำงานเป็นการวลูปการตรวจสอบจะทำในแต่ละรอบโดยมีตัวควบคุมการวนลูป (Sentinel-contolledLoop)ตัวควบคุมนับจำนวนการวนลูป (Count-controlledLoop)เละเงื่อนไขการวนลูปทั่วไป(General Condition Loop)ซึ่งเป็นการทำงานอื่นๆ ในลูปและช่วยการตรวจสอบ โครงสร้างการทำงานสุดท้ายของเซ็กต์เม้นท์คือ การเรียกฟังก์ชันมาทำงาน (Function Call) ในการตรวจสอบความถูกต้องจะใช้ค่าพารามิเตอร์ต่าง ๆเป็นเงื่อนไขตอนต้นค่าต่าง ๆ ที่ต้องส่งกลับคืนมาเป็นเงื่อไขตอนท้ายและตัวฟังก์ชันเป็นการวินิจฉัยตอนกลาง

ดังนั้นทางเลือกการเขียนแรแกรมที่ดีจึงต้องมีการวางกฎเกณฑ์ในการวินิจฉัยลัคเนินการตรวจสอบตามแนวทางที่วางไว้ และถึงแม้ว่าไม่สามารถรับประกันว่าอัลกอริทึมจะทำงานถูกต้องอย่างสมบูรณ์ แก็ทำให้ผู้เขียนโปรแกรมมีความเข้าใจอัลกอริทึมมากขึ้นและเกิดความมั่นใจในการทำงานที่ถูกต้องหลังจากได้มีการตรวจสอบ

ตัวอย่างการตรวจสอบอัลกอริทึม

ในปี ค.ศ. 1950 คำว่าอ้ลกอริทึมได้ถูกนำมาใช้กับอัลกอริทึมขิงยูคลิด (Euclid’s Algorithm) เป็ฯการหาค่าหารร่วมมาก (ห.ร.ม.)ซ฿งเป็ฯค่าสูงสุดที่สามารดนำไปหารค่าสองค่าได้ลงตัว (GreatestCommon Divisor : GCD)ได้เป็นอัลกอริทึมดังในตารางที่9.2 โดยมีการรับค่าตัวเลขบวก mและnเพื่อหาค่าหารร่วมมากตัวเลขที่รับเข้ามานี้ค่าที่มากกว่าจะว่าจะถูกหารด้วยค่าทีนอยกว่า

ตารางที่ 8.2 อเลกอริทึมของยูคลิด

1 . หารตัวแปร m ด้วยตัวแปร n และเก็บค่าเศษที่เหลือให้กับตัวแปร r2. ถ้าตัวแปร r = 0ให้จบการทำงานและได้ n เป็นค่าหารรวมมาก3. กำหนด ค่า m = n ,n = r และไปทงานต่อในรอบถัดไปที่บรรทัด 1

อัลกอริทึมอื่น ๆ และของยูคลิดเป็นชุดการทำงานเพื่อใช้งานหรือแก้ไขปัญหาบางอย่างโดยการทำงานต้องมีขอบเขตที่สามารถไปถึงจุดสิ้นสุด (Terminate) ได้โดยเฉพาะต้องระมัดระวังการวนลูปที่ไม่สิ้นสุด ( EndlessLoop)หากพิจารณาจากอัลกอริทึมของยูคลุดซึ่งกำหรดให้ m= 144 และ n=60 จะได้ว่าค่าทั้งสองถูกตอ้งเพราะเป็นค่าบวกตามเงื่อนไขตอนต้นและการทำงานของัลกอริทมเป็นารวนลูปสม่ำเสรโดยแต่ละบรรทัดถูเรียกให้ทำงานเป็นไปตามลำดับ ดังนี้

บรรทัดที่ 1:r=240จากการหาร146/60=2 เหลือเศษ24

บรรทัดที่ 2:r ไม่เท่ากับศุนย์

บรรทัดที่ 3:m =60 ,n=24

บรรทัดที่ 1:r =12 จากการหาร 60/24=2 เหลือเศษ12

บรรทัดที่ 2:rไม่เท่ากับศุนย์

บรรทัดที่ 3:m =24 ,n=12

บรรทัดที่ 1:r=0 จากการหาร24/12=2 เหลือเศษ0

บรรทัดที่ 2:r เท่ากับศุนย์นการทำงานและค่าหารร่วมมากเท่ากับ 12

จากการตรวจสอบลำดับการทำงาตั้แต่เงื่อนไขตอนต้นที่ถูกต้องและการทำงานของวนลูปสม่ำเสมอในตอนกลางจนถึงเงื่อนไขตอนท้ายจะได้ค่า 12 เป็นค่าหารร่วมมากของค่า 144และ 60 ดังนั้นอัลกอริทึมนี้ที่งานได้ผลตามที่ตัองการทำงานของอัลกอริทึมที่ถูกต้องและได้ผลตามที่ต้องการในทุกกรณีการเขียนโปรแกรมจึงต้องมีการตรวจสอบความถูกต้องของการทำงานโดยทดสอบช่วงของค่าที่รับเข้ามากับค่าที่เป็นผลลัพธ์ออกมาถ้าโปรแกรมผ่านการทดสอบทุกรูปแบบที่เป็นไปได้ก็จะทำให้ผู้เขียนโปรแกราเกิดความมั่ใจ

อัลกอริทึมของยูคลิดมีการทำงานที่ถึงจุดสิ้นสุดคือค่าที่เหลือเก็บไว้ที่rน้อยกว่าค่าของnและถ้าเริ่มต้นให้n< mในแต่ละรอบการวนลูปทั้งค่าของmและnจะถูกแทนด้วยค่าที่น้อยกว่าซึ่งค่าใหม่ของmยังคงมากกว่าค่าของnจะน้อยลงเรื่อยๆจนเงื่อนไขที่ค่าของr=0เป็นจริงในกรณีโชคร้ายหรือแย่ที่สุดคือค่าของnลดลงเป็น1หากพบว่าเริ่มต้นค่าของn>mจะมีการสลับค่ากันละหว่างmกับnโดยอัลกอริทึมของยูคลิดเขียนเป็นตัวอย่างโปรแกรมได้เป็นตารางที่8.3

ตารางที่ 8. 3 การหาค่าหารร่วมมาก

#include <stdio.h>#include <stelib.h>#include <conio.h>

int euclid

intem;

rem =m%n;

while(rem !=0 ){

m = n ;

m =rem;

rem = m%n;

}

retutn n;

}

main(){

intm,n ;

printf(“Enter first positive integer: “);

scanf(“%d”,&m);

printf(“Enter first positive integer: “);

scanf(“%d”,&n);

printf(“\nGCDof%dand%dis %d \n “,m,n,euclid(m,n));

getch ();

}

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s