Bài giảng Cấu trúc dữ liệu và giải thuật - Giới thiệu - Đậu Ngọc Hà Dương

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Giới thiệu - Đậu Ngọc Hà Dương

1. Giảng viên: Đậu Ngọc Hà Dương
2. 2  Thông tin môn học  Quy định môn học  Tài liệu tham khảo  Nội dung môn học Cấu trúc dữ liệu và giải thuật - HCMUS
3. 3 • Ths. Đậu Ngọc Hà Dương (dnhduong@fit.hcmus.edu.vn) • Giờ học: bắt đầu 9h20 sáng T5 hàng tuần (3t) Lý thuyết: • Địa điểm: E403 Thực hành: Cấu trúc dữ liệu và giải thuật - HCMUS
4. 4   Sử dụng cho các việc:  Đặt câu hỏi  Giải đáp thắc mắc  Nhận thông báo  Nhận/nộp bài tập Cấu trúc dữ liệu và giải thuật - HCMUS
5. 5  Điểm lý thuyết: 6 điểm  Thi viết.  Điểm thực hành: 4 điểm  Hình thức thi: Theo quy định của Giáo viên HDTH.  Điểm cộng: 2 điểm  Hình thức cộng: tham gia trả lời, lên bảng giải bài, game win  Bất kỳ trường hợp gian lận nào bị phát hiện trong quá trình học, thi, bài tập, sẽ bị phạt theo qui định sau:  Lần 1: trừ 30% trên tổng số điểm của môn học.  Lần 2: trừ 50% trên tổng số điểm của môn học.  0d thực hành hay lý thuyết xem như 0d cả môn! Cấu trúc dữ liệu và giải thuật - HCMUS
6. 6  KHÔNG bắt buộc phải có mặt. Nếu đi học, phải đi học đúng giờ và nghiêm túc.  Có thể có các bài kiểm tra nhỏ với nội dung của phần học có liên quan.  Có thể có điểm trừ cho việc chuẩn bị bài, làm bài không tốt. Cấu trúc dữ liệu và giải thuật - HCMUS
7. 7  Ngôn ngữ lập trình: C/C++  Công cụ lập trình: Visual C++ 6 hoặc Visual Studio 2005, 2008, 2010 (chế độ console).  Chương trình viết phải ngăn nắp, thẳng hàng, ghi chú đầy đủ. Đặt tên biến và tên hàm phải gợi nhớ, có qui ước xác định. Cấu trúc dữ liệu và giải thuật - HCMUS
8. 8  Adam Drozdek (2001), Data structures and Algorithms in C++ (Second Edition)  Dương Anh Đức – Trần Hạnh Nhi (2003), Nhập môn Cấu trúc dữ liệu và giải thuật, NXB ĐHQG TP.HCM  Đinh Mạnh Tường (2008), Cấu trúc dữ liệu và thuật toán, NXB ĐHQG HN.  Đỗ Xuân Lôi (2007), Cấu trúc dữ liệu và giải thuật, NXB ĐHQG HN.  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001), Introduction to Algorithms (Second Edition) Cấu trúc dữ liệu và giải thuật - HCMUS
9. 9 1. Giới thiệu 2. Các khái niệm cơ bản 3. Các cấu trúc dữ liệu cơ bản 4. Cấu trúc cây 5. B-cây và ứng dụng 6. Nén dữ liệu 7. Các thuật toán sắp xếp 8. Các chiến lược tìm kiếm 9. Đối sánh chuỗi Cấu trúc dữ liệu và giải thuật - HCMUS
10. 10 Cái khái niệm cơ bản • Kiểu dữ liệu: cơ bản, có cấu trúc, trừu tượng • Đánh giá thuật toán • Ôn tập: Con trỏ, Đệ qui Các cấu trúc dữ liệu cơ bản: • Danh sách liên kết • Ngăn xếp • Hàng đợi Cấu trúc dữ liệu và giải thuật - HCMUS
11. 11 Cấu trúc cây: • Cây tổng quát • Cây nhị phân tìm kiếm • Cây nhị phân tìm kiếm tự cân bằng: cây AVL, cây AA B-cây và ứng dụng: • Cây tìm kiếm m-nhánh • B-cây, Cây B+ Cấu trúc dữ liệu và giải thuật - HCMUS
12. 12 Nén dữ liệu: • Tổng quan về mã hóa (nén) • Nén Huffman tĩnh • Đọc thêm: Nén Run-Length Encoding, Nén Huffman động Các thuật toán sắp xếp: • Selection Sort, Insertion Sort, Bubble Sort • Heap Sort, Quick Sort, Merge Sort Cấu trúc dữ liệu và giải thuật - HCMUS
13. 13 Các chiến lược tìm kiếm: • Tìm kiếm tuần tự • Tìm kiếm nhị phân • Bảng băm và các phương pháp xử lý đụng độ Đối sánh chuỗi: • Brute force • Morris-Pratt, Knuth-Morris-Pratt Cấu trúc dữ liệu và giải thuật - HCMUS
14. 14  Mục đích môn học  Phương pháp học  Ngôn ngữ lập trình  Thuật toán  Biểu diễn thuật toán Cấu trúc dữ liệu và giải thuật - HCMUS
15. 15 Học môn này để làm gì? Cấu trúc dữ liệu và giải thuật - HCMUS
16. 16  Giải bài tập  Làm bài thực hành  Thảo luận nhóm  Tham gia trò chơi đối kháng  Seminar  Cấu trúc dữ liệu và giải thuật - HCMUS
17. 17 Cấu trúc dữ liệu và giải thuật - HCMUS
18. 18 George Boole Cấu trúc dữ liệu và giải thuật - HCMUS
19. 19 Alan Turing Cấu trúc dữ liệu và giải thuật - HCMUS
20. 20 Von Neumann Cấu trúc dữ liệu và giải thuật - HCMUS
21. 21  An algorithm is a sequence of steps required to accomplish a task (Al-Khwārizmī).  Thuật toán là tập hợp hữu hạn các lệnh chính xác để thực hiện tính toán hoặc để giải một bài toán (Rosen) Al-Khwārizmī Cấu trúc dữ liệu và giải thuật - HCMUS
22. 22 Nhập Xuất Xử lý dữ liệu dữ liệu Cấu trúc dữ liệu và giải thuật - HCMUS
23. 23 Lưu đồ Ngôn Biểu Bảng ngữ lập quyết trình diễn định Mã giả Cấu trúc dữ liệu và giải thuật - HCMUS
24. 24 Bắt đầu Nhập vào 2 số nguyên Tính tổng 2 số Hiển thị kết quả Kết thúc Cấu trúc dữ liệu và giải thuật - HCMUS
25. 25 Luật Máy in không in C C C C K K K K Điều Đèn lỗi báo sáng C C K K C C K K kiện Máy in không được nhận biết C K C K C K C K Kiểm tra cáp nguồn X Kiểm tra cáp nối máy tinh – máy X X Hành in động Kiểm tra driver X X X X Kiểm tra/thay mực X X X X Kiểm tra khe để giấy X X Cấu trúc dữ liệu và giải thuật - HCMUS
26. 26  Cấu trúc dữ liệu là một cách tổ chức các dữ liệu thành một đơn vị hoàn chỉnh bao gồm các thành phần (phần tử) là các dữ liệu cơ bản, các mối liên kết giữa các phần tử ấy và các thao tác cơ bản trên chúng.  Các thao tác này thường được gọi là các phép toán trên cấu trúc dữ liệu xác định. Các phép toán cơ bản thường gặp là tạo lập (create), hủy (dipose), thêm (add), chèn (insert), xóa (delete), tìm kiếm (search),  Tùy theo yêu cầu của thuật toán, khi thiết kế chương trình người ta định nghĩa và sử dụng các cấu trúc dữ liệu khác nhau. Các cấu trúc dữ liệu cơ bản hay dùng là: mảng (array), danh sách (list), ngăn xếp (stack), hàng đợi (queue), cây(tree), [Wikipedia, tháng 6 - 2009] Cấu trúc dữ liệu và giải thuật - HCMUS
27. 27 Cấu trúc Giải Chương dữ liệu thuật trình Cấu trúc dữ liệu và giải thuật - HCMUS
28. 28 Programming is for programmers [C++ in Action] Cấu trúc dữ liệu và giải thuật - HCMUS
29. 29 Cấu trúc dữ liệu và giải thuật - HCMUS