อัลกอริทึ่ม

อัลกอริทึม

                  การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบทที่  1  มี 2 ส่วนที่สำคัญคือการเลือกใช้โครงสร้างข้อมูลและการออกแบบอัลกอริทึม (Algorithm) ซึ่งที่ผ่านมาได้กล่าวถึงโครงสร้างข้อมูลพื้นฐานแบบต่างๆ และในบทนี้จะกล่าวถึงรายละเอียดของอัลกอริทึมโดยพิจารณาวิธีการตรวจสอบการทำงานของอัลกอริทึมว่ามีความถูกต้องมากน้อยเพียงใดซึ่งใช้เทคนิคแบบการตรวจสอบความจริง (Verification) นอกจากมีการพิจารณาเปรียบเทียบหลายๆ อัลกอริทึมที่ใช้แก้ปัญหาเรื่องเดียวกันว่ามีประสิธิภาพต่างกันอย่างไรซึ่งมีเทคนิคที่นำมาใช้ตรวจวัดว่าอัลกอริทึมไหนดีกว่ากัน
การตรวจสอบความถูกต้องของอัลกอริทึม
                 การเรียกให้โปรแกรมหรือระบบทำงานแบบเบื้องต้นเพื่อทดสอบกับข้อมูลที่หลากหลาย ยังไม่มีประสิทิภาเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฎอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่รากฎจำม่สามารถทราบได้จึงนำการตรวจสอบแบบการอนุมาน (Deductive) มาใช้เพื่อรับประกันว่าผลลัพฑ์มีความถูกต้อง
      การตรวจสอลอัลกอริทคึมเพื่อใช้แก้ไขปัญหาว่ามีความถูกต้องจึงใฃ้การอนุมานซึ่งแสดงขั้นตอนการประมวลผลของอัลกอริทึมถูกต้องหรือไม่ตั้งแต่มีการรับข้อมูลเข้ามาและแก้ปัญหาจนถุงผลลัพธ์ที่ได้ออกมา  ดังนั้น  การตรวจสอบความถูกต้องของอัลกอริทึม  A  เรื่มต้นด้วยการวินิจฉัย  I  เป็นการสมมุติข้อมูลี่จะรับเข้ามาใช้งาน (Input Assertion)  เรยกว่าเงื่อนไขตอนต้น(Precondition)  และการวินจฉัย   O   เป็นการสรุปผลลัพธ์ที่ได้ออกมา (Output   Assertion)เรียกว่าเงื่อนไขตอนท้าย ( postcondition)ได้เป็นขอ้พิสูจน์ทางตรรกะแสดงให้ทราบว่า Oจะเกิดขึ้นตาม  I และได้เป็น
I => O (“I  Implies O”)
    ได้หลัเกณฑ์  คือ เมือกำหนดเงื่อนไขต้น  I หลังจากอัลกอริทึม  A ทำงานจนถึงงจุดสิ้นสุด (Terminate)จะต้องได้เงื่อนไขตอนท้าย   O  โดยพิจารณาจากตัวอย่างอีลกอริทึมหม่าฉลี่ยของค่าทั้งหมดที่เก็บไว้อาร์เรย์ดังในตารางที่  8.1

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

1. กำหนดค่าเรื่มต้นให้ตัวแปร sum =0
2. กำหนดค่าเรื่มต้นให้ตัวแปรดัชนั i=0
3. วนลูป  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 ซึ่งจะเป็นจริงทุกครั้งเมื่อการทำงานมาถึงช่วงนี้และการวินิจฉัยตอกลางี้เรียกว่าการวนลูปสม่ำเสมอ (Loop  Invariant)  จะได้ว่า
I: ค่าที่รับเข้ามาประกอบด้วยตัเลข  n ≥  1 และอาร์เราย์ X ที่เก็บค่าเลขทศนิยม
1 .  กำหนดค่าเริ่มต้นให้ตัวแปร sum =0
2.     กำหนดค่าเริ่มต้นให้วแปรดัชนี i=0
3. while  i<n ให้ทำดังนี้
a. นำค่าของอาร์เรย์ X [i] บวกให้กับตวแปร Sum
 b. เพิ่มค่าให้กับตัวแปร I หนึ่งค่า
L : ค่าของตัวแปร I เป็นจำนวนครังในการทำงานที่ถึงในแต่ละช่วง   และตัวแปร sum เป็นผลลรวม่าของแตลสมาชิก I ในอร์เรย์ X
4.  คำนวณหาค่าเฉสี่ย Sum /n  และส่งค่ากลับ
O :อัลกอริทึมทำงานเสร็จ  ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉสี่ยของ X[0],…,X[n-1]
          การตรวจสอบจึงประกอบด้วยการแสดงคำอธิบายใหทราบว่าการวินิจฉัย  Lได้โดยสมติให้ k เป็นจำนวนครั้งในการทำงานที่ถึงส่วนล่งของการวนลูปให้  ik  และ sumk เป็นค่าของตัวแปร 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+1 เกิดขึ้นมาตาม Li สำหรับแต่ละ i=1,…,n-1   ใจได้โครงสร้างของการตรวจ สอยความถูกตอ้งเป็น  ดังนี้
     I=> L1 => L2=>…=>Ln=> O
