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

Chia sẻ: Lê Thị Na | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

88
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ẢNG CẤ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&GT - 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&GT - 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ếm 4 CTDL&GT - 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ếm 5 CTDL&GT - 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ình 6 CTDL&GT - 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ình 7 CTDL&GT - 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&GT - 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 được 9 CTDL&GT - 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ình 10 CTDL&GT - 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&GT - 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&GT - 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&GT - Trần Đăng Hưng 1 September 2015
Một số tính chất  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 14 CTDL&GT - Trần Đăng Hưng 1 September 2015
Cách tìm độ phức tạp tính toán  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. 15 CTDL&GT - Trần Đăng Hưng 1 September 2015
Ví dụ 16 CTDL&GT - Trần Đăng Hưng 1 September 2015
Tổng kết  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 17 CTDL&GT - Trần Đăng Hưng 1 September 2015