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à 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.

1. 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.
2. 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ệ).
3. 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.
4. 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.
5. Đ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).
6. 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ế.
7. 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).
8. 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.
9. 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).
10. 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.