วันอาทิตย์ที่ 23 กันยายน พ.ศ. 2555

เขียนโดย ที่ ไม่มีความคิดเห็น:

วันศุกร์ที่ 21 กันยายน พ.ศ. 2555

พื้นฐานโครงสร้างข้อมูล

คอมพิวเตอร์เป็นอุปกรณ์ที่สร้างขึ้นมาเพื่อใช้จัดการและ เปลี่ยนแปลงข้อมูลข่าวสาร (Information) ดังนั้น จึงต้องมีการศึกษาถึงการควบคุมดูแลการทำงานของคอมพิวเตอร์ที่ยุ่งเกี่ยวกับ ข้อมูลข่าวสาร เมื่อมีการเปลี่ยนแปลงแก้ไขหรือเพื่ออำนวยประโยชน์ที่ต้องการการทำงานเพื่อน แก้ไขปัญหาต่าง ๆ ด้วยระบบคอมพิวเตอร์จะประกอบด้วยส่วนต่าง ๆ ทางด้านฮาร์ดแวร์ (Hardware) เช่น ซีพียู (CPU) หน่วยความจำ (Memory) อุปกรณ์รับส่งข้อมูล(Input/Output Device)และซอฟแวร์(Software)ที่นำมาใช้ควบคุมการทำงานของฮาร์ดแวร์ เพื่อแก้ไขปัญหานั้น ๆ ในการแก้ไขปัญหาจึงต้องมีกระบวนการพัฒนาซอฟต์แวร์ (Software Development) ที่เป็นขั้นตอนมาใช้ดังนี้
ขั้นตอนการพัฒนาซอฟแวร์
การแยกแยะและวิเคราะห์ปัญหา
                ในขั้นตอนแรกเป็นการแก้ไขปัญหาโดยการวิเคราะห์และแยกแยะ สิ่งแรกที่ต้องพิจารณา คือ เอาต์พุต ที่ต้องการและมีข้อมูลข่าวสารอะไรบ้างที่ทำที่ทำให้สามารถแก้ไขปัญหาได้หลัง จากพิจารณาเอ้าท์พุตก็คือพิจารณาอินพุต และมีข้อมูลข่าวสารอะไรบ้างที่ทำให้สามารถแกไขปัญหาได้ หลังจากแยกแยะเอ้าท์พุตและอินพุต รวมถึงข้อมูลข่าวสารที่ต้องการเสร็จสิ้นลงก้เป็นการพัฒนาเขียนอัลกอรึทึมและ โปรแกรม
การออกแบบระบบ
                เนื่องจากระบบคอมพิวเตอร์ไม่สามารถที่จะเข้าใจและแกไขปัญหาบางอย่างได้ จึงต้องมีวิธีการที่จะแก้ไขปัญหาโดยการออกแบบระบบ ซึ่งเป็นการวางแผนออกแบบที่แยกแยะออกเป็นปัญหาย่อย และพิจารณาสร้างชุดคำสั่งเพื่อแก้ไขปัญหาย่อยนั้น จากนั้นมารวมกันเป็นระบบที่สามารถแก้ไขปัญหาทั้งหมด มีลักษณะการวางแผนออกแบบจากบนลงล่าง (Top-down Design) ซึ่งประกอบด้วย 2 ส่วนหลัก ๆ คือ
                1. โครงสร้างข้อมูล (Data Strutcure) ใช้ควบคุมและจัดการกับข้อมูลของปัญหานั้น ๆ หรือที่เรียกว่าชนิดข้อมูลมีโครงสร้าง เรียกสั้น ๆ ว่าชนิดข้อมูล เช่น ชนิดข้อมูลอาร์เรย์ ชนิดข้อมูลสแตก และชนิดข้อมูลลิ้งค์ ลิสต์ การออกแบบระบบต้องเลือกใช้โครงสร้างข้อมูลอย่างเหมาะสมเพื่อจัดการกับข้อมูล ที่ใช้ในระบบ
                2. การออกแบชุดคำสั่ง (Module Design) ในการแก้ไขปัญหาจะต้องมีกระบวนการทำงานเพื่อให้ได้มาซึ่งข้อมูลข่าวสารหรือ เอ้าท์พุต ที่ต้องการโดยชุดคำสั่งเป็นส่วนประกอบของระบบ จึงต้องมีการออกแบบการทำงานที่เป็นชุดคำสั่งหรือโมดุลนั้นๆ และเรียกว่า อัลกอรึทึม ได้เป็น
โครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม
                การที่จะเลือกใช้โครงสร้างข้อมูลและอัลกอริทึมในการออกแบบให้การทำงานอย่ส งมีประสิทธิภาพ  ซึ่งถือว่าเป็นหัวใจสำคัญของการออกแบบซอฟต์แวร์จะพิจารณาได้จากลักษณะดังต่อ ไปนี้
  1. ความถูกต้อง
  2. ระยะเวลาการทำงาน
  3. จำนวนพื้นที่ใช้งาน
  4. ความเรียบง่าย
  5. ความเหมาะสมที่สุด
การเขียนคำสั่งและรวมกัน
                การเขียนคำสั่ง (Coding) คือ การเขียนคำสั่งต่าง ๆ ของโปรแกรมให้ทำงานเป็นไปตามโครงสร้างข้อมูลและอัลกอริทึมด้วยภาษาเขียน โปรแกรมภาหนึ่ง ถ้าโครงสร้างข้อมูลและอัลกอริทึมถูกออกแบบไว้เป็นอย่างดีทำให้กระบวนการแปลง คำสั่งจากภาษาเขียนให้เป็นภาษาเครื่องก็จะง่ายไม่ยุ่งยากลำบาก
                การรวมกัน (Integration) เป็นกระบวนการนำคำสั่งต่าง ๆ ที่เขียนเป็นแต่ละชุดคำสั่งมารวมกันและให้มีการทำงานร่วมกันได้เป็นซอฟต์แวร์โปรแกรมขึ้นมา
                การเขียนโปรแกรมที่ดีนั้นจะต้องมีความถูกต้องในการทำงาน สามารถอ่านคำสั่งและทำความเข้าใจได้ง่าย จึงต้องมีโครงสร้างการเขียนโปรแกรมที่ดี ซึ่งมีวิธีการเข้ามาช่วยเหลือในการเขียนโดยพิจารณาได้จากเรื่องต่อไปนี้
                1. การเขียนโปรแกรมควรเป็นแบบบนลงล่าง (Top-Down) โดยเฉพาะกับปัญหาที่มีขนาดใหญ่หรือมีความซับซ้อน จึงควรแยกปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ จากการเขียนคำสั่งทั้งหมดในโปรแกรม ก็แยกเป็นชุดคำสั่งย่อย ๆ
                2. ใช้โครงสร้างควบคุมการทำงาน (Control Structure) ในการเขียนโปรแกรมหรือชุดคำสั่ง เช่น การใช้เงื่อนไข IF การใช้วนลูปแบบต่าง ๆ
                3. ควรใช้ตัวแปรที่เป็นแบบโลคอล (Local Variable) และใช้กับชุดคำสั่งเพื่อแก้ปัญหาย่อย
                4. ควรใช้ตัวแปรพารามิเตอร์ (Parameter)  กับชุดคำสั่งเพื่อแก้ไขปัญหาย่อย หลีกเลี่ยงที่จะใช้ตัวแปรที่เป็นแบบโกลบอล และตัวพารามิเตอร์ควรมีการป้องกันหากมีการแก้ไขค่า
                5. นำตัวแปรค่าคงที่ ( Constant Variable) มาใช้ จะช่วยให้การเขียนโปรแกรมมีความยืดหยุ่นมากขึ้นและอ่านเข้าใจง่าย
                6. การเขียนโปรแกรมควรมีการจัดพื้นที่หรือบรรทัดว่างเพื่อให้อ่านสะดวก มีการย่อหน้าเพื่อจัดระดับของคำสั่งและมีลักษณะที่เป็นกรอบ
ทดสอบความถูกต้อง
                1. การตรวจคำสั่ง (Validation) เป็นการตรวจสอบการเขียนโปรแกรมว่ามีความถูกต้องตามโครงสร้างของภาษาและทำงานตรงตามที่ต้องการหรือไม่
                2. การตรวจสอบความจริง (Verification) เป็นการตรวจสอบขั้นตอนการทำงานของโปรแกรมว่ามีความถูกต้องและสอดคล้องกัน หรือไม่
                3. การทดสอบ (Testing) เป็นการทดสอบการทำงานว่าในแต่ละส่วนหรือชุดคำสั่งและการทำงานทั้งหมดใน โปรแกรมมีความถูกต้องหรือไม่ มีการทดสอบแต่ละยูนิต   ทดสอบการรวมกันของยูนิต
การดูแลระบบ
                หลังจากการพัฒนาซอฟต์แวร์เสร็จสมบูรณ์และนำไปใช้งาน  หากมีความต้องการที่จะเปลี่ยนแปลงแก้ไขเพื่อเติม  หรือโปรแกรมมีปัญหาเกิดขึ้น  จึงต้องมีการดูแลระบบ เพื่อนำกลับมาปรับปรุงแก้ไขใหม่ให้เป็นไปตามความต้องการ
