English version of this page

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

2002-2003 учебный год

Примерная программа курса

Программа экзамена

Содержание лекций (для части лекций имеется их полная запись)

• Лекция 1.
  Знакомство с языком C++. Типы, операции. Классы, члены классов, методы. Конструктор по умолчанию и copy-конструктор. Переопределение операторов для классов на примере классов "вещественный вектор" R2Vector и "вещественная точка" R2Point на плоскости. Правильное использование модификатора const и задание типов возвращаемых значений для разных типов операторов. Библиотека классов для поддержки двумерной графики (вектор, точка, прямоугольник и т.п.).
  Задачи по теме "Релизация классов".
  Сравнение традиционных и объектно ориентированных языков и промежуточное положение C++ в этой классификации.
• Лекция 2.
  Обработка исключений в языке C++. Стек, реализация стека на базе массива. Обратная польская запись формул. Проект "Стековый калькулятор" (StackCalc.zip). Аппаратная реализация стека. Размещение локальных переменных в аппаратном стеке, механизм вызова функций и передачи параметров.
  Задачи по проекту "Стековый калькулятор".
• Лекция 3.
  Статические члены и методы классов. Наследование классов. Виртуальные методы. Программирование в оконных средах: общие принципы. Преимущества объектно ориентированного в случае программирования в оконной среде. Проект "Графическое окно" (GWindow.zip) как пример простейшей библиотеки классов для поддержки программирования в среде X-Windows (Unix).
  Программирование под X11, краткое введение (Brian Hammond).
  Задачи по теме "Графика".
• Лекция 4.
  Структуры данных: последовательного доступа -- стек, очередь, дек, двусвязный и односвязный списки; прямого доступа -- массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека и дека (очереди) на базе массива. Битовая реализация ограниченного множества целых чисел. Способы реализация циклов "для каждого элемента": итераторы, методы типа "forEach".
• Лекция 5.
  Проект "Выпуклая оболочка" (R2Conv.zip). Его реализация на языке C++ с использованием классов, поддерживающий двумерную графику (R2Vector, R2Point и т.п.). Графическая иллюстрация работы с исполнителем "Выпуклая оболочка" с использованием класса "Графическое окно".
  Задачи по теме "Выпуклая оболочка".
• Лекция 6.
  Схема построения цикла с помощью инварианта. Применения этой схемы: алгоритм Евклида, алгоритм быстрого возведения в степень, расширенный алгоритм Евклида, вычисление логарифма без разложения в ряд.
• Лекция 7.
  Непрерывные реализации множества: битовая реализация (проект BitSet.zip), наивная реализация, реализация с помощью бинарного поиска. Применение сxемы построения цикла с помощью инварианта в алгоритме бинарного поиска.
• Лекция 8.
  Задача сортировки массива. Оценка минимального числа сравнений в произвольном алгоритме сортировки. Три алгоритма сортировки.
  1. Пирамидальная сортировка (Heap Sort): идея, применение схемы построения цикла с помощью инварианта для написания программы и доказательства ее правильности.
  2. Сортировка слиянием, идея.
  3. Алгоритм быстрой сортировки (Quick Sort). Применение схемы построения цикла с помощью инварианта для написания подпрограммы, разделяющей массив на три отрезка: элементы меньше медианы, медиана, элементы больше медианы.
• Лекция 9.
  Непрерывные и ссылочные реализации структур данных. Идея ссылочной реализации, достоинства и недостатки непрерывных и ссылочных реализаций.
  

  Реализация Л2-списка на С++: классы L2ListHeader и L2List. Особенность реализации с использованием динамической памяти: элементы списка являются объектами класса, который наследуется из класса L2ListHeader; поэтому у класса L2ListHeader и у наследуемых из него классов должен быть виртуальный деструктор.

