Программа курса
"Математические методы в программировании"

Часть 1. Формальные языки и грамматики

1.1. Основные понятия теории формальных языков

  1. Алфавит A, или множество терминальных символов. Операция * над алфавитом A. Общее понятие языка L в алфавите A. Синтаксис и семантика. Возможные способы задания языка.
  2. Задание языка с помощью формальных грамматик. Определение грамматики общего вида: алфавит метасимволов (нетерминалов), начальный метасимвол, правила грамматики, вывод цепочек языка.
  3. Иерархия Хомского: классы формальных грамматик. Примеры языков, принадлежащих разностям классов, показывающие, что включения классов строгие. Алгоритмическая разрешимость проблемы принадлежности цепочки языку в каждом из классов (без доказательств).
  4. Контекстно-зависимые языки. Теорема о совпадении классов языков, заданных контекстно-зависимыми и неукорачивающими грамматиками (без доказательства). Примеры контекстно-зависимых языков и грамматик.
  5. Контекстно-свободные языки и грамматики. Левые и правые выводы. Синтаксическое дерево вывода цепочки языка. Соответствие между синтаксическими деревьями, левыми и правыми выводами.
  6. Необходимое условие контекстной свободности языка: лемма о разрастании (или лемма о накачке, pumping lemma). Примеры не контекстно-свободных языков. Пример контекстно-зависимого языка, не являющегося контекстно-свободным.
  7. Однозначные контекстно-свободные грамматики (КС-грамматики). Примеры однозначных и неоднозначных грамматик. Существенно неоднозначные языки.
  8. Определение порождающх, достижимых и полезных метасимволов в контекстно-свободной грамматике. Преобразования контекстно-свободных грамматик, не меняющие порождаемый язык: устранение бесполезных символов (путем устранения непорождающих и затем недостижимых символов); устранение эпсилон-правил; устранение цепных правил.
  9. Нормальная форма Хомского для контекстно-свободных грамматик. Теорема об эквивалентности произвольной КС грамматики некоторой грамматике в нормальной форме Хомского, примеры ее применения.

1.2. Конечные автоматы и регулярные языки

  1. Понятие конечного автомата: состояния автомата, входной алфавит, переходы, начальное и конечные состояния. Диаграмма состояний конечного автомата (диаграмма Мура). Автоматы с полным и неполным набором переходов (источники). Детерминированные и недетерминированные конечные автоматы.
  2. Реализация устройств и программирование при помощи конечных автоматов. Наиболее общая модель: действия, совершаемые в момент входа в состояние и при переходе из состояния в состояние. Общая структура программы, использующей автоматный подход, примеры.
  3. Язык, задаваемый конечным автоматом (детерминированным или недетерминированным). Модель порождения и модель распознавания цепочек языка с помощью детерминированных и недетерминированных автоматов. Примеры автоматных языков.
  4. Лемма о разрастании (лемма о накачке, pumping lemma) для автоматных языков. Примеры ее применения для доказательства того, что конкретный язык не является автоматным.
  5. Теорема о совпадении классов языков, задаваемых детерминированными и недетерминированными конечными автоматами. Алгоритм построения детерминированного конечного автомата, эквивалентного заданному недетерминированному, примеры его применения. Примеры недетерминированных КА, для которых минимальное число состояний эквивалентного детерминированного КА экспоненциально зависит от числа состояний НКА.
  6. Минимальный детерминированный конечный автомат, задающий автоматный язык. Изоморфизм всех минимальных детерминированных конечных автоматов для данного автоматного языка. Критерий минимальности ДКА. Построение минимального ДКА по данному автоматному языку (определение состояний этого автомата как классов эквивалентных слов языка). Алгоритм минимизации детерминированного конечного автомата.
  7. Регулярные языки и выражения, примеры. Теорема Клини о совпадении классов автоматных и регулярных языков.
  8. Леволинейные и праволинейные грамматики. Теорема о совпадении классов языков, заданных леволинейными грамматиками, праволинейными грамматиками и класса автоматных языков (а также и класса регулярных языков ввиду теоремы Клини). Построение леволинейной и праволинейной грамматики по конечному автомату и конечного автомата по леволинейной или праволинейной грамматике. Лемма о разрастании для праволинейных (леволинейных, автоматных, регулярных) языков.
  9. Операции над регулярными языками (пересечение, дополнение, произведение, итерация и т.п.). Проблема вычисления звездной высоты регулярного выражения.
  10. Использование программы LEX для создания лексических анализаторов (сканеров) и решения различных задач, связанных с разбиением текста на лексемы, которые можно задать набором регулярных выражений. Примеры.
  11. Построение минимального детерминированного конечного автомата для решения задачи контекстного поиска.
  12. Конечные автоматы с выходом (конечные преобразователи): модели Миля (Mealy) и Мура (Moore). Примеры применения автоматов с выходом в задачах преобразования текстов. Эквивалентность моделей Миля и Мура: алгоритмы построения автомата Мура по автомату Миля и, обратно, автомата Миля по автомату Мура.
  13. Композиция двух автоматов с выходом. Построение автомата с выходом, реализующего композицию двух автоматов.
  14. Детерминированные функции конечного веса (ограниченно-детерминированные функции), определение и свойства. Совпадение класса функций конечного веса, принимающих пустое значение на пустом слове, с классом функций, задаваемых конечными автоматами с выходом. Построение автомата Миля по детерминированной функции конечного веса.

