Часть 1. Структуры данных и алгоритмы над ними

1. Понятие об алгоритме, его свойствах и реализации, эффективности (повторение). Виды эффективности. Понятие об оптимальном алгоритме. Понятие о структуре данных. Использование различных структур данных для повышения эффективности алгоритмов. Основные виды структур данных и их особенности.

2. Примеры использования различных алгоритмов и структур данных на примере задачи о поиске в словаре. Идея алгоритмов линейного поиска, бинарного поиска, поиска в хеш-таблице и дереве. Эффективность алгоритмов поиска. Компромисс между эффективностью по времени и эффективностью по памяти. Сравнительная эффективность алгоритмов.

3. Понятие об абстрактной структуре данных и контейнерном объекте. Классификация методов контейнерного объекта. Методы, общие для всех объектов вообще. Назначение и классификация. Методы, общие для всех контейнерных объектов. Понятие о методах, специфичных для каждого данного контейнерного объекта. Понятие обобщенных методов.

4. Хранение данных в контейнерных объектах. Реализация «хранилища» и доступа к нему. Доступ к данным по индексам. Исключительные ситуации, связанные с использованием структур данных и их обработка. Использование нулевого индекса как индикатора исключительной ситуации. Примеры использования индексного доступа и исключительных ситуаций.

5. Понятие согласованности данных в объекте. Ошибки, связанные с нарушением согласованности. Методы проверки согласованности. Контрольная распечатка объекта. Итераторы контейнерных объектов. Виды итераторов и их использование в программе.

6. Объектно-ориентированный подход в программировании. Понятие объекта, его данных и методов. Использование объектов для выражения понятий. Объект как тип языка программирования. Описание объекта, создание его экземпляров и работа с ними. Общность и индивидуальность экземпляров объекта.

7. Понятие метода объекта. Описание, определение и использование методов. Контекст использования метода объекта. Особенности работы с переменной, являющейся экземпляром объекта. Доступ к данным объекта и вызов методов. Стратегия работы с данными объекта. Ошибки, связанные с применением объектно-ориентированного подхода в программировании.

8. Объект «Стек». Основные характеристики как абстрактной структуры данных и набор методов объекта. Классификация методов. Реализация методов объекта «Стек». Особенности реализации специфичных методов. Сравнительная характеристика эффективности различных способов реализации методов добавления и удаления элементов стека.

9. Примеры использования стека в различных задачах. Программа стекового калькулятора. Ошибки, связанные с реализацией стека и его использованием. Примеры возникновения и устранения.

10. Практическая работа «Объект Стек». Программа стекового калькулятора.

11. Объект «Очередь». Виды очередей. Очередь как обобщение стека. Основные характеристики как абстрактной структуры данных и набор методов объекта. Классификация методов. Реализация методов объекта «Очередь». Особенности реализации специфичных методов. Сравнительная характеристика эффективности различных способов реализации методов добавления и удаления элементов очереди.

12. Реализация очереди при помощи кольцевого буфера. Итераторы очередей. Понятие нормализации индекса. Примеры использования итераторов очередей. Примеры использования очереди в различных задачах. Возможности очереди с двумя концами. Понятие о приоритете. Ошибки, связанные с реализацией очереди и его использованием. Примеры возникновения и устранения.

13. Практическая работа «Объект Очередь». Программа «Телеграф Морзе».

14. Объект «Список». Виды списков. Основные характеристики как абстрактной структуры данных и набор методов объекта. Классификация методов. Односвязный список. Схема реализации и эффективность методов вставки и удаления. Двусвязный список. Схема реализации и эффективность методов вставки и удаления.

15. Реализация методов объекта «Список». Особенности реализации специфичных методов. Понятие о списке свободных элементов и методы его реализации. Эффективность использования списка свободных элементов Примеры использования списков в различных задачах. Сравнение эффективности алгоритмов с использованием списков и без их использования.

16. Практическая работа «Объект Двунаправленный список». Программа «Списковый процессор».

17. Обобщающий урок по линейным структурам данных. Стратегия реализации контейнерных объектов. Сравнение наборов методов различных контейнерных объектов. Реализация обобщенных методов добавления и удаления элементов.

18. Нелинейные структуры данных. Особенности строения и реализации. Реализация нелинейных структур данных через линейные.

19. Хеш-таблица, ее свойства. Хеш-таблица как контейнерный объект. Идея хеш-поиска. Эффективность хеш-поиска. Хеш-функции и их характеристики. Требования, предъявляемые к хеш-функциям. Распределение значений хеш-функций. Стохастический характер работы хеш-таблицы.

20. Реализация хеш-поиска. Реализация хеш-таблицы при помощи массива списков. Набор методов объекта «хеш-таблица». Классификация методов. Особенности реализации специфических методов. Практическая работа «Объект Хеш-таблица».

21. Использование хеш-таблиц для представления множеств. Словари и таблицы имен как примеры множеств. Реализация программы русско-английского и англо-русского словаря с помощью хеш-таблицы. Множественность хеш-таблиц для словарей. Таблицы имен идентификаторов. Пример использования таблицы имен в программе калькулятора.

22. Практические работы «Англо-русский и русско-английский словарь» и «Стековый калькулятор с таблицей имен».

23. Понятие дерева. Дерево как вид общего графа. Элементы графов, виды графов, понятия пути, достижимости, связности, корня, цикла. Дерево как связный ациклический граф. Понятия узла, арности узла и дерева. Понятие уровня узла и дерева.

24. Хранение данных и поиск на деревьях. Применение деревьев для задачи поиска в словаре. Особенности словарного дерева. Вырожденные случаи деревьев, сбалансированные и несбалансированные деревья. Время поиска с использованием деревьев. Вставка и удаление элементов дерева.

25. Бинарные деревья. Особенности бинарных деревьев. Поиск на бинарном дереве. Построение бинарных деревьев. Перечисление элементов дерева. Прохождение деревьев и его виды. Рекурсивный характер алгоритмов прохождения деревьев. Вставка и удаление элементов бинарного дерева. Перегруппировка поддеревьев при вставке и удалении элементов.

26. Балансировка деревьев. Необходимость балансировки для поддержания оптимальности поиска. Алгоритм балансировки бинарного дерева. Особенности алгоритма балансировки. Деревья с быстрой балансировкой (2-3, AVL- и B-деревья).

27. Практическая работа «Объект двоичное дерево».

28. Использование двоичных деревьев для кодирования информации. Код Хаффмана. Понятие об избыточности информации и ее сжатии. Характеристики сжатой информации и алгоритма сжатия. Схема работы архиватора. Алгоритм работы архиватора, работающего при помощи метода Хаффмана. Статический и динамический варианты метода.

29. Пирамиды. Пирамиды как бинарные полностью сбалансированные деревья. Работа с пирамидой. Сортировка при помощи пирамиды. Другие методы сортировки. Расчет эффективности методов сортировки. Практическая работа «Объект Пирамида».

30. «Классические» алгоритмы сортировки и их особенности. Сравнение с методами сортировки на деревьях. Практическая работа «Сравнение и анализ различных видов сортировки».

31. Общие графы. Представление графов. Понятие конечного автомата (КА). Детерминированные и недетерминированные КА. Преобразование недетерминированного КА в детерминированный. КА и регулярные выражения. Задача об удалении комментариев. Лексический анализ, КА для основных типов лексем. Практическая работа «Лексический анализатор».

32. Классические алгоритмы на графах (обзор задач и основных алгоритмов).