หากเซ็กต์เม้นท์ของโปรแกรมมีโครงสร้างการทำงานแบบเรียงลำดับ (Sequential)การตรวจสอบความถูกตอ้งจะทำทีละประโยคคำสั่งตามลำดับ  ถ้ามีโครงสร้างการทำงานเป็ทางเลือกหรือเงื่อนไข (if)ก็จะมีหลายเส้นทางการทำงานเป็นไปได้เดระหว่างจาก Li ไปยังLi+1
และมีความจะเป็นจะต้องตรวจสอบเส้นทางการทำงานทั้งหมด  ทำให้การตรวจสอบความถูกต้องมีความซับซ้อนมากขึ้น  ซึ่งต้งใช้เวลาและความพยายามเพื่อตรวจสอบอย่างอลเอียดเพื่อให้เกดตวามถูกต้อง  หากโครงสร้างการทำงานเป็นการวลูป  การตรวจสอบจะทำในแต่ละรอบโดยมีตัวควบคุมการวนลูป (Sentinel-contolled  Loop)ตัวควบคุมนับจำนวนการวนลูป (Count-controlled  Loop)เละเงื่อนไขการวนลูปทั่วไป(General Condition Loop)ซึ่งเป็นการทำงานอื่นๆ ในลูปและช่วยการตรวจสอบ โครงสร้างการทำงานสุดท้ายของเซ็กต์เม้นท์  คือ การเรียกฟังก์ชันมาทำงาน (Function Call) ในการตรวจสอบความถูกต้องจะใช้ค่าพารามิเตอร์ต่าง ๆ  เป็นเงื่อนไขตอนต้น  ค่าต่าง ๆ ที่ต้องส่งกลับคืนมาเป็นเงื่อไขตอนท้าย  และตัวฟังก์ชันเป็นการวินิจฉัยตอนกลาง
                ดังนั้น   ทางเลือกการเขียนแรแกรมที่ดีจึงต้องมีการวางกฎเกณฑ์ในการวินิจฉัยลัคเนินการตรวจสอบตามแนวทางที่วางไว้  และถึงแม้ว่าไม่สามารถรับประกันว่าอัลกอริทึมจะทำงานถูกต้องอย่างสมบูรณ์ แก็ทำให้ผู้เขียนโปรแกรมมีความเข้าใจอัลกอริทึมมากขึ้นและเกิดความมั่นใจในการทำงานที่ถูกต้องหลังจากได้มีการตรวจสอบ
ตัวอย่างการตรวจสอบอัลกอริทึม
ในปี ค.ศ. 1950 คำว่าอ้ลกอริทึมได้ถูกนำมาใช้กับอัลกอริทึมขิงยูคลิด (Euclid’s Algorithm) เป็ฯการหาค่าหารร่วมมาก (ห.ร.ม.)ซ฿งเป็ฯค่าสูงสุดที่สามารดนำไปหารค่าสองค่าได้ลงตัว (Greatest  Common Divisor : GCD)ได้เป็นอัลกอริทึมดังในตารางที่9.2 โดยมีการรับค่าตัวเลขบวก mและnเพื่อหาค่าหารร่วมมาก  ตัวเลขที่รับเข้ามานี้ค่าที่มากกว่าจะว่าจะถูกหารด้วยค่าทีนอยกว่า

 อเลกอริทึมของยูคลิด
1 . หารตัวแปร m ด้วยตัวแปร n และเก็บค่าเศษที่เหลือให้กับตัวแปร r
2. ถ้าตัวแปร r = 0ให้จบการทำงานและได้ n เป็นค่าหารรวมมาก
3. กำหนด ค่า m = n ,n = r และไปทงานต่อในรอบถัดไปที่บรรทัด 1
 อัลกอริทึมอื่น ๆ และของยูคลิดเป็นชุดการทำงานเพื่อใช้งานหรือแก้ไขปัญหาบางอย่างโดยการทำงานต้องมีขอบเขตที่สามารถไปถึงจุดสิ้นสุด (Terminate) ได้โดยเฉพาะต้องระมัดระวังการวนลูปที่ไม่สิ้นสุด ( Endless  Loop)  หากพิจารณาจากอัลกอริทึมของยูคลุดซึ่งกำหรดให้ 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  โดยอัลกอริทึมของยูคลิดเขียนเป็นตัวอย่างโปรแกรมได้