ความหมายโครงสร้างข้อมูล/ชนิดข้อมูล
                การทำงานของคอมพิวเตอร์จะมีการจัดการอย่างไรเพื่อให้ได้มาซึ่งข้อมูลข่าว สาร   และสามารถนำมาใช้งานออกมาเป็นข้อมูลข่าวสารในรูปแบบต่าง ๆ  ที่ทำความเข้าใจได้  แต่เนื่องจากคอมพิวเตอร์เป็นเพียงเครื่องจักรที่ไม่สามารถเข้าใจความหมายของ ข้อมูลข่าวสารได้เช่นเดียวกับคน  จึงมีการกำหนดรูปแบบที่ใช้สื่อความหมายของข้อมูลข้าวสารให้คอมพิวเตอร์กับ ผู้ใช้งานเข้าในตรงกันเรียกว่า โครงสร้างข้อมูลหรือชนิดข้อมูล โดยแบ่งออกได้เป็นดังนี้

บิต (Bit)
                เป็นหน่วยที่เล็กที่สุดในการทำงานของคอมพิวเตอร์ที่แสดงเป็นสถานะได้ 2 สถานะ คือ เปิดกับปิด จึงกำหนดเป็นการเก็บค่าได้ 2 ค่า คือ 0 กับ 1 เรียกว่าไบนารี่ดิจิต (Binary Digit)
ไบต์ (Byte)
                เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดค่าได้มากขึ้น เช่น 3 บิต มาต่อเรียงกันจะทำให้เกิดสถานะที่ต่างกันคือ 000,001,010,100,011,010, และ 111 ก็จะได้เป็น 8 สถานะ เมื่อนำบิตมาเรียงต่อรวมกันเป็น 8 บิต เรียกว่าไบต์ มี 256 สถานะ และกำหนดเป็นโครงสร้างข้อมูลที่มีขนาดเล็กที่สุดที่ใช้งานได้ มีค่าตั้งแต่ 0 – 255 (00000000 – 11111111)
เลขจำนวนเต็ม (Integer)
                เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดเป็นเลขจำนวนเต็ม ซึ่งได้เป็นระบบเลขฐานสอง โดยแต่ละบิตมีความหมายเป็นเลขยกกำลังสอง เช่น 20 = 1, 23 = 8 หรือ
21 + 22 +25 = 2+4+32 = 38 เลขที่ได้เป็นเลขจำนวนเต็มบวก ถ้าต้องการเป็นเลขจำนวนเต็มลบ จะต้องใช้วิธีการเรียกว่า One-complement Notation โดยการเปลี่ยนค่าของบิตที่เป็น 0 ให้เป็น 1 และค่าที่เป็น 1 ให้เป็น 0 เช่น 00100110 = 38 เมื่อสลับค่าจะได้บิต 11011001 = -38 ด้วยวิธีนี้ทำให้เก็บค่าได้ทั้งเลขจำนวนเต็มบวกและเต็มลบ ซึ่งมีบิตซ้ายสุดเป็นตัวกำหนดให้มีค่าบวกหรือลบเรียกว่า Sign Bit เมื่อนำบิตมาเรียงต่อกัน 16 บิตได้เป็นเลขจำนวนเต็มฐานสิบ มีอีกวิธีคือ Two-complement Notation โดยการบวกค่า 1 เข้าไปกับค่าของ One-complement Notation  เช่นจาก 11011001 = -38 เมื่อบวก 1 จะได้ 11011010 = -38 เช่นกัน แต่วิธีนี้จำทำให้เก็บค่าได้มากกว่า คือ มีตั้งแต่ -2n-1 ถึง 2n-1 -1 ดังต่อไปนี้
1000000000000000 = -32768                         0000000000000000 = 0
1000000000000001 = -32767                         0000000000000001 = 1
1000000000000010 = -32766                         0000000000000010 = 2
1111111111111101 = -3                                  0111111111111101 = 32765
1111111111111110 = -2                                  0111111111111110 = 32766
1111111111111111 = -1                                  0111111111111111 = 32767


เลขจำนวนจริง (Real Number)
                เป็นรูปแบบของตัวเลขที่มีเลขทศนิยมเรียกว่า Floating – point Number โดยทำการแบ่งบิตออกเป็นสองส่วน โดยบิตที่อยู่ด้านซ้ายเก็บค่าเป็นตัวเลขจำนวนเต็ม เรียกว่า แมนทิสสา (Mantissa) การเก็บค่าเป็นแบบเดียวกับตัวเลขจำนวนเต็ม ส่วนบิตที่อยู่ด้านขวาเก็บค้าเป็นจำนวนหลักของ เลขทศนิยมเรียกว่า เอ็กซ์โพเนนท์ (Exponent) ในการเก็บจะใช้วิธี Two – complement Notation ซึ่งได้มาจากเลขยกกำลังของ 10 เช่น .01 = 10-2, 6.25 x 10-2 การเก็บค่าเลขทศนิยมจะใช้บิตจำนวน 32 บิต โดยแบ่งส่วนที่เป็นแมนทิสสาจำนวน 24 บิต และส่วนที่เป็นเอ็กซ์โพเนนท์จำนวน 8 บิต ดังนี้
                00000000000000000000000000000000 = 0
                00000000000000000000110000000011 = 12000
                00000000000000000000010111111111 = 0.5
                00000000000000000000010111111010 = 0.000005
                11111111011010001001111111111110 = -387.53
ตัวอักษร (Character)
                เป็นการเก็บค่าที่เป็นตัว อักษร แต่เนื่องจากคอมพิวเตอร์ไม่สามารถเข้าใจจึงใช้เลขจำนวนเต็มสื่อความหมายแทน โดยใช้บิตจำนวน 8 บิต เรียกว่า Bit String ซึ่งค่าตัวเลขที่ได้จะกำหนดเป็นตัวอกษรหนึ่งตัว ดังนั้นจะได้ตัวอักษรทั้งหมด 256 ตัวที่เรียกว่าเอ็บซีดิก (EBCDIC) เช่น
 ตัวอักษรA จะมีค่า 01000001 = 65 หรือ B มีค่า 01000010 = 66 ประกอบด้วยอักษรตัวเล็ก ตัวใหญ่ ตัวเลข และตัวอักษรพิเศษ และที่ใช้เพียง 7 บิตเรียกว่าวหัสแอสกี (ASCII Code) ใช้ครึ่งเดียวของเอ็บซีดิกแต่การทำงานรวดเร็วกว่า เมื่อใดที่นำตัวอักษรหลาย ๆ ตัวมาเรียงต่อกันก็จะได้เป็นข้อความ เช่น AB จะได้เป็น 0100000101000010 หากต้องการเก็บจำนวนรูปแบบของตัวอักษรมากกว่านี้ก็สามารถทำได้โดยการเพิ่ม จำนวนบิตเข้าไป ซึ่งขึ้นกับสถาปัตยกรรมของคอมพิวเตอร์จะรับได้หรือไม่ เช่นใช้ 10 บิตก็จะได้ตัวอักษร 1024 รูปแบบ
โครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม
                จากรูปแบบต่าง ๆ ของส่วนที่เป็นข้อมูลข่าวสาร คอมพิวเตอร์ไม่สามารถจะให้ความหมายได้ว่าคืออะไร แต่เมื่อนำการจัดการให้มีการทำงานที่เป็นรูปแบบตามที่กำหนดก็จะสามารถสื่อ ความหมายขึ้นมาได้ ด้วยกระบวนการจัดการแบบนี้จะเรียกว่าโครงสร้างข้อมูลหรือชนิดข้อมูลและด้วย วิธีการดังกล่าวจึงนำไปใช้ในการแก้ปัญหาต่าง ๆได้
               
โครงสร้างข้อมูลมีส่วนสำคัญในระบบคอมพิวเตอร์ ตัวแปรทุกตัวต้องมีการกำหนดชนิดข้อมูลซึ่งอาจเปิดเผยชัดเจน หรือปิดบังไว้ โครงสร้างข้อมูลเหล่านี้จึงมีลักษณะทางตรรกะ  แต่ในทางกายภาพ อาจมีความแตกต่างกัน โครงสร้างข้อมูลสามารถแบ่งออกเป็นแต่ละประเภทดังในรูปที่ 1.1 ซึ่งแบ่งตามลักษณะวิธีการจัดเก็บข้อมูล
โครงสร้างข้อมูลเบื้องต้น
โครงสร้างข้อมูล
เรียบง่าย
โครงสร้างข้อมูลซับซ้อน
การจัดการแฟ้มข้อมูล
เชิงเส้น
ไม่เป็นเชิงเส้น
ไบนารี
N-อาร์เรย์
เลขจำนวนเต็ม อาร์เรย์ สแตก ไบนารีทรี กราฟ แฟ้มข้อมูลลำดับ
เลขทศนิยม สตริง คิว ไบนารีเสิร์ชทรี ทรี แฟ้มข้อมูลโดยตรง
บูลีน เรคคอร์ด ลิ้งลิสต์
เสิร์ชทรี M-ทาง แฟ้มข้อมูลลำดับเชิงดัชนี
ตัวอักษร
บีทรี แฟ้มข้อมูลหลายคีย์

บี*-ทรีมบีพลัว-ทรี
ทราย
รูปที่ 1.1 ประเภทของโครงสร้างข้อมูล
                1. โครงสร้างข้อมูลเบื้องต้น (Primitive Data Structure) เป็นชนิดข้อมูลที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอย เมื่อต้องการเก็บค่าสามารถเรียกใช้งานได้ทันที บางครั้งเรียกว่าชนิดข้อมูลพื้นฐาน (Base Type) หรือสร้างมาให้ใช้ด้วยภาษานั้น ๆ
                ส่วนโครงสร้างข้อมูลแบบอื่น ๆ จะมีโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ เมื่อต้องการใช้จะต้องกำหนดรูปแบบรายละเอียดโครงสร้างขึ้นมาก่อนเรียกว่า ข้อมูลชนิดผู้ใช้กำหนด
