วันจันทร์ที่ 24 กันยายน พ.ศ. 2555

ความหมายของอัลกอริทึม

 อัลกอริทึม

.............ขั้นตอนวิธี หรือ อัลกอริทึม (อังกฤษ: algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)

.............โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน

.............ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน

.............การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง

.............หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้

.............ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบจดค่ามันไว้จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด

และนี่คือรหัสเทียมสำหรับขั้นตอนวิธีนี้

Algorithm LargestNumber   Output: จำนวนเต็มที่มีค่ามากที่สุดในรายการ.
  Input: รายการจำนวนเต็ม.
  largest ← -∞
  for each item in รายการ, do
    if the item > largest, then
      largest ← the item
  return largest

ขั้นตอนวิธี

..en:Bulletproof algorithms
..ขั้นตอนวิธีการเรียงลำดับ
..ขั้นตอนวิธีการค้นหา
..ขั้นตอนวิธีการประสาน (en:Merge algorithms)
..ขั้นตอนวิธีสายอักขระ (en:String algorithms)
..ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithms)
..ขั้นตอนวิธีแบบสุ่ม
..ขั้นตอนวิธีการประมาณ
..ขั้นตอนวิธีโรห์ของพอลลาร์ด (en:Pollard's rho algorithm)

 


การเขียนผังงาน

 ผังงาน

..........ผังงาน หรือ โฟลว์ชาร์ต (อังกฤษ: flowchart) เป็นแผนภาพแสดงขั้นตอนการทำงานของโปรแกรม โดยใช้สัญลักษณ์ต่างๆ เชื่อมกันเป็นลำดับขั้นตอนด้วยลูกศร

สัญลักษณ์ต่างๆ

จุดเริ่มต้นและจุดสิ้นสุด

..........แสดงด้วยรูปวงกลม รูปวงรี หรือรูปสี่เหลี่ยมมุมมน ภายในนิยมใช้คำว่า "Start" สำหรับจุดเริ่มต้น และ "End" สำหรับจุดสิ้นสุด

ลูกศร

..........เป็นเส้นทางการทำงานของโปรแกรม

ประมวลผล

..........ใช้กล่องสีเหลี่ยม ภายในเขียนคำสั่งต่างๆ

รับค่าเข้า และแสดงผล

..........ใช้กล่องสี่เหลี่ยมด้านขนาน ยกตัวอย่างเช่น ภายในเขียน "Get X" เพื่อรับค่า X; เขียน "Display X" เพื่อแสดงผลค่า X

ตัดสินใจ

..........ใช้กล่องสี่เหลี่ยมขนมเปียกปูน และภายในเขียนประโยคที่มีค่าความจริง เป็น "จริง" หรือ "เท็จ" และแบ่งลูกสรออกเป็น 2 ข้างคือ เส้นทางการทำงานเมื่อ ประโยคดังกล่าวเป็น "จริง" และ เส้นทางการทำงานเมื่อประโยคดังกล่าวเป็น "เท็จ"