Tin học cơ sở - Chương 7

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ộ.Cho: Hồ sơ gốc của các cán bộ trong cơ quan
Nội dung trích xuất từ tài liệu:
Tin học cơ sở - Chương 7Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin CHƯƠNG 7. GIẢI THUẬT7.1. KHÁI NIỆM BÀI TOÁN VÀ GIẢI THUẬTTrướ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ộ.Cho: Hồ sơ gốc của các cán bộ trong cơ quanCần biết: 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): cái cho trước • Thông tin ra (output): cái cần tìmNhư vậy, việc cho một bài toán có nghĩa là mô t ả rõ input và output c ủa nó. Chobà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ôngcho 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ùngmột số hữu hạn số lần thực hiện các thao tác thích h ợp đ ể tìm đ ược output theoyê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 ạicủa output khi cho input và nếu có thể, xét xem có bao nhiêu l ời gi ải và nghiêncứ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 ầntì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 ọckhá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, định lý c ủa gi ải tích kh ẳng đ ịnh r ằng n ếuhàm f(x) liên tục trên đoạn [a, b] và f(a). f(b)Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tinVí dụ, cho hai số nguyên dương a, b. Cần xây d ựng gi ải thu ật đ ể tìm ước s ốchung lớn nhất (UCLN) của a và b. D ưới đây là gi ải thu ật Euclid đ ề xu ất cho bàitoá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 thì USCLN(a,b) = USCLN(b-a, a) n ếu a < b vàUSCLN(a,b) = USCLN(b, a-b) nếu a>b.Bài toán • input : a, b nguyên dương • output: UCLN của a và bGiải thuật EuclidBước 1: Nhập a và bBước 2: Nếu a = b thì lấy giá trị chung này làm USCLN rồi kết thúc.Bước 3: Nếu a> b thì bớt a đi một lượng là b rồi chuyển bước 5.Bước 4: Bớt b đi một lượng là a rồi quay trở lại bước 2.Bước 5: Kết thúc.Các thao tác bao gồm: • Phép gán 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 giải thuật trên ta gặp thao tác trở lại bước 2. Trong tr ườnghợp này bộ xử lý sẽ chuyển sang thực hiện bước 2 của giải thu ật. Khi di ễn đ ạtgiải thuật 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 ậybước 3 nếu không quay về bước 2 thì sẽ thực hiện tiếp bước 4.7.2. MỘT SỐ ĐẶC TRƯNG CỦA GIẢI THUẬTNgười ta thường liệt kê các đặc trưng sau đây của giải thuật:7.2.1. Tính kết thúc (tính dừng)Giải thuật phải đưa ra được output sau một số hữu hạn bước thực hi ện. Gi ảithuật 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 ảmthực sự nhưng không được hơn 2. Vì vậy quá trình trên nh ất đ ịnh ph ải d ừng saumột số hữu hạn bước.Lưu ý rằng số bước của một quy tắc thao tác có thể là h ữu hạn nh ưng quy t ắc đókhông có tính dừng. Ví dụ, Xét quy tắc sau:Bước 1: Xoá bảngBước 2: Vẽ hình trònBước 3: Quay lại bước 1Quy tắc đó có 3 bước nhưng không có tính dừng 53Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin7.2.2. Tính xác địnhTính xác định của giải thuật đòi hỏi ở mỗi b ước các thao tác ph ải hoàn toàn xácđịnh, đơn trị không có sự nhập nhằng, lẫn lộn, tuỳ ti ện. Nói cách khác, trong cùngmộ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 ướccủa giải thuật thì phải cho cùng một kết quả. Nhờ tính chất này mà việc thực hiện thuật toán thuần tuý mang tính c ơ h ọc,không cần bất kỳ một sự chỉ dẫn nào về cách giải bài toán cả.7.2.3. Tính phổ dụngTính phổ dụng có nghĩa là một giải thuật có thể được áp dụng v ới m ột l ớp các bàitoán với input thay đổi chứ không chỉ áp d ụng cho m ột tr ường h ợp c ụ th ể. Gi ảithuật 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 giải thuật thì tính phổ dụng chỉ là một tính chất th ường th ấy vì có nhi ều bàitoá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.2.4. Đại lượng vàoMỗi giải thuật có một hoặc nhiều đại lượng vào. Ví dụ, Gi ải thu ật Euclid ở trên cóđại lượng vào là a và b.7.2.5. Đại lượng raSau khi giải thuật đã được thực hiện xong nó phải cho ra kết qu ả: Ví d ụ, Gi ảithuật Euclid cho UCLN của 2 số a và b7.3. CÁC PHƯƠNG PHÁP DIỄN TẢ GIẢI THUẬTNgười ta thường diễn tả giải thuật 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 thao tác, các chỉ thị thực hiện bằng ngôn ng ữ t ự nhiên.Ví dụ, có N que diêm. Hai người chơi luân phiên b ốc diêm. M ỗi l ượt, m ỗi ng ườibốc từ 1 đến 3 que diêm. Người nào bốc cuối cùng s ẽ th ắng cu ộc. Giải thuật để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: Nhập N.Bước 2: Bốc 3 que rồi đợi đối phương đi.Bước 3: Đối phương bốc (giả sử x que, 0Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Hình 7.1. Các loại biểu diễn hình học trong sơ đồ khốiKhố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 ộthoặ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á ...