Анализ структур данных и алгоритмов на языке 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. Освоить три основных принципа рекурсии: уметь точно определять и писать рекурсивные функции, содержащие базовый случай, изменение состояния и рекурсивный вызов.