Bài giảng Cấu trúc dữ liệu và giải thuật

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT BÀI GIẢNG Trần Đăng Hưng Khoa CNTT - ĐHSPHN Giới thiệu  Mục tiêu môn học  Cung cấp các kiến thức về các loại cấu trúc dữ liệu, các chiến lược thiết kế thuật toán, và kỹ năng sử dụng các cấu trúc dữ liệu trong giải thuật  Rèn luyện kỹ năng lập trình với các bài toán có sử dụng các cấu trúc dữ liệu trong ngôn ngữ lập trình C++  Thời lượng: 3 tín chỉ  Thời gian: tiết 3-5, thứ 3  Phòng học: Phòng máy số 2, Tầng 2 nhà C.  Hình thức thi: trên máy  Liên hệ: [email protected]  Website: 1 September 2015 CTDL> - Trần Đăng Hưng 2 Giới thiệu 1 September 2015 CTDL> - Trần Đăng Hưng 3  Tài liệu tham khảo [1] Giải thuật và Lập trình, Lê Minh Hoàng, ĐHSPHN [2] Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi, [3] Cấu trúc dữ liệu và thuật toán, Đinh Mạnh Tường  Môi trường lập trình  Ngôn ngữ: C/C++  Dev C++,  Giảng viên  Lý thuyết và bài tập: TS. Trần Đăng Hưng  Thực hành: ThS. Nguyễn Thị Phương Dung  Kiểm tra & Đánh giá  Chuyên cần: 10%  Giữa kì (thi trên máy): 30%  Thi kết thúc học phần (trên máy): 60% Nội dung 1 September 2015 CTDL> - Trần Đăng Hưng 4  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm Nội dung 1 September 2015 CTDL> - Trần Đăng Hưng 5  Chương 1: Giới thiệu  Chương 2: Đệ quy và Giải thuật đệ quy  Chương 3: Quy hoạch động  Chương 4: Danh sách móc nối  Chương 5: Stack và Queue  Chương 6: Cây và Ứng dụng  Chương 7: Đồ thị và Ứng dụng  Chương 8: Các thuật toán sắp xếp  Chương 9: Các thuật toán tìm kiếm Các bước giải bài toán tin học (1/2) 1 September 2015 CTDL> - Trần Đăng Hưng 6  Xác định bài toán  Cần xác định xem giải quyết vấn đề gì?  Những giả thiết nào đã cho (ràng buộc)  Những yêu cầu về lời giải (như tốc độ, độ lớn của dữ liệu)  Tìm thuật toán  Phù hợp cho bài toán đặt ra  Tìm cấu trúc dữ liệu biểu diễn  CTDL biểu diễn được input và output của bài toán  CTDL phù hợp với thuật toán  CTDL cài đặt được trên ngôn lập trình Các bước giải bài toán tin học (2/2) 1 September 2015 CTDL> - Trần Đăng Hưng 7  Lập trình  Có khả năng chuyển từ thuật toán thành chương trình máy tính  Thành thạo ngôn ngữ lập trình (Pascal, C/C++, JAVA,)  Có kỹ thuật lập trình tốt (dễ đọc, dễ hiểu, dễ sửa đổi)  Kiểm thử  Phát hiện lỗi trong chương trình  Lỗi cú pháp (dễ phát hiện)  Lỗi cài đặt (cài đặt sai thuật toán)  Lỗi thuật toán (thuật toán sai trong một số trường hợp)  Thiết kế các bộ dữ liệu test  Bộ test đa dạng: nhỏ, vừa, và to để kiểm chứng khả năng chịu lỗi của chương trình Thuật toán 1 September 2015 CTDL> - Trần Đăng Hưng 8  Khái niệm: Thuật toán là một hệ thống rõ ràng và chặt chẽ các quy tắc cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn  Ví dụ: thuật toán Euclide tìm USCLN của 2 số Đặc trưng của thuật toán 1 September 2015 CTDL> - Trần Đăng Hưng 9  Tính đơn nghĩa  Tại mỗi bước các thao tác rõ ràng, không gây nhập nhằng  Tính dừng  Thuật toán phải dừng sau 1 số hữu hạn bước  Tính đúng  Luôn cho kết quả đúng với yêu cầu bài toán với tất cả các bộ dữ liệu vào  Tính phổ dụng  Dễ sửa đổi  Tính khả thi  Thực hiện được với dữ liệu lớn và có thể lập trình được Biểu diễn thuật toán 1 September 2015 CTDL> - Trần Đăng Hưng 10  Bằng ngôn ngữ tự nhiên  Bằng mã giả (Pseudocode)  Bằng sơ đồ khối  Bằng ngôn ngữ lập trình Độ phức tạp của giải thuật 1 September 2015 CTDL> - Trần Đăng Hưng 11  Làm thế nào để đánh giá một giải thuật tốt hay không?  Làm sao so sánh được hai giải thuật với nhau?  Thời gian thực hiện giải thuật phụ thuộc vào những yếu tố nào?  Máy tính  Dữ liệu vào  Ngôn ngữ lập trình Cần phân tích độ phức tạp của giải thuật. Các kí pháp đánh giá độ phức tạp tính toán 1 September 2015 CTDL> - Trần Đăng Hưng 12  Cho bài toán với dữ liệu vào n, giả sử thời gian thực hiện giải thuật là T(n) và g(n) là một hàm xác định dương với mọi n.  Khi đó, độ phức tạp tín toán kí hiệu là: O(g(n)) nếu tồn tại số dương c và n0 sao cho T(n)  c.g(n) với mọi n  n0  Ngoài ra còn có các kí hiệu khác. Các quy tắc xác định độ phức tạp tính toán 1 September 2015 CTDL> - Trần Đăng Hưng 13  Quy tắc loại bỏ hằng số  Một đoạn chương trình có độ phức tạp T(n) = O(c.g(n)), với c > 0, thì T(n) = O(g(n)).  Quy tắc lấy max  Một đoạn chương trình có độ phức tạp T(n) = O(g(n) + f(n)), thì T(n) = O(max(g(n), f(n))).  Quy tắc cộng  Hai đoạn chương trình có độ phức tạp là T1(n) = O(g(n)) và T2(n) = O(f(n)), thì độ phức tạp để thực hiện hai đoạn chương trình này nối tiếp nhau là: T(n) = T1(n) + T2(n) = O(g(n) + f(n))  Quy tắc nhân  Nếu đoạn chương trình có T(n) = O(f(n)), thực hiện k(n) lần đoạn chương trình này, với k(n) = O(g(n)), thì T(n) = O(f(n).g(n)) Một số tính chất 1 September 2015 CTDL> - Trần Đăng Hưng 14  T(n) = hằng số, thì kí hiệu O(1)  T(n) = O(g(n)), mà g(n) là một hàm bậc k, thì kí hiệu O(nk)  Nếu độ phức tạp phụ thuộc tình trạng dữ liệu vào, xét các trường hợp:  Tốt nhất  Xấu nhất  Trung bình  Một số hàm quen thuộc Cách tìm độ phức tạp tính toán 1 September 2015 CTDL> - Trần Đăng Hưng 15  Việc xét độ phức tạp của một thuật toán bất kì là một vấn đề khó.  Một số thuật toán có thể tìm được bằng tính toán các phép toán xảy ra trong thuật toán và áp dụng các quy tắc bên trên để tìm ra độ phức tạp  Thực tế để rút ngắn quá trình, người ta chỉ quan tâm đến “phép toán tích cực” trong chương trình, là những phép toán được thực hiện không ít hơn bất kì một phép toán nào khác. Ví dụ 1 September 2015 CTDL> - Trần Đăng Hưng 16 Tổng kết 1 September 2015 CTDL> - Trần Đăng Hưng 17  Các bước giải bài toán tin học  Thuật toán và các đặc trưng  Phân tích độ phức tạp tính toán  Các quy tắc xác định độ phức tạp tính toán