I/ Thuật Toán là gì?

Từ "Thuật Toán" có tên tiếng anh là "Algorithm" (viết tắt: algo) xuất phát từ tên của một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al'Khwarizmi, thường gọi là al'Khwarizmi. Ông là tác giả của một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là chuẩn mực và được nhiều nhà Toán Học khác tuân theo. Từ "Algorithm" ra đời dựa theo tên phiên âm của ông.

Muhammad ibn Mūsā al-Khwārizmī (780 - 850)

Thuật Toán còn được gọi là "Giải Thuật" là một khái niệm cơ sở của Toán Học và Tin Học. Là tập hợp dãy (hữu hạn) các chỉ thị (hành động) được định nghĩa rõ ràng nhằm giải quyết một bài toán cụ thể nào đó.

Và sau đây chúng ta sẽ lấy một vài ví dụ về thuật toán trong Lập Trình:

VD 1: Thuật toán giải phương trình bậc 1

VD 2: Thuật toán giải phương trình bậc 2

II/ Tính chất thuật toán:

Bao gồm 5 tính chất sau:

Tính chính xác: quá trình tính toán hay các thao tác máy tính thực hiện là chính xác.
Tính rõ ràng: các câu lệnh được minh bạch được sắp xếp theo thứ tự nhất định.
Tính khách quan: được viết nhiều bởi người trên máy tính nhưng kết quả phải như nhau.
Tính phổ dụng: có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
Tính kết thúc: hữu hạn các bước tính toán.

III/ Xây dựng thuật toán/thuật giải:

Thuật toán là một tập hợp các bước liệt kê dưới dạng ngôn ngữ đơn giản. Rất có thể rằng các bước trên do hai người khác nhau viết vẫn tương tự nhau, nhưng ngôn ngữ dùng để diễn tả các bước có thể khác nhau. Do đó cần thiết có những phương pháp chuẩn mực cho việc trình bày thuật toán để mọi người dễ dàng hiểu nó. Chính vì vậy, thuật toán được viết bằng cách dùng hai phương pháp chuẩn là Mã Giả (Psuedo Code) và Lưu Đồ (Flowchart).

1) Mã Giả (Psuedo Code):

Mã giả không phải là mã thật. Mã giả sử dụng tập hợp những từ tương tự như mã thật nhưng nó không thể biên dịch và thực thi như mã thật. Hiều đơn giản hơn là nó vay mượn ngôn ngữ lập trình nào đó để biểu diễn thuật toán.

VD: Mã giả sử dụng ngôn ngữ Pascal

2) Lưu Đồ (Flowchart):

Một lưu đồ là một hình ảnh minh họa cho một thuật toán hay bài toán nào đó. Nó vẽ ra biểu đồ của luồng chỉ thị hay những hoạt động trong một tiến trình. Mỗi hoạt động như vậy được biểu diễn qua những ký hiệu.

Những ký hiệu trong lưu đồ được trình bày trong hình sau đây:

VD:

IV/ Phân loại các thuật toán:

Rất khó có thể phân loại chính xác mỗi thuật toán, tùy vào tiêu chí phân loại mà có thể phân thuật toán ra thành nhiều loại khác nhau.

1) Phân loại theo tính năng của thuật toán:

Thuật toán Tìm Kiếm (Search): tìm kiếm dữ liệu trong một tập các giá trị.
Thuật toán Sắp Xếp (Sort): sắp xếp một tập các giá trị theo một trật tự cho trước.
Thuật toán Đồ Thị (Graph): xử lý những bài toán liên quan tới đồ thị như tìm đường đi ngắn nhất, tìm đường đi qua 1 điểm, ...

2) Phân loại theo cách thực hiện thuật toán:

Thuật toán Chia Để Trị (Divide & Conquer): chia bài toán lớn ra thành những bài toán nhỏ và giải quyết từng bài toán nhỏ đó.
Thuật toán Tham Lam (Greedy): thuật toán được thay đổi trạng thái được thiết đặt để qua mỗi hành động, thuật toán sẽ đi lại gần hơn với bài toán cần giải quyết.

V/ Vai trò của thuật toán:

Đi kèm với cách tổ chức dữ liệu (Cấu Trúc Dữ Liệu), thuật toán là phần không thể thiếu khi bước chân vào lĩnh vực lập trình. Thuật toán tốt giúp chương trình chạy nhanh hơn, ít tốn tài nguyên hơn và giúp chương trình dễ hiểu hơn. Bên cạnh việc sáng tạo một thuật toán mới thì phải hiểu và sử dụng thành thạo các thuật toán có sẵn.

VI/ Ứng dụng của thuật toán:

Thuật toán được ứng dụng rộng rãi nhiều trong mọi lĩnh vực Công Nghệ. Được sử dụng và ứng dụng nhiều nhất trong Khoa Học Máy Tính (Computer Science) và Ứng Dụng Máy Tính (Computer Applications).

Nguồn: Tổng Hợp