Chương 3 Thuật toán và lưu đồ thuật toán

Chương 3 THUẬT TOÁN VÀ LƯU ĐỒ THUẬT TOÁN Lý thuyết ngôn ngữ lập trình 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 nối Chương trình con Đường đi Lựa chọn (điều kiện) Thi hành Nhập / Xuất Bắt đầu /Kết thúc thuật toán Ý nghĩaKhố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 CÂU HỎI ÔN TẬP CHƯƠNG 3 1. Trình bày khái niệm thuật toán 2. Trình bày các đặc trưng của một thuật toán và cho ví dụ 3. Hãy biểu diễn thuật toán giải các bài toán sau bằng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ và mã giả: - Tìm số lớn nhất trong n số cho trước - Thuật toán Euclide, tìm ước số chung lớn nhất giữa hai số a, b. - Phân tích một số ra thừa số nguyên tố 4. Trình bày các cấu trúc suy luận cơ bản của thuật toán và cho ví dụ. 5. Dùng lưu đồ biểu diễn thuật toán giải bài toán sau: Tìm học sinh điểm số lớn nhất sau kỳ thi Tin học văn phòng của một lớp có N học sinh trong hai trường hợp: - N biết trước - N được nhập tuỳ vào người sử dụng