Bài giảng Cấu trúc dữ liệu và giải thuật 1 - Chương 1: Tổng quan

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TINCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1Số tiết lý thuyết: 45 Số tiết thực hành: 30Tài Liệu Tham KhảoTrầ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, 1999A.V. Aho, J.E Hopcroft, J.D Ullman. Data structures and Algorithms, Addison Wesley, 1983.Thời lượng và hình thức ThiThời lượng học45 tiết lý thuyết 11 Buổi - mỗi buổi 4 tiết30 thực hành 8 Buổi - mỗi buổi 4 tiếtHình thức thiGiữa kỳ: 2 điểm (giấy)Cuối kỳ: 8 điểmLý thuyết: Thi trên giấy (5 điểm)Thực hành: Viết Chương Trình (3 điểm)Tổng điểm: 10 điểmNội Dung Chương TrìnhBuổ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: Các thuật tóan sắp xếp có độ phức tạp O(N2): Interchange Sort, Selection Sort, Bubble Sort, Insertion SortBuổi 3: Các thuật toán có độ phức tạp O(NlogN): Quick Sort, Shell Sort, Heap Sort, Merge Sort.Nội Dung Chương TrìnhBuổi 4: Cấu trúc động, Danh sách liên kết đơn.Buổi 5: tiếp tục Cấu trúc động, Danh sách liên kết đơn, Stack, Queue. Giới thiệu qua danh sách liên kết đơn vòngBuổi 6:Danh sách liên kết képGiới thiệu qua danh sách liên kết đôi vòng)Nội Dung Chương TrìnhBuổi 7: Cây, Cây nhị phân, cây nhị phân tìm kiếmBuổi 8: cây nhị phân tìm kiếm (tt)Buổi 9: Cây cân bằng (AVL)Buổi 10: Cây cân bằng (tt)Buổi 11: Ôn tậpCHƯƠNG 1TỔNG QUAN VỀ CTDL VÀ THUẬT TOÁNNội DungTổng quan về CTDL và thuật toánCác tiêu chuẩn của CTDLVai trò của CTDLĐộ phức tạp của thuật toánThực hiện và hiệu chỉnh chương trìnhTiêu chuẩn của chương trình Khái Niệm Về CTDL Và Thuật ToánNiklaus Wirth: CTDL + Thuật toán = Chương trìnhCần nghiên cứu về thuật toán và CTDL!Sự Cần Thiết Của Thuật ToánTạ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!”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 () Input: Output: EndBiể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 od6. Một số câu lệnh khác: Trả giá trị về: return [giá trị] Lời gọi hàm: (tham số)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;Biểu Diễn Bằng Ngôn Ngữ Lập TrìnhDù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ể.Độ Phức Tạp Của Thuật ToánMộ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.Phương Pháp Thực NghiệmCà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.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)Sự Phân Lớp Theo Độ Phức Tạp Của Thuật ToánSử dụng ký hiệu BigO Hằng số : O(c)logN : O(logN)N : O(N)NlogN : O(NlogN)N2 : O(N2)N3 : O(N3)2N : O(2N)N! :O(N!) Độ phức tạp tăng dầnDữ LiệuTheo 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ệuCá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.Vai Trò Của Cấu Trúc Dữ LiệuCấ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ơnThực Hiện Và Hiệu Chỉnh Chương TrìnhChạ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).Tiêu Chuẩn Của Một Chương TrìnhTính tin cậyGiải thuật + Kiểm tra cài đặtTính uyển chuyểnĐáp ứng quy trình làm phần mềm.Tính trong sángDễ hiểu và dễ chỉnh sửaTính hữu hiệu.Tài nguyên + giải thuậtQuy Trình Làm Phần MềmBướ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).Bước 6: Vận hành, theo dõi và bảo dưỡng (Operation, follow-up and Maintenance).