Bài giảng Cấu trúc dữ liệu và giải thuật - Ôn tập kiến thức - Đậ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 - Ôn tập kiến thức - Đậu Ngọc Hà Dương

1. Giảng viên: ThS. Đậu Ngọc Hà Dương – ĐH KHTN HCM
2. 2 1. Đánh giá thuật toán 2. DSLK – Stack - Queue 3. Cấu trúc cây: cây nhị phân tìm kiếm, cây AVL 4. Các thuật toán sắp xếp 5. Các chiến lược tìm kiếm 6. Đối sánh chuỗi 7. Nén dữ liệu Cấu trúc dữ liệu và giải thuật - HCMUS
3. 3 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
4. 4 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á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
5. 5 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
6. 6 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ấu trúc dữ liệu và giải thuật - HCMUS
7. 7 Cấu trúc dữ liệu và giải thuật - HCMUS
8. 8 George Boole Cấu trúc dữ liệu và giải thuật - HCMUS
9. 9 Alan Turing Cấu trúc dữ liệu và giải thuật - HCMUS
10. 10 Von Neumann Cấu trúc dữ liệu và giải thuật - HCMUS
11. 11  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
12. 12 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
13. 13 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
14. 14 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
15. 15 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
16. 16  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
17. 17 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
18. 18 Programming is for programmers [C++ in Action] Cấu trúc dữ liệu và giải thuật - HCMUS
19. 19 Cấu trúc dữ liệu và giải thuật - HCMUS