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

Осенний семестр

1. Обзор алгоритмических языков: традиционные языки — Си, Фортран, объектно-ориентированные — Java, C#. Основные различия между традиционными и объектно-ориентированными языками. Размещение переменных и объектов в памяти в случае традиционных языков. Три вида памяти — статическая, стековая и динамическая. Организация динамической памяти и способы размещения объектов в объектно-ориентированных языках. Промежуточное положения языка C++ между традиционными и объектно-ориентированными: по способу размешения объектов в памяти — традиционный язык, однако поддерживает ряд понятий, свойственных объектно-ориентированным языкам.
2. Знакомство с языком C++. Основные понятия — класс, члены класса, методы класса. Типы переменных: обычные переменные, указатели и ссылки, модификатор "const". Важность правильного задания прототипов методов класса и функций. Переопределение операторов для классов. Класс R2Vector (вектор на плоскости) как пример класса. Десять способов неправильного описания прототипов методов сложения (operator+) и "увеличить на" (operator+=) и единственный правильный способ. Реализация классов "вектор", "точка" и "прямоугольник", используемых в двумерной графике. Два этапа реализации класса: задание интерфейса и реализация методов. Реализация других классов, представляющих математические объекты: многочлен от одной переменной, ортогональное преобразование двух- и трехмерного пространства и т.п.
3. Исключения "exception" и их использование в современных языках. Конструкция "try — catch". Использование исключений для обработки ошибочных ситуаций. Преимущества использования исключений вместо анализа кодов возврата. Общее понятие исполнителя и класс в C++ как его конкретное воплощение. Язык "Псевдокод" как неформальный язык для описания алгоритмов.
4. Структуры данных: общие понятия. Стек и реализация стека на псевдокоде и на C++. Обратная польская запись формул и ее использование (байткод Java, язык Postscript и т.п.). Проект "Стековый калькулятор". Аппаратная реализация стека: процессор, оперативная память, регистры процессора, роль регистров PC, SP и FP. Размещение локальных переменных функции в аппаратном стеке. Механизм вызова функций и передачи параметров функциям.
5. Статические члены и методы класса. Наследование и виртуальные методы. Различия в механизме вызова обычных и виртуальных методов. Зачем нужны виртуальные методы. Абстрактные классы, примеры.
6. Программирования в оконных средах, общие принципы. Событийная модель программирования: события, сообщения о событиях, очередь сообщений, цикл обработки событий и обработчики событий. Преимущества объектно-ориентированного подхода при программировании в оконных средах. Использование виртуальных методов класса "Окно" для реализации обработчиков событий. Понятие API операционной системы и библиотека классов как надстройка над API. Конкретные библиотеки классов для работы в оконных средах: MFC в случае MS Windows, системно-независимые библиотеки классов Qt и GTKMM (реализованы под X-Window и MS Windows).
7. Введение в программирование под X11. Понятие X-клиента и X-сервера, переменная DISPLAY. Программирование над Xlib (нижнй уровень). Класс "Графическое окно" GWindow и его использование для создания графических программ. Статические методы и переменные класса GWindow. Типы событий в X11, виртуальные методы класса GWindow, используемые для обработки событий. Создание окна и рисование в окне. Проект "GWindow".
8. Структуры данных: последовательного доступа — стек, очередь, дек, двусвязный и односвязный списки; прямого доступа — массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека и дека (очереди) на базе массива. Битовая реализация ограниченного множества целых чисел. Реализация циклов "для каждого элемента структуры данных" с помощью итераторов.
9. Схема построения цикла с помощью инварианта на примерах обычного и расширенного алгоритма Евклида, быстрого возведения в степень, бинарных алгоритмов умножения и деления, вычисления логарифма без использования разложения в ряд.
10. Применение схемы инварианта цикла в алгоритме бинарного поиска. Непрерывная реализация множества на базе массива с использованием бинарного поиска.
11. Теоретическая оценка снизу минимального числа операций в произвольном алгоритме сортировки. Алгоритм быстрой сортировки, идея, реализация функции partition с применением схемы инварианта цикла; недостаток чисто рекурсивной схемы реализации функции quickSort, комбинированная схема ее реализации — с применением как итерации, так и рекурсии.
12. Алгоритм сортировки кучей (или пирамидой) HeapSort. Бинарная куча, ее построение и модификация при удалении максимального элемента. Реализация алгоритма сортировки с помощью кучи, применение схемы инварианта цикла для написания программы. Реализация функции sieve просеивания элемента в куче (при которой элемент опускается на свое место).
13. Стабильные алгоритмы сортировки (сохраняющие взаимный порядок равных элементов). Алгоритм двунаправленной сортировки слиянием с использованием дополнительной памяти: реализация функции merge, рекурсивная (нисходящая) и итеративная (восходящая) схемы реализации сортировки слиянием. Модификация классического алгоритма: использование вспомогательной памяти вдвое меньшего размера, алгоритм слияния двух соседних упорядоченных блоков, в котором результат получается в исходном массиве, а не во вспомогательном.
14. Алгоритм стабильной сортировки слиянием, не использующий дополнительной памяти (т.е. основанный только на сравнениях и перестановках элементов сортируемого массива): идея алгоритма и оценка времени его работы. Рекурсивная реализация функции inPlaceMergeBlocks, сливающей два соседних упорядоченных блока в один упорядоченный без использования вспомогательной памяти.
    RADIX-сортировка: идея алгоритма, оценка скорости его работы и объема вспомогательной памяти.