(Uses-defined Type) ดังนี้
                2. โครงสร้างข้อมูลแบบเรียบง่าย (Simple Data Structure) จะมีสมาชิกที่เป็นโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ มีรูปแบบง่าย ๆ ไม่ซับซ้อน สามารถทำความเข้าใจและสร้างขึ้นมาใช้งานได้ง่าย
                3. โครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) เป็นโครงสร้างที่ความซับซ้อนมากขึ้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงต่อกันเป็นแนวเส้น
               
4. โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) เป็นโครงสร้างที่มีความซับซ้อนเช่นกัน ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงกันในรูปแบบไบนารี่ ที่จัดเรียงสมาชิกมีการแยกออกเป็นสองทาง และแบบ N- อาร์เรย์ ที่จัดเรียงสมาชิกมีการแยกออกได้หลายทางหลายรูปแบบไม่แน่นอน
5. โครงสร้างการจัดการแฟ้มข้อมูล (File Organization) เป็นโครงสร้างสำหรับนำข้อมูลเก็บไว้ในหน่วยความจำสำรอง โดยข้อมูลจะอยู่ในรูปแบบโครงสร้างข้อมูลอื่น และมีวิธีการจัดการโดยการนำโครงสร้างข้อมูลอื่น ๆ มาช่วย
โครงสร้างข้อมูลต่าง ๆที่กล่าวมาอาจต้องมีการควบคุมการทำงานที่เกี่ยวข้องกับข้อมูลและส่วนที่มา เกี่ยวข้องให้เป็นไปตามที่ต้องการเรียกว่า โครงสร้างข้อมูลนามธรรม ลักษณะโครงสร้างจะแบ่งออกเป็น 2 ส่วน คือ ส่วนข้อมูลและส่วนปฏิบัติการ โดนภายในจะมีรายลเอียดการทำงานต่าง ๆ ประกอบด้วยโครงสร้างการจัดเก็บข้อมูลและอัลกอริทึม เมื่อใดที่เรียกใช้งานโครงสร้างนามธรรมในส่วนรายละเอียดการทำงานจะไม่ถูก เกี่ยวข้องหรือมีผลกระทบโดยถูกปิดบังไว้ จะเห็นว่าโครงสร้างข้อมูลซับซ้อนจะเป็นโครงสร้างข้อมูลนามธรรมที่ต้องมีส่วน การจัดเก็บข้อมูลและส่วนปฏิบัติการ
โครงสร้างข้อมูลกับภาษาเขียนโปรแกรม
                ภาษาเขียนโปรแกรม (Programming Language) ช่วยให้ผู้เขียนโปรแกรมสามารถกำหนดโครงสร้างข้อมูลที่มีความหมายให้กับตำแปร เนื่องจากตัวแปรเหล่านี้ต้องเก็บค่าตามลักษณะของโครงสร้างข้อมูลที่ได้กำหนด มาและส่วนของการปฏิบัติการที่ช่วยให้การทำงานกับโครงสร้างข้อมูลมีความถูก ต้อง ภาษาเขียนโปรแกรมหลายภาษาจะมีแนวทางที่แตกต่างกันในการกำหนดโครงสร้างข้อมูล มาให้ใช้ เช่น ภาษาซี(C) อนุญาตให้โครงสร้างข้อมูลตัวอักษรกับเลขจำนวนเต็มสามารถใช้ร่วมกันและคำนวณ ได้ ภาษาปาสคาล (Pascal) จะต้องประกาศตัวแปรอย่างชัดเจนว่ากำหนดโครงสร้างข้อมูลเป็นแบบใด ขณะที่ภาษาฟอร์แทรน(Fortran) เป็นการประกาศปิดบังไว้จึงไม่ต้องกำหนดโครงสร้างข้อมูลให้กับตัวแปร
เขียนโดย ที่ ไม่มีความคิดเห็น:

การอธิบายการประมวลผล (Process Description)

การอธิบายการประมวลผล (Process Description)


  การวิเคราะห์ความต้องการของผู้ใช้โดยการใช้แผนภาพการไหลของข้อมูล (Data Flow Diagram) โดย การเขียนสัญลักษณ์การประมวลผลนั้นจะเขียนเพียงหัวข้อในการประมวลผลเท่านั้น ยังไม่มีการเขียนคำอธิบายโดยละเอียด ซึ่งเราสามารถเขียนอธิบายโดยละเอียดได้ด้วยการเขียนคำอธิบายการประมวลผล (Process Description) หรือ Process Specification
จุดประสงค์ของการเขียน Process Specification เพื่อ ใช้เป็นสื่อระหว่างผู้ใช้ระบบโปรแกรมเมอร์ และนักวิเคราะห์ระบบ ได้เข้าใจตรงกันในการประมวลผลนั้น โดยโปรแกรมเมอร์จะเข้าใจการประมวลผลนั้นเพื่อใช้ในการเขียนโปรแกรม โดยเฉพาะในกรณีของการมีโปรแกรมเมอร์หลายคนในการเขียนโปรแกรมในการสื่อให้ เข้าใจตรงกัน ส่วนผู้ใช้ระบบจะได้เห็นถึงผลการวิเคราะห์ของนักวิเคราะห์ระบบว่าเข้าใจถูก ต้องหรือไม่

จุดมุ่งหมายในการใช้การอธิบายการประมวลผลนั้นสรุปได้ 3 ข้อคือ

1.เพื่อให้การประมวลผลนั้นชัดเจน เข้า ใจง่าย การใช้วิธีนี้จะทำให้ผู้วิเคราะห์ได้เรียนรู้รายละเอียดเกี่ยวกับขั้นตอนใน การประมวลผลการทำงานในส่วนที่ไม่ชัดเจนต่างๆ จะถูกบันทึก และเขียนออกมาให้ชัดเจนยิ่งขึ้น โดยจะรวมมาจากการสืบค้นข้อมูลที่ได้จากการสืบค้นข้อมูลวิธีต่างๆ
2.เพื่อให้เกิดความเข้าใจถูกต้องในการอธิบายในรูปแบบเฉพาะของการประมวลผลนั้นระหว่างนักวิเคราะห์ระบบและโปรแกรมเมอร์ ใน การสื่อถึงกันให้เข้าใจตรงกันระหว่างนักวิเคราะห์และโปรแกรมเมอร์นั้น ถ้าไม่สื่อกันให้ชัดเจนจะมีผลตามมาอย่างมากเมื่อลงรหัสโปรแกรม เนื่องจากจะต้องเสียเวลา เสียค่าใช้จ่าย และอาจทำให้การบริหารโครงการไม่เป็นไปตามกำหนดเวลาอีกด้วย ดังนั้นในการอธิบายการประมวลผลจึงมีส่วนช่วยอย่างมากในการสื่อการประมวลผล ให้เกิดความเข้าใจตรงกันระหว่างนักวิเคราะห์ระบบและโปรแกรมเมอร์
3.เพื่อตรวจสอบการออกแบบระบบ โดย การประมวลผลนั้นจะถูกต้องหรือไม่ในด้านข้อมูลที่ป้อนเข้าเครื่อง การออกรายงานทั้งหน้าจอ และการพิมพ์รายงานนั้นจะเป็นไปตามการวิเคราะห์ตามแผนภาพการไหลของข้อมูล (Data Flow Diagram) หรือ ไม่ จะสามารถตรวจสอบได้จากการอธิบายการประมวลผลนี้ การเขียนคำอธิบายการประมวลผลนี้จะมีเฉพาะโพรเซสในระดับล่างสุดเท่านั้น ระดับแม่เราจะไม่เขียนคำอธิบายเนื่องจากเราเขียน DFD ระดับแม่เพื่อใช้เป็นเครื่องมือเขียน DFD ระดับลูกเพื่อให้เกิดการแตกโครงสร้างแบบบน-ลง-ล่าง (Top - Down) และเมื่ออธิบายโพรเซสระดับลูกแล้วก็หมายความรวมถึงการทำงานระดับแม่โดยปริยาย


วิธีการที่ใช้อธิบายการประมวลผลที่จะกล่าวในที่นี้มีอยู่ด้วยกัน 2 วิธีคือ

  ประโยคโครงสร้าง (Structure Sentences)
  การตัดสินใจแบบตาราง (Description Tables)

 เรา จะเลือกใช้วิธีการอันใดอันหนึ่งหรือใช้ปนกันก็ได้ขึ้นอยู่กับความเหมาะสม แต่ไม่ว่าจะเขียนด้วยวิธีใดๆ เมื่อเขียนแล้วควรจะมีคุณสมบัติ ดังนี้
เขียน แล้วคำอธิบายนั้นสามารถนำมาตรวจสอบความถูกต้องกับผู้ใช้ได้ง่ายการเขียนเป็น ประโยคโครงสร้างอาจจะไม่เหมาะสมถ้าต้องนำมาตรวจสอบกับผู้ใช้เพราะว่าคำ อธิบายนั้นจะยาวและคำอธิบายเกี่ยวกับเงื่อนไข หรือการทำงานซ้ำก็เขียนไม่สะดวก ตัวอย่างเช่น เงื่อนไขที่มี AND,OR หรือ NOT เป็นต้น
เขียน แล้วคำอธิบายนั้นควรจะใช้สื่อสารกับผู้อื่นที่เกี่ยวข้องในระบบได้ง่ายผู้ อื่นที่เกี่ยวข้องอาจจะเป็นผู้ใช้ ผู้จัดการ ผู้ตรวจสอบ เป็นต้น การเขียนคำอธิบายเป็นประโยคโครงสร้าง หรือเขียนเป็นการตัดสินใจแบบตารางจะเหมาะสมกับบุคคลเหล่านั้นเพราะว่าทั้ง 2วิธีนั้นง่ายต่อการทำความเข้าใจถึงแม้ว่าอาจจะยาวไปหน่อยก็ตาม
โดย ทั่วไปแล้ววิธีการเขียนแบบประโยคโครงสร้างเป็นที่นิยมใช้กันมากที่สุด และในโครงการเดียวกันควรจะเลือกใช้วิธีเดียวกันเพื่อให้ง่ายต่อการสื่อสาร การจะเลือกใช้วิธีการมากกว่าหนึ่งวิธีก็อาจจะเป็นไปได้
ทั้งนี้ขึ้นอยู่กับ

  ความชอบของผู้ใช้
  ความชอบของผู้เขียน (นักวิเคราะห์ระบบ)
  ลักษณะการทำงานของโพรเซส
