![©FIT-HCMUS 14
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
27
Luật
Điều
kiện
Máy in không in C C C C K K K K
Đèn lỗi báo sáng C C K K C C K K
Máy in không được nhận biết C K C K C K C K
Hành
động
Kiểm tra cáp nguồn X
Kiểm tra cáp nối máy tinh – máy
in
X X
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 2011
28
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]](https://image.slidesharecdn.com/ctdl-00-introduction-150427151049-conversion-gate01/85/C-u-truc-d-li-u-c-b-n-Gi-i-thi-u-14-320.jpg)
![©FIT-HCMUS 15
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
29
Cấu trúc
dữ liệu
Giải
thuật
Chương
trình
Cấu trúc dữ liệu và giải thuật - HCMUS 2011
30
Programming is for programmers
[C++ in Action]](https://image.slidesharecdn.com/ctdl-00-introduction-150427151049-conversion-gate01/85/C-u-truc-d-li-u-c-b-n-Gi-i-thi-u-15-320.jpg)
Cấu trúc dữ liệu cơ bản - Giới thiệu
- 1. ©FIT-HCMUS 1 Giảng viên: Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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
- 2. ©FIT-HCMUS 2 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 3 Lý thuyết: • Văn Chí Nam (vcnam@fit.hcmus.edu.vn) • Giờ học: t4-t6 sáng T4 hàng tuần • Địa điểm: F203 Thực hành: • t1-t6 ngày T5 (B40a, b) • t7-t12 ngày T7 (B40a) • Bắt đầu từ 28/02/2011 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 4 http://courses.cs.hcmus.edu.vn/ 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
- 3. ©FIT-HCMUS 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 5 Điểm lý thuyết: 60% Thi viết. Điểm thực hành: 40% Hình thức thi: Theo quy định của Giáo viên HDTH. Điểm thưởng: Tính theo từng phần, không cộng dồn. 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. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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.
- 4. ©FIT-HCMUS 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 2011 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)
- 5. ©FIT-HCMUS 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 2011 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
- 6. ©FIT-HCMUS 6 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 2011 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 • Heap Sort, Quick Sort, Merge Sort
- 7. ©FIT-HCMUS 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 2011 14 Ngày Bài học Nội dung 16/02/2011 Giới thiệu - Ôn tập 23/02/2011Bài 1 Các khái niệm cơ bản 02/03/2011Bài 2 Danh sách liên kết 09/03/2011Bài 2 Stack - Queue 16/03/2011Bài 3 Các khái niệm trên cây - Cây nhị phân tìm kiếm 23/03/2011Bài 3 Các thao tác trên cây NPTK - Cây AVL 30/03/2011Bài 3 Cây AA
- 8. ©FIT-HCMUS 8 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 15 Ngày Bài học Nội dung 06/04/2011 Bài 4 B-Cây 13/04/2011 Bài 5 Nén dữ liệu 20/04/2011 Bài 6 Tìm kiếm tuần tự - Nhị phân 27/04/2011 Bài 6 Bảng băm 04/05/2011 Bài 7 Thuật toán sắp xếp: Selection Sort - Heap Sort 11/05/2011 Bài 7 Thuật toán sắp xếp: Quick Sort - Merge Sort 18/05/2011 Bài 8 Đối sánh chuỗi - Tổng kết Cấu trúc dữ liệu và giải thuật - HCMUS 2011 16 Mục đích môn học Ngôn ngữ lập trình Thuật toán Biểu diễn thuật toán
- 9. ©FIT-HCMUS 9 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 17 Học môn này để làm gì? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 18
- 10. ©FIT-HCMUS 10 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 19 George Boole Cấu trúc dữ liệu và giải thuật - HCMUS 2011 20 Alan Turing
- 11. ©FIT-HCMUS 11 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 21 Von Neumann Cấu trúc dữ liệu và giải thuật - HCMUS 2011 22 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ī
- 12. ©FIT-HCMUS 12 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 23 Nhập dữ liệu Xử lý Xuất dữ liệu Cấu trúc dữ liệu và giải thuật - HCMUS 2011 24 Tính xác định Tính đúng đắn Tính hữu hạn Tính hiệu quả Tính tổng quát
- 13. ©FIT-HCMUS 13 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 25 Biểu diễn Lưu đồ Bảng quyết định Mã giả Ngôn ngữ lập trình Cấu trúc dữ liệu và giải thuật - HCMUS 2011 26 Nhập vào 2 số nguyên Tính tổng 2 số Bắt đầu Kết thúc Hiển thị kết quả
- 14. ©FIT-HCMUS 14 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 27 Luật Điều kiện Máy in không in C C C C K K K K Đèn lỗi báo sáng C C K K C C K K Máy in không được nhận biết C K C K C K C K Hành động Kiểm tra cáp nguồn X Kiểm tra cáp nối máy tinh – máy in X X 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 2011 28 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]
- 15. ©FIT-HCMUS 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 29 Cấu trúc dữ liệu Giải thuật Chương trình Cấu trúc dữ liệu và giải thuật - HCMUS 2011 30 Programming is for programmers [C++ in Action]