15. Бинарная куча (очередь с приоритетами): определение, реализация на базе массива. Алгоритм Дийкстры нахождения кратчайшего пути в графе (транспортной сети). Применение бинарной кучи в алгоритме сортировки кучей heapSort и алгоритме Дийкстры.
16. Ссылочные реализации. Реализации Л1 и Л2-списков на языке C++.
17. Проект "Текстовый редактор" (class TextEdit), реализация на языке C++ с использованием Л2-списка строк и класса "Графическое окно" (GWindow).
18. Бинарные деревья и деревья поиска. Идея реализации множества и нагруженного множества с помощью бинарного дерева поиска. Алгоритмы поиска и добавления элемента для деревьев поиска. Алгоритм нахождение следующей вершины дерева и обхода вершин дерева в порядке их возрастания.
19. Сбалансированные и почти сбалансированные деревья. Логарифмическая оценка сверху высоты почти сбалансированного дерева с баланс-фактором C≥1 в зависимости от числа вершин. Конкретные классы почти сбалансированных деревьев с баланс фактором C: AVL-деревья (определение и свойства без доказательств), красно-черные деревья.
20. Красно-черные деревья: определение и свойства, логарифмическая оценка сверху высоты дерева в зависимости от числа вершин. Восстановление структуры красно-черного дерева при добавлении элемента: операции вращения вершины вправо и влево, рассмотрение различных случаев при добавлении элемента с нарушением свойств красно-черного дерева. Реализация нагруженного множества на основе красно-черного дерева: проект "TreeSet".
21. Идея реализации множества и нагруженного множества с помощью хеширования. Два способа реализации множества с помощью хеширования: внешнее разрешение коллизий с помощью вектора множеств, использование дополнительного массива ("кучи"). Ссылочная реализация вектора множеств на языке C++ и и хеш-реализация множества на его основе. Проект "HashSet".

Весенний семестр

1. Процессы и их ресурсы. Механизм виртуальной памяти. Создание child-процессов с помощью системных вызовов fork, exec, system. Передача данных между процессами через разделяемую память (shared memory) и при помощи программных каналов pipe.
2. Паралельное программирование с использованием нитей Thread (легковесных процессов). Способы синхронизации нитей: семафоры, мьютексы, критические секции. Примеры параллельных программ в системе Unix, использующих библиотеку поддержки нитей pthread.
3. Компьютерные сети. Обзор, классификация. Понятие протокола. Уровневая модель описания сетевых протоколов. Примеры протоколов физического уровня (CSMA/CD, Ethernet, Token Ring, DQDB).
4. Стек интернетовских протоколов TCP/IP. Форматы адресов в Internet. Протоколы транспортного уровня (IP, UDP), сессионного уровня (TCP), уровня приложений (FTP, HTTP, SMTP и т.п.). Программирование с использованием интерфейса BSDI-сокетов на C и C++.
5. Применение элементарной теории чисел в программировании: кодирование с открытым ключом (RSA), тесты простоты, факторизация целых чисел. Использование колец вычетов в программировании. Расширенный алгоритм Евклида и Китайская теорема об остатках. Теорема Эйлера как обобщение Малой теоремы Ферма. Схема кодирования с открытым ключом RSA. Электронная подпись.
6. Вероятностный алгоритм Рабина проверки простоты. Методы факторизации чисел: вероятностные алгоритмы Полларда (поиск цикла в последовательности и (p-1)-алгоритм), обощение Ленстра (p-1)-алгоритма Полларда для эллиптических кривых над Z_m, метод квадратичного решета.
7. Представление информации: формат гипертекста HTML. Описание данных с помощью языка XML. Представление математических формул в HTML: стандарт MathML.
8. TeX как основное средство написания статей и книг по математике. Используемые пакеты: Plain TeX, AmS-TeX, LaTeX2e.
9. Трехмерная графика: представление трехмерных объектов. Удаление невидимых линий с помощью буфера глубины (Z-буфера). Закрашивание треугольника: алгоритмы Гуро и Фонга, использование нормалей.
   
10. Библиотека OpenGL и программирование трехмерный графики с ее помощью.
    Языки описания трехмерных объектов VRML и STL.