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!
Nội dung trích xuất từ tài liệu:
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 CHƯƠNG 3. THUẬT TOÁN VÀ LÝ THUYẾT ĐỒ THỊ3.1. Thuật toán 3.1.1. Thuật toán và cách biểu diễn thuật toán 3.1.1.1. 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ằngmá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ácthuậ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ạnnhư thuật toán chia, được sử dụng bởi các nhà toán học Babylon cổ đại vào khoảng2500 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 HyLạ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ântí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ánnhư 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 theotừ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ônngữ 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ướccủ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ụ 3.1. 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ó nghiệm duy nhất là x arồi kết thúc. 69  Phương pháp sơ đồ khối Hình 3.1. Sơ đồ khối thuật toán giải phương trình bậc nhấtVí dụ 3.2. Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên.Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện: Bước 1: Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. Bước 2: So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giátrị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó. Bước 3: Lặp lại bước trước nếu còn các số nguyên trong dãy. Bước 4: Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời ởđiểm này chính là số nguyên lớn nhất của dãy.Ví dụ 3.3. Mô tả thuật toán giải phương trình bậc 2: ax 2  bx  c  0  Phương pháp liệt kê 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ựchiện bước 1. Bước 3: Tính biểu thức   b 2  4ac . Bước 4: Nếu   0 thông báo “phương trinh vô nghiệm” và chuyển đến bước 8. b Bước 5: Nếu   0 , tính x 1  x 2  và chuyển sang bước 7. 2a b   b   Bước 6: Tính x 1  , x2  và chuyển sang bước 7. 2a 2a Bước 7: Thông báo các nghiệm x 1, x 2 . 70 Bước 8: Kết thúc thuật toán.  Phương pháp sơ đồ khối Hình 3.2. Sơ đồ khối thuật toán giải phương trình bậc hai 3.1.1.2. Các đặc trưng của thuật toán - Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập đã được chỉ rõ. - Đầu ra (Output): Từ mỗi tập các giá trị đầu vào, thuật toán sẽ tạo ra các giá trịđầu ra. Các giá trị đầu ra chính là nghiệm của bài toán. - Tính dừng: Sau một số hữu hạn bước thuật toán phải dừng. - Tính xác định: Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gâynê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ệnmột bước của thuật toán phải cho những kết quả như nhau. 71 - Tính hiệu quả: Trước hết thuật toán cần đúng đắn, nghĩa là sau khi đưa dữ liệuvào thuật toán hoạt động và đưa ra kết quả như ý 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àitoán. Cụ thể là thuật toán có thể có các đầu vào ...