Lý thuyết ngôn ngữ lập trình
Chương 3 THUẬT TOÁN VÀ LƯU ĐỒ THUẬT TOÁN
Nội dung
Khái niệm thuật toán
Các đặc trưng của thuật toán
Ngôn ngữ biểu diễn thuật toán
Khái niệm thuật toán
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc xác định một dãy các thao tác trên dữ liệu vào sao cho sau một số hữu hạn bước thực hiện các thao tác đó ta thu được kết quả của bài toán
Khái niệm thuật toán
Ví dụ: Thuật toán tìm UCLN của a và b
Bước 1: Nhập vào 2 số a và b
Bước 2: So sánh hai số a và b, gán số nhỏ hơn gán
cho UCLN
Bước 3: Nếu một trong hai số a hoặc b không chia hết cho UCLN thì thực hiện bước 4, ngược lại nếu cả a và b đều chia hết cho UCLN thì thực hiện bước 5
Bước 4: Giảm UCLN một đơn vị và quay lại bước 3
Bước 5: Chỉ ra UCLN - Kết thúc
Các đặc trưng của thuật toán
Tính đúng
Tính dừng
Tính xác định
Tính phổ dụng
Tính hiệu quả
Các đặc trưng của thuật toán
Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đưa ra nhận xét:
Có nhiều bài toán cho đến nay vẫn chưa tìm ra một
cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.
Có nhiều bài toán có thuật toán để giải nhưng không chấp nhận được vì thời gian giải quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng.
Có những bài toán được giải theo những cách giải vi
phạm thuật toán nhưng vẫn chấp nhận được.
Các đặc trưng của thuật toán
Người ta đã mở rộng hai tiêu chuẩn tính xác định và tính đúng đắn của thuật toán
Việc mở rộng tính xác định thể hiện qua các giải thuật
đệ quy và ngẫu nhiên
Tính đúng của thuật toán không còn bắt buộc đối với
một bài toán, nhất là các cách giải gần đúng
Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán được gọi là các thuật giải
Thuật giải thường được đề cập và sử dụng trong khoa học trí tuệ nhân tạo
Ngôn ngữ biểu diễn thuật toán
Để biểu diễn thuật toán cần phải có một tập hợp các ký hiệu
Mỗi ký hiệu biểu diễn một hành động
Tập hợp các ký hiệu được gọi là ngôn ngữ biểu diễn thuật toán:
Ngôn ngữ tự nhiên
Ngôn ngữ lưu đồ
Mã giả
Ngôn ngữ tự nhiên
Ví dụ: Thuật toán giải phương trình bậc nhất ax + b = 0
Bước 1: Nhập giá trị các tham số a và b
Bước 2: Kiểm tra a có bằng 0 hay không? Nếu a = 0 thì thực hiện bước 3, ngược lại thì thực hiện bước 4.
Bước 3: Kiểm tra nếu b = 0 thì kết luận phương trình có vô số nghiệm, ngược lại thì kết luận phương trình vô nghiệm.
Bước 4: Kết luận phương trình có nghiệm x = -b/a
Ngôn ngữ lưu đồ
Dùng để mô tả giải thuật bằng các sơ đồ hình khối, mỗi khối quy định một hành động cụ thể, riêng biệt
Khối
Ý nghĩa
Bắt đầu /Kết thúc thuật toán
Nhập / Xuất
Thi hành
Lựa chọn (điều kiện)
Đường đi
Chương trình con
Khối nối
Ngôn ngữ lưu đồ
Ví dụ:
Mã giả
Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán.
Mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp.
Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán.
Mã giả
Ví dụ: Thuật toán giải phương trình bậc 2
if Delta > 0 then
begin
x1=(-b-sqrt(delta))/(2*a)
x2=(-b+sqrt(delta))/(2*a)
xuất kết quả : phương trình có hai nghiệm là x1 và x2
end
else
if delta = 0 then
xuất kết quả : phương trình có nghiệm kép là -b/(2*a)
else {trường hợp delta < 0 }
xuất kết quả : phương trình vô nghiệm
