tailieunhanh - Giáo trình Toán rời rạc ứng dụng trong Tin học và công nghệ Tiểu học: Phần 2

Giáo trình Toán rời rạc ứng dụng trong Tin học và công nghệ Tiểu học: Phần 2 cung cấp cho người đọc những kiến thức như: Lý thuyết đồ thị; Sơ lược về cây; Bài toán về đường đi ngắn nhất; Đại số Boole; Mạng các cổng và công thức đa thức tối tiểu; Phương pháp biểu đồ Karnaugh; .Mời các bạn cùng tham khảo! | CHƯƠNG 3. THUẬT TOÁN VÀ LÝ THUYẾT ĐỒ THỊ . Thuật toán . Thuật toán và cách biểu diễn thuật toán . Khái niệm thuật toán Trong toán học và khoa học máy tính một thuật toán còn gọi là giải thuật là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng có thể thực hiện được bằng máy tính thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính. Các thuật toán luôn rõ ràng và được sử dụng chỉ rõ việc thực hiện các phép tính xử lý dữ liệu suy luận tự động và các tác vụ khác. Khái niệm thuật toán đã tồn tại từ thời cổ đại. Các thuật toán số học chẳng hạn như thuật toán chia được sử dụng bởi các nhà toán học Babylon cổ đại vào khoảng 2500 TCN và các nhà toán học Ai Cập vào khoảng 1550 TCN. Các nhà toán học Hy Lạp sau đó đã sử dụng các thuật toán trong sàng Eratosthenes để tìm số nguyên tố và thuật toán Euclide để tìm ước chung lớn nhất của hai số. Các nhà toán học Ả Rập như al-Kindi vào thế kỷ thứ 9 đã sử dụng các thuật toán mật mã để phá mã dựa trên phân tích tần số. Có nhiều khái niệm khác nhau trên cơ sở đó ta đi đến khái niệm về thuật toán như sau Thuật toán là một bảng liệt kê các chỉ dẫn hay quy tắc cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho. Để trình bày thuật toán người ta có thể dùng ngôn ngữ tự nhiên ngôn ngữ lưu đồ sơ đồ khối ngôn ngữ lập trình. Thuật toán ngoài việc được trình bày bằng ngôn ngữ tự nhiên cùng với những kí hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình. Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh như trong các ngôn ngữ lập trình. Ví dụ . Thuật toán giải phương trình bậc nhất Phương pháp liệt kê Bước 1 Nhập hai số thực a b Bước 2 Nếu a 0 b 0 thì thông báo vô nghiệm rồi kết thúc Bước 3 Nếu a 0 b 0 thì thông báo phương trình nghiệm đúng với mọi giá trị rồi kết thúc b Bước 4 Nếu a 0 thì x thông báo phương trinh có .