ПРОГРАММА ЛЕКЦИЙ ПЕРВОГО ПОТОКА ВТОРОГО КУРСА

1996-97 учебный год

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

1. Знакомство с языком C++. Типы, операции. Классы, члены
   классов, методы. Статические члены и методы. Наследование и
   виртуальные методы. Проект "Стековый калькулятор" на C++.

2. Конструктор по умолчанию и copy-конструктор. Переопределение
   операторов для классов на примере классов "вещественный вектор"
   RVect и "вещественная точка" RPoint на плоскости. Правильное
   использование модификатора const и задание типов возвращаемых
   значений для разных типов операторов.
   Библиотека классов для поддержки двумерной графики.
   Класс "Графическое окно" GWindow. Проект "Двумерная графика".

3. Структуры данных: последовательного доступа -- стек, очередь,
   дек, двусвязный и односвязный список; прямого доступа -- массив
   (вектор), динамический массив, матрица, множество, нагруженное
   множество. Реализация стека и дека (очереди) на C++.
   Битовая реализация ограниченного множества целых чисел.

4. Проект "Выпуклая оболочка". Реализация на C++ с использованием
   графического пакета.

5. Ссылояные реализации. Две реализации Л2-списка: с использованием и
   без использования пула свободных блоков.

6. Индуктивные функции: определение, алгоритм вычисления.
   Критерий индуктивности. Индуктивные расширения,
   минимальное индуктивное расширение. Критерий минимальности
   (без доказательств).

7. Схема построения цикла с помощью инварианта
   на примере расширенного алгоритма Евклида, быстрого возведения в
   степень и вычисления логарифма без использования разложения в ряд.

7. Применение схемы инварианта цикла в алгоритме бинарного поиска.
   Реализация множества с использованием бинарного поиска.

8. Оценка снизу минимального числа операций в произвольном
   алгоритме сортировки. Алгоритм пирамидальной сортировки.

9. Идея реализации множества с помощью хеширования. Два способа
   реализации множества с помощью хеширования: внешнее
   разрешение коллизий с помощью вектора множеств, использование
   дополнительного множества ("кучи"). Ссылочная реализация
   вектора множеств.

10. Формальные грамматики (рассматриваются только контекстно
    свободные грамматики). Левые и правые выводы. Дерево вывода.
    Детерминированные языки. Лемма о разрастании.

11. Конечные автоматы. Детерминированные и недетерминированные КА.
    Построение детерминированного КА, эквивалентного заданному
    недетерминированному. Язык, задаваемый КА. Лемма о разрастании
    для автоматных языков. Регулярные выражения. Теорема Клини об
    совпадении классов автоматных и регулярных языков.

12. LEX, примеры написания сканеров.

13. Метод определения принадлежности заданной цепочки языку, заданному
    формальной грамматикой, и восстановления вывода цепочки:
    LR-разбор. Определение понятий ситуации грамматики и состояния
    разбора. Состояния LR(0)-разбора и LR(1) разбора. Построение
    множества возможных состояний и переходов. Построение таблиц для
    LR(0) и LR(1) разбора. Алгоритм работы парсера.

14. YACC. Компилятор и интерпретатор для языка арифметических
    формул, реализация с помощью LEX и YACC.

=================================================================
=================================================================
=================================================================
Темы, которые были первоначально запланированы, но не прочитаны
из-за недостатка времени (возможно, будут прочитаны в следующем
году)

15. Проект "Редактор текстов", реализация на C++.

16. Трехмерная графика. Алгоритмы удаления невидимых линий.
    Проект "Полиедр".

17. Работа в сети Internet. Структура адресов в Internet.
    Уровневая модель сетевых протоколов. Протоколы в Internet:
    IP, UDP, TCP, FTP, TELNET, SMTP, HTTP.
    Worl Wide Web и стандарт построения гипертекстов HTML.
    Примеры гипертекстов.

                    - Конец программы лекций -