1.3. Контекстно-свободные языки (продолжение)

  1. Линейные грамматики. Лемма о разрастании для линейных языков (без доказательства). Примеры контекстно-свободных языков, не являющихся линейными, и линейных языков, не являющихся регулярными.
  2. Операции на контекстно-свободными языками, не выводящие за пределы этого класса: объединение, произведение, итерация Клини. Операции, выводящие за пределы класса контекстно-свободных языков: пересечение и дополнение. Примеры КС-языков, пересечение которых не является контекстно-свободным языком. Пример КС-языка, дополнение к которому не является КС-языком.
  3. Теорема о контекстной свободности пересечения контекстно-свободного и автоматного языков. Алгоритм построения контекстно-свободной грамматики для пересечения, примеры.

1.4. Алгоритмы синтаксического разбора

  1. Задача разбора, т.е. восстановления вывода цепочки языка. Грамматики с маркером конца цепочки. Рекусивный, или нисходящий, разбор, восстанавливающий левые выводы цепочек языка. Класс КС-грамматик, допускающих рекурсивный разбор: LL(1)-грамматики (определение и примеры). Преобразование грамматики к виду LL(1) (избавление от левой рекурсии) в тех случаях, когда это возможно, примеры. Программная реализация LL(1)-парсера, примеры.
  2. Восходящий разбор, или разбор с помощью конечного автомата со стеком. Определение LR-процесса и возможных действий (сдвиг и свертки по правилам грамматики). Соответствие между успешными LR-процессами и правыми выводами цепочек языка. Возможные неоднозначности при построении LR-процесса.
  3. Разрешение неоднозначности LR-процесса путем построения множества состояний LR-разбора. Определение LR(0)-ситуации разбора. Определение LR(0)-состояния разбора как конечного множества LR(0)-ситуаций. Алгоритм построения множества состояний LR(0)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(0)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(0)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(0) и не LR(0)-грамматик. Алгоритм работы LR(0)-парсера.
  4. LR(1)-разбор. Определение LR(1)-ситуации разбора и LR(1)-состояния разбора как конечного множества LR(1)-ситуаций. Алгоритм построения множества состояний LR(1)-разбора. Построение таблицы действий (сдвиг и свертка по правилу) для LR(1)-разбора, примеры. Возможные конфликты типа сдвиг-свертка или свертка-свертка. Определение LR(1)-грамматики через отсутствие конфликтов в построенном множестве. Примеры LR(1) и не LR(1)-грамматик. Алгоритм работы LR(1)-парсера. Соответствие стека состояний LR(1) разбора и стека LR-процесса.
  5. Использование семантического стека параллельно стеку состояний LR(0) или LR(1) разбора для решения задачи компиляции, т.е. перевода с одного языка на другой. Примеры.
  6. Программные средства для построения компиляторов: LEX (или FLEX) и YACC (или BISON). Построение синтаксического анализатора, или парсера, с помощью системы YACC (BISON). Входной язык описания парсера. Использование сканера, реализованного с помощью LEX, как поставщика информации для парсера. Описание грамматики языка средствами YACC. Способы разрешения конфликтов с помощью приписывания приоритета лексемам и правилам. Семантический стек парсера и определение семантических действий во входном языке для YACC. Примеры построения простых компиляторов с помощью YACC.

