DAA - Giới thiệu

Thuật toán là một tập hợp các bước hoạt động để giải quyết một vấn đề thực hiện các tác vụ tính toán, xử lý dữ liệu và lập luận tự động. Thuật toán là một phương pháp hiệu quả có thể được biểu diễn trong khoảng thời gian và không gian hữu hạn.

Thuật toán là cách tốt nhất để biểu diễn giải pháp của một vấn đề cụ thể một cách rất đơn giản và hiệu quả. Nếu chúng ta có một thuật toán cho một vấn đề cụ thể, thì chúng ta có thể triển khai nó bằng bất kỳ ngôn ngữ lập trình nào, nghĩa làalgorithm is independent from any programming languages.

Thiết kế thuật toán

Các khía cạnh quan trọng của thiết kế thuật toán bao gồm tạo ra một thuật toán hiệu quả để giải quyết vấn đề một cách hiệu quả bằng cách sử dụng thời gian và không gian tối thiểu.

Để giải quyết một vấn đề, có thể tuân theo các cách tiếp cận khác nhau. Một số trong số chúng có thể hiệu quả về mức tiêu thụ thời gian, trong khi các phương pháp khác có thể hiệu quả về bộ nhớ. Tuy nhiên, một điều cần lưu ý là không thể đồng thời tối ưu hóa cả tiêu thụ thời gian và sử dụng bộ nhớ. Nếu chúng ta yêu cầu một thuật toán chạy trong thời gian ít hơn, chúng ta phải đầu tư vào nhiều bộ nhớ hơn và nếu chúng ta yêu cầu một thuật toán chạy với ít bộ nhớ hơn, chúng ta cần có nhiều thời gian hơn.

Các bước phát triển vấn đề

Các bước sau đây liên quan đến việc giải quyết các vấn đề tính toán.

Định nghĩa vấn đề
Phát triển một mô hình
Đặc điểm kỹ thuật của một thuật toán
Thiết kế một thuật toán
Kiểm tra tính đúng đắn của một thuật toán
Phân tích một thuật toán
Triển khai một thuật toán
Thử nghiệm chương trình
Documentation

Đặc điểm của thuật toán

Các đặc điểm chính của thuật toán như sau:

Các thuật toán phải có một tên duy nhất
Các thuật toán phải có tập hợp đầu vào và đầu ra được xác định rõ ràng
Các thuật toán được sắp xếp hợp lý với các hoạt động rõ ràng
Các thuật toán tạm dừng trong một khoảng thời gian hữu hạn. Các thuật toán không nên chạy đến vô cùng, tức là, một thuật toán phải kết thúc tại một số điểm

Mã giả

Mã giả đưa ra mô tả cấp cao của một thuật toán mà không có sự mơ hồ liên quan đến văn bản thuần túy nhưng cũng không cần biết cú pháp của một ngôn ngữ lập trình cụ thể.

Thời gian chạy có thể được ước tính theo cách tổng quát hơn bằng cách sử dụng Mã giả để biểu diễn thuật toán dưới dạng một tập hợp các hoạt động cơ bản sau đó có thể được tính.

Sự khác biệt giữa Thuật toán và Mã giả

Thuật toán là một định nghĩa chính thức với một số đặc điểm cụ thể mô tả một quá trình, có thể được thực thi bởi một máy tính hoàn chỉnh Turing để thực hiện một tác vụ cụ thể. Nói chung, từ "thuật toán" có thể được sử dụng để mô tả bất kỳ nhiệm vụ cấp cao nào trong khoa học máy tính.

Mặt khác, mã giả là một mô tả không chính thức và (thường là thô sơ) con người có thể đọc được về một thuật toán để lại nhiều chi tiết cụ thể về nó. Viết mã giả không có giới hạn về kiểu dáng và mục tiêu duy nhất của nó là mô tả các bước cấp cao của thuật toán theo cách thực tế nhiều bằng ngôn ngữ tự nhiên.

Ví dụ, sau đây là một thuật toán cho Sắp xếp Chèn.

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

Đây là một mã giả mô tả quá trình trừu tượng mức cao được đề cập ở trên trong thuật toán Insertion-Sort có thể được mô tả theo cách thực tế hơn.

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

Trong hướng dẫn này, các thuật toán sẽ được trình bày dưới dạng mã giả, tương tự về nhiều mặt với C, C ++, Java, Python và các ngôn ngữ lập trình khác.