PHÂN I. KIẾN THỨC BỔ TRỢ
Chương 1. CÁC KHÁI NIỆM CƠ BẢN CỦA THUẬT TOÁN VÀ PHƯƠNG PHÁP ĐỆ QUY
§1. KHÁI NIỆM THUẬT TOÁN
1.1. Thuật toán là gì
Thuật toán là một khái niệm quan trọng của toán học. Nói đến thuật toán là nói đến một dây các quy tắc, nhằm xác định một đây các thao tác trên các đối tượng, sao cho sau một số hữu hạn bước thực hiện các thao tác, ta đạt được mục tiêu cần làm.
1.2. Các đặc trưng của thuật toán
– Tính dừng: Sau một số hữu hạn bước thuật toán phải đừng
– Tính xác định: Ở mỗi bước, các thao tác phải rõ ràng, không gây nên sự nhập nhàng. Nói rõ hơn, trong cùng một điều kiện hai bộ xử lý cũng thực hiện một bước của thuật toán phải cho những kết quả như nhau.
– Tính hiệu quả: Trước hết thuật toán phải đúng đắn, nghĩa là sau khi đưa dữ liệu vào thuật toán hoạt động và đưa ra kết quả mong muốn.
– Tính phổ dụng: Thuật toán có thể giải bất kỳ một bài toán nào trong lớp các bài toán. Cụ thể là thuật toán có thể có các đầu vào là các bộ dữ liệu khác nhau trong miến xác định.
Yếu tố vào ra: Đối với một thuật toán luôn có một đối tượng vào (input) và đối tượng ra (output).
1.3. Ngôn ngữ thuật toán
Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán.
Thuật toán thường được mô tả bằng một dây các lệnh. Bộ xử lý sẽ thực hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết thúc.
Ngôn ngữ thuật toán bao gồm:
+ Ngôn ngữ liệt kê từng bước:
+ Sơ đồ khối:
+ Ngôn ngữ lập trình.
a) Ngôn ngữ liệt kẻ từng bước bao gồm:
Thuật toán: Tên thuật toán và chức năng.
Đầu vào: Các dữ liệu vào với tên, kiểu.
– Đầu ra: Các dữ liệu ra với tên, kiểu.
Biến phụ (nếu có) gồm tên, kiếu.
– Hành động là các thao tác với các lệnh có nhân là các số tự nhiên.
Ví dụ 1: Để giải phương trình bậc hai ax+bx c = 0 ( a ne0), ta có thế mô tả thuật toán bằng ngôn ngữ liệt kê như sau:
Bước 1: Xác định các hệ số a, b, c.
Bước 2: Kiểm tra xem hệ số a có khác 0 hay không? Nếu a = 0 quay lại thực hiện bước 1.
Bước 3: Tính biểu thức Delta = b ^ 2 – 4ac
Bước 4: Nếu Delta < 0 thông báo “phương trình vô nghiệm” và chuyển đến bước 8.
