Giáo trình Kỹ thuật lập trình - Module 7: Thuật toán xử lý thông tin

MODULE 7. THUẬT TOÁN XỬ LÝ THÔNG TIN 7.1. Khái niệm bài toán và thuật toán Trướ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ơ quan Cầ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ài 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 "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 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. 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ủa 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 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 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 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 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). f(b)<0 thì tồn tại điểm c nằm giữa a và b sao cho f(c) = 0. Sự tồn tại lời giải theo nghĩa này không cho ta cách khả thi để tìm ra lời giải. Ở đây, ta sẽ quan niệm việc giải bài toán là việc xác định tường minh output theo input bằng một quá trình có thể thực hiện một cách hiệu quả. Đó chính là nội dung cơ bản của lý thuyết tính toán. Theo lý thuyết tính toán, một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán được gọi là một thuật toán (algorithm). Như vậy, khác với quan niệm về việc giải một bài toán theo toán học truyền thống, việc giải bài toán theo quan niệm của tin học có nghĩa là chỉ ra một thuật toán mà về nguyên tắc, các thao tác này có thể "giao cho máy làm được". Từ điển Oxford đưa ra một định nghĩa về thuật toán như sau “Algorithm: set of well-defined rules for solving a problem in a finite number of steps”. Thực ra các định nghĩa như trên không được chặt chẽ về mặt toán học. Tuy nhiên, quan niệm như vậy về việc giải bài toán là cơ sở để có thể chuyển giao công việc cho máy tính. Bản thân máy tính là một thiết bị vật lý vô tri vô giác, do đó với thể hiện vật lý cụ thể, máy tính chỉ có thể thực hiện được các thao tác rất đơn giản (tất nhiên với tốc độ rất nhanh và chính xác). Ví dụ, cho hai số nguyên dương a, b. Cần xây dựng thuật toán để tìm ước số chung lớn nhất (UCLN) của a và b. Dưới đây là thuật toán Euclid đề xuất cho bài toán nêu trên dựa trên một tính chất hiển nhiên là : Nếu a = b thì chính b là USCLN của a và b. Ngược lại nếu a b thì USCLN(a,b) = USCLN(b, a-b) . Bài toán Input : a, b nguyên dương Output: UCLN của a và b Thuật toán Euclid ƒ Bước 1: Nếu a = b thì lấy giá trị chung này làm USCLN và kết thúc ƒ 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. ƒ 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à b hay 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". Trong 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 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ẽ 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 khô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án 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 sau đâ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 đích giải quyết bài toán thông qua thuật toán ƒ 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 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, 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 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ữ 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 trong 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 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 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ô 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 cho bà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ải 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 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ì 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ụng 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 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ự nhiên 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 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 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ự. 7.3. Các phương pháp diễn tả thuật toán Ngườ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ước 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 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 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 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: ƒ Bước 1: Bốc 3 que rồi đợi đối phương đi ƒ Bước 2: Đối phương bốc (giả sử x que, 0<x<4). Sau đó thực hiện bước 3 ƒ Bước 3: Đến lượt người đi trước bốc a = (4-x) que và nếu còn diêm thì quay lại bước 2. ƒ Bước 4 : Tuyên bố thắng cuộc - kết thúc. Bạn đọc hãy tự lý giải tại sao theo thuật toán này người đi trước luôn luôn thắng. 7.3.2. Lưu đồ hay còn gọi là sơ đồ khối Lưu đồ (flow chart) là một phương tiện hình học giúp ta diễn tả thuật toán một cách trực quan. Lưu đồ được tạo bởi các kiểu khối cơ bản nối với nhau bằng các đường có hướng. Sau đây là một số khối được dùng để diễn đạt thuật toán. Khối tính toán được biểu diễn bằng hình chữ nhật. Trong khối này ta viết một hoặc một dãy các thao tác như tạo giá trị, hoặc là một nhóm công việc. Nếu để thể hiện việc tính giá trị ta sẽ dùng dấu gán := với ý nghĩa đại lượng đứng bên trái dấu gán được gán giá trị cho phía phải dấu gán. Khối tính toán có nhiều đường đi đến và 1 đường đi ra. Hình 7.1. Các loại biểu diễn hình học trong sơ đồ khối Khối điều kiện được biểu diễn bằng hình thoi hoặc hình lục giác. Trong khối này ta viết một điều kiện. Tuỳ theo điều kiện này thoả mãn hay không mà việc thực hiện tiếp theo sẽ được chỉ dẫn bởi một trong hai đường đi ra mang dẫu + (cho trường hợp đúng) hoặc dấu - (cho trường hợp sai). Như vậy khối điều kiện có 1 đường đi đến và 2 đường đi ra. Hai khối đặc biệt là khối bắt đầu và khối kết thúc được biểu diễn bằng hình tròn chỉ rõ điểm bắt đầu và điểm kết thúc (điểm dừng) của thuật toán. Khối bắt đầu không có đường đi đến và có 1 đường đi ra. Khối kết thúc không có đường đi ra. Khối chỉ điểm bắt đầu Khối chỉ điểm kết thúc Hướng xử lý Khối input Khối output Khối thao tác Khối điều kiện d := a + + a, b d a=b a > b a:= a - b b := b-a Hình 7.2. Lưu đồ cho thuật toán Euclid Trong khối input ghi rõ các đại lượng vào, và ở khối output ghi các đại lượng ra. Khối input có thể đặt kế tiếp khối bắt đầu, còn khối output có thể đặt liền trước khối kết thúc. Chúng ta dùng lưu đồ diễn tả lại thuật toán Euclid tìm UCLN của hai số nguyên dương. Sau đây là lưu đồ cho bài toán bốc diêm. Lưu đồ này không cần cả khối input và output. Trong các ô thao tác không chỉ là phép gán mà có thể là mô tả một hành động nào đó 7.3.3. Ngôn ngữ thuật toán 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 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 “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 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 đó 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 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 luận kỹ hơn trong phần ngôn ngữ lập trình. Ví dụ thuật giải Euclid có thể thể hiện như sau: Tuyên bố thắng cuộc Lấy 3 que + Số diêm còn > 0 Ta lấy 4-x que Đối phương lấy x que diêm Hình 7.3. Lưu đồ thuật toán trò chơi bốc diêm Trong khi a ≠ b thì lặp lại khối sau Nếu a > b thì Bớt a đi một lượng là b Nếu không thì Bớt b đi một lượng là a Cho tới khi a= b thì tuyên bố USCLN chính là giá trị chung của a và b Hình 7.4. Thể hiện thuật toán Euclid bằng các cấu trúc điều khiển 7.4. Sơ lược về đánh giá thuật toán Đối với một bài toán, có thể có nhiều thuật toán nhưng chúng phải cho cùng một output đối với một input. Tuy nhiên chúng có thể khác nhau về hiệu quả: ƒ Hiệu quả thời gian: cách xử lý là nhanh hay chậm. Ta có thể đánh giá căn cứ vào số bước thực hiện. ƒ Hiệu quả không gian. Có thể đánh giá không gian lưu trữ theo số các đối tượng dùng để ghi nhớ các kết quả (kể cả kết quả trung gian). Ví dụ: Để tìm USCLN có thể có nhiều thuật toán như Thuật toán 1: ƒ Bước 1: Phân tích các số a và b thành tích của các thừa số nguyên tố. ƒ Bước 2:lấy tích của các thừa số chung với số mũ nhỏ nhất làm USCLN ƒ Bước 3: Kết thúc xử lý Thuật toán 2 : Thuật toán Euclid cải tiến ƒ Bước 1: Chia a cho b tìm số dư r; ƒ Bước 2: Nếu r = 0 thì thông báo kết quả: UCLN là b và kết thúc công việc ƒ Bước 3: Nếu r > 0 thì gán giá trị b cho a, gán giá trị r cho b rồi quay trở lại thực hiện bước 1. Về hiệu quả cả về không gian và thời gian thì thuật toán 1 tồi hơn thuật toán Euclid đã trình bày trước đây rất nhiều vì số bước cần thiết thực sự để phân tích ra thừa số nguyên tố là rất lớn. Thuật toán 2 thực sự là một cải tiến so với thuật toán Euclid mà ta đã trình bày trước đây vì phép chia lấy phần dư thực tế đã thay cho hàng loạt phép trừ nói trong thuật toán Euclid. Vì vậy trong trường hợp chung nó tìm được USCLN với số bước xử lý ít hơn nhiều. Trong tin học có cả một ngành chuyên đánh giá độ phức tạp của thuật toán, chủ yếu là đánh giá về hiệu quả thời gian. Thực tế sử dụng cho thấy thách thức về không gian lưu trữ có thể giải quyết dễ hơn thách thức về thời gian thực hiện.