Анализ структур данных и алгоритмов на языке Python (2-е издание)

📚 Краткое содержание

Этот учебник является классическим руководством по структурам данных и алгоритмам на языке Python. Охватывает повторение основ Python, анализ алгоритмов (нотация O), базовые структуры данных (стеки, очереди, списки), рекурсию, поиск и сортировку, алгоритмы деревьев и графов. Через практические примеры кода помогает читателям понять, как эффективно реализовать различные абстрактные типы данных на языке Python.

Только глубокое понимание структур данных и алгоритмов позволяет действительно освоить Python.

Авторы: Брэдли Миллер (почётный профессор информатики, Университет Лутхера, США), Дэвид Ранум (инженер когнитивного программного обеспечения, IBM Watson)

Благодарности: Благодарим коллегу Стива Хаббарда за обширную обратную связь по первому изданию и новые материалы для нового издания; также благодарим коллег со всего мира, которые сообщали об ошибках и давали ценные советы. Особая благодарность персоналу кафе «Java John's» в городе Дикола (Мэри, Боб и др.), позволившему нам во время отпуска превратиться в «постоянных авторов» заведения. Также благодарим сотрудников издательства Franklin, Beedle & Associates (особенно Джима Лейси и Тома Съмнера) за приятное сотрудничество. Наконец, особая благодарность нашим женам — Джейн Миллер и Бренде Ранум — за любовь и поддержку, благодаря которым эта книга стала реальностью.

🎯 Цели обучения

1. Понять взаимосвязь между компьютерными науками, алгоритмами и программированием, а также освоить концепции абстрактных типов данных (ADT) и скрытия информации.
2. Свободно использовать встроенные коллекции языка Python (списки, кортежи, множества, словари) и управляющие структуры (циклы, ветвления, обработка исключений).
3. Освоить основы объектно-ориентированного программирования (ООП) на языке Python: определение классов, методы-конструкторы, перегрузка операторов (например, сложение дробей), применение алгоритма Евклида, различие между глубоким и поверхностным равенством.
4. Сравнение нескольких подходов к решению задач: объяснить четыре метода проверки анаграмм (подсчёт, сортировка, полный перебор, подсчёт частот) и соответствующую им сложность по времени.
5. Количественная оценка производительности контейнеров в Python: знать асимптотическую сложность ключевых операций для списков (List) и словарей (Dict), а также различать производительность pop() и pop(i).
6. Умение проверять производительность: уметь использовать модуль timeit для разработки экспериментов, подтверждающих соответствие теоретической сложности и фактического времени выполнения.
7. Понимать и различать логические характеристики линейных структур данных (стек, очередь, двусторонняя очередь, список).
8. Уметь реализовать собственные стеки, очереди и двусторонние очереди с использованием базовых конструкций языка (например, списков).
9. Применять стеки при обработке выражений (преобразование инфиксной записи в постфиксную, вычисление постфиксных выражений) и очереди при моделировании систем (модель печати).
10. Освоить три основных принципа рекурсии: уметь точно определять и писать рекурсивные функции, содержащие базовый случай, изменение состояния и рекурсивный вызов.

🔹 Урок 1: Основы программирования на Python и абстракция на основе ООП

Обзор: Этот модуль предназначен для перехода от фундаментальных теоретических знаний в области компьютерных наук к практике программирования на языке Python. Сначала определяются ключевые понятия: компьютерные науки, алгоритмы и абстрактные типы данных (ADT). Затем подробно рассматриваются встроенные коллекции, управляющие структуры и обработка исключений в Python. В заключение демонстрируется мощная применимость объектно-ориентированного программирования (ООП) при абстракции процессов и данных на примере создания класса Fraction и иерархии наследования «логических элементов».

Результаты обучения:

