Đề cương ôn tập Cấu trúc dữ liệu và giải thuật
1, Các khái niệm: dữ liệu cơ sở, thuật toán, cấu trúc dữ liệu
– Dữ liệu cơ sở: Một tập hợp các phần tử dữ liệu ban đầu trong một bài toán
– Giải thuật (Algorithm): là một dãy các qui tắc chặt chẽ xác định một trình tự các thao tác trên một đối tượng cụ thể để giải quyết một vấn đề hoặc để hoàn thành một mục đích cuối cùng nào đó .
– Cấu trúc dữ liệu: là sự kết hợp các dữ liệu cơ sở theo một phương thức nào đó nhằm liên kết chúng thành một cấu trúc thống nhất tiện lợi cho quá trình xử lý
2, Các pp thiết kế dữ liệu TOP DOWN, BOTTOM UP
THIẾT KẾ TỪ TRÊN XUỐNG ( TOP DOWN DESIGN)
Đây là một phương pháp thiết kế giải thuật dựa trên tư tưởng module hoá.
Trước hết người ta xác định các vấn đề chủ yếu nhất mà việc giải quyết bài toán yêu cầu , bao quát được toàn bộ bài toán . Sau đó phân chia nhiệm vụ cần giải quyết thành các niệm vụ cụ thể hơn, tức là chuyển dần từ môdule chính đến các môdun con từ trên xuống dưới , do vậy phương pháp có tên gọi là thiết kế ” từ đỉnh xuống”(Top down design ) .
THIẾT KẾ TỪ DƯỚI LÊN ( BOTTOM UP DESIGN )
Tiến hành giải quyết các vấn đề cụ thể ,sau đó trên cơ sở đánh giá mức độ tương tự về chức năng của các vấn đề này trong việc giải quyết bài toán người ta gộp chúng lại thành từng nhóm cùng chức năng từ dưới lên trên cho đến môđun chính . Sau đó sẽ thiết kế thêm một số chương trình làm phong phú hơn ,đầy đủ hơn chức năng của các phân hệ và cuối cùng là thiết kế một chương trình làm nhiệm vụ tập hợp các môđun thành một hệ chương trình thống nhất, hoàn chỉnh.
3, PP xác định độ phức tạp giải thuật theo ký pháp chữ O lớn.
Thời gian tính toán T(n) của một giải thuật được gọi là có bậc f(n), ký hiệu: T(n)= O(f(n)) nếu tồn tại các số dương C và No sao cho : T(n) ≤ C .f(n) với mọi n ≥ No
Tức là T(n) bị chặn trên bởi một hằng số nhân với f(n) với mọi giá trị của n từ một điểm nào đó. Độ phức tạp của giải thuật này được gọi là O(F(n))
Ví dụ: độ phức tạp của 1 giải thuật là T(n) = 4n+5
Vì 4n+5 ≤ 4n+n với mọi n>5. Ta có: T(n) ≤ 5n với mọi n>5 .
Ta chỉ cần chọn f(n)=n, No=5 và C=5 chúng ta có thể viết: T(n) = O(n) .
Bất đẳng thức cũng đúng khi ta viết T(n)=O(5280n) hay T(n) = O(4n+5) hay T(n)= (3.1416 n+ 2.71828)