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

MODULE 7. THUẬT TOÁN XỬ LÝ THÔNG TIN<br /> <br /> 7.1. Khái niệm bài toán và thuật toán<br /> Trước khi xem xét đặc trưng của “bài toán” ta xét một số ví dụ.<br /> Ví dụ 1. Bài toán kiểm tra tính nguyên tố.<br /> Cho : số nguyên dương N;<br /> Cần biết: N có là số nguyên tố hay không?<br /> Ví dụ 2. Bài toán quản lý hồ sơ cán bộ.<br /> Có : Hồ sơ gốc của các cán bộ trong cơ quan<br /> Cần : Bảng thống kê, phân loại cán bộ theo trình độ văn hoá<br /> 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:<br /> Thông tin vào (input): Thông báo cho ta biết các dữ liệu đã có;<br /> Thông tin ra (output) : Thông báo cho ta cái cần tìm từ input;<br /> 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ài<br /> toá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ết<br /> "Phả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ạn<br /> cá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.<br /> 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.<br /> 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ủa<br /> output 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ính<br /> chấ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ột<br /> cá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ích<br /> hợ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ẳng<br /> hạ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).<br /> f(b)b thì USCLN(a,b) =<br /> USCLN(b, a-b) .<br /> <br /> Bài toán<br /> Input : a, b nguyên dương<br /> Output: UCLN của a và b<br /> Thuật toán Euclid<br /> Bước 1: Nếu a = b thì lấy giá trị chung này làm USCLN và kết thúc<br /> Bướ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.<br /> 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.<br /> Các thao tác bao gồm:<br /> 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à b<br /> hay cho USCLN là a)<br /> Phép dừng, kết thúc quá trình xử lý<br /> 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<br /> đó ví dụ sau bước 2 quay trở lại bước 1.<br /> Ở 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". Trong<br /> trườ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 đạt<br /> thuậ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ẽ<br /> 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ếu<br /> không quay về bước 1 thì sẽ thực hiện tiếp bước 3.<br /> <br /> 7.2. Một số đặc trưng của thuật toán<br /> Knuth – tác giả của bộ sách nổi tiếng “Nghệ thuật lập trình” đã đưa ra 5 đặc trưng<br /> sau đây của thuật toán:<br /> 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<br /> đầu. Trong ví dụ thuật toán Euclid nói trên đó là hai số m và n.<br /> Output (Kết quả): Thuật toán phải cho ra được kết quả - chính là mục đích<br /> giải quyết bài toán thông qua thuật toán<br /> Tí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ải<br /> hoà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,<br /> 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ùng<br /> <br /> mộ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ữ<br /> mô tả thuật toán phải chặt chẽ để không thể hiểu lầm.<br /> 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 trong<br /> mộ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 cho<br /> x 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àu<br /> khô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ô<br /> các nước trong bản đồ đề hai nước có biên giới chung phải có màu khác nhau.<br /> Người ta kiểm chứng trên thực tế thì đúng nhưng chưa tìm được chứng minh cho<br /> bài toán này)<br /> 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ải<br /> dừ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ừng<br /> vì 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ì<br /> vậy quá trình trên nhất định phải dừng sau một số hữu hạn bước.<br /> 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.<br /> 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ụng<br /> vớ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ường<br /> hợ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ự<br /> nhiên<br /> Cầ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ình<br /> là 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án<br /> có 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ự.<br /> <br /> 7.3. Các phương pháp diễn tả thuật toán<br /> Người ta thường diễn tả thuật toán bằng một trong ba cách thức sau đây.<br /> <br /> 7.3.1. Liệt kê từng bước<br /> Liệ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ên<br /> Ta xét thêm ví dụ sau. Có 43 que diêm. Hai người chơi luân phiên bốc diêm. Mỗi<br /> lượt, mỗi người bốc từ 1 đến 3 que diêm. Người nào bốc cuối cùng sẽ thắng cuộc. Thuật<br /> toán để người đi trước luôn thắng cuộc được diễn tả bằng cách liệt kê từng bước như sau:<br /> Bước 1: Bốc 3 que rồi đợi đối phương đi<br /> Bước 2: Đối phương bốc (giả sử x que, 0 0<br /> <br /> Tuyên bố<br /> thắng cuộc<br /> <br /> +<br /> Đối phương lấy<br /> x que diêm<br /> <br /> Ta lấy 4-x que<br /> <br /> Hình 7.3. Lưu đồ thuật toán trò chơi bốc diêm<br /> <br /> 7.3.3. Ngôn ngữ thuật toán<br /> Với cách thức này, thuật toán được diễn đạt gần như ngôn ngữ tự nhiên bằng một<br /> số cách nói như “trong khi một điều kiện thoả mãn thì lặp lại một nhóm thao tác“ hay<br /> “nếu một điều kiện thoả mãn thì thực hiện nhóm thao tác này ngược lại thực hiện nhóm<br /> thao tác kia” hay “sau thao tác này thì thực hiện thao tác kia”. Như vậy các diễn đạt đó<br /> chỉ rõ cách thiết lập thứ tự các thao tác và được gọi là cấu trúc điều khiển. Cấu trúc điều<br /> khiển chính là cách thể hiện thuật toán của các ngôn ngữ lập trình bậc cao mà ta sẽ thảo<br /> luận kỹ hơn trong phần ngôn ngữ lập trình.<br /> Ví dụ thuật giải Euclid có thể thể hiện như sau:<br /> <br />