Thuật toán và tư duy thuật toán

Thuật toán và tư duy thuật toánRÈN LUYỆN TƯ DUY VÀ KHẢ NĂNG CÀI ĐẶT THUẬT TOÁN Ở TRƯỜNG PTHồ Cẩm Hà-ĐHSPHN Mục tiêu Củng cố khái niệm và những đặc trưng cơ bản về thuật toán. Củng cố và phân tích thêm về thiết kế thuật toán Nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT * 1. THUẬT TOÁN Khái niệm thuật toán Máy tính và thuật toán Đánh giá thuật toán* 1.1 KHÁI NIỆM THUẬT TOÁN (1)Không đề cập đến khái niệm hình thức chính xác của thuật toán (định nghĩa thông qua mô hình máy Turing). Xem xét một số định nghĩa (không hình thức) ít nhiều khác nhau Bản chất mô tả một cách thức mà một nhiệm vụ hay một tiến trình được thực hiện như thế nào của thuật toán.* 1.1 KHÁI NIỆM THUẬT TOÁN (2)Định nghĩa 1(K.Rosen):Một thuật toán là một thủ tục xác định để giải một bài toán (vấn đề), sử dụng một số hữu hạn bước. Mỗi bước có thể gồm một hoặc một số thao tác/phép toán.* 1.1 KHÁI NIỆM THUẬT TOÁN (3) Định nghĩa 2.(G. Brookshear) Một thuật toán là một tập hợp có thứ tự các bứớc không nhập nhằng, thực hiện được, xác định một tiến trình có kết thúc, (tức việc thực hiện thuật toán phải dẫn tới một kết thúc). * 1.1 KHÁI NIỆM THUẬT TOÁN (4) Định nghĩa 3.(A. V. Aho, J.E. Hopcroft, J. D. Ullman) Thuật toán là một dãy hữu hạn các câu lệnh, mỗi câu lệnh đều có một ý nghĩa rõ ràng và có thể được thực hiện với một lượng công sức hữu hạn trong một thời gian hữu hạn. * 1.1 KHÁI NIỆM THUẬT TOÁN (5) Định nghĩa 4. (C. A. Shaffer) Một thuật toán là một bảng chỉ dẫn để giải một bài toán, trong đó các bước là cụ thể và không nhập nhằng. Thuật toán phải đúng đắn theo nghĩa nó phải tính đúng hàm mong muốn , chuyển đổi mỗi đầu vào (dữ liệu vào) thành đầu ra (dữ liệu ra) đúng, có độ dài hữu hạn và phải kết thúc với mọi dữ liệu vào hợp lệ.* 1.1 KHÁI NIỆM THUẬT TOÁN (6) Các tính chất: Đầu vào (dữ liệu vào) có các giá trị đầu vào được lấy từ một tập xác định. Đầu ra (kết quả ra) Từ một tập các giá trị đầu vào, thuật toán sản sinh ra các giá trị đầu ra thuộc một tập xác định. Các giá trị đầu ra chứa lời giải của bài toán.Tính xác định Các bước trong một thuật toán phải được định nghĩa chính xác (không nhập nhằng).* 1.1 KHÁI NIỆM THUẬT TOÁN (7) Các tính chất (tiếp) Tính hữu hạn Phải cho kết quả (đầu ra) mong đợi sau một số hữu hạn bước (có thể rất lớn) với mọi đầu vào thuộc tập các dữ liệu vào hợp lệ. Tính hiệu quả Phải có khả năng thực hiện mỗi bước của thuật toán một cách đúng đắn (chính xác) và trong một thời gian chấp nhận được.Tính tổng quát (phổ dụng) phải được áp dụng cho mọi bài toán có chung một dạng, mà không phải chỉ cho riêng một tập các dữ liệu vào đặc biệt.* 1.1 KHÁI NIỆM THUẬT TOÁN (8) Không chỉ có trong tin học, có nhiều thuật toán mô tả nhiều loại tiến trình của đời sống hàng ngày như đan áo len, làm một loại bánh, chơi một bản nhạc, pha một tách cà phê,... Nói chung, một tác nhân thực hiện một tiến trình được gọi là một bộ xử lý. Một bộ xử lý có thể là một người, một máy tính hay một thiết bị cơ hoặc điện nào đó. * 1.2 Máy tính và thuật toán (1)MT là một bộ xử lý đặc biệt với các đặc trưng về Tốc độ Tính tin cậy Bộ nhớ Chi phí* 1.2 Máy tính và thuật toán (2)Để bộ xử lý có thể thực thi một tiến trình: Nó phải đ­ược cung cấp một thuật toán thích hợp Nó phải có khả năng lý giải (cũng gọi là thông dịch) thuật toán, tức phải có khả năng :hiểu đ­ược ý nghĩa mỗi bước của thuật toán ;thực hiện đ­ược thao tác ( phép toán) t­ương ứng.VD* 1.2 Máy tính và thuật toán (3)Trư­ờng hợp bộ xử lý là một máy tính thì thuật toán phải đư­ợc biểu thị d­ưới dạng một chư­ơng trìnhĐể thực thi một tiến trình trên một máy tính, cần phải : Thiết kế một thuật toán (đư­a ra một mô tả tiến trình phải đ­ược thực hiện như­ thế nào); Biểu thị thuật toán thành một chư­ơng trình trong một ngôn ngữ lập trình thích hợp (cài đặt); Cho máy tính thực hiện chư­ơng trình (chạy chư­ơng trình).* 1.2 Máy tính và thuật toán (4)Vai trò của thuật toán là cơ bản. Không có thuật toán không có chư­ơng trình  không có gì để thực hiện.Các thuật toán còn là cơ bản: độc lập với ngôn ngữ đư­ợc dùng để biểu thị thuật toán; độc lập với các máy tính thực hiện chúng. Các thuật toán có thể đ­ược thiết kế và nghiên cứu độc lập với công nghệ hiện hành: các kết quả vẫn giữ nguyên giá trị bất kể sự ra đời của các máy tính và các ngôn ngữ lập trình mới. * 1.3 Đánh giá thuật toánXem tài liệu* Thế nào là không nhập nhằng? Thông tin về trạng thái của tiến trình phải đủ để xác định duy nhất và đầy đủ các hành động được đòi hỏi ở mỗi bướcThực hiện mỗi bước không đòi hỏi kỹ năng sáng tạo mà chỉ cần có khả năng làm theo các mệnh lệnh.THẢO LUẬN THÊM* 2. THIẾT KẾ THUẬT TOÁN (1) Các cấu trúc điều khiển Tinh chế thuật toán từng bước một Tính đơn thể. Các chiến lược thiết kế thuật toán* 2. THIẾT KẾ THUẬT TOÁN (2)Việc thiết kế một thuật toán là một công việc trí óc khó khăn, đòi hỏi phải có sáng tạo, sự am hiểu lĩnh vực ứng dụng và không thể đư­a ra một tập các quy tắc chung. Không có thuật toán nào cho việc thiết kế thuật toán.* 2.1 Các cấu trúc điều khiểnCấu trúc tuần tựThông th­ường các bước của một thuật toán đ­ược thực hiện theo đúng trình tự viết của chúng: Các bước đư­ợc thực hiện từng bước một ; Mỗi bước đư­ợc thực hiện đúng một lần ; Thứ tự các bứớc đ­ược thực hiện chính là thứ tự chúng đư­ợc viết trong thuật toán ; Sự dừng của bước cuối cùng kéo theo sự dừng của thuật toán.* 2.1 Các cấu trúc điều khiểnCấu trúc tuần tự (2)Dễ thấy là, nếu một thuật toán chỉ là một dãy các bước thì sẽ không mềm dẻo chút nào vì cách thực hiện của nó là cố định và không thể đư­ợc thay đổi theo các tình huống khác nhau.Ví dụ: Thuật toán “pha một cốc cafe tan” để một robot phục vụ:- - - Đun n­ước sôiCho cafe vào cốcCho nư­ớc sôi vào cốcNếu xảy ra một số tình huống....* 2.1 Các cấu trúc điều khiểnCấu trúc tuyển chọn (rẽ nhánh)Nếu điều kiện Thì b­ước 1Còn không bư­ớc 2 Cấu trúc tuyển chọn (hay câu lệnh tuyển chọn nếu ta xét một thuật toán đư­ợc biểu diễn d­ưới dạng một chư­ơng trình ) cho phép thực hiện theo một trong nhiều nhánh khác nhau của một thuật toán tuỳ thuộc vào một tình huống nhất định* 2.1 Các cấu trúc điều khiểnCấu trúc tuyển chọn (rẽ nhánh)Bộ xử lý phải có khả năng thông dịch các điều kiện trong một thuật toán đúng như­ nó phải có khả năng thông dịch các bước. Các điều kiện do đó cũng đư­ợc tinh chế tới khi chúng đủ chi tiết và chính xác để cho phép bộ xử lý thông dịch chúng.* 2.1 Các cấu trúc điều khiểnCấu trúc lặpCác cấu trúc tuần tự và tuyển chọn là ch­ưa đủ để diễn đạt các thuật toán có độ dài thay đổi tuỳ theo các tr­ường hợp. Cái ta cần là một cách thức lặp lại một số bư­ớc trong thuật toán một số lần tuỳ ý. Ví dụ:?* 2.1 Các cấu trúc điều khiểnCấu trúc lặp (2)Lặp.khi (while ... Do)Lặp ... đến khi (repeat until)Sức mạnh của phép lặp là nó cho phép một tiến trình có thời gian không xác định đ­ược mô tả bởi một thuật toán có độ dài hữu hạn.một trong những lỗi thư­ờng gặp khi thiết kế thuật toán là xác định không đúng điều kiện kết thúc của một vòng lặp* 2.2 TINH CHẾ THUẬT TOÁN (1)Tinh chế từng bước (hay thiết kế trên-xuống) là cách tiếp cận cho việc thiết kế thuật toán , thường được sử dụng rộng rãi và cho kết quả tốt.* 2.2 TINH CHẾ THUẬT TOÁN (2) Ý t­ưởng là chia tiến trình phải thực hiện thành một số b­ước, mỗi bư­ớc có thể được mô tả bởi một thuật toán nhỏ và đơn giản hơn so với thuật toán cho toàn bộ tiến trình.Vì mỗi thuật toán nhỏ là đơn giản hơn , ng­ười thiết kế th­ường có một ý t­ưởng sáng rõ hơn về cách thức xây dựng nó và có thể phác thảo nó chi tiết hơn là nếu làm ngay với toàn bộ thuật toán. Tới lư­ợt mình, các thuật toán nhỏ lại đư­ợc chia thành những phần nhỏ hơn mà với tính đơn giản hơn nữa của chúng, có thể đ­ược biểu diễn chi tiết hơn và chính xác hơn. Tinh chế thuật toán đ­ược tiếp tục theo cách đó cho tới khi mỗi một bư­ớc của nó đã đủ chi tiết và chính xác để bộ xử lý có thể thực hiện đư­ợc.* 2.2 TINH CHẾ THUẬT TOÁN (3)Ví dụ minh họa?* 2.3 TÍNH ĐƠN THỂ (1)Trong quá trình thiết kế một thuật toán theo cách tinh chế dần từng b­ước, thư­ờng thì các thành phần nhỏ hơn thu đư­ợc có thể hoàn toàn độc lập với thuật toán chính theo nghĩa chúng có thể đ­ược thiết kế mà không cần xét tới ngữ cảnh trong đó chúng đ­ược sử dụng.* 2.3 TÍNH ĐƠN THỂ (2)Một thành phần như­ vậy có thể:đ­ược thiết kế bởi một ngư­ời nào đó kháccó thể được dùng xem nh­ư một thành phần của một thuật toán hoàn toàn khác. Thành phần đ­ược “cấy vào”(cắm phích) một khi đã được thiết kế , có thể đư­ợc tham gia vào bất kỳ thuật toán nào cần tới nó* 2.3 TÍNH ĐƠN THỂ (ví dụ)Robot có thể giải thích (thông dịch) và thực hiện các lệnh có dạng : dịch chuyển (x) Đi thẳng x cm Trái (x) quay x độ về bên trái Phải (x) quay x độ về bên phảiNhấc bút lên nhấc bút lên khỏi mặt giấy hạ bút xuống đặt bút xuống mặt giấy* 2.3 TÍNH ĐƠN THỂ (ví dụ)Giả sử ta muốn robot vẽ hai hình vuông đồng tâm như được chỉ ra trong hình sau     Hai hình vuông đồng tâm mà robot phải vẽ khi thoạt đầu nó ở điểm X là tâm điểm của hai hình vuông. * 2.3 TÍNH ĐƠN THỂ (ví dụ)Giả sử robot lúc đó mặt nhìn vào tờ giấy và bút đang được nhấc lên. Phiên bản đầu tiên của thuật toán: (1) Dịch chuyển tới điểm AVẽ một hình vuông có cạnh 10cm Dịch chuyển tới điểm B Vẽ một hình vuông có cạnh 20cm* 2.3 TÍNH ĐƠN THỂ (ví dụ)Bước 2 và bước 4 của thuật toán trên bao gồm việc vẽ một hình vuông, là một quá trình tự đầy đủ, hoàn toàn độc lập với phần còn lại của thuật toánMột môđun là một thuật toán tự đầy đủ và có thể được thiết kế độc lập với ngữ cảnh trong đó nó được sử dụng. Một thuật toán sử dụng một môđun được nói là gọi tới môđun. (Chẳng hạn thuật toán trên gọi tới thủ tục vẽ hình vuông hai lần).* 2.3 TÍNH ĐƠN THỂ (ví dụ)module vẽhìnhvuông(kíchthước) For i:=1 to 4 do begin hạ bút xuống dịch chuyển (kíchthước ) nhấc bút lên trái (90) end; * 2.3 TÍNH ĐƠN THỂ (ví dụ)Tổng quát, một môđun có dạng sau module têncủamôđun (các tham số hình thức) { đặc tả tiến trình đưưîc môđun mô tả } ... thân của môđun ...* 2.3 TÍNH ĐƠN THỂMột lời gọi tới một môđun có dạng têncủamôđun ( các tham số thực sự ) Lời gọi đó sẽ được bộ xử lý hiểu như một lệnh thực hiện thân của môđun (tên được chỉ rõ), còn các tham số hình thức được thay thế bằng các tham số thực sự* 2.3 TÍNH ĐƠN THỂ tham số hình thức đ­ược xem nh­ư biểu diễn thông tin cần cho môđun khi nó đ­ược gọi tới tham số thực sự là các mảnh thông tin đ­ược cung cấp cho một lần gọi cụ thể và chúng sẽ thế chỗ của các tham số hình thức khi môđun đ­ược thực hiện.* 2.3 TÍNH ĐƠN THỂ (ví dụ)Có thể tinh chế thuật toán vẽ hai hình vuông đồng tâm như sau: (2) trái (45) dịch chuyển ( 50 ) { đi thẳng tới điểm A } trái (135) vẽ hình vuông (10) { vẽ hình vuông bên trong } trái (45) dịch chuyển ( 50 ) { đi thẳng tới điểm B} trái (135) vẽ hình vuông (20) { vẽ hình vuông bên ngoài }* 2.3 TÍNH ĐƠN THỂ (ví dụ)Người thiết kế thuật toán chính không cần biết môđun làm việc như thế nào , mà chỉ cần biết kết quả của việc thực hiện nó (chỉ cần đọc đặc tả ở đầu của môđun). Điều đó làm giảm độ phức tạp của quá trình thiết kế  có thiết kế tin cậy hơnĐặc tả của một thuật toán mô tả thuật toán làm gì mà không đi sâu vào cách thức làm như thế nào * 2.3 TÍNH ĐƠN THỂ (ví dụ)Xét một cách tiếp cận khác cho môđun vẽhìnhvuông: Thiết kế một môđun vẽ hình đa giác đều và sau đó gọi nó với các tham số thực sự thích hợp mỗi khi cần vẽ một hình vuông. * 2.3 TÍNH ĐƠN THỂ (ví dụ) module vẽđagiác ( kíchthưước, N ) For i:=1 To N Do begin hạ bút xuống dịch chuyển (kíchthước) nhấc bút lên trái ( 360/N ) end* 2.3 TÍNH ĐƠN THỂCác môđun phù hợp một cách tự nhiên với cách tinh chế thuật toán cho một thiết kế trên-xuống.Một môđun là một thành phần tự đầy đủ của một thuật toán lớn hơn bất kỳ gọi tới nó. Việc thiết kế môđun và thuật toán gọi tới nó có thể được thực hiện riêng biệt khiến quá trình thiết kế đơn giản và tin cậy hơn ( ít lỗi, ít sai sót hơn)* 2.3 TÍNH ĐƠN THỂĐể sáp nhập (cấy) một mô đun vào một thuật toán, chỉ cần biết thuật toán làm gì mà không cần biết nó làm như thế nào.Dùng môđun làm đơn giản việc thiết kế thuật toán, nên việc hiểu thuật toán cũng dễ dàng hơn. Do đó, trong trường hợp cần phải sửa đổi thuật toán thì công việc cũng dễ dàng, thuận lợi hơn.* 2.3 TÍNH ĐƠN THỂMột khi một môđun đã được thiết kế, nó có thể được “cấy” vào một thuật toán cần tới nó  có thể xây dựng một thư viện các môđun, phục vụ cho những ứng dụng thuộc một chủ đề nào đó. BÀI TẬP THỰC HÀNHHỆ THỐNG THÔNG TIN