เขียนโดย ที่ ไม่มีความคิดเห็น:

Selection

Selection

โครงสร้างการทำงานแบบมีการเลือกเป็นโครงสร้างที่ใช้การตรวจสอบเงื่อนไขเพื่อการทำงานอย่างใดอย่างหนึ่ง โดยโครงสร้างแบบนี้จะมีอยู่ด้วยกัน 2 รูปแบบ คือ IF - THEN - ELSE และ IF - THENN

โครงสร้างแบบ IF - THEN - ELSE เป็นโครงสร้างที่จะทำการเปรียบเทียบเงื่อนไขที่ใส่ไว้ในส่วนหลังคำว่า IF และเมื่อได้ผลลัพธ์จากการเปรียบเทียบก็จะเลือกว่าจะทำงานต่อในส่วนใด กล่าวคือถ้าเงื่อนไขเป็นจริง ( TRUE ) ก็จะเลือกไปทำงานต่อที่ส่วนที่อยู่หลังTHEN แต่ถ้าเงื่อนไขเป็นเท็จ ( FALSE ) ก็จะไปทำงานต่อในส่วนที่อยู่หลังคำว่า ELSEแต่ถ้าสำหรับโครงสร้างแบบ IF - THEN เป็นโครงสร้างที่ไม่มีการใช้ ELSE ดังนั้น ถ้ามีการเปรียบเทียบเงื่อนไขที่อยู่หลัง IF มีค่าเป็นจริง ก็จะไปทำส่วนที่อยู่หลัง Then แต่ถ้าเงื่อนไขเป็นเท็จ ก็จะไปทำคำสั่งที่อยู่ถัดจาก IF - THEN แทนตัวอย่าง 3 การเขียนผังงานอ่านค่าข้อมูลเข้ามาเก็บไว้ในตัวแปร A และ B แล้วทำการเปรียบเทียบในตัวแปรทั้งสอง โดยมีเงื่อนไขดังนี้ถ้า A มากกว่า B ให้คำนวณหาค่า A - B และเก็บผลลัพธ์ไว้ในตัวแปรชื่อ RESULTถ้า A น้อยกว่าหรือเท่ากับ B ให้คำนวณหาค่า A + B และเก็บผลลัพธ์ไว้ในตัวแปรชื่อ RESULT
ตัวอย่าง 4 การเขียนผังงานเปรียบเทียบค่าข้อมูลที่เก็บอยู่ในตัวแปร X โดยมีเงื่อนไขดังนี้ถ้า X > 0 ให้พิมพ์คำว่า " POSITIVE NUMBER "ถ้า X < 0 ให้พิมพ์คำว่า " NEGATIVE NUMBER "ถ้า X = 0 ให้พิมพ์คำว่า " ZERO NUMBER "

เขียนโดย ที่ ไม่มีความคิดเห็น:

โครงสร้างการทำงานแบบมีการทำงานซ้ำ

โครงสร้างการทำงานแบบมีการทำงานซ้ำ


เป็นโครงสร้างที่มีการประมวลผลกลุ่มคำสั่งซ้ำหลายครั้ง ตามลักษณะเงื่อนไขที่กำหนด อาจเรียก การทำงานซ้ำแบบนี้ได้อีกแบบว่า การวนลูป ( Looping ) โครงสร้างแบบการทำงานซ้ำนี้จะมีอยู่ 2 ประเภท คือ
DO WHILE
DO UNTILDO WHILE
เป็นโครงสร้างที่มีการทดสอบเงื่อนไขก่อน ถ้าเงื่อนไขเป็นจริงก็จะเข้ามาทำงานในกลุ่มคำสั่งที่ต้องทำซ้ำ ซึ่งเรียกว่าการเข้าลูป หลังจากนั้นก็จะย้อนกลับไปตรวจสอบเงื่อนไขใหม่อีก ถ้าเงื่อนไขยังคงเป็นจริงอยู่ ก็ยังคงต้องทำกลุ่มคำสั่งซ้ำหรือเข้าลูปต่อไปอีก จนกระทั่งเงื่อนไขเป็นเท็จ ก็จะออกจากลูปไปทำคำสั่งถัดไปที่อยู่ถัดจาก DO WHILE หรืออาจเป็นการจบการทำงาน
DO UNTIL
เป็นโครงสร้างการทำงานแบบทำงานซ้ำเช่นกัน แต่มีการทำงานที่แตกต่างจาก DO WHILE คือจะมีการเข้าทำงานกลุ่มคำสั่งที่อยู่ภายในลูปก่อนอย่างน้อย 1 ครั้ง แล้วจึงจะไปทดสอบเงื่อนไข ถ้าเงื่อนไขเป็นเท็จก็จะมีการเข้าทำกลุ่มคำสั่งที่ต้องทำซ้ำอีก หลังจากนั้นก็จะย้อนกลับไปตรวจสอบเงื่อนไขใหม่อีก ถ้าเงื่อนไขยังคงเป็นเท็จอยู่ ก็ยังต้องทำกลุ่มคำสั่งซ้ำหรือเข้าลูปต่อไปอีก จนกระทั่งเงื่อนไขเป็นจริง จึงจะออกจากลูปไปทำคำสั่งถัดจาก UNTIL หรืออาจเป็นการจบการทำงาน
สรุปข้อแตกต่างระหว่าง DO WHILE และ DO UNTIL มีดังนี้
1. DO WHILE ในการทำงานครั้งแรกจะต้องมีการตรวจสอบเงื่อนไขก่อนทุกครั้ง ก่อนที่จะมีการเข้ลูปการทำงาน
2. DO UNTIL การทำงานครั้งแรกจะยังไม่มีการตรวจสอบเงื่อนไข แต่จะเข้าไปทำงานในลูปก่อนอย่างน้อย 1 ครั้งแล้วจึงจะไปตรวจสอบเงื่อนไข
3. DO WHILE จะมีการเข้าไปทำงานในลูปก็ต่อเมื่อตรวจสอบเงื่อนไขแล้วพบว่า เงื่อนไขเป็นจริง แต่เมื่อพบว่าเงื่อนไขเป็นเท็จ ก็จะออกจากลูปทันที
4. DO UNTIL จะมีการเข้าไปทำงานในลูปก็ต่อเมื่อตรวจสอบเงื่อนไขแล้วพบว่า เงื่อนไขเป็นเท็จ แต่เมื่อพบว่าเงื่อนไขเป็นจริง ก็จะออกจากลูปทันที

ตัวอย่าง 5 จงเขียนผังงานแสดงการเพิ่มของข้อมูลตัวเลขที่เป็นอยู่ในหน่วยความจำที่แอดเดรส 1 โดยที่ค่าเริ่มต้นจาก 0 ให้ทำการเพิ่มค่าทีละ 1 เรื่อยไปจนกระทั่ง J มีค่าข้อมูลมากกว่า 100 จึงหยุดการทำงาน
ตัวอย่างนี้ เป็นตัวอย่างการทำงานแบบทำซ้ำ ซึ่งจะสามารถแสดงการเขียนได้ทั้งแบบ DO WHILE และ DO UNTIL ดังนี้

เขียนโดย ที่ ไม่มีความคิดเห็น:

