DAA - บทนำ

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

อัลกอริทึมเป็นวิธีที่ดีที่สุดในการนำเสนอวิธีแก้ปัญหาเฉพาะด้วยวิธีที่ง่ายและมีประสิทธิภาพ หากเรามีอัลกอริทึมสำหรับปัญหาที่เฉพาะเจาะจงเราสามารถใช้งานได้ในภาษาโปรแกรมใด ๆ ซึ่งหมายความว่าไฟล์algorithm is independent from any programming languages.

การออกแบบอัลกอริทึม

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

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

ขั้นตอนการพัฒนาปัญหา

ขั้นตอนต่อไปนี้เกี่ยวข้องกับการแก้ปัญหาด้านการคำนวณ

  • นิยามปัญหา
  • การพัฒนาแบบจำลอง
  • คุณสมบัติของอัลกอริทึม
  • การออกแบบอัลกอริทึม
  • ตรวจสอบความถูกต้องของอัลกอริทึม
  • การวิเคราะห์อัลกอริทึม
  • การใช้อัลกอริทึม
  • การทดสอบโปรแกรม
  • Documentation

ลักษณะของอัลกอริทึม

ลักษณะสำคัญของอัลกอริทึมมีดังนี้ -

  • อัลกอริทึมต้องมีชื่อเฉพาะ

  • อัลกอริทึมควรมีชุดอินพุตและเอาต์พุตที่กำหนดไว้อย่างชัดเจน

  • อัลกอริทึมได้รับการจัดลำดับอย่างดีโดยมีการดำเนินการที่ไม่คลุมเครือ

  • อัลกอริทึมหยุดลงในระยะเวลาที่ จำกัด อัลกอริทึมไม่ควรทำงานแบบอินฟินิตี้กล่าวคืออัลกอริทึมต้องจบลงในบางจุด

รหัสเทียม

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

เวลาทำงานสามารถประมาณได้โดยทั่วไปมากขึ้นโดยใช้ Pseudocode เพื่อแสดงอัลกอริทึมเป็นชุดของการดำเนินการพื้นฐานซึ่งสามารถนับได้

ความแตกต่างระหว่าง Algorithm และ Pseudocode

อัลกอริทึมเป็นคำจำกัดความที่เป็นทางการโดยมีลักษณะเฉพาะบางอย่างที่อธิบายกระบวนการซึ่งสามารถดำเนินการได้โดยเครื่องคอมพิวเตอร์ทัวริงเพื่อทำงานเฉพาะ โดยทั่วไปคำว่า "อัลกอริทึม" สามารถใช้เพื่ออธิบายงานระดับสูงในวิทยาการคอมพิวเตอร์ได้

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

ตัวอย่างเช่นต่อไปนี้เป็นอัลกอริทึมสำหรับการเรียงลำดับการแทรก

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

นี่คือรหัสเทียมที่อธิบายว่ากระบวนการนามธรรมระดับสูงที่กล่าวถึงข้างต้นในอัลกอริทึมการเรียงลำดับการเรียงลำดับสามารถอธิบายได้อย่างสมจริงมากขึ้นอย่างไร

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

ในบทช่วยสอนนี้อัลกอริทึมจะถูกนำเสนอในรูปแบบของรหัสเทียมซึ่งคล้ายกับ C, C ++, Java, Python และภาษาโปรแกรมอื่น ๆ ในหลาย ๆ ด้าน