• Понимать взаимосвязь между компьютерными науками, алгоритмами и программированием, а также освоить концепции абстрактных типов данных (ADT) и скрытия информации.
• Свободно использовать встроенные коллекции языка Python (списки, кортежи, множества, словари) и управляющие структуры (циклы, ветвления, обработка исключений).
• Освоить основы объектно-ориентированного программирования (ООП) на языке Python: определение классов, методы-конструкторы, перегрузка операторов (например, сложение дробей), применение алгоритма Евклида, различие между глубоким и поверхностным равенством.

🔹 Урок 2: Анализ алгоритмов и производительность контейнеров в Python

Обзор: В этом модуле подробно рассматривается, как оценивать эффективность алгоритмов с помощью нотации О, а также демонстрируется эволюция сложности от O(n!) до O(n) на примере задачи проверки анаграмм. Кроме того, проводится количественный анализ производительности ключевых операций в основных структурах данных Python (списки и словари), чтобы помочь разработчикам принимать оптимальные решения при выборе контейнеров и проектировании алгоритмов.

Результаты обучения:

• Сравнение нескольких подходов к решению задач: объяснить четыре метода проверки анаграмм (подсчёт, сортировка, полный перебор, подсчёт частот) и соответствующую им сложность по времени.
• Количественная оценка производительности контейнеров в Python: знать асимптотическую сложность ключевых операций для списков (List) и словарей (Dict), а также различать производительность pop() и pop(i).
• Умение проверять производительность: уметь использовать модуль timeit для разработки экспериментов, подтверждающих соответствие теоретической сложности и фактического времени выполнения.

🔹 Урок 3: Основные линейные структуры: стеки, очереди и списки

Обзор: В этом модуле подробно рассматриваются четыре основные линейные структуры данных: стек (Stack), очередь (Queue), двусторонняя очередь (Deque) и список (List). Ключевая черта линейных структур — сохранение относительного порядка элементов, различия же заключаются в способах добавления и удаления элементов. Реализуя эти абстрактные типы данных (ADT) на языке Python, студенты научатся использовать принципы LIFO (последним пришёл — первым ушёл) и FIFO (первым пришёл — первым ушёл) для решения практических алгоритмических задач, таких как преобразование выражений, моделирование систем и управление памятью в списках.

Результаты обучения:

• Понимать и различать логические характеристики линейных структур данных (стек, очередь, двусторонняя очередь, список).
• Уметь реализовать собственные стеки, очереди и двусторонние очереди с использованием базовых конструкций языка (например, списков).
• Применять стеки при обработке выражений (преобразование инфиксной записи в постфиксную, вычисление постфиксных выражений) и очереди при моделировании систем (модель печати).

🔹 Урок 4: Принципы рекурсивных алгоритмов и введение в динамическое программирование

Обзор: В этом модуле глубоко исследуются основы рекурсивных алгоритмов, начиная с трёх ключевых принципов рекурсии. На примерах числовых преобразований, фракталов, классических головоломок (Ханойская башня, лабиринт) раскрывается внутренний механизм рекурсивных вызовов — стек фреймов. В заключение вводится концепция динамического программирования (Dynamic Programming), показывая, как с помощью техники мемоизации можно решить проблему дублирования вычислений в рекурсии и тем самым кардинально повысить эффективность алгоритма.

Результаты обучения:

• Освоить три основных принципа рекурсии: уметь точно определять и писать рекурсивные функции, содержащие базовый случай, изменение состояния и рекурсивный вызов.
• Понимать механизм выполнения на низком уровне: как стек вызовов Python (Stack Frame) управляет локальными переменными и путями возврата в процессе рекурсии.
• Обладать способностью моделировать сложные задачи: уметь решать нелинейные задачи, такие как Ханойская башня и поиск пути в лабиринте, с помощью рекурсии и возврата (backtracking).

🔹 Урок 5: Технологии поиска, хэширование и сортировка

