Анализ структур данных и алгоритмов на языке Python (2-е издание)
Этот учебник по данным структурам и алгоритмам на языке Python является классическим. Охватывает повторение основ Python, анализ алгоритмов (обозначение О), базовые структуры данных (стеки, очереди, списки), рекурсию, поиск и сортировку, алгоритмы деревьев и графов. Через практические примеры кода помогает читателям понять, как эффективно реализовать различные абстрактные типы данных на языке Python.
Обзор курса
📚 Краткое содержание
Этот учебник является классическим руководством по структурам данных и алгоритмам на языке Python. Охватывает повторение основ Python, анализ алгоритмов (нотация O), базовые структуры данных (стеки, очереди, списки), рекурсию, поиск и сортировку, алгоритмы деревьев и графов. Через практические примеры кода помогает читателям понять, как эффективно реализовать различные абстрактные типы данных на языке Python.
Только глубокое понимание структур данных и алгоритмов позволяет действительно освоить Python.
Авторы: Брэдли Миллер (почётный профессор информатики, Университет Лутхера, США), Дэвид Ранум (инженер когнитивного программного обеспечения, IBM Watson)
Благодарности: Благодарим коллегу Стива Хаббарда за обширную обратную связь по первому изданию и новые материалы для нового издания; также благодарим коллег со всего мира, которые сообщали об ошибках и давали ценные советы. Особая благодарность персоналу кафе «Java John's» в городе Дикола (Мэри, Боб и др.), позволившему нам во время отпуска превратиться в «постоянных авторов» заведения. Также благодарим сотрудников издательства Franklin, Beedle & Associates (особенно Джима Лейси и Тома Съмнера) за приятное сотрудничество. Наконец, особая благодарность нашим женам — Джейн Миллер и Бренде Ранум — за любовь и поддержку, благодаря которым эта книга стала реальностью.
🎯 Цели обучения
- Понять взаимосвязь между компьютерными науками, алгоритмами и программированием, а также освоить концепции абстрактных типов данных (ADT) и скрытия информации.
- Свободно использовать встроенные коллекции языка Python (списки, кортежи, множества, словари) и управляющие структуры (циклы, ветвления, обработка исключений).
- Освоить основы объектно-ориентированного программирования (ООП) на языке Python: определение классов, методы-конструкторы, перегрузка операторов (например, сложение дробей), применение алгоритма Евклида, различие между глубоким и поверхностным равенством.
- Сравнение нескольких подходов к решению задач: объяснить четыре метода проверки анаграмм (подсчёт, сортировка, полный перебор, подсчёт частот) и соответствующую им сложность по времени.
- Количественная оценка производительности контейнеров в Python: знать асимптотическую сложность ключевых операций для списков (List) и словарей (Dict), а также различать производительность
pop()иpop(i). - Умение проверять производительность: уметь использовать модуль
timeitдля разработки экспериментов, подтверждающих соответствие теоретической сложности и фактического времени выполнения. - Понимать и различать логические характеристики линейных структур данных (стек, очередь, двусторонняя очередь, список).
- Уметь реализовать собственные стеки, очереди и двусторонние очереди с использованием базовых конструкций языка (например, списков).
- Применять стеки при обработке выражений (преобразование инфиксной записи в постфиксную, вычисление постфиксных выражений) и очереди при моделировании систем (модель печати).
- Освоить три основных принципа рекурсии: уметь точно определять и писать рекурсивные функции, содержащие базовый случай, изменение состояния и рекурсивный вызов.
Уроки 共 8 课时 · 预计 24.0h
Уроки
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.