ประโยคโครงสร้าง (Structure Sentence

ประโยคโครงสร้าง (Structure Sentence)

วิธี นี้ใช้การอธิบายเป็นประโยคโดยเขียนให้มีลักษณะเป็นโครงสร้าง คล้ายๆ การเขียนโปรแกรมโครงสร้างดังตัวอย่างข้างต้น การเขียนประโยคโครงสร้างเราใช้คำศัพท์ต่างๆ กัน ซึ่งอาจจะเลือกใช้คำต่างๆ กันได้ ดังนี้
ใช้ คำกริยาที่เมื่อทำแล้วมีความหมายว่าได้ผลลัพธ์บางอย่างออกมา เช่น "คำนวณ" สิ่งนั้นสิ่งนี้หรือ "เปรียบเทียบ" สิ่งนั้นกับสิ่งนี้ เป็นต้น คำกริยาที่อาจจะเลือกใช้ได้ เช่น GET , COMPUTE, PUT, DELET, FIND, VALIDATE,DIVEIDE ,ADD, MOVE, SUBTRACT, REPLACE, MULTIPLY, SET,SORT
ใช้ชื่อข้อมูลเป็นคำนามในประโยค ตัวอย่างเช่น วันชำระเงินใบทวงหนี้ รายงานเพื่อเตรียมเงินสด เป็นต้น
ใช้คำศัพท์ที่แสดงความสัมพันธ์ระหว่างข้อมูล เช่น "และ" "หรือ" "เท่ากับ" "ไม่เท่ากับ" "มากกว่า" และ "น้อยกว่า" เป็นต้น
ใช้คำที่บอกการเคลื่อนที่ของข้อมูลคล้ายกับคำที่ใช้ในการเขียนโปรแกรมได้แก่

1. ถ้า……..มิฉะนั้น (If……else……..)
2. กรณี…. (case)
3. ทำซ้ำ (Do…..Loop)
4. ทำตามลำดับ (Sequence)

ตัวอย่างที่ 1 ประโยคโครงสร้างที่ทำงานตามลำดับ

อ่านข้อมูลจาก Employee
คำนวณหาเงินเดือน
ค่าจ้าง = จำนวนชั่วโมงที่ทำงาน X อัตราค่าจ้างต่อชั่วโมง
เงินเดือน = ค่าจ้าง X อัตราภาษี
พิมพ์รายงานแสดงเงินเดือน

ตัวอย่างที่ 2 ประโยคโครงสร้างที่ทำงานตามลำดับและมีการใช้เงื่อนไข Do…Case

อ่านข้อมูลคะแนนรวม
Do คะแนนรวม
Case1 คะแนนรวม >=80
เกรด = A< br>
Case2 คะแนนรวม >=70
เกรด = B
Case3 คะแนนรวม >=60
เกรด = C
Case4 คะแนนรวม >=50
เกรด = D
End (ถ้าไม่ตรงกับทุกกรณี)
เกรด = E
เขียนโดย ที่ ไม่มีความคิดเห็น:

ผังงานกับชีวิประจำวัน

ผังงานกับชีวิประจำวัน


  การทำงานหลายอย่างในชีวิตประจำวัน จะมีลักษณะที่เป็นลำดับขั้นตอน ซึ่งก่อนที่ท่านจะได้ศึกษาวิธีการเขียนผังงานโปรแกรม จะแนะนำให้ท่านลองฝึกเขียนผังงานที่แสดงการทำงานในชีวิตประจำวันวันก่อน เพื่อเป็นการสร้างความคุ้น เคยกับสัญลักษณ์รูปภาพต่าง ๆ ที่จะมีใช้ในผังงานโปรแกรมต่อไป

ตัวอย่าง 1 เขียนผังงานที่แสดงขั้นตอนการส่งจดหมาย
ตัวอย่างที่ 2 เขียนผังงานแสดงวิธีการรับประทานยา ที่แบ่งขนาดรับประทานตามอายุของผู้ทานดังนี้
อายุมากกว่า 10 ปี รับประทานครั้งละ 2 ช้อนชา
อายุมากกว่า 3 ปี ถึง 10 ปี รับประทานครั้งละ 1 ช้อนชา
อายุมากกว่า 1 ปี ถึง 3 ปี รับประทานครั้งละ 1/2 ช้อนชา
แรกเกิดถึง 1 ปี ห้ามรับประทาน

เขียนโดย ที่ ไม่มีความคิดเห็น:

การเขียนผังงาน ( Flowchart )

การเขียนผังงาน ( Flowchart )

ผัง งาน คือ แผนภาพที่มีการใช้สัญลักษณ์รูปภาพและลูกศรที่แสดงถึงขั้นตอนการทำงานของ โปรแกรมหรือระบบทีละขั้นตอน รวมไปถึงทิศทางการไหลของข้อมูลตั้งแต่แรกจนได้ผลลัพธ์ตามที่ต้องการ                                                                                                

 ประโยชน์ของผังงาน

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

ใช้สัญลักษณ์ตามที่กำหนดไว้
ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากบนลงล่าง หรือจากซ้ายไปขวา
คำอธิบายในภาพควรสั้นกะทัดรัด และเข้าใจง่าย
ทุกแผนภาพต้องมีลูกศรแสดงทิศทางเข้า - ออก
ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ควรใช้สัญลักษณ์จุดเชื่อมต่อแทน
ผังงานควรมีการทดสอบความถูกต้องของการทำงานก่อนนำไปเขียนโปรแกรม
เขียนโดย ที่ ไม่มีความคิดเห็น:

Program Flowchart

Program Flowchart

ผังงานโปรแกรม
การเขียนผังโปรแกรมจะประกอบไปด้วยการใช้สัญลักษณ์มาตรฐานต่าง ๆ ที่เรียกว่า สัญลักษณ์ ANSI ( American National Standards Institute ) ในการสร้างผังงาน ดังตัวอย่างที่แสดงในรูปต่อไปนี้
จุดเริ่มต้น / สิ้นสุดของโปรแกรม
ลูกศรแสดงทิศทางการทำงานของโปรแกรมและการไหลของข้อมูล
ใช้แสดงคำสั่งในการประมวลผล หรือการกำหนดค่าข้อมูลให้กับตัวแปร
แสดงการอ่านข้อมูลจากหน่วยเก็บข้อมูลสำรองเข้าสู่หน่วยความจำหลักภายในเครื่องหรือการแสดงผลลัพธ์จากการประมวลผลออกมา
การตรวจสอบเงื่อนไขเพื่อตัดสินใจ โดยจะมีเส้นออกจารรูปเพื่อแสดงทิศทางการทำงานต่อไป เงื่อนไขเป็นจริงหรือเป็นเท็จ
แสดงผลหรือรายงานที่ถูกสร้างออกมา
แสดงจุดเชื่อมต่อของผังงานภายใน หรือเป็นที่บรรจบของเส้นหลายเส้นที่มาจากหลายทิศทางเพื่อจะไปสู่การทำ งานอย่างใดอย่างหนึ่งที่เหมือนกัน
การขึ้นหน้าใหม่ ในกรณีที่ผังงานมีความยาวเกินกว่าที่จะแสดงพอในหนึ่งหน้า
เขียนโดย ที่ ไม่มีความคิดเห็น:

อัลกอริทึม

 อัลกอริทึม

       ขั้นตอนวิธี หรือ อัลกอริทึม (อังกฤษ: algorithm) หมาย ถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและ ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)
โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน
ในการทำงานอย่างเดียว กัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน
การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง
หนึ่งในขั้นตอนวิธี อย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้
1.    ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบจดค่ามันไว้
2.   จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด
และนี่คือรหัสเทียมสำหรับขั้นตอนวิธีนี้
Algorithm LargestNumber   Output: จำนวนเต็มที่มีค่ามากที่สุดในรายการ.
  Input: รายการจำนวนเต็ม.
  largest ← -∞
  for each item in รายการ, do
    if the item > largest, then
      largest ← the item
  return largest

            การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบท ที่  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
ตารางที่ 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                                                                    
                                                           

                                                                        Li+1


รูปที่ 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เพื่อหาค่าหารร่วมมาก  ตัวเลขที่รับเข้ามานี้ค่าที่มากกว่าจะว่าจะถูกหารด้วยค่าทีนอยกว่า
  ตารางที่ 8.2 อเลกอริทึมของยูคลิด

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  โดยอัลกอริทึมของยูคลิดเขียนเป็นตัวอย่างโปรแกรมได้เป็นตารางที่  8.3






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

#include <stdio.h>
#include <stelib.h>
#include <conio.h>
int euclid <int m, int n)  {
                 int em;
                rem =m%n;
                while(rem !=0 ){
                           m = n ;
                           m =rem;
                           rem = m%n;
            }
          retutn n;
}
main(){
          int m,n ;
         
          printf(“Enter first positive integer  : “);
          scanf(“%d”,&m);
          printf(“Enter first positive integer  : “);
          scanf(“%d”,&n);
           printf(“\nGCD  of  %d  and  %d  is %d \n “,m,n,euclid(m,n));
          getch ();
}

  ประสิทธิภาพการทำงานของอัลกอริทึม
             ประสิธิภาของอัลกอริทึมโดยทั่ว ไปมีมตรฐานการวัดผลสองแบบโดยแบบแรก  คือ การใช้พื้นที่ว่าง (Space Utilization)เป็นจำนวนของหส่วยความจำที่ต้องการใช้เพื่อให้งานสำเร็จประกอบ ด้วยพื้นที่เก็บคำสั่งทา นที่เก็บข้อมูล และพื้นที่สภาวะแวดลอ้มสแตกแบบที่ 2  คือประสิทธิภวะเวลา (Time Efficiency) เป็นจำนนของเวลาที่ต้องกรใช้การประมวลผลข้อมูลเพื่อให้งานสำเร็จ การสำทั้งสองแบบมาวัดปลด้วยันไม่สามารถเป็นไปได้ เนื่องจากอัลกอริทึมที่ขอใหชื้นที่หน่วยความจำได้ต้อ่ยกว่ามักจะทำงานช้า กว่าอัลกอริทึมที่ขอได้มากกว่า  ดังนั้น ผู้เขียนแรแกรมจึงต้งเลือกว่าจะใช้การขอในที่ว่างหรือประสิทธิภาพเวลา แต่แระสิธิภาพเวลาของอัลกอริทึมจะมีความสำคัญกว่าจึงนำมาใช้พิจารณา  ซึ่งเวลาที่ใช้ในการทำงานของอัลกอริทึมชขึ้นกับปัจจัยหลายๆอย่าง  ดังนี้
       
          1.ขนาดข้อมูลที่รับเข้ามา  จำวนของข้อมูลที่รับเข้ามาทำงานจะมีผลกระทบต่อเวลาที่ใช้ทานใจนการปรมวลล ข้อมูลที่รับเข้ามา  เช่น  เวลาที่ใช้จัดเรียงลำดับข้อมูลของรายการขึ้นกับจำนวนของข้อมูลที่มีอยู่ใน รายการ ( รายละเอียดการจัดเรียงงลำดับอยู่ในบทที่ 11)  ดังนั้น  เวลาในทำงาน  T  ของอัลกอริทึมจะแสดงในรูปแบบฟังก์ชัน T(n)ของข้อมูลที่รับเข้ามามีขนาด n ค่า
          2. ขนิดของเครื่องคอมพิวเตอร์  คำสั่ง (Instruction)และความเร็วของคอมพิวเตอร์มีผลต่อเวลาในการทำงาน  ปัจจัยนี้ขึ้นกับเครื่องคอมิวเตอร์ที่นำมาใช้  ซึ่งไม่สามารถคาดคะเนให้ความหมายเวลา T(n)อยู่ในลักษณะของเวลาที่เป็นจริง(วินาที)แต่จะนับจำนวนของคำสั่งที่ใช้ใน การทำงานโดยประมาณเป็นเวลาT(n )แทน
             3.   คุณภาะซอรสโค้ดและคอมไพเลอร์  เป็น อีกปัจจัยหนค่งที่มีผลต่อเวลาทีใช้ทำงานซึ่งขึ้นกับคุณภาพของซอร์สโคด้ (Source  Code) ที่เขียนการทำงานเป็นอัลกอริทึมและคุณภาพของคอมไพเลอร์(Compiler)ในการแปลง ซอร์สโค้ดไปเป็นโค้ดถกษาเครื่อง(Machine Code ) ในบางภาษาเขียนโปแกรมมีความเหมาะสมกว่าในการเขียนอัลกอริทึมในขณะที่บางภาษา มีคอมไพเลอร์ที่แปลงงโค้ดได้ดีกว่า ซึ่งหมายความว่าค่า T(n)ไม่สามารถจะทราบได้เมื่อไช้กับการนับจำนวนของคำสั่งในการทำงาน(ข้อ 2)