• Лекция 10.
  Проект "Текстовый редактор" (TextEdit.zip). Класс Text, представляющий Л2-список строк, и класс TextLine, представляющий строку текста. Особенности реализации класса TextLine:
  • используется как элемент Л2-списка, поэтому наследуется из класса L2ListHeader;
  • представляет собой динамический массив символов;
  • имеет конструктор, инициализирующий объект по адресу строки в стиле языка Си, и оператор приведения к типу Си-строки (т.е. к типу "const char*");
  • реализует все привычные операции для текстовых строк (конкатенация, вставка/удаление символов и т.п.).
  Реализация класса TextEdit, представляющего собой текстовый редактор в оконной системе X-Windows:
  • наследуется из класса GWindow ("Графическое окно");
  • хранит текст в объекте "text" типа "Text". Класс "Text" наследуется из класса "L2List" и представляет собой Л2-список строк типа TextLine;
  • координаты курсора (измеряемые в колонках и строках) относительно начала текста хранятся в переменных cursorX, cursorY;
  • координаты окна относительно начала текста и его размер хранятся в переменных windowX, windowY, windowWidth, windowHeight;
  • хранится статическая таблица соответствия между кодами нажатых клавиш и методами, реализующими соответствующие команды. Когда пользователь нажимает клавишу, осуществляется поиск в этой таблице и вызывается соответствующий метод, если команда найдена.
  Задачи по проекту "Текстовый Редактор".
• Лекция 11.
  Реализация множества и нагруженного множества, основанная на использовании хеш-функции. Идея реализации: расслоение множества на N небольших подмножеств. Иллюстрация -- записная книжка: аналогом хеш-функции является первая буква фамилии, страницы нумеруются значениями хеш-функции, т.е. буквами алфавита. Требования к хеш-функции. Коллизии, cпособы разрешения коллизий:
  1. Хеш-таблица представляет собой массив голов однонаправленных списков, список с индексом h хранит элементы со значением хеш-функции равным h, где h=0, 1, ..., N-1.
  2. Хеш-таблица представляет собой массив элементов того же типа, что и элементы множества, с индексом типа 0..N-1. Дополнительно используется массив "мощность слоя" целого типа с индексом типа 0..N-1 и массив "остаток" с индексом типа 0..MAX-1, где MAX - некоторая константа, не меньшая, чем потенциальное число элементов множества. Элемент массива "мощность слоя" с индексом h хранит общее число элементов множества, значение хеш-функции от которых равно h. Один из таких элементов хранится в ячейке хеш-таблицы с индексом h, остальные -- в массиве "остаток".
  3. Хеш-таблица представляет собой массив элементов того же типа, что и элементы множества, с индексом типа 0..N-1. Никаких дополнительных массивов не используется. Считаем, что множество может содержать не более чем N-1 элемент. "Пустая" ячейка хеш-таблицы отмечается специальным значением, которое не может содержаться в множестве. При добавлении элемента x к множеству сначала вычисляется значение хеш-функции от него: h=hash(x). Если элемент хеш-таблицы с индексом h занят, то к h прибавляется некоторая фиксированная константа D, где D взаимно просто с N, затем вычисляется остаток от деления полученного числа на N. Таким образом вычисляется новое значение h. Если опять ячейка с индексом h занята, операция снова повторяется, пока не найдется свободная ячейка. Всего может быть не более N-1 повторения. Поиск элемента осуществляется аналогично. Числа N и D в этой реализации обычно выбираются простыми, наример, N=5009, D=1021. Удалять элементы из множества в этой реализации нельзя.

  Проект "Хеш-реализация нагруженного множества" HashSet.zip (используется первый способ разрешения коллизий).
  Задачи по теме "Хеш-реализация множества".

• Лекция 12.
  Формальные языки и грамматики. Определение контекстно-свободной грамматики. Терминалы (элементы исходного алфавита) и нетерминалы, или метасимволы, обозначающие составные элементы цепочек языка. Правила грамматики, начальный нетерминал. Понятие вывода цепочки. Левые и правые выводы, синтаксическое дерево вывода. Свойство детерминированности грамматики (дерево вывода единственно для любой выводимой цепочки). Примеры детерминированных и недетерминированных грамматик: две грамматики языка арифметических формул. Лемма о разрастании (или о накачке, "pumping lemma") для контекстно-свободных языков.