Часть 2. Применения элементарной теории чисел в программировании. Схема кодирования с отрытым ключом и задачи, связанные с ней

  1. Обзор необходимых результатов элементарной теории чисел: понятие фактор-кольца, кольцо Zm вычетов по модулю m, группа Um его обратимых элементов. Китайская теорема об остатках. Обычный и расширенный алгоритмы Евклида, алгоритм быстрого возведения в степень. Применение расширенного алгоритма Евклида для вычисления обратного элемента в кольце Zm и в китайской теореме об остатках. Малая теорема Ферма и ее обощенная форма. Определение и вычисление функции Эйлера. Теорема Эйлера и ее форма для колец вычетов по модулю m, свободному от квадратов (т.е. произведению разных простых чисел).
  2. Симметричные и асимметричные адгоритмы кодирования (общие понятия). Классические алгоритмы кодирования: шифр Цезаря, подстановочные шифры. Взламывание подстановочного шифра методом частотного анализа. Шифр Виженера. Способы взлома шифра Виженера: методы Касицкого и Фридмана. История и устройство немецкой шифровальной машины "Энигма", связь с историей второй мировой войны и возникновением компьютеров.
  3. Схема RSA кодирования с открытым ключом. Идея построения электронной подписи.
  4. Алгоритмы теории чисел, связанные со схемой RSA: генерация больших простых чисел и факторизация (разложение на множители) целых чисел. Вероятностный тест простоты Рабина.
  5. Алгоритмы факторизации целых чисел: наивный алгоритм, алгоритм "колесо со спицами". Вероятностные алгоритмы факторизации Полларда (методы Монте-Карло): 1) алгоритм, основанный на поиске цикла в рекурсивной последовательности; 2) (p-1)-алгоритм Полларда. Вариант Ленстра (p-1)-алгоритма Полларда, основанный на применении эллиптических кривых над кольцом вычетов Zm.
  6. Алгоритмы факторизации типа "квадратичное решето", основанные на применении мультипликативных баз в множестве целых чисел.

Часть 3. Трехмерная графика и библиотека OpenGL

  1. Основные алгоритмы двумерной графики: растеризация изображений, представление цветов, сглаживание (antialising), алгоритмы Брезенхема растеризации прямых и кривых.
  2. Основные алгоритмы трехмерной графики: использование буфера глубины (Z-буфера) для удаления невидимых объектов, закрашивание треугольника или выпуклого многоугольника в пространстве — использование источников света и нормалей к поверхности, алгоритмы Гуро и Фонга.
  3. Основная идея библиотеки OpenGL: разделение программы, работающей с трехмерными изображениями, на клиентскую и серверную часть, передача описания трехмерного мира от клиента к серверу вместо его непосредственного рисования. Функции OpenGL-сервера, его реализация (аппаратная, программная, комбинированная).
  4. Система координат в OpenGL — трехмерное проективное пространство, координаты (x, y, z, w), расположение координатных осей. Проективные преобразования и реализация основных афинных трехмерных преобразования с помощью проективных. Задание преобразований в OpenGL. Последовательность преобразования координат точки в процессе ее изображения: преобразования ModelView, Projection, Clipping, ViewPort. Способы использования преобразования ModelView для размещения объектов трехмерного мира, поворотов и перемещения камеры.
  5. Способы задания объектов: задание координат точек и нормалей к поверхности, ориентация многоугольников, задание материальных свойств объектов (рассеиваемый и фоновый цвет, отражающая способность поверхности, светимость и т.п.). Описание источников света.
  6. Описание объектов в парадигме "glBegin(тип объекта)... glEnd()". Типы объектов: отрезки GL_LINES, ломаная GL_LINE_STRIP, замкнутая ломаная GL_LINE_LOOP, треугольники GL_TRIANGLES, веер из треугольников GL_TRIANGLE_FAN, полоска из треугольников GL_TRIANGLE_STRIP, четырехугольники GL_QUADS, полоска из четырехугольников GL_QUAD_STRIP, многоугольник GL_POLYGON и др.
  7. Использование OpenGL в конкретных операционных системах и их графических оболочках: Win32, Unix X-Window. Системно-зависимые и независимые части OpenGL-программы. Примеры OpenGL-программ.
  8. Способы реализации полупрозрачных объектов в OpenGL: использование матрицы прозрачности "Screen Door", смешивание цветов "Color Blending"; порядок рисования непрозрачных и полупрозрачных объектов в случае применения техники смешивания цветов. Задание текстур.

Литература

  1. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. — Интернет-университет информационных технологий www.intuit.ru. — Москва, "Бином", 2006. — 247 стр.
  2. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты. — Москва, Вильямс, 2001. — 768 стр.
  3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. — Москва, Мир, 1978. — 612 стр.
  4. Басалова Г.В. Основы криптографии. — Интернет-университет информационных технологий www.intuit.ru. — Москва, 2008. — 208 стр.
  5. Ву М., Девис Т., Нейдер Дж., Шрайнер Д. OpenGL. Руководство по программированию. Библиотека программиста. 4-е издание. — Питер СПб, 2006. — 624 стр.
  6. Лихачев В.Н. Создание графических моделей с помощью Open Graphics Library. — Интернет-университет информационных технологий www.intuit.ru. — Москва, 2011.