tailieunhanh - Bài giảng Thuật toán và tư duy thuật toán

Bài giảng Thuật toán và tư duy thuật toán với mục tiêu củng cố khái niệm và những đặc trưng cơ bản về thuật toán; củng cố và phân tích thêm về thiết kế thuật toán; nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT. | Thuật toán và tư duy thuật toán RÈN LUYỆN TƯ DUY VÀ KHẢ NĂNG CÀI ĐẶT THUẬT TOÁN Ở TRƯỜNG PT Phần II Hồ Cẩm Hà-ĐHSPHN Mục tiêu Củng cố khái niệm và những đặc trưng cơ bản về thuật toán. Củng cố và phân tích thêm về thiết kế thuật toán Nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT 1. THUẬT TOÁN Khái niệm thuật toán Máy tính và thuật toán Đánh giá thuật toán KHÁI NIỆM THUẬT TOÁN (1) Không đề cập đến khái niệm hình thức chính xác của thuật toán (định nghĩa thông qua mô hình máy Turing). Xem xét một số định nghĩa (không hình thức) ít nhiều khác nhau Bản chất mô tả một cách thức mà một nhiệm vụ hay một tiến trình được thực hiện như thế nào của thuật toán. KHÁI NIỆM THUẬT TOÁN (2) Định nghĩa 1(): Một thuật toán là một thủ tục xác định để giải một bài toán (vấn đề), sử dụng một số hữu hạn bước. Mỗi bước có thể gồm một hoặc một số thao tác/phép toán. KHÁI NIỆM THUẬT TOÁN (3) Định nghĩa 2.(G. Brookshear) Một thuật toán là một tập hợp có thứ | Thuật toán và tư duy thuật toán RÈN LUYỆN TƯ DUY VÀ KHẢ NĂNG CÀI ĐẶT THUẬT TOÁN Ở TRƯỜNG PT Phần II Hồ Cẩm Hà-ĐHSPHN Mục tiêu Củng cố khái niệm và những đặc trưng cơ bản về thuật toán. Củng cố và phân tích thêm về thiết kế thuật toán Nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT 1. THUẬT TOÁN Khái niệm thuật toán Máy tính và thuật toán Đánh giá thuật toán KHÁI NIỆM THUẬT TOÁN (1) Không đề cập đến khái niệm hình thức chính xác của thuật toán (định nghĩa thông qua mô hình máy Turing). Xem xét một số định nghĩa (không hình thức) ít nhiều khác nhau Bản chất mô tả một cách thức mà một nhiệm vụ hay một tiến trình được thực hiện như thế nào của thuật toán. KHÁI NIỆM THUẬT TOÁN (2) Định nghĩa 1(): Một thuật toán là một thủ tục xác định để giải một bài toán (vấn đề), sử dụng một số hữu hạn bước. Mỗi bước có thể gồm một hoặc một số thao tác/phép toán. KHÁI NIỆM THUẬT TOÁN (3) Định nghĩa 2.(G. Brookshear) Một thuật toán là một tập hợp có thứ tự các bứớc không nhập nhằng, thực hiện được, xác định một tiến trình có kết thúc, (tức việc thực hiện thuật toán phải dẫn tới một kết thúc). KHÁI NIỆM THUẬT TOÁN (4) Định nghĩa 3.(A. V. Aho, . Hopcroft, J. D. Ullman) Thuật toán là một dãy hữu hạn các câu lệnh, mỗi câu lệnh đều có một ý nghĩa rõ ràng và có thể được thực hiện với một lượng công sức hữu hạn trong một thời gian hữu hạn. KHÁI NIỆM THUẬT TOÁN (5) Định nghĩa 4. (C. A. Shaffer) Một thuật toán là một bảng chỉ dẫn để giải một bài toán, trong đó các bước là cụ thể và không nhập nhằng. Thuật toán phải đúng đắn theo nghĩa nó phải tính đúng hàm mong muốn , chuyển đổi mỗi đầu vào (dữ liệu vào) thành đầu ra (dữ liệu ra) đúng, có độ dài hữu hạn và phải kết thúc với mọi dữ liệu vào hợp lệ. KHÁI NIỆM THUẬT TOÁN (6) Các tính chất: Đầu vào (dữ liệu vào) có các giá trị đầu vào được lấy từ một tập xác định. Đầu ra (kết quả ra) Từ một tập các giá trị đầu vào, thuật toán sản sinh ra các giá trị đầu ra thuộc một tập