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

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

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

Рекомендуемая литература

1. Б. Страуструп. Язык программирования C++ (третье издание). — Пер. с англ. — СПб., М.: «Невский диалект». Издательство «Бином», 1999.
2. Д. Кнут. Искусство программирования для ЭВМ. Т. 1–3. — Пер. с англ. — М.: Мир, 1976–1978.
3. Н. Вирт. Алгоритмы + структуры данных = программы. — Пер. с англ. — М.: Мир, 1985.
4. А. Г. Кушниренко, Г. В. Лебедев. Программирование для математиков: Учебное пособие для вузов. — М., Наука, 1988.
5. А. Г. Кушниренко, Г. В. Лебедев, Р. А. Сворень. Основы информатики и вычислительной техники. — М.: Просвещение, 1996.
6. В. В. Борисенко. Основы программирования. — М., Интернет-университет информационных технологий–ИНТУИТ.ру, 2005.
7. У. Робинсон. C# без лишних слов. — Пер. с англ. — М., ДМК-Пресс, 2002.
8. Френл М. Каррано, Джаннет Дж. Причард. Абстракция данных и решение задач на C++. Стены и зеркала. 3-е издание. "Диалектика-Вильямс", 2003.
9. Роберт Седжвик. Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных. 2 книги в одной! "Диалектика-Вильямс", 2010.
10. Бьярне Страуструп. Программирование: принципы и практика использования языка C++. Вильямс, 2010.
11. Бертран Мейер. Объектно-ориентированное конструирование программных систем + CD. Интернет-университет информационных технологий - ИНТУИТ.ру, Русская Редакция, 2005.