В. В. Борисенко

2011-12 учебный год

1. Основные понятия объектно-ориентированного программирования: класс, описание класса и объекты. Члены и методы класса. Виды памяти в C++ (статическая, стековая, динамическая), способы создания и удаление объектов в памяти. Особенности языка С++ как промежуточного между традиционными и объектно-ориентированными в узком смысле языками (Java, C#, Visual Basic), отличия в организации памяти, создании и удалении объектов (контролируемая динамическая память и процесс сборки мусора в объектно-ориентированных языках). Достоинства и недостатки объектно-ориентированных языков.
2. Язык C++. Типы, операции. Классы, члены классов, методы. Конструктор по умолчанию и copy-конструктор. Переопределение операторов для классов на примере классов "вектор на плоскости", "точка", "прямоугольник". Правильное использование модификатора const и задание типов возвращаемых значений для разных типов операторов и методов.
3. Механизм исключений (Exceptions) языка C++ и его использование для обработки ошибочных ситуаций. Стек, реализация стека на базе массива на C++. Обратная польская запись формул и примеры ее использования.
4. Статические члены и методы классов. Наследование классов, виртуальные методы. Программирование в оконных средах: общие принципы. Преимущества объектно-ориентированного подхода в случае программирования в оконной среде.
5. Абстрактные типы данных и контейнеры как обобщение структур данных. Описание абстрактного типа данных и его реализация. Основные виды контейнеров, используемые в программировании: последовательного доступа — стек, очередь, дек, двусвязный и односвязный списки; прямого доступа — массив, динамический массив (вектор), матрица, множество, нагруженное множество (отображение, словарь), дерево, граф.
6. Реализация дека и очереди на базе массива или динамического массива.
7. Способы реализация циклов "для каждого элемента" контейнера. Итераторы, их использование и реализация.
8. Схема построения цикла с помощью инварианта. Применения этой схемы: алгоритм Евклида, алгоритм быстрого возведения в степень, расширенный алгоритм Евклида, вычисление логарифма без разложения в ряд.
9. Непрерывные реализации множества и нагруженного множества (отображения): битовая реализация ограниченного множества, наивная реализация, реализация с помощью бинарного поиска. Применение сxемы построения цикла с помощью инварианта в алгоритме бинарного поиска.
10. Задача сортировки массива. Оценка минимального числа сравнений в произвольном алгоритме сортировки.
11. Пирамидальная сортировка (сортировка кучей, Heap Sort): идея, применение схемы построения цикла с помощью инварианта для написания программы и доказательства ее правильности.
12. Сортировка слиянием, идея, рекурсивная и итеративная реализации, оценка времени работы.
13. Алгоритм быстрой сортировки (Quick Sort). Применение схемы построения цикла с помощью инварианта для написания функции "partition", разделяющей массив на три отрезка: элементы меньше медианы, медиана, элементы больше медианы. Рекурсивная реализация алгоритма быстрой сортировки с применением рекурсии к обеим половинам массива и итеративная с применением рекурсии только к меньшей половине.
14. Непрерывные и ссылочные реализации контейнеров. Идея ссылочной реализации, достоинства и недостатки непрерывных и ссылочных реализаций. Реализация Л2-списка на С++: классы L2ListHeader и L2List. Особенность реализации с использованием динамической памяти: наследование и виртуальные деструкторы.
15. Бинарные деревья и деревья поиска. Идея реализации множества и нагруженного множества (отображения) с помощью бинарного дерева поиска. Особенности реализации на языке C++ (классы TreeNode и Tree). Алгоритмы поиска и добавления элемента для деревьев поиска. Алгоритм нахождение следующей вершины дерева и обхода вершин дерева в порядке их возрастания.
16. Полностью сбалансированные и почти сбалансированные деревья. Логарифмическая оценка высоты почти сбалансированного дерева с баланс-фактором C в зависимости от числа его вершин. Классы почти сбалансированных деревьев с баланс-фактором C: AVL-деревья, красно-черные деревья (определения).
17. Красно-черные деревья: определение и свойства. Логарифмическая оценка высоты красно-черного дерева в зависимости от числа его вершин.
18. Восстановление структуры красно-черного дерева при добавлении элемента (процедура ребалансировки): операции вращения вершины дерева поиска вправо и влево, рассмотрение различных случаев при добавлении элемента с нарушением свойств красно-черного дерева.