ประสิทธิภาพกับขนาดข้อมูลที่รับเข้ามา
            ตัวอย่างต่อไปนี้เป็นอัลกอริทคม ที่ได้กล่าวมาแลวนารางที่ 8/.1 เป็นการคำนวนหาค่าเฉลี่ยจากการรับค่าเข้ามา n ค่าท่เก็บไว้ในอาร์เรย์  และมีการกำหนดหมายเลขบรรทัดให้กับและประโยคเพื่อความสะดวกในการอ้างถึงได้ เป็นดังในตารางที่ 8.4
  ตารางที่ 8.4  อัลกอริทึมการคำนวนหาคาเฉลี่ย

1.กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2.กำหนดค่าเริ่มต้นให้ตัวแปรดับนี i =0
3. วนลูป while i<n ให้ทำดังนี้
4. a.นำค่าของอาร์เรย์ X[i]บวกให้กับตัวแปร sum
5.b. เพิ่ค่าให้กับตัแปร I หนึ่งค่า
6.คำนวนหาค่าเฉลี่ย sum/n  และส่งคืนกลับ
           ประโยคบรรทัด 1  และ  2  มีการนำงนเยงครั้งเดียว  ประโยคบรรทัด  4 และ 5 ประกอบกันเป็นการทำงานแบบวนลูปมีการทำงาน n ครั้ง  ประโยคบรรทัด   3  ซึ่งเป็นตัวควบคุมการทำงานซ้ำมีการทำงาน  n+1ครั้ง  เพิ่ม 1 เข้ามาเป็นการตรวจสอบเงื่อนไขในกรณีที่ตัวแปร iมีค่าไม่น้อยกว่า n หลังจากจบการวนลูปประโยคบรรทัด   6 มีการทำงานครั้งเดียว  จากการวิเคราะห์ดังกล่าวได้เป็นตารางผลสรุปดังรูปที่  8.2

ประโยค #
จำนวนการทำงาน
1
2
3
4
5
6
1
1
n+1
n
n
1
ยอดรวม
3n+4
รูปที่ 8.2จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่ 8.2
จะเห็นว่าเวลาที่ใช้ในการทำงานของอัลกอริทึมนี้ได้เป็น
T(n)  =3n+4
     เมื่อจำนานข้อมูลที่รับเข้ามาเพิ่มขึ้น   ค่าเวลาในการทำงานของ  T(n)  ก็จะเพิ่มมากขึ้นตามอัตราส่วนของ nและได้ว่า T(n) มีลำดับขาดตามค่าของ nซึ่งกำหนดเป็นสัญลักษณ์เครื่องหมายบิ๊โอ  (Big  Oh notation) ได้เป็นดังนี้
 
T(n)  = O(n)
ในลักษณะทั่วค่าเวลา  T(n) ของอัลกอริทึมจะบอกว่ามีลำดับขนาดตามค่าของ f(n) แสดงเป็น
T(n)  = O(f(n))
ถ้ามีค่าคงที่ c จะได้ว่า
T(n) ≤ c•f(n) สำหรับทุกๆค่าของ n ที่สามารถมีค่าได้สูงสุด       
       จะได้ว่า T(n)ถูกกำหนดขอบเขตช่วงบนด้วยเวลาคงที่ f(n)สำหรับทุกๆ ค่าของnในช่วงใดช่วงหนึ่ง  และการคำนวนเชิงซ้อน (Computational  Complexity)ของอัลกอริทึมเรียกเป็นO(f(n)) จากลักษณะเชิงซ้อนของอัลกอริทคมตัวอย่างที่ผ่านมาได้เป็น O(n)โดยพบว่าเวลาที่ใช้ในการทำงานได้เป็น 
   T(n)  =3n+4
และ
3n+4 ≤  3n+n  สำหรับ  n≤4
จะได้ว่า
T(n) ≤ 4n สำหรับทุก n ≥ 4
ดังนั้นเมื่อให้ f(n)=nและc=4ก็เขียนได้เป็น
T(n)=O(n)
          นอกจากนี้ยังคงมีความถูกต้องเช่นกันเมื่อเขียนเป็น T(n)=O(5280n)หรือ T(n)=O(4n+5)หรือ T(n)=O(3.141n+2.71828)แต่การเขียนที่ต้องการจะให้อยู่ในรูปแบบของฟังก์ชัน เรียบง่าย เช่น n , n2  หรือlog2 เพื่อแสดงให้ทราบถึงลักษณะเชิงซ้อนของอัลกอริทึม และมีรูปแบบทั่วไปเป็น T(n)  = O(g(n)) ถ้า g(n) ≥ n สำหรับทุก ๆค่าของ n
ประสิทธิภาพกับการจัดเก็บข้อมูล
จากตัวอย่างที่ผ่านมา  เวลาที่ใช้ทำงานจะขึ้นกับขนาดหรือจำนวนของข้อมูลที่รับเข้ามาในปัญหาอื่น  ๆ  อาจขึ้นกับวิธีจัดการกับข้อมูลที่รับเข้ามา เช่น  การจดเรียงลำดั่บข้อมูลจะใช้เวลาต้องใช้เวลาจัดเรียงลำดับมากขึ้น
      ดังนั้น  ในการพยายามวัดผลเวลาของ Tอาจใช้ในกรณีดีที่สุด (Best Case)ในกรณีเฉลี่ย (Aver age Case )หรือในกรณีแย่ที่สุด(Worst Cast)การวัดสิทธิภาพของอัลกอริทึมในกรณีดีที่สุดดูเป็นเรื่องง่ายแต่ไม่ สามารถนำมาวัดผลได้และในกรณีเฉลี่ยก็เป็นการยากที่จะต้องพิจารณาค่าเฉลี่ย ที่ชัดเจน   แต่ในกรณีที่แย่ที่สุดเหมือนไม่ง่ายแต่ก็ไม่ยากที่จะนำมาใช้วัดผลดังนั้น เวลา T(n)จึงนำมาใช้วัดประสิทธิภาพของอัลกอริทึมในกรณีที่แย่ที่สุด
    ตัวอย่างที่นำมาแสดงเป็นอัลกอริทึมการจัดเรียงลำดับข้อมูลแบบเลือก Selection Sorting)
ดังในตารางที่ 8.5 และมีการกำหนดหมายเลขบรรทัดให้กับแต่ละประโยค
ตารางที่ 8.5 อัลกอริทึมการเรียงลำดับแบบเลือก

1.วนลูปforตั้งแต่ i=0ถึงn-2ให้ทำดังนี้
2.     a กำหนดตัวแปร smallpos มีค่าเท่ากับ i
3.     b กำหนดตัวแปรsmallestมีค่าเท่ากับอาร์เรย์ X[smallpos]
4.     c  วนลูป forตั้งแต่ j=i=+1ถึงn-1ให้ทำงานดังนี้
5.                   ถ้า X[j]นอ้ยกว่า  smallest ทำดังนี้
6.           1  กำหนดตัวแปร smallpos มีค่าเท่ากับ j
7.           2  กำหนดตัวแปรsmallestมีค่าเท่ากับอาร์เรย์ X[smallpos]
8.        d  กำหนดอาร์เรย์ X[smallest]มีค่าเท่ากับ X[i]
9.            e  กำหนดอาร์เรย์  X[i] มีค่าเท่ากับ smallest

        ประโยคบรรทัดที่ 1 มีการทำงานบนวนลูป n ครั้งจากช่วง  i=0 ถึง n-2 และหนึ่งครั้งเพื่อจบการวนลูป ประโยคบรรทัด 2,3,8และ 9 แต่ละบรรทัดมีการทำงาน n-1 ครั้งภายในลูปในการวนลูปรอบแรกค่า i =0 โดยประโยคบรรทัดที่ 4 เป็นตัวควบคุมการทำงานซ้ำมีการทำงาน n ครั้งประโยคบลรรทัด 5 เป็นการตรวจเงื่อนไข มีการทำงาน n-1 และในการทำงานของประโยคบรรทัด 6,7เป็นกรณียี่สุดจึงมีการทำงาน n-1  ครั้งเช่นกัน
      ในการวนลูปรอบที่ สองค่า I =1 ประโยคบรรทัด  4มีการทำงาน n-1 ครั้ง ประโยคบรรทัด 5,6และ7 มีการทำงานทั้งหมด n-2  ครั้งเมื่อการทำงานไปเรื่อยๆจนจบ  จะได้ว่าประโยคบรรทัด  4มีการทำงานทั้งหมด n+(n-1)+…+2 ครั้ง ประโยคบรรทัด 5,6และ7 แต่ละบรรทัดมีการทำงานทั้งหมด(n-1)+ n-2)+…+1ครั้งได้ผลรวมทั้งหมดเท่ากับn(n-1)/2-1 และ n(n-1)/2 ตามลำดับซึ่งจะได้เวลาในการทำงานของอัลกอริทึมเป็น ดังนี้
   T(n)  =3n+4(n-1) +-1+3
            =2n2+4n-5