Обзор: В этом модуле сосредоточено внимание на ключевых технологиях обработки данных в компьютерных науках: поиске, хэшировании (Hashing) и сортировке. Рассматриваются от простого последовательного поиска до эффективного двоичного поиска, детально изучается устройство хэш-таблиц (Hash Tables), методы разрешения коллизий и реализация абстрактного типа данных «Отображение» (Map). Также подробно анализируются алгоритмы сортировки: пузырьковая, Шелла и слиянием, их логика и производительность.

Результаты обучения:

• Понимать и сравнивать сферы применения последовательного и двоичного поиска, а также их временные сложности (O(n) против O(\log n)).
• Уметь проектировать хэш-функции (метод складывания, метод среднего квадрата) и применять механизмы разрешения коллизий (линейное пробирование, квадратичное пробирование, метод цепочек).
• Уметь ручным образом моделировать и реализовать на языке программирования пузырьковую, сортировку Шелла и сортировку слиянием, понимая применение стратегии «разделяй и властвуй» в сортировке.

🔹 Урок 6: Структуры деревьев: двоичные кучи, деревья поиска и сбалансированные деревья (AVL)

Обзор: В этом модуле глубоко изучается одна из самых важных структур данных в компьютерных науках — дерево. Мы начинаем с базовых терминов и реализации двоичного дерева, затем переходим к его продвинутым приложениям, включая деревья выражений и методы обхода. Далее рассматриваются два эффективных варианта: двоичная куча (для приоритетных очередей) и двоичное дерево поиска (BST) для быстрого поиска. В заключение изучаем деревья AVL, где с помощью операций поворота поддерживается баланс фактора, решая проблему снижения производительности в худшем случае у обычного дерева поиска.

Результаты обучения:

• Уметь точно определять ключевые термины дерева (корень, ребро, путь, высота) и описывать рекурсивную природу двоичного дерева.
• Освоить основные алгоритмы реализации на языке Python: двоичные кучи, двоичные деревья поиска и деревья AVL (вставка, удаление, повороты, перебалансировка).
• Уметь выполнять и объяснять три алгоритма обхода деревьев, а также использовать дерево выражений для обработки математических выражений.

🔹 Урок 7: Алгоритмы теории графов: поиск, кратчайшие пути и минимальные остовные деревья

Обзор: В этом модуле подробно рассматриваются основы теории графов и их эффективная реализация на языке Python. Включены абстрактные типы данных графов (матрица смежности и список смежности), базовые алгоритмы поиска (BFS и DFS) и их классические применения. В завершение рассматриваются алгоритмы для взвешенных графов: кратчайший путь (Дейкстра) и минимальное остовное дерево (Прим).

Результаты обучения:

• Понимать и сравнивать две основные формы представления графов (матрица смежности и список смежности) с точки зрения производительности и применимости.
• Освоить принципы работы алгоритмов широтного поиска (BFS) и глубинного поиска (DFS), а также уметь решать задачи поиска пути и обхода.
• Уметь применять алгоритмы графов для решения сложных задач логической зависимости (топологическая сортировка) и сетевой связности (сильные компоненты связности, минимальные остовные деревья).

🔹 Урок 8: Тематический обзор: шифрование RSA, skip-списки и октадеревья для квантования цветов

Обзор: В этом модуле рассматриваются перспективы перехода от базовых структур данных к сложным алгоритмам в компьютерных науках. Охватываются вопросы: внутренняя реализация списков (ArrayList) на языке Python с анализом средней стоимости (амортизированная сложность), рекурсивные числовые алгоритмы, поддерживающие шифрование по методу RSA, построение skip-списков для повышения скорости поиска в словарях, а также принципы квантования цветов цифровых изображений с использованием октадеревьев.

Результаты обучения:

• Понимать организацию памяти ArrayList и математическое обоснование амортизированного анализа (Amortized Analysis).
• Освоить основные математические принципы шифрования по методу RSA, включая теорему о сравнениях, степенные остатки и расширенный алгоритм Евклида.
• Уметь описать иерархическую структуру skip-списков, вероятностный процесс построения и их O(\log n) производительность поиска.