CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã chương: Mh1701 Giới thiệu: Tổng quan về giải thuật. Đầu tiên là cách phân tích 1 vấn đề, từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng máy tính. Tiếp theo, các phương pháp phân tích, đánh giá độ phức tạp và thời gian thực hiện giải thuật cũng được xem xét trong chương. Mục tiêu: Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật.
Trình bày được các tiêu chuẩn để đánh giá độ phức tạp của giải thuật. Ghi nhớ được các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tượng và các cấu trúc dữ liệu cơ bản. Thực hiện các thao tác an toàn với máy tính. Nội dung chính: 1.Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật Mục tiêu: Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải thuật.
Trình bày được các tiêu chuẩn để đánh giá độ phức tạp của giải thuật. Khái niệm giải thuật Giải thuật, còn gọi là thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin học. Thuật ngữ thuật toán xuất phát từ nhà toán học Arập Abu Ja'far Mohammed ibn Musa al Khowarizmi (khoảng năm 825). Giải thuật thể hiện một giải pháp cụ thể, thực hiện từng bước một để đưa tới lời giải cho một bài toán.
Nói cách khác, giải thuật là một tập hữu hạn các phép toán cơ sở, được sắp đặt theo những quy tắc chính xác, nhằm giải một bài toán, hay là một bộ các qui tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn, nhằm cung cấp một kết quả từ một tập hợp c ủa các dữ kiện đưa vào. Các phép toán cơ sở là những phép toán đơn giãn mà thời gian thực hiện nó là hữu hạn và không phụ thuộc vào kích thước của dữ liệu. 10 Các phép toán trong giải thuật phải được xác định rỏ ràng, dễ hiểu, không mập mờ. Với mọi bộ dữ liệu vào thoả mãn các điều kiện của bài toán, thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện 1.
Ngôn ngữ diễn đạt giải thuật Ngôn ngữ tự nhiên. Giả ngữ, là một ngôn ngữ ”tựa ngôn ngữ lập trình”. Ngôn ngữ lập trình (Pascal, C,. Trong tài liệu này chúng ta sử dụng ngôn ngữ tựa Pascal để trình bày.
Sau đây là một số qui tắt cơ bản: 1. Quy cách về cấu trúc chương trình Mỗi chương trình đều được gán một tên để phân biệt, tên này được viết bằng chữ in hoa, có thể có thêm dấu gạch nối và bắt đầu bằng từ khoá Program Ví d ụ : Prorgram NHANMATRAN Độ dài tên không hạn chế. Sau tên có thể kèm theo lời thuyết minh (ở đây ta quy ước dùng Tiếng Việt) để giới thiệu tóm tắt nhiệm vụ của giải thuật hoặc một số chi tiết cần thiết. Phần thuyết minh được đặt giữa hai dấu {.
Chương trình bao gồm nhiều bước, mỗi bước được phân biệt bởi số thứ tự, có thể kèm theo những lời thuyết minh. Kí tự và biểu thức Kí tự dùng ở đây cũng giống như trong các ngôn ngữ chuẩn, nghĩa là gồm : 26 chữ cái Latinh in hoa hoặc in thường 10 ch ữ s ố th ậ p phân Các dấ u phép toán s ố họ c: +, , *, /, (lũy th ừ a) Các dấu phép toán quan hệ: <, =, >, , , #. Giá tr ị logic : true, false D ấ u phép toán logic : and, or, not Tên bi ế n là dãy ch ữ cái và ch ữ s ố , b ắ t đ ầ u b ằ ng ch ữ cái Biến chỉ số có dạng : A[i], B[ij] v. 11 Còn biểu thức cũng như thứ tự ưu tiên của các phép toán trong biểu thức cũng theo quy tắc như trong PASCAL hay các ngôn ngữ chuẩn khác.
Các câu lệnh Các câu lệnh trong chương trình được viết cách nhau bởi dấu chấm phảy chúng bao gổm : Câu l ệ nh gán Có dạng Tên biến/ Tên hàm : = Biểu thức Ở đây cho phép dùng phép gán chung. Ví dụ : X : = Y : = 5 Câu l ệ nh ghép Có dạng : begin Câu l ệ nh 1 ; Câu l ệ nh 2 ;. ; Câu l ệ nh n end Nó cho phép ghép nhiều câu lệnh lại để được coi như một câu lệnh. Câu l ệ nh đi ề u ki ệ n Có dạng : if < Điều kiện > then < Câu lệnh > Có thể diễn tả bởi sơ đồ : Hoặc true Câu lệnh1 Điều if < Điều kiện > then < Câu lệnh1 > else < Câu lệnh2 > false Câu lệnh2 Câu lệnh tuyến Điều true Câu lệnh Case kiện Điều kiện1: Câu lệnh1; falselệnh ; Điều kiện2: Câu 2 12 …… …… Điều kiệnn: Câu lệnhn; Else: Câu lệnhn+1 End case Câu lệnh này cho phân biệt các tình huống xử lí khác nhau trong các điều kiện khác nhau mà không phải tới các câu lệnh if – then – else khác nhau.
Có thể diễn tả bởi sở đồ : false false false Vài điBể1 m linh động B2 Bn Sn+1 esle có thể không có mặt tru tru lệnhi(i = 1, 2,tru…, n) có thể được thay thế bằng Câu Chúm ột dãy các câu thích: e e không cần phảei đặt giữa : begin và end. lệnh mà Bi: Điều kiện S S2 Sn Si: Câu lệnh Câu lệ1 nh lặp Với số lần lặp biết trước : for i : = m to n do < Câu lệnh>. nhằm thực hiện < Câu lệnh > với i lấy giá trị nguyên từ m tới n ( n m) với bước nhảy tăng bằng 1, hoặc : for i := n down to m do < Câu lệnh> tương tự như câu lệnh trên vơi bước nhảy giảm bằng 1. Với số lần lặp không biết trước: 13 While < Điều kiện > do < Câu lệnh> Chừng nào mà < Điều kiện > có giá trị bằng true thì thực hiện < Câu lệnh> true Câu lệnh Điều Hoặc : kiện repeat < Câu lệnh> until < Điều kiện > Lặp lại < Câu lệnh> cho tới khi < Điều kiện > có giá trị true.
false Câu lệnh nhập: read (<danh sách biến>) Câu lệnh xu Câuấtlệ: nh write(<danh sách biến hoặc dòng kí tự>)fasle Điều các biến trong danh sách cách nhau bởi dấu phkiẩệy.n Dòng kí tự là một dãy các kí tự đặt giữa hai dấu nháy’ ‘. Câu lệnh kết thúc chương trình: End 1. Chương trình con true Chương trình con hàm Có dạng : Function <tên hàm> (<danh sách tham số>) S1; S2; … ; Sn. 14 Return Chương trình con thủ tục Có dạng : Function <tên hàm> (<danh sách tham số>) S1; S2; … ; Sn.
Return Câu lệnh kết thúc chương trình ở đây là return thay cho end. Trong cấu tạo của chương trình con hàm bao giờ cũng có câu lệnh gán mà tên hàm nằm ở vế trái. Còn đối với chương trình con thủ tục thì không có. Lời gọi chương trình con hàm thể hiện bằng tên hàm cùng danh sách tham số thực sự, nằm trong biểu thức.
Còn với chương trình con thủ tục lời gọi được thể hiện bằng câu lệnh call có dạng : Call <tên thủ tục> (<danh sách tham số thực sự>) Chú ý : Trong các chương trình diễn đạt một giải thuật ở đây phần khai báo dữ liệu được bỏ qua. Nó được thay vởi phần mô ta cấu trúc dữ liệu bằng ngôn ngữ tự nhiên, mà ta sẽ nêu ra trước khi bước vào giải thuật. Thiết kế giải thuật Tạo lập giải thuật để giải một bài toán là một nghệ thuật mà không bao giờ có thể nêu đầy đủ ngay một lúc. Có nhiều phương pháp thiết kế giải thuật khác nhau.
Tuy nhiên ta cũng thấy rằng mọi việc sẽ đơn giản hơn nếu như có thể phân chia bài toán lớn thành những bài toán nhỏ hơn, điều đó có nghĩa là có thể coi bài toán của ta như là một Modul chính, cần chia thành các Modul con, và trên tinh thần như vậy đến các modul con ta có thể chia thành các modul nhỏ hơn, chia cho đến khi tới những modul con đủ nhỏ để có thể xử lý trực tiếp. Sau đó chỉ cần tổng hợp lại các phép xử lý để có giải thuật của bài toán gốc. Để làm được những điều đó, đứng trước một bài toán, thông thường ta phải: Xác định được rõ dữ liệu và yêu cầu : cho biết cái gì ?(dữ liệu input) và đòi hỏi cái gì ? ( dữ liệu output). Để giải quyết được yêu cầu thì “phải làm gì ?” : ở đây mới chỉ phân hoạch hỏi cái gì ? ( dữ liệu output).
Với mỗi công việc ấy thì “ phải làm thê nào “ ? 15 Trên cơ sở đó mới cụ thể hóa dần dần các phép xử lí để xây dựng giải thuật cần thiết. Tất nhiên, khi giải quyết câu hỏi “ làm thế nào ?” thì dữ liệu input cũng phải được định hình về cấu trúc. Ví dụ, ta xét bài toán : Sắp xếp là một dãy số ( a1,a2,….,an) thành một dãy số tăng dần. Như vậy dãy số input, nếu có dạng, chẳng hạn : (33, 77, 11, 55, 99, 22, 44, 88, 66) thì dãy số output phải có dạng : (11, 22, 33, 44, 55, 66, 77, 88, 99) Để có được kết quả output như vậy thì phải làm gì ? Có thể thấy rằng : sắp xếp theo thứ tự tăng dần nghĩa là : –Số bé nhất trong n số phải được đặt vào vị trí đầu tiên ; –Số bé nhất trong (n – 1 ) số còn lại phải được đặt vào vị trí thứ hai ; v.v… Như vậy sẽ có hai công việc chính phải làm : Chọn số bé nhất trong dãy số chưa được sắp.
Đặt nó vào vị trí sau phần tử cuối của dãy số đã được sắp ( nó lại trở thành phần tử cuối cho bước tiếp theo ). Chú ý rằng : lúc đầu dãy số được sắp còn rỗng, sau đó nó được bổ sung dần dần các phần tử vào. Các công việc trên sẽ được lặp lại (n 1) lần : đầu với n số, lần cuối với 2 số. Để thực hiện được hai công việc nêu trên thì phải “làm thế nào ? ” Trước hết phải nghĩ ngay tới : dãy số ở đây được định hình theo cấu trúc nào ? (cấu trúc dữ liệu) và được cài đặt trong máy theo cấu trúc nào ? (mà ta sẽ được gọi là : cấu trúc lưu trữ).
Thông thường nó được định hình và cài đặt theo cấu trúc vectơ. Ở đây có hai vectơ : vectơ input và vectơ output.