Module 7: Thuật toán xử lý thông tin

Module 7: Thuật toán xử lý thông tin được biên soạn nhằm trang bị cho các bạn những kiến thức về khái niệm bài toán và thuật toán; một số đặc trưng của thuật toán; sơ lược về đánh giá thuật toán. Mời các bạn tham khảo tài liệu để bổ sung thêm kiến thức.
Nội dung trích xuất từ tài liệu:
Module 7: Thuật toán xử lý thông tinMODULE 7. THUẬT TOÁN XỬ LÝ THÔNG TIN7.1. Khái niệm bài toán và thuật toánTrước khi xem xét đặc trưng của “bài toán” ta xét một số ví dụ.Ví dụ 1. Bài toán kiểm tra tính nguyên tố.Cho : số nguyên dương N;Cần biết: N có là số nguyên tố hay không?Ví dụ 2. Bài toán quản lý hồ sơ cán bộ.Có : Hồ sơ gốc của các cán bộ trong cơ quanCần : Bảng thống kê, phân loại cán bộ theo trình độ văn hoáQua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:Thông tin vào (input): Thông báo cho ta biết các dữ liệu đã có;Thông tin ra (output) : Thông báo cho ta cái cần tìm từ input;Như vậy, việc cho một bài toán có nghĩa là cho input và output của nó. Cho bàitoán nghĩa là làm rõ câu hỏi Có các dữ kiện gì và phải làm gì? nhưng không cho biếtPhải làm thế nào. Việc giải bài toán có nghĩa là xuất phát từ input dùng một số hữu hạncác bước thao tác thích hợp để tìm được output theo yêu cầu của bài toán đã đề ra.Lưu ý rằng trong toán học có một xu hướng nghiên cứu định tính các bài toán.Theo xu hướng này, khi xem xét các bài toán, người ta chỉ cần chứng tỏ sự tồn tại củaoutput khi cho input và nếu có thể, xét xem có bao nhiêu lời giải và nghiên cứu tínhchất của chúng. Trong các nghiên cứu như vậy, nhiều khi ta không cần tìm ra lời giải mộtcách tường minh nhưng bằng cách dùng các công cụ toán học khác nhau một cách thíchhợp ta vẫn có thể chứng minh chặt chẽ các điều khẳng định liên quan đến lời giải. Chẳnghạn, một định lý toán học khẳng định rằng nếu hàm f(x) liên tục trên đoạn [a, b] và f(a).f(b)b thì USCLN(a,b) =USCLN(b, a-b) .Bài toánInput : a, b nguyên dươngOutput: UCLN của a và bThuật toán EuclidBước 1: Nếu a = b thì lấy giá trị chung này làm USCLN và kết thúcBước 2: Nếu a> b thì bớt a đi một lượng là b rồi quay trở lại bước 1.Bước 3: Ngược lại, bớt b đi một lượng là a rồi quay trở lại bước 1.Các thao tác bao gồm:Phép gán giá trị: xây dựng các giá trị của đối tượng (ví dụ bớt a đi một lượng là bhay cho USCLN là a)Phép dừng, kết thúc quá trình xử lýPhép chuyển có hoặc không có điều kiện cho phép thực hiện tiếp từ một bước nàođó ví dụ sau bước 2 quay trở lại bước 1.Ở cuối bước 3 của thuật toán trên ta gặp thao tác thực hiện bước 1. Trongtrường hợp này bộ xử lý sẽ chuyển sang thực hiện bước 1 của thuật toán. Khi diễn đạtthuật toán ta ngầm qui định rằng nếu không gặp phép chuyển điều khiển thì bộ xử lý sẽthực hiện tuần tự: sau bước thứ i sẽ chuyển sang bước thứ i + 1. Như vậy bước 2 nếukhông quay về bước 1 thì sẽ thực hiện tiếp bước 3.7.2. Một số đặc trưng của thuật toánKnuth – tác giả của bộ sách nổi tiếng “Nghệ thuật lập trình” đã đưa ra 5 đặc trưngsau đây của thuật toán:Input (dữ liệu vào): Mỗi thuật toán cần có một số (có thể bằng 0) các dữ liệu banđầu. Trong ví dụ thuật toán Euclid nói trên đó là hai số m và n.Output (Kết quả): Thuật toán phải cho ra được kết quả - chính là mục đíchgiải quyết bài toán thông qua thuật toánTính xác định:Tính xác định của thuật toán đòi hỏi ở mỗi bước các thao tác phảihoàn toàn xác định, không có sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác,trong cùng một điều kiện, các chủ thể xử lý dù là người hay máy thực hiện cùngmột bước của thuật toán thì phải cho cùng một kết quả. Chính vì vậy, ngôn ngữmô tả thuật toán phải chặt chẽ để không thể hiểu lầm.Tính khả thi: Các chỉ dẫn trong thuật toán phải có khả năng thực hiện được trongmột thời gian hữu hạn. Ví dụ sau đâu không thể là mô tả một thuật toán: gán chox giá trị 1 nếu bài toán tô màu giải được và cho giá trị 0 nếu bài toán tô màukhông giải được (Bài toán tô màu khẳng định không cần dùng quá 4 màu để tôcác nước trong bản đồ đề hai nước có biên giới chung phải có màu khác nhau.Người ta kiểm chứng trên thực tế thì đúng nhưng chưa tìm được chứng minh chobài toán này)Tính kết thúc (tính dừng): Việc thực hiện các bước theo một thuật toán phảidừng sau một số hữu hạn bước. Thuật toán Euclid tìm UCLN thoả mãn tính dừngvì sau mỗi bước ta thấy tổng a+b giảm thực sự nhưng không được nhỏ hơn 2. Vìvậy quá trình trên nhất định phải dừng sau một số hữu hạn bước.Ngoài 5 đặc trưng trên, trong một số tài liệu khác người ta còn nói đến tính phổ dụng.Tính phổ dụng: Tính phổ dụng có nghĩa là một thuật toán có thể được áp dụngvới một lớp các bài toán với input thay đổi chứ không chỉ áp dụng cho một trườnghợp cụ thể. Thuật toán Euclid nói trên có thể áp dụng cho bất kỳ cặp hai số tựnhiênCần lưu ý là trong khi tính dừng và tính xác định là điều kiện cần để một quá trìnhlà một thuật toán thì tính phổ dụng chỉ là một tính chất thường thấy vì có nhiều bài toáncó input hoàn toàn xác định, không tồn tại một lớp các bài toán tương tự.7.3. Các phương pháp diễn tả thuật toánNgười ta thường diễn tả thuật toán bằng một trong ba cách thức sau đây.7.3.1. Liệt kê từng bướcLiệt kê ra các quy tắc, các chỉ thị thực hiện giống như các ví dụ nói trênTa xét thêm ví dụ sau. Có 43 que diêm. Hai người chơi luân p ...