Phân tích Cấu trúc Dữ liệu và Thuật toán Python (ấn bản thứ 2)
Cuốn sách này là một tài liệu kinh điển về cấu trúc dữ liệu và thuật toán sử dụng Python. Bao gồm ôn tập nền tảng Python, phân tích thuật toán (ký hiệu O lớn), các cấu trúc dữ liệu cơ bản (ngăn xếp, hàng đợi, danh sách), đệ quy, tìm kiếm và sắp xếp, thuật toán cây và đồ thị. Thông qua các đoạn mã thực hành, giúp người đọc hiểu cách triển khai hiệu quả các kiểu dữ liệu trừu tượng khác nhau bằng Python.
Tổng quan khóa học
📚 Tóm tắt nội dung
Cuốn sách này là giáo trình kinh điển về cấu trúc dữ liệu và thuật toán được trình bày bằng Python. Bao gồm ôn tập nền tảng Python, phân tích thuật toán (ký hiệu O lớn), các cấu trúc dữ liệu cơ bản (ngăn xếp, hàng đợi, danh sách), đệ quy, tìm kiếm và sắp xếp, thuật toán cây và đồ thị. Qua các ví dụ mã thực tế, giúp người đọc hiểu cách triển khai hiệu quả các kiểu dữ liệu trừu tượng (ADT) bằng Python.
Chỉ khi thấu hiểu sâu sắc cấu trúc dữ liệu và thuật toán, mới thực sự thành thạo Python.
Tác giả: Bradley Miller (Giáo sư danh dự Khoa Công nghệ thông tin, Trường Đại học Luther, Mỹ), David Ranum (Kỹ sư phần mềm nhận thức IBM Watson)
Lời cảm ơn: Cảm ơn đồng nghiệp Steve Hubbard đã cung cấp nhiều phản hồi cho bản đầu tiên và tài liệu mới cho bản cập nhật; cảm ơn các đồng nghiệp khắp nơi đã gửi email chỉ ra lỗi và đóng góp ý kiến. Cảm ơn các nhân viên Mary, Bob tại quán cà phê Java John's ở thành phố Decora, cho phép chúng tôi trở thành "nhà văn thường trú" trong thời gian nghỉ ngơi. Ngoài ra, xin gửi lời cảm ơn chân thành đến toàn thể nhân viên công ty xuất bản Franklin, Beedle & Associates (đặc biệt là Jim Leisy và Tom Sumner) vì sự hợp tác vui vẻ. Cuối cùng, xin đặc biệt cảm ơn hai người vợ của chúng tôi là Jane Miller và Brenda Ranum, những tình yêu và sự hỗ trợ của họ đã biến cuốn sách này thành hiện thực.
🎯 Mục tiêu học tập
- Hiểu mối quan hệ giữa khoa học máy tính, thuật toán và lập trình, nắm vững các khái niệm về kiểu dữ liệu trừu tượng (ADT) và ẩn giấu thông tin.
- Thành thạo sử dụng các kiểu dữ liệu tập hợp tích hợp trong Python (danh sách, bộ, tập hợp, từ điển) và các cấu trúc điều khiển (vòng lặp, nhánh, xử lý ngoại lệ).
- Nắm vững các yếu tố cốt lõi của lập trình hướng đối tượng (OOP) trong Python: định nghĩa lớp, phương thức khởi tạo, ghi đè toán tử (ví dụ như cộng hai phân số), ứng dụng thuật toán Euclid, và sự khác biệt giữa so sánh sâu và so sánh nông.
- So sánh đa phương án thuật toán: có thể giải thích bốn phương án phát hiện từ đảo (đếm, sắp xếp, bạo lực, đếm tần suất) và độ phức tạp tương ứng theo thời gian.
- Đo lường năng lực chứa đựng của Python: nắm vững hiệu suất O lớn của các thao tác chính trong danh sách (List) và từ điển (Dict) Python, phân biệt hiệu suất giữa
pop()vàpop(i). - Khả năng kiểm chứng hiệu năng: có thể sử dụng mô-đun
timeitđể thiết kế thí nghiệm, xác minh tính nhất quán giữa độ phức tạp lý thuyết và thời gian chạy thực tế. - Hiểu và phân biệt được các đặc điểm logic của các cấu trúc tuyến tính (ngăn xếp, hàng đợi, hàng đợi kép, danh sách).
- Có thể sử dụng các tập hợp cơ bản của Python (như danh sách) để triển khai ngăn xếp, hàng đợi và hàng đợi kép tùy chỉnh.
- Nắm vững ứng dụng của ngăn xếp trong xử lý biểu thức (chuyển đổi trung tố sang hậu tố, đánh giá hậu tố) và hàng đợi trong mô phỏng hệ thống (mô phỏng máy in).
- Nắm vững ba nguyên tắc cốt lõi của đệ quy: có thể xác định chính xác và viết hàm đệ quy bao gồm trường hợp cơ sở, sự tiến hóa trạng thái và gọi tự thân.
Bài học 共 8 课时 · 预计 24.0h
Bài học
Lesson
This lesson introduces the core principles of computer science, focusing on problem-solving through algorithms, procedural abstraction, and Python’s object-oriented nature. Students will learn to manage complexity by leveraging Python’s dynamic variable references, efficient built-in data structures, and robust error-handling techniques to build reliable, scalable software.
本课程深入探讨了算法分析的核心工具——大O记法，通过异序词检测案例展示了从暴力法到计数法的性能优化过程。学习重点在于理解不同操作（如列表索引与pop操作）的复杂度差异，并掌握如何通过空间换时间及选择合适的数据结构来提升程序效率。
This lesson introduces linear data structures and the concept of Abstract Data Types (ADTs), focusing on the stack as a fundamental LIFO (Last-In, First-Out) structure. Students will learn to implement stacks in Python and apply them to complex tasks, including converting infix expressions to postfix notation and evaluating those expressions efficiently.
本课程深入探讨了递归算法的核心原理，重点讲解了递归三原则（基准情况、状态改变、自我调用）以及递归与系统调用栈之间的内在联系。通过进制转换、汉诺塔及动态规划等案例，学生将学习如何将复杂问题拆解为自相似的子问题，并掌握从递归思维向高效动态规划算法的进阶转换。
This lesson explores fundamental search and retrieval algorithms, progressing from $O(n)$ sequential search to the $O(\log n)$ efficiency of binary search and the $O(1)$ potential of hash tables. Students learn to optimize data access through divide-and-conquer strategies, sophisticated hash function design, and collision-handling techniques to build efficient, dictionary-like data structures.
This lesson explores the hierarchical and recursive nature of tree data structures, covering fundamental terminology, implementation methods like nested lists and object-oriented references, and the construction of expression trees. It also introduces essential tree traversal algorithms—preorder, inorder, and postorder—and explains how these recursive patterns are applied to tasks like file system analysis and AVL tree balancing.
This lesson introduces graph theory as a powerful tool for modeling real-world problems by abstracting entities as vertices and relationships as edges. Students will learn to implement graphs using adjacency lists, compare storage efficiency, and master the Breadth-First Search (BFS) algorithm to solve pathfinding and state-space challenges.
This lesson explores the memory efficiency of Python's ArrayList, explaining how amortized analysis ensures $O(1)$ performance for append operations through strategic over-allocation. It also covers the mathematical foundations of RSA encryption, demonstrating how modular exponentiation and divide-and-conquer algorithms optimize complex calculations for secure data processing.