By Brad Miller and David Ranum, Luther College
Assignments¶
Введение¶
- Цели
- Приступая к работе
- Что такое информатика?
- Что такое программирование?
- Для чего изучать структуры и абстрактные типы данных?
- Для чего изучать алгоритмы?
- Обзор основ Python
- Приступая к работе с данными
- Ввод и вывод
- Управляющие структуры
- Обработка исключений
- Определение функций
- Объектно-ориентированное программирование в Python: определение классов
- Заключение
- Ключевые термины
- Вопросы для обсуждения
- Упражнения
Анализ¶
Основные структуры данных¶
- Цели
- Что такое линейные структуры?
- Что такое “стек”?
- Абстрактный тип данных “стек”
- Реализация стека на Python
- Простые сбалансированные скобки
- Сбалансированные символы (общий случай)
- Конвертирование десятичных чисел в двоичные
- Инфиксные, префиксные и постфиксные выражения
- Что такое очередь?
- Абстрактный тип данных “очередь”
- Реализация очереди на Python
- Симуляция: Hot Potato
- Симуляция: Задания на печать
- Что такое дек?
- Абстрактный тип данных “дек”
- Реализация дека в Python
- Проверка палиндрома
- Списки
- Абстрактный тип данных “неупорядоченный список”
- Реализация неупорядоченного списка: связанные списки
- Абстрактный тип данных “упорядоченный список”
- Реализация упорядоченного списка
- Заключение
- Ключевые термины
- Вопросы для обсуждения
- Упражнения для программирования
Рекурсия¶
Сортировка и поиск¶
Деревья¶
- Цели
- Примеры деревьев
- Терминология и определения
- Представление дерева в виде списка списков
- Узлы и ссылки
- Дерево синтаксического разбора
- Обход дерева
- Очереди с приоритетом с двоичной кучей
- Операции с двоичной кучей
- Реализация двоичной кучи
- Двоичные деревья поиска
- Операции для дерева поиска
- Реализация дерева поиска
- Анализ деревьев поиска
- Сбалансированные деревья поиска
- Производительность АВЛ-дерева
- Реализация АВЛ-дерева
- Заключение по реализациям АТД Map
- Заключение
- Ключевые термины
- Вопросы для обсуждения
- Упражнения для программирования
Графы и алгоритмы на графах¶
- Цели
- Терминология и определения
- Абстрактный тип данных “граф”
- Матрица смежности
- Список смежности
- Реализация
- Задача о словесной лестнице
- Построение графа для “словесной лестницы”
- Реализация поиска в ширину
- Анализ поиска в ширину
- Задача о ходе коня
- Построение графа для задачи о ходе коня
- Решение задачи о ходе коня
- Анализ задачи о ходе коня
- Поиск в глубину: общий случай
- Анализ поиска в глубину
- Топологическая сортировка
- Сильно связные компоненты
- Задача поиска кратчайшего пути
- Алгоритм Дейкстры
- Анализ алгоритма Дейкстры
- Алгоритм Прима для островного дерева
- Заключение
- Ключевые термины
- Вопросы для обсуждения
- Упражнения для программирования