• Лекция 13.
  Конечные автоматы. Детерминированные и недетерминированные КА. Язык, заданный конечным автоматом. Алгоритм определения принадлежности цепочки языку, заданному КА, в случаях детерминированного и недетерминированного автоматов. Алгоритм построения детерминированного КА, эквивалентного данному недетерминированному КА, примеры его применения. Экспоненциальная оценка числа вершин детерминированного КА, эквивалентного исходному недетерминированному. Минимальный детерминированный конечный автомат, критерий минимальности, изоморфизм всех минимальных автоматов. Алгоритм построения минимального КА. Лемма о разрастании ("pumping lemma") для автоматных языков. Примеры автоматных и неавтоматных языков. Автоматные языки как подкласс контекстно-свободных.

  Регулярные языки и регулярные выражения. Примеры задания языков с помощью регулярных выражений. Теорема Клини о совпадении классов автоматных и регулярных языков.

  Утилита LEX для построения сканера, разбивающего поток символов на лексемы в соответствии с заданным набором регулярных выражений. Утилита GREP для поиска фрагмента, соответсвующего регулярному выражению, в файле или в множестве файлов.

• Лекция 14.
  Задача определения принадлежности цепочки языку и восстановления вывода цепочки: синтаксический разбор. Притовоположность задач разбора и вывода. Нисходящий, или рекурсивный, или LL(1) разбор, ограничения при его применении. Восходящий, или LR(1)-разбор. Определение LR-процесса: стек LR-процесса, сдвиги и свертки. Определение ситуации LR(0)-разбора и состояния LR(0)-разбора как конечного множества ситуаций. Алгоритм построения множества LR(0)-состояний для заданной грамматики. Конфликты сдвиг-свертка и свертка-свертка. Определение LR(0)-грамматики: построенное множество LR(0)-состояний не содержит конфликтов. Аналогичные определения для LR(1)-разбора. Таблицы LR-разбора, алгоритм работы LR-парсера, примеры. Стек LR-разбора и семантический стек.

  Инструментальные средства построения компиляторов: утилита LEX для построения лексического анализатора, или "сканера", и утилита YACC для построения синтаксического анализатора, или "парсера" (от английского "to parse" -- разбирать). Проект "Калькулятор формул" (YaccCalc.zip), его реализация с помощью утилит LEX и YACC.
  Задачи по проекту "Калькулятор формул".

Прошлый год (2001-2002), ориентация на язык Java

• Программа курса (2001-2002 уч. год, ориентация на язык Java)
• Проекты, использованные в курсе, задачи для экзамена
• Билеты экзамена 2001-2002 уч. года:
  • подготовленные в LaTeX'е
  • в виде Postscript-файла

  • ---

  • в LaTeX'е, подготовленные для экзамена
  • в виде Postscript-файла, подготовленные для экзамена
• Примеры дополнительных задач на экзамене.

• ---

• Лекция 1. Объектно ориентированные и традиционные языки программирования.
• ... еще не готово...
• Лекция 12. Формальные грамматики. Контекстно-свободные языки.
• Лекция 13. Конечные автоматы и регулярные выражения. LEX, grep.
• Лекция 14. LR-разбор. YACC.
• Описание LEX'а и YACC'а.

• ---

• Программа предыдущего курса (1997-98, ориентация на C++)

Четвертый семестр

• Компьютерные сети. Обзор, классификация. Понятие протокола. Уровневая модель описания сетевых протоколов. Примеры протоколов физического уровня (CSMA/CD, Ethernet, Token Ring, DQDB). Стек интернетовских протоколов TCP/IP. Программирование с использованием интерфейса BSDI-сокетов.
• Простейший пример пары client--server, использующий интерфейс сокетов, реализованный на C++.
• Пример пары клиент--сервер, реализованный на Яве и на C++.
• Сетевое программирование: список задач.
• Применение элементарной теории чисел в программировании: кодирование с открытым ключом (RSA), тесты простоты, факторизация целых чисел и т.п.
  
• Кодирование с открытым ключом (RSA): список задач
• . . .