เมื่อ n ≤ n2สำหรับทุก n ≥ 0จะได้ว่า
2n2 + 4n - 5 ≤ 2n2 + 4n = 6n2
และได้ว่า
T(n) ≤ 6n2 สำหรับทุก  n ≥ 0
กำหนดให้f(n) = n2 และ c = 6 ตามเครื่องหมายบิ๊กโอได้เป็น
 T(n) = O(n2)
                   เครื่องหมายบิ๊กโอบอกให้ทราบว่าเป็นการวัดผลโดยประมาณกบเวลาการทำงานของอับ ลกอริทึมสำหรับข้อมูลที่รับเข้ามีจำนวนมาก ๆ ถ้าหากมีสองอัลกอริทึมที่ทำงานกับปัญหาแบบเดียวกันแต่มีลักษณะเชิงซ้อนต่าง กันอัลกอริทึมที่มีเวลาการทำงานน้อยที่สุดจะมีความเวลาการทำงาน T2(n) ของอัลกอริทึม  2  เป็นO(n2)นะได้ว่าอัลกอริทึม  2  และมีประสิทธิภาพมากกว่าเมื่อขนาดข้อมูลเท่ากับ n
           
                    อย่างไรก็ตาม หากขนาดข้อมูลที่รับเข้ามามีจำนวนน้อย  อัลกอริทึม 2  อาจดีกว่าอัลกอริทึม 1  เช่นไห้ T1(n)  =10n และ T2(n)  =0.1n2 ซึ่ง 10n<0.1n2 สำหรับค่าของ n  ที่นอ้ยกว่า 100 และจะได้ว่า
 T1(n)  < T2(n)  สำหรับเฉพาะ n >  100
ดังนั้นอัลกอริทึม  1  มีประสิทธิภาพมากกว่าอัลกอริทึม  2 เฉพาะข้อมูลที่รับเข้มีจำนวนมากกว่า  100
ประสิทธิภาพของอัลกอริทึมจึงขึ้นอยู่กับการจัดการกับข้อมูลอย่าไรโดย ตัวอย่างที่นำมาแสดงให้ทราบความแตกต่างของแต่ละอัลกอริทึมที่ใช้แก้ปัญหาแก้ ปัญหาแบบเดียว  ซึ่งเป็นการค้นหาค่าที่ต้องการมีอยู่ในอาร์เรย์ที่มีสมาชิก  n ตัวหรือไม่ แบบแรกเป็นอัลกอริทึมแบบง่าที่นำมาใช้ดำเนินการค้นหาเป็นการค้นหาตามลำดับ เชิงเส้น (Linear Search) ซึ่งเริ่มต้นการค้นหาที่สมาชิกในตำแหน่งแรกของรายการและทดสอบกับสมาชิกใน ตำแหน่งถัดแรกของรายการและทดสอบกับสมาชิกในตำแหน่งส่งถัดไปจนกว่าจะพบค่าที่ ต้องการหรือสิ้นสุดการค้นหาที่ท้ายรายการได้เป็นอัลกอริทึมดันในตารางที่  8.6

ตารางที่ 8.6 อับกอริทึมการค้นหาแบบเชิงเส้น
  1. การหนดตัวแปร found  มีค่าเท่ากับ false
  2. กำหนดตัวแปร Ioc มีค่าเท่ากับ 0
  3. วนลูปwhile Ioc ≤ n -1 และ  not found ให้ทำดังนี้
  4. ถ้า X[Ioc] มีค่าเท่ากับ item ที่ต้องการหาคำดังนี้
  5. กำหนดตัวแปร found  มีค่าเท่ากับTrue
  6. ไม่เช่นนั้น  เพิ่มหนึ่งค่าให้กับตัวแปร Ioc เท่ากับ Ioc+1

ในกรณีแย่ที่สุดของการค้นหาคือ  ไม่พบค่าที่ต้องการมีอยู่ในรายการ  ซึ่งใช้เวลาการทำงาน TL(n)สำหรับอัลกอริทึมการค้นหาแบบเชิงเส้นในรูที่ 8.3
                   

ประโยค #
จำนวนการทำงาน
1
2
3
4
5
6
1
1
n+1
n
0
n
รูปที่ 8.3 จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่  8.6
เมื่อ TL(n) = 3n+3 จะได้ว่า
TL(n)=O(n)
และ 3n+3 ≤ 4nสำหรับทุก n ≥ 3
 ถ้าหากรายการที่นำมาใช้ค้นหามีการจัดเรียงลำดับข้อมูลอยู่ก่อนแล้ว  ก็สามารถใช้แบบที่ สองโดยอัลกอริทึมจะดำเนินการค้นหาแบบแบ่งครึ่ง (Binary Search)แทนการใช้แบบเชิงเส้นเป็นการค้นหาที่ต้องการโดยไปยังสมาชิกตรงกลาง ของรายการและทำการตรวจสอบค่าซึ่งมีความเป็นไปได้  3 รูปแบบ คือ
   1.ค่าที่ต้องการหาน้อยกว่าค่าของสมาชิกที่อยู่ตรงกลาง ค้นหาต่อในส่วนครึ่งแรกที่เหลือของรายการ
   2.ค่าที่ต้องการหามากกว่าค่าของสมาชิดที่อยู่ตรงกลาง   ค้นหาต่อในส่ายครึ่งท้ายี่เหลือของรายการ
    3.ค่าที่ต้องการหาเท่ากับค่าของสมาลอกที่อยู่ตรงกลาง   ค้นพบค่าที่ต้องการ
 
    กระบวนการค้นหาจะทำไปเรื่อย ๆ จนกว่าจะพบค่าที่ต้องการหรือไม่พบเมือรายการย่อยที่ต้องค้นหาว่างเปล่าได้ เป็นอัลกอริทึมดังในตารางที่  8.7
ตารางที่ 8.7 อัลกอริทึมการค้นหาแบบแบ่งครึ่ง

1.กำหนดตัวแปร found  มีค่าเท่ากับfalse
2.กำหดตัวแปร first มีค่าเท่ากับ 0
3.กำหดตัวแปร last  มีค่าเท่ากับ n-1
4. วนลูป while first  last และ  not foundให้ทำดังนี้
5.คำนาณค่าตัวแปร loc  มีค่ากับ(fist + last)/2
6.ถ้าค่า item ที่ต้องการหาน้อยกว่าX[loc] ทำดังนี้
7.กำหนดตัวแปร last มีคากับ loc+1
8.ไม่เช่นนั้นถ้าค่า item ที่ต้องการหามากกว่า X[loc] ทำดังนี้
9.กำหนดตัวแปร first  มีค่าเท่ากับ loc+1
10.ไม่เช่นนั้นกำหนดตัวแปร found มีค่ากับ true
จากอัลกอริทึมนี้จะเห็นว่าประโยคบรรทัด 1 , 2 และ 3 มีการทำงานเพียงครั้งเดียว การทำงานถัดไปใช้กับกรณีแย่ที่สุดในการทำนวณเวลา Ta(n) โดยพิจารณาจากจำนวณครั้งการทำงานวนลูปตั้งแต่ประโยคบรรทัด  4 จนถึง  10 ซึ่งในการทำงานแต่ละราบของการวนลูป ขนาดของรายการจะลดลงเหลือครึ่งหนึ่งไปเรื่อย ๆ
 จนกว่าจะพบค่าที่ต้องการ นื่องจากใช้กรณีแย่ที่สุดจึงค้นหาถึงรอบท้ายสุดที่รายการเหลือเพียงค่า เดียว  ดังนั้นจำนวนครั้งในการวนลูปกับบวกจำนวน k ราบของการนลูปจนกราการเหลือเพียงคาเดียว
 เนื่องจากขนาดของรายการที่เหลืเพื่อใช้ค้นหาในเราบที่ได้ n/2k และต้องเป็น
                   <2
ซึ่งจะได้ว่า
n < 2k+1
หรือเท่ากับ
Log2  n < k+1
     สิ่งที่ต้องการคือ จำนวนราบที่ผ่านมาซึ่งเป็นตัวเลขน้อยที่สุด คือ ในส่วนของ  log2 เมื่อให้การทำงานเป็นกรณีแย่ที่สุดและค่าที่ต้องการหาจะมากกว่าแต่ละค่าของ X[0],…,X[n-1] จะได้ประโยคบรรทัด 4ทำงานไม่มากกว่า 1+ log2  n ประโยค่บรรทัด 5,6,8,9ทำงานมากกว่า 1+ log2 n และประโยคบรรทัดที่ 7,10ไม่มีการทำงานเทากับ 0 เวลาที่ใช้ทำงานทั้งหมดจึงไม่มากกว่า 9+5 log2 n และได้เป็น
Tb(n)  = O(log2 n)
 จากกัลป์กอริทึมทั้งสองแบบเวลาในการทำงานการค้นหาแบบเชิงเส้นมีลักษณะฃอง เชิงซ้อนเป็นO(n)และการค้นหาแบบแบ่งครึ่งมีแนะสิทธิภาพมากกว่าการค้นหาแบบ เชิงเส้นสำหรับข้อมูลในรายการมีจำนวนมาอย่างไรก็ตาม จากการศึกษาพบว่าการค้นหาแบบเชิงเส้นมีประสิทธิภาพมากกว่าการค้นหาแบบแบ่ง ครึ่งก็ต่อเมื่อจำนายข้อมูลในรายการไม่มากกว่า 20
ตัวอย่างการเปรียบเทียบประสิทธิภาพ
          จากตัวอว่างการหาค่าหารร่วมมากโดยใช้อัลกอริทึมของยูคลิดที่ผ่านมา  เวลาที่ใช้ทำงานในบรรทัด 1จำนวน 3ครั้งสำหรับการวนลูปโดยแต่ละรอบมีการเปรียบเทียบค่า  การส่งค่า และการหารเหลือเศษ  หากพิจารณาสำหรับทุกค่าของ n ที่เป็นไปได้และ 1 ≤ n ≤ m ในกรณีที่ดีที่สุดการทำงานมีเพียงครั้งเดียวที่บรรทัด  1  ในกรณีแย่ที่สุดซึ่งจะได้ค่าหารร่วมมากเท่ากับ 1 เสมอได้เป็นดังในรูปที่ 8.4 โดยแสดงเฉพาะจำนวนการทำงานมากที่สุดในแต่ละช่วง  สำหรับค่าที่อยู่ระหว่างช่วงเหล่านี้จำนวรการทำงานจะไม่มากกว่าจำนวนของ m ในลำดับถัดไป เช่น ให้ m =6 หรือ 7จำนวนการทำงานนกรณีแย่ที่สุดจะไม่มากกว่า  4 ที่เป็นของ m =8

m
n
จำนวนการทำงานของบรรทัด
2
3
5
8
13
21
34
55
89
144
1
2
3
5
8
13
21
34
55
89
1
2
3
4
5
6
7
8
9
10
 รูปที่ 8.4 จำนวนการทำงานของอัลกอริทึมของยุคลิดในกรณีที่แย่ที่สุดในแต่ละช่วง
       จากรูป 8.4 แสดงเฉพาะค่าของ m ที่เป็นค่าน้อย ๆ แต่สำหรับทุกๆค่าของ m ที่น้อยกว่า1,000,000
ในกรณีที่แย่ที่สุดจำนวนการทำงานของบรรทัด 1 จะไม่มากกว่า 28 ครั้ง
      เพื่อให้มีการเปรียบเทียบอัลกอริทึม การหาค่าหารร่วมมากของยูคลิดจึงมีอัลกอริทึมอีกรูปแบบหนึ่งที่ใช้หาค่าหาร ร่วมมากเช่นกันดังในคารางมรา  8.8 โดยจะชิจารณาถึงประสิทธิภาพว่าเป็นอย่างไร
ตารางที่ 8.8 อัลกอริทึมการหาค่าหารร่วมมาก

1.กำหนดตัวแปร g มีค่าเท่ากับค่าที่น้อยกว่าระหว่างตัวแปร mและ n
2.ถ้าตัวแปร g หารด้วยตัวแป mและnให้จบการทำงานและได้ g เป็นค่าหารร่วมมาก
3.กำหรดค่า g = g-1 และไม่ทำงานต่อในรอบถัดไปที่บรรทัด 1
อัลกอริทคมนี้นะลดค่าของ g  ตามลำดับต่อเนื่องจนกว่าจะพบคาที่สามารถหารค่าของ mและnลงตัว หากไม่พบค่าที่ตอ้งการจะจบลงเมื่อค่าของ g เท่ากับ 1ซึ่งเป็นค่าหารร่วมมากของ ทึก ๆ ค่าและเป็นกรณีแย่ที่สุดพิจารณาเส้นทางการ ทำงานของอัลกอริทึมนี้เมื่อให้ m = 144 และ n =60 เป็นไปตามลำดับดังนี้
บรรทัด 1:        g = 60 เป็นค่าที่น้อยที่สุดระหว่าง 144และ60
บรรทัด 2:        144/60 =2 เหลือเศษ 24และ60/60 = 1 เหลือเศษ 0
บรรทัด 3:         g = 59
บรรทัด 2:          144/59 =2 เหลือเศษ 26และ60/59 = 1 เหลือเศษ 1
บรรทัด 3:          g = 58
        …
        …
        …
บรรทัด 3:         g = 48 
บรรทัด 2:          144/48 =3 เหลือเศษ 0และ60/48 = 1 เหลือเศษ 12
บรรทัด 3:          g = 47
           …
        …
       …
บรรทัด 3:          g = 17
บรรทัด 2:          144/12 =12 เหลือเศษ 0และ60/12 = 5เหลือเศษ 0
การหารทั้งสองมีเศษเหลือเท่ากับ 0 จบการทำงานและค่าหารร่วมมากกับ 12
     อัลกอริทึมนี้ทำงานถูกตอ้งรับค่าที่รับเข้ามาเป็นแบบเดียวกับตัวอย่างอัลกอ ริทึมของยูคลิด ถึงแม้การทำงานจะถึงจุดสิ้นสุดแต่มีแระสิทธิภาพน้อยกว่า   เนื่องจากการทำงานวนซ้ำถึง  49 ครั้ง แต่ละครั้งมีการหารเหลือเศษ 2ครั้งเดียวกับการเปรียบเทียบค่า  3  ครั้งในการวนลูปหากเป็นกรณีดีที่สุดจะทำงานเพียงครั้งเดียวที่บรรทัด  2 ส่วนใหญ่กรณีแย่ที่สุดเกิดขึ้นเมื่อ  n =m -1 และ mเป็นเลขขั้นข้อมูล (Prime Number)ซึ่งจำนวนการทำงานขอบรรทัด  2  เท่ากับ m-1 ครั้งอัลกอริทึมนี้เขียนเป็นตัวอย่างโปรแกรมได้เป็นตารางที่ 8.9
ตารางที่ 8.9 โปรแกรมการหาค่าหารร่วมมาก

#include <stdio.h> #include<stdlib.h>
#include <conio.h>
int gcd (int m, int n) {
             int g;
             if(m < n)
                             g=m;
            else
                             g  =n;
            while (g>1)  {
                     if((m%g==0)&&(n%g==0);
                                        return g;
                             g--;
           }
          return 1;
}
main() {
          int m,n;
          printf(“Enter fist positive integer :”);
          scanf(“%d”,&m);
          printf(“Enter fist positive integer :”);
          scanf(“%d”,&n);
          printf(“\nGCD  of %d  and  %d  is %d  \n”,m,n,  gcd(m,n));
getch();
}
ลักษณะเชิงซ้อนของอัลกอริทึม
การวัดผลประสิทธิภาพของอัลกอริทึมโดยใช้เวลาในการทำงานเพื่อให้งานสำเร็จ เผ็นการประมาณการของเวลาที่ต้องใช้ซึ่งมีอยู่ 2 วิธีคือ นับการดำเนินการ(Operation Count) จะแยกแยะการดำเนินการของคำสั่งและนับจะนวนเวลาที่ใช้ดำเนินการสั้นอีกวิธี คือนับขั้นตอ(Step Count) จะนับจำนวนเวลาของขั้นตอนการทำงานทั้งหมดในโปรแกรมดังในตัวอย่างที่ผ่านมา ใช้วิธีนี้  ซึ่งเห็นผลสำคัญที่นำมาใช้เพื่อคาดการณ์ล่วงหน้าถึงการเติบโตของเวลาที่ใช้ ทำงานเมื่อของมูลมีจำนวนมากขึ้น  และใช้เปรียบเทียบเวลาการทำงานของสองโปรแกรมที่แก้ปัญหางานแบบเดียวกัน โดยมีเครื่องหมายที่นำมาใช้ 3ลักษณะ  คือ
1 เครื่องหมายบิ๊กโอ   (Big  oh Notat6ion ,O) แสดงเป็น f(n)  = O(g(n)) หมายความว่าเวลาการทำงานของ f(n) น้อยกว่าหรือเท่ากับ g(n)และได้ว่า g(n)เป็นขอบเขตด้านบนของ f(n)
2 เครื่องหมายโอเมก้า  (Onega Notat6ion ,) แสดงเป็น f(n)  = (g(n))หมายความว่าเวลาการทำงานของ f(n) มากกว่าหรือเท่ากับ g(n)และได้ว่า g(n)เป็นขอบเขตด้านบนของ f(n)
3 เครื่องหมายเตตตะ  (Theta Notat6ion ,) แสดงเป็น f(n)  = (g(n))หมายความว่าเวลาการทำงานของ f(n) เท่ากับ g(n)
ในการเปรียบเทียบอัลกอริทึมโดยส่วนใหญ่ใช้เครื่องหมายบิ๊กโอซึ่งอธิบายของ เขตด้ายบน ในลักษณะเชิงซ้อนที่มีอัตราการเติบโคตรของฟังก์ชัน  f  ไม่สิ้นสุด (Asymptotic Complexity)และเวลาการทำงานไม่เกินของเขตลนี้ไปได้ให้ฟังก์ชัน  f และ g มีเลขบวกสองตัวและข้อกำหนดมีดังนี้
   f(n) เป็น O(g(n))ถ้ามีค่าคงที่ c และ N  เป็นเลขบวกดังนั้น f(n) ≤ cg(n) สำหรับทุกๆ n โดย n ≥ N
หมายความว่า f    หน้า 138
เขียนโดย ที่ ไม่มีความคิดเห็น:
สมัครสมาชิก: ความคิดเห็น (Atom)