Giới thiệu sách “Cấu Trúc Dữ Liệu Và Thuật Toán Tập 1”
Chương 1: CÁC KHÁI NIỆM CHUNG VỀ THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU
1.1. MỘT VÀI KHÁI NIỆM VỀ THUẬT TOÁN
Về thuật ngữ, tiếng Anh “thuật toán” là “algorithm” có xuất sứ từ tên của nhà toán học cổ ở Trung Á là Abu Ja’fa Mohammed Ibn Musa Al Khowarizmi (khoảng năm 825). Trong khi nghiên cứu cách giải một loạt các bài toán đại số, Al Khowarizmi nhận thấy có một lớp những bài toán cùng kiểu có chung một cách giải. Và ông đã quy trình hóa cách giải lớp các bài toán đó bằng một tập hợp các bước giải có trình tự trước sau mà trước ông, các nhà toán học cổ đại chưa làm.
Để kỷ niệm thành quả này của ông, các “hậu duệ” của ông đã lấy tên ông đặt cho những quy trình giải các bài toán cùng kiểu ấy là Al Khowarizmi. Dần dần theo thời gian, các nhà toán học đã Anh hóa thuật ngữ này thành Algorithm hiện đại, ngắn gọn và tiện dùng như ngày nay.
1.1.1. Định nghĩa thuật toán: Một cách đơn giản và dễ hiểu, song thiếu chặt chẽ, thiếu chính xác, khi hiểu thuật toán là cách giải bài toán. Về thuật ngữ này có khá nhiều tác giả đã phát biểu khác nhau, thể hiện các cách tiếp cận khác nhau về cùng một khái niệm. Trong các cách định nghĩa về thuật toán, định nghĩa sau đây ngắn gọn nhất, rõ ràng nhất và chặt chẽ nhất:
“Thuật toán là một tập hợp hữu hạn các chỉ thị (Instructions) hoặc các thao tác (Operations) được sắp xếp theo một trật tự xác định để dạy cho con người, máy tính hoặc robot giải một bài toán hoặc giải quyết một vấn đề nào đó”.
Từ định nghĩa này, ta trực tiếp suy ra các tính chất dưới đây của thuật toán:
1.1.2. Các tính chất của thuật toán
a. Tính hữu hạn (tỉnh dừng): Bất kỳ thuật toán nào cũng phải dừng sau một số hữu hạn bước. Tức là mọi thuật toán đều phải có Bắt đầu và Kết thúc. (Cuốn sách này không bàn về những thuật toán có vô hạn các chỉ thị (một ví dụ dễ thấy nhất là các thuật toán chạy lặp vòng (quần) vô kỳ hạn, tức nó không dùng). Có nhiều sinh viên mới học lập trình trên một ngôn ngữ bậc cao nào đó, khi thực hành rất hay mắc lỗi quên tính chất này.
Cụ thể hơn: các sinh viên đó quên viết từ khóa bắt đầu (trong C/C++ là ký tự {) hoặc từ khóa kết thúc (trong C/C++ là ký tự }) của ngôn ngữ đang thực hành cho chương trình đó, dẫu rằng trình dịch đã bắt lỗi mà cứ lóng ngóng mãi không sửa được lỗi cơ bản này. Hãy luôn thường trực trong đầu tính chất này của thuật toán khi lập trình.
b. Tính xác định đơn nhất: Tại mỗi bước của thuật toán, các chỉ thị phải rõ ràng, chuẩn xác. Các chỉ thị không được diễn đạt bằng những ngôn từ mập mở, hình như, hoặc có thể hiểu theo những nghĩa khác nhau. Sự diễn đạt các chỉ thị chỉ có một cách hiều duy nhất. Nói rõ hơn, trong cùng một điều kiện, những người khác nhau, những máy tính khác nhau cùng thực thi một chỉ thị nào đó của thuật toán thì phải cho cùng một kết quả.
c. Tính đúng đắn: Sau khi thực thi xong toàn bộ các bước của thuật toán, ta phải thu được kết quả mong muốn. Kết quả này phải được người xây dựng thuật toán xác định trước trong lúc xây dựng thuật toán.
d. Tính phổ dụng: Thuật toán phải giải được tất cả các bài toán thuộc cùng một lớp các bài toán cùng kiểu.
Ví dụ 1.1: Dân số Việt Nam hiện tại là 86 triệu người. Tỷ lệ bình quân tăng dân số hàng năm là 0,003%.
Tính xem sớm nhất đến năm nào dân số nước ta đạt ít nhất 100 triệu người?
Ví dụ 1.2: Tôi hiện có số vốn là 130 triệu đồng. Lãi suất hàng năm thu được là 8%. Tính xem sớm nhất đến năm nào tôi thu được số tiền (cả vốn lẫn lãi) là 300 triệu đồng?
Thuật toán xây dựng cho bài toán ở ví dụ 1.1 cũng phải dùng được cho bài toán ở ví dụ 1.2 và ngược lại (đó là hai bài toán cùng kiểu, dẫu rằng ý nghĩ của dữ liệu hoàn toàn khác nhau).
e. Tính hiệu quả: Tính chất này của thuật toán được đánh giá trên các chỉ tiêu sau:
Thuật toán sử dụng tiết kiệm nhất các tài nguyên (resources) của máy tính như dung lượng bộ nhớ trong, bộ nhớ ngoài.
– Thực thi trên máy tính (chạy) nhanh nhất có thể được. (Chỉ tiêu này có tên khác là: thời gian chạy chương trình hoặc thời gian thực hiện thuật toán). Về mặt lý thuyết, chỉ tiêu này đáng chú ý nhất.
– Dễ cài đặt (Set Up) trên máy tính.
1.1.3. Ba đặc trưng của thuật toán
Bất kỳ thuật toán nào cũng có ba đặc trưng sau:
a. Vào dừ liệu (Data Input). Hiển nhiên là bất kỳ thuật toán nào cũng phải có bộ dữ liệu vào. Đó là tập các dừ liệu phải nạp vào thuật toán khi nó bắt đầu được thực thi.
b. Xừ lý dữ liệu (Data Process). Mọi thao tác trên dữ liệu vào (nói riêng là tính toán) ta gọi là xừ lý chúng để đạt được kết quà của bài toán. Công việc đặc trưng này về thực chất là nội dung chù yếu (chính là các bước thực thi) cùa thuật toán. Không có đặc trưng này thì bất thành thuật toán.
c. Xuất dừ liệu (Data Output). Cuối cùng thì thuật toán cũng phải cho ra kết quà giãi bài toán hay giãi quyết vấn đề. Không thể khác được! Việc này trong Tin học gọi là xuất dữ liệu. Các dừ liệu được xuất này có liên quan tới bộ dữ liệu vào và quá trình “chế biến ” nó bời các bước cùa thuật toán (công đoạn Data Process), đây là kết quả cần có sau khi chạy (thực thi) thuật toán.
