Giáo trình Nhập môn Tin học LỜi nóI ĐẦU
tải về 4.67 Mb.
|
- Điều hướng trang này:
- 3.2 Các đặc trưng của thuật giải
- 3.3 Các phương pháp biểu diễn thuật giải
- 3.3.2 Lưu đồ - sơ đồ khối
3.1. Khái niệmKhi viết một chương trình máy tính, ta thường cài đặt một phương pháp đã được nghĩ ra trước đó để giải quyết một vấn đề. Phương pháp này thường là độc lập với một máy tính cụ thể sẽ được dùng, nó hầu như thích hợp như nhau cho nhiều máy tính. Trong bất kỳ trường hợp nào thì phương pháp phải được nghiên cứu để làm thế nào đi sâu vào bài toán. Từ "Thuật giải" được dùng trong khoa học máy tính để mô tả một phương pháp giải bài toán. Thuật toán là "Chất liệu" của khoa học máy tính, chúng là những đối tượng nghiên cứu trung tâm trong nhiều, nếu không nói là hầu hết các lĩnh vực của Tin học. Thuật giải nổi tiếng nhất có từ thời cổ Hy lạp là thuật giải Euclid, thuật giải tìm ước số chung lớn nhất của 2 số m và n. Thuật toán này được mô tả như sau: -Dữ liệu vào (Input): m, n nguyên dương, giả sử m>n -Dữ liệu ra (Output): U, ước số chung lớn nhất của m và n -Phương pháp giải (Method): +Bước 1: Tìm phần dư r của phép chia m cho n (r= m mod n) +Bước 2: Nếu r=0 thì gán giá trị của n cho U ( U=n) và dừng lại. Trong trường hợp ngược lại (r0) thì m = n , n = r và quay lại bước 1. Chúng ta có thể quan niệm các bước cần thực hiện để nấu một nồi cơm là một thuật giải. Chúng ta đưa ra định nghĩa không hình thức về thuật giải như sau: Thuật giải là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện, để giải quyết một vấn đề. Với một vấn đề đặt ra, có thể có nhiều thuật toán giải. Một vấn đề có thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn vấn đề tìm nghiệm của hệ phương trình tuyến tính là vấn đề giải được. Một vấn đề không tồn tại thuật toán giải gọi là vấn đề không giải được (bằng thuật toán) Trên đây chúng ta đã trình bày định nghĩa không hình thức về thuật giải. Có thể xác định khái niệm thuật giải một cách chính xác bằng cách sử dụng các hệ hình thức như: máy Turing, hệ thuật toán Markôp, văn phạm Chomsky dạng 0,... Song vấn đề này không thuộc phạm vi chúng ta quan tâm. Đối với chúng ta, chỉ sự hiểu biết trực quan, không hình thức về khái niệm thuật giải là đủ.
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: 1. Input: Mỗi thuật giải cần có một số (có thể bằng không) dữ liệu vào. Đó là giá trị cần đưa vào khi thuật giải bắt đầu làm việc. Chẳng hạn trong thuật giải Euclid trên thì m và n là các dữ liệu vào 2. Output: Mỗi thuật giải cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có quan hệ xác định với giá trị vào và là kết quả của sự thực hiện thuật giải. Trong thuật giải Euclid thì dữ liệu ra là U. 3. Tính xác định: Mỗi bước của thuật giải cần phải được mô tả một cách chính xác, chỉ có một cách hiểu duy nhất. Bởi vì, nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những người thực hiện thuật giải khác nhau có thể cho ra kết quả khác nhau. Nếu ta mô tả thuật giải bằng ngôn ngữ tự nhiên, không có gì đảm bảo người đọc hiểu đúng ý của người viết thuật giải, bởi ngôn ngữ tự nhiên thường là đa nghĩa. Để đảm bảo đòi hỏi này, thuật giải cần được mô tả trong một ngôn ngữ lập trình, chẳng hạn một ngôn ngữ lập trình (Pascal, C...). trong các ngôn ngữ này, các mệnh đề được tạo thành theo các qui tắc cú pháp nghiêm nghặt và chỉ có một ý nghĩa duy nhất. 4. Tính khả thi: Tất cả các phép giải có mặt trong các bước của thuật giải phải đủ đơn giản. Điều đó có nghĩa là các phép giải phải sao cho, ít nhất về nguyên tắc có thể thực hiện được bởi con người trong một khoảng thời gian hữu hạn. Chẳng hạn trong thuật giải Euclid, ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh. 5. Tính dừng: Với mọi bộ dữ liệu vào thoả mãn điều kiện qui định, thuật giải phải dừng lại sau một số hữu hạn bước thực hiện. Chẳng hạn đối với thuật giải Euclid là thuật giải thoả mãn điều kiện này. Bởi vì số dư r luôn nhỏ hơn n, nếu r0 thì giá trị của n ở bước sau là giá trị của r ở bước trước, ta có n>r=n1>r1=n2>r2.....Dãy số nguyên dương giảm dần cần phải kết thúc ở 0, do đó sau một số bước giá trị của r=0 thuật giải dừng. 3.3 Các phương pháp biểu diễn thuật giải3.3.1 Ngôn ngữ tự nhiênTrong cách biểu diễn thuật giải theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật giải (Các ví dụ về thuật giải trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật giải cũng như người đọc thuật giải phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật giải, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật giải bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, ... Bạn có thể tham khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật giải theo ngôn ngữ tự nhiên. 3.3.2 Lưu đồ - sơ đồ khốiLưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật giải. Biểu diễn thuật giải bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật giải. Phương pháp lưu đồ thường được dùng trong những thuật giải có tính rắc rối, khó theo dõi được quá trình xử lý. Vẽ lưu đồ hoặc sơ đồ khối, mỗi khối mô tả một bước. Sử dụng mũi tên nối khối này với khối kia để chỉ trình tự thực hiện các bước. Để dễ dàng nhận biết chức năng của từng khối, mỗi khối được thể hiện ở một dạng như sau: - - Kết thúc - Thực hiện công việc
- Điều kiện Ví dụ 3.1:. Tìm nghiệm thực của phương trình bậc hai ax2+bx+c=0. Thuật toán được dạy gồm các bước sau: + Nhập dữ liệu a, b, c. + Tính biệt số = b2-4ac. + So sánh với 0. Bước tiếp theo sẽ phụ thuộc vào giá trị của . + Nếu <0, đáp số của bài toán là “Vô nghiệm”. + Nếu =0, tính và ghi đáp số trị của nghiệm kép  .
+ Nếu >0, tính và ghi đáp số trị của hai nghiệm phân biệt:   .
Lưu đồ biểu diễn thuật toán này được thể hiện như sau: 
Каталог: file -> downloadfile9 file -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc file -> TIÊu chuẩn quốc gia tcvn 7790-5 : 2008 iso 2859-5 : 2005 file -> Qcvn 81: 2014/bgtvt file -> UỶ ban nhân dân cộng hòa xã HỘi chủ nghĩa việt nam file -> VIỆn chăn nuôi trịnh hồng sơn khả NĂng sản xuất và giá trị giống của dòng lợN ĐỰc vcn03 luậN Án tiến sĩ NÔng nghiệp hà NỘI 2014 downloadfile9 -> Môn: Sinh học lớp 11 Câu 1 downloadfile9 -> Đề cương ôn thi Olympic 30/4 môn Sinh Biên soạn: Nguyễn Hoàng Thiên Tân downloadfile9 -> Họ và tên: Lớp: ĐỀ thi số 5 MÔN: dinh dưỠng học ngàNH: bqcbns downloadfile9 -> Đề tài Tìm hiểu về lợi ích của alexa downloadfile9 -> Em xin chân thành cảm ơn! Hải Dương, ngày 31tháng 5 năm 2012 Sinh viên Vũ Tiến Duy MỤc lụC tải về 4.67 Mb. Chia sẻ với bạn bè của bạn:
|
Bắt đầu
