Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Đăng Hưng

Nội dung chương 1 giới thiệu đến sinh viên 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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Đăng Hưng BÀI GIẢNGCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 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ệ: hungtd@hnue.edu.vn  Website: http://fit.hnue.edu.vn/~hungtd/CTDLGT2015/2 CTDL> - Trần Đăng Hưng 1 September 2015 Giới thiệu  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++, http://dev-c.updatestar.com/vi  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%3 CTDL> - Trần Đăng Hưng 1 September 2015 Nội dung  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ếm4 CTDL> - Trần Đăng Hưng 1 September 2015 Nội dung  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ếm5 CTDL> - Trần Đăng Hưng 1 September 2015 Các bước giải bài toán tin học (1/2)  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ình6 CTDL> - Trần Đăng Hưng 1 September 2015 Các bước giải bài toán tin học (2/2)  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ình7 CTDL> - Trần Đăng Hưng 1 September 2015 Thuật toán  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ố8 CTDL> - Trần Đăng Hưng 1 September 2015 Đặc trưng của thuật toán  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 được9 CTDL> - Trần Đăng Hưng 1 September 2015 Biểu diễn thuật toán  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ình10 CTDL> - Trần Đăng Hưng 1 September 2015 Độ phức tạp của giải thuật  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.11 CTDL> - Trần Đăng Hưng 1 September 2015 Các kí pháp đánh giá độ phức tạp tính toán  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.12 CTDL> - Trần Đăng Hưng 1 September 2015 Các quy tắc xác định độ phức tạp tính toán  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))13 CTDL> - Trần Đăng Hưng ...