Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về CTDL và thuật toán - Trịnh Quốc Sơn

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về CTDL và thuật toán - Trịnh Quốc Sơn

1. TRƢỜNG ĐH CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ThS. Trịnh Quốc Sơn CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 1
2. Tài Liệu Tham Khảo  Trần Hạnh Nhi, Dương Anh Đức. Giáo trình Cấu Trúc Dữ Liệu 1, ĐHQG Tp. HCM, 2000.  Robert Sedgewick. Cẩm nang thuật toán (bản dịch của nhóm tác giả ĐH KHTN), NXB Khoa học kỹ thuật, 1994.  P. S. Deshpande, O. G. Kakde. C & Data Structures, 2004.  Dr. Dobb's. Algorithms and Data Structures, 1999  A.V. Aho, J.E Hopcroft, J.D Ullman. Data structures and Algorithms, Addison Wesley, 1983. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 2
3. Nội Dung Chƣơng Trình  Buổi 1: Giới thiệu về CTDL & Giải Thuật. Các thuật toán tìm kiếm.  Buổi 2: Interchange Sort, Selection Sort, Bubble Sort, Insertion Sort.  Buổi 3: Shaker Sort, Shell Sort, Heap Sort.  Buổi 4: Quick Sort, MergeSort, Radix Sort.  Buổi 5: Cấu trúc động, Danh sách liên kết đơn. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 3
4. Nội Dung Chƣơng Trình  Buổi 6: Stack, Queue.  Buổi 7: Danh sách liên kết kép.  Buổi 8: Cây, Cây nhị phân, cây nhị phân tìm kiếm.  Buổi 9: Cây cân bằng (AVL).  Buổi 10: Các CTDL mở rộng.  Buổi 11: Ôn tập. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 4
5. CHƢƠNG 1 TỔNG QUAN VỀ CTDL VÀ THUẬT TOÁN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 5
6. Nội Dung  Tổng quan về CTDL và thuật toán  Các tiêu chuẩn của CTDL  Vai trò của CTDL  Độ phức tạp của thuật toán  Thực hiện và hiệu chỉnh chương trình  Tiêu chuẩn của chương trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 6
7. Sự Cần Thiết Của Thuật Toán  Tại sao sử dụng máy tính để xử lý dữ liệu? . Nhanh hơn. . Nhiều hơn. . Giải quyết những bài toán mà con người không thể hoàn thành được.  Làm sao đạt được những mục tiêu đó? . Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu hình máy  chi phí cao  . Nhờ vào các thuật toán hiệu quả: thông minh và chi phí thấp  “Một máy tính siêu hạng vẫn không thể cứu vãn một thuật toán tồi!” CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 7
8. Thuật Toán  Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi hành để đạt mục tiêu đề ra nào đó.  Ví dụ: Thuật toán tính tổng tất cả các số nguyên dương nhỏ hơn n gồm các bước sau: Bước 1: S=0, i=1; Bước 2: nếu i<n thì s=s+i; Ngược lại: qua bước 4; Bước 3: i=i+1; Quay lại bước 2; Bước 4: Tổng cần tìm là S. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 8
9. Các Tiêu Chuẩn Của Thuật Toán  Xác định  Hữu hạn  Đúng  Tính hiệu quả  Tính tổng quát CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 9
10. Biễu Diễn Thuật Toán  Dạng ngôn ngữ tự nhiên  Dạng lưu đồ (sơ đồ khối)  Dạng mã giả  Ngôn ngữ lập trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 10
11. Biểu Diễn Bằng Ngôn Ngữ Tự Nhiên  NN tự nhiên thông qua các bước được tuần tự liệt kê để biễu diễn thuật toán.  Ưu điểm: . Đơn giản, không cần kiến thức về về cách biểu diễn (mã giả, lưu đồ, )  Nhược điểm: . Dài dòng, không cấu trúc. . Đôi lúc khó hiểu, không diễn đạt được thuật toán. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 11
12. Lƣu Đồ  Là hệ thống các nút, cung hình dạng khác nhau thể hiện các chức năng khác nhau. A A Thực hiện A Gọi hàm A Vào / Ra dữ liệu Đúng B Begin End Sai Nút giới hạn bắt đầu / Điều kiện rẻ nhánh B kết thúc chƣơng trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 12
13. Biểu Diễn Bằng Lƣu Đồ Bắt đầu amax = a0 Tìm phần tử mang giá trị lớn nhất i = 1 trong mảng S i<n amax là lớn nhất Kết thúc Đ Đ amax < ai amax =ai S i = i+1 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 13
14. Biểu Diễn Bằng Mã Giả  Ngôn ngữ tựa ngôn ngữ lập trình: . Dùng cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C. . Dùng các ký hiệu toán học, biến, hàm.  Ưu điểm: . Đỡ cồng kềnh hơn lưu đồ khối.  Nhược điểm: . Không trực quan bằng lưu đồ khối. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 14
15. Biểu Diễn Bằng Mã Giả  Một số quy ƣớc 1. Các biểu thức toán học 2. Lệnh gán: “=” (AB) 3. So sánh: “==”, “!=” 4. Khai báo hàm (thuật toán) Thuật toán ( ) Input: Output: End CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 15
16. Biểu Diễn Bằng Mã Giả 5. Các cấu trúc: Cấu trúc chọn: if then [else ] fi Vòng lặp: while do do while ( ) for do od 6. Một số câu lệnh khác: Trả giá trị về: return [giá trị] Lời gọi hàm: (tham số) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 16
17. Biểu Diễn Bằng Mã Giả  Ví dụ: Tìm phần tử lớn nhất trong mảng một chiều. amax=a0; i=1; while (i<n) if (amax<ai) amax = ai; i++; end while; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 17
18. Biểu Diễn Bằng Ngôn Ngữ Lập Trình  Dùng ngôn ngữ máy tính (C, Pascal, ) để diễn tả thuật toán, CTDL thành câu lệnh.  Kỹ năng lập trình đòi hỏi cần học tập và thực hành (nhiều).  Dùng phương pháp tinh chế từng bước để chuyển hoá bài toán sang mã chương trình cụ thể. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 18
19. Độ Phức Tạp Của Thuật Toán  Một thuật toán hiệu quả: . Chi phí cần sử dụng tài nguyên thấp: Bộ nhớ, thời gian sử dụng CPU,  Phân tích độ phức tạp thuật toán: . N là khối lượng dữ liệu cần xử lý. . Mô tả độ phức tạp thuật toán qua một hàm f(N). . Hai phương pháp đánh giá độ phức tạp của thuật toán: . Phương pháp thực nghiệm. . Phương pháp xấp xỉ toán học. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 19
20. Phƣơng Pháp Thực Nghiệm  Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm.  Thống kê các thông số nhận được khi chạy các bộ dữ liệu đó.  Ưu điểm: Dễ thực hiện.  Nhược điểm: . Chịu sự hạn chế của ngôn ngữ lập trình. . Ảnh hưởng bởi trình độ của người lập trình. . Chọn được các bộ dữ liệu thử đặc trưng cho tất cả tập các dữ liệu vào của thuật toán: khó khăn và tốn nhiều chi phí. . Phụ thuộc vào phần cứng. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 20
21. Phƣơng Pháp Xấp Xỉ  Đánh giá giá thuật toán theo hướng tiệm xấp xỉ tiệm cận qua các khái niệm O().  Ưu điểm: Ít phụ thuộc môi trường cũng như phần cứng hơn.  Nhược điểm: Phức tạp.  Các trường hợp độ phức tạp quan tâm:  Trường hợp tốt nhất (phân tích chính xác)  Trường hợp xấu nhất (phân tích chính xác)  Trường hợp trung bình (mang tích dự đoán) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 21
22. Sự Phân Lớp Theo Độ Phức Tạp Của Thuật Toán  Sử dụng ký hiệu BigO  Hằng số : O(c)  logN : O(logN)  N : O(N)  NlogN : O(NlogN) Độ phức tạp tăng dần  N2 : O(N2)  N3 : O(N3)  2N : O(2N)  N! :O(N!) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 22
23. Dữ Liệu  Theo từ điển Tiếng Việt: số liệu, tư liệu đã có, được dựa vào để giải quyết vấn đề  Tin học: Biểu diễn các thông tin cần thiết cho bài toán. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 23
24. Cấu Trúc Dữ Liệu  Cách tổ chức lưu trữ dữ liệu.  Các tiêu chuẩn của CTDL: . Phải biểu diễn đầy đủ thông tin. . Phải phù hợp với các thao tác trên đó. . Phù hợp với điều kiện cho phép của NNLT. . Tiết kiệm tài nguyên hệ thống. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 24
25. Vai Trò Của Cấu Trúc Dữ Liệu  Cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán.  CTDL hỗ trợ cho các thuật toán thao tác trên đối tượng được hiệu quả hơn CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 25
26. Thực Hiện Và Hiệu Chỉnh Chƣơng Trình  Chạy thử.  Lỗi và cách sửa: . Lỗi thuật toán. . Lỗi trình tự. . Lỗi cú pháp.  Xây dựng bộ test.  Cập nhật, thay đổi chương trình theo yêu cầu (mới). CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 26
27. Tiêu Chuẩn Của Một Chƣơng Trình  Tính tin cậy . Giải thuật + Kiểm tra cài đặt  Tính uyển chuyển  Tính trong sáng . Dễ hiểu và dễ chỉnh sửa  Tính hữu hiệu. . Tài nguyên + giải thuật CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 THUẬT GIẢI VÀ LIỆU DỮ TRÚC CẤU 27