Bài giảng 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

Nội dung text: Bài giảng 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

1. TRƯỜNG ĐH CÔNG NGHỆ ĐỒNG NAI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số tiết lý thuyết: 45 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Số tiết thực hành: 30 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø A.V. Aho, J.E Hopcroft, J.D Ullman. Data structures and Algorithms, Addison Wesley, 1983. 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Buổi 5: Cấu trúc động, Danh sách liên kết đơn. 3
4. Nội Dung Chương Trình Ø Buổi 6: Đệ qui, 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Buổi 11: Ôn tập. 4
5. Hình Thức Thi Ø Giữa kỳ: Seminar theo nhóm Kiểm tra lý thuyết trên giấy Bài thu hoạch. Điểm cộng thêm Ø Cuối kỳ: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thi trắc nghiệm trên máy Ø Tổng điểm: 10 điểm. 5
6. 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 6
7. 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 7
8. Khái Niệm Về CTDL Và Thuật Toán Ø Niklaus Wirth: CTDL + Thuật toán = Chương trình Ø Cần nghiên cứu về thuật toán và CTDL! CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 8
9. 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 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!” 9
10. 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; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Quay lại bước 2; Bước 4: Tổng cần tìm là S. 10
11. 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 11
12. 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 12
13. 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT § Đôi lúc khó hiểu, không diễn đạt được thuật toán. 13
14. 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 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 14
15. 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT S i = i+1 15
16. 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Nhược điểm: § Không trực quan bằng lưu đồ khối. 16
17. 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: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Output: End 17
18. 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: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trả giá trị về: return [giá trị] Lời gọi hàm: (tham số) 18
19. Biểu Diễn Bằng Mã Giả v 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++; CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT end while; 19
20. 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 20
21. Độ 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT thuật toán: § Phương pháp thực nghiệm. § Phương pháp xấp xỉ toán học. 21
22. 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 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 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. 22
23. 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) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ä 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) 23
24. Đánh giá thuật giải Ø Gọi n là số lượng dữ liệu nhập vào và t là thời gian thực hiện một lệnh. Ø Tính f(n) là tổng số lần thực hiện các lệnh => T/gian thực hiện thuật toán là T = f(n)*t Ø Cho n-> vô cực thì f(n)->g(n); Ø O(g(n)) gọi là độ phức tạp của thuật toán CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 24
25. 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) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ä N! :O(N!) 25
26. Đồ thị hàm số n2 n log(n) a n Nhận xét: Ta thấy khi n->vc thì n3 n3 lớn rất nhanh, do đó những CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT thuật toán có độ phức tạp là O(n3),O(2n), O(n!), O(nn) khó sử dụng được khi n rất lớn 26
27. Vi dụ: đánh giá giải thuật tìm số lớn nhất của n số Ø Giải thuật: B0: nhập n và dãy n số nguyên a[0], a[1], ,a[n-1] B1: max=a[0]; i=1; B2: Trong khi i max thì max=a[i]; B2.2: i=i+1; B3: In max. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Đánh giá: trường hợp dữ liệu xấu nhất (dãy tăng) Tính các bước? 27
28. Tổng hợp các bước Bước Số lần thực hiện lệnh 1 2 2 n 2.1 2(n-1) 2.2 n-1 3 1 f(n)= 4n CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø G.sử: t =10-3ms (t.gian thực hiện 1 lệnh) Ø TH xấu nhất: T = 4n*10-3 Ø Cho n->vc thì f(n)->n Độ phức tạp của thuật toán: O(n) 28
29. Vi dụ: đánh giá giải thuật sort n số nguyên Ø Giải thuật: B0: nhập n, nhập dãy n số nguyên a[0], a[1], ,a[n-1] B1: i=0; B2: Trong khi i<n-1 lặp lại các bước sau: B2.1: m=i, j=i+1; B2.2: Trong khi j<n lặp lại các bước sau: B2.2.1: Nếu a[j]<a[m] thì m=j; B2.2.2: j=j+1; B2.3: Nếu (m!=i) thì { t=a[i]; a[i]=a[m]; a[m]=t; } B2.4: i=i+1; B3: In dãy a[0], a[1], ,a[n-1] . CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Đánh giá: trường hợp dữ liệu xấu nhất là dãy giảm Tính các bước? 29
30. Tổng hợp các bước Bước Số lần thực hiện lệnh gán 1 1 2 n 2.1 2(n-1) 2.2 n+(n-1)+ +2 = n(n+1)/2 – 1 = a 2.2.1 2(a-1) 2.2.2 a-1 2.3 3(n-1) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2.4 n-1 3 n TC f(n)= 30
31. Ø Cho n->vc thì f(n)->n2 Ø Vậy độ phức tạp của thuật toán là O(n2) . Ø Nhận xét chung: Nếu thuật toán có Ä Một vòng lặp thì độ phức tạp của thuật toán là O(n) Ä Hai vòng lặp lồng nhau là O(n2) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ä Ba vòng lặp lồng nhau là O(n3) Ä vv 31
32. 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 32
33. 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. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT § Tiết kiệm tài nguyên hệ thống. 33
34. 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 34
35. 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ẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Cập nhật, thay đổi chương trình theo yêu cầu (mới). 35
36. 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 § Đáp ứng quy trình làm phần mềm. Ø Tính trong sáng § Dễ hiểu và dễ chỉnh sửa CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Tính hữu hiệu. § Tài nguyên + giải thuật 36
37. Quy Trình Làm Phần Mềm Ø Bước 0: Ý tưởng (concept). Ø Bước 1: Xác định yêu cầu (Requirements Specification). Ø Bước 2: Phân tích (Analysis). Ø Bước 3: Thiết kế (Design). Ø Bước 4: Cài đặt (Implementation). Ø Bước 5: Thử nghiệm (Testing). CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ø Bước 6: Vận hành, theo dõi và bảo dưỡng (Operation, follow-up and Maintenance). 37
38. Các kiểu dữ liệu Ø Kiểu dữ liệu cơ sở Ø Kiểu dữ liệu cấu trúc (structure) Ø Kiểu dữ liệu động (Dynamic) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 38
39. Tổ chức Seminar Ø Mỗi nhóm 5 sinh viên Ø Mỗi buổi ~2 nhóm trình bày Ø Trình bày trong 20-30 phút (kể cả thảo luận) Ø Trình bày bằng slide (~30 slide) Ø Nội dung: Ä Mục tiêu, phạm vi của vấn đề Ä Mô tả thuật toán, hướng giải quyết CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ä Các ứng dụng có thể sử dụng Ä Kết luận 39
40. Tổ chức thảo luận trên group Ø Thảo luận theo chủ đề được đưa ra hàng tuần/tháng Ø Mục tiêu: Tăng khả năng làm việc nhóm và tìm kiếm thông tin. Ø Thắc mắc email tới về sacvn@yahoo.com CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 40
41. Chủ đề tuần đầu tiên Ø Các phương pháp tìm kiếm Ø Các khó khăn & Hướng giải quyết cho các bài toán tìm kiếm với dữ liệu lớn CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 41