2001-02 учебный год

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

1. Основы языка Java. Типы, операции. Классы, члены классов, методы, константы. Статические члены и методы. Наследование классов и интерфейсы. Пакеты. Соглашения об именах. Исключения (Exception), использование нитей (Thread), примеры. Основные отличия объектно-ориентированных языков от традиционных на примере языков Java (объектно-ориентированный язык) и C или C++ (традиционный язык).
2. Библиотека Java Developer Kit (JDK), версия 1.1. Приложения и аплеты, графический интерфейс (пакет jawa.awt). Создание окна верхнего уровня (Frame) приложения. Вложенные окна, абстрактные классы "Container" и "Component" и их конкретные реализации. Интерфейс "LayoutManager" и конкретные классы, реализующие его. Создание и размещение управляющих элементов в окнах (клавиш, текстовых полей, радио-кнопок и т.д.), примеры.
3. Обработка событий в Java Developer Kit (JDK) версии 1.1. Интерфейсы типа "Listener" и классы типа "Adapter". Создание полоски меню и выполнение команд, выбранных с помощью меню, для окон типа "Frame". Закрытие окна типа "Frame". Обработка нажатий на клавиши и других событий, связанных с управляющими элементами окон, примеры.
4. Структуры данных: последовательного доступа -- стек, очередь, дек, двусвязный и односвязный списки; прямого доступа -- массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека и дека (очереди) на базе массива. Битовая реализация ограниченного множества целых чисел. Реализация циклов "для каждого элемента" в JDK 1.1: интерфейс Enumeration, методы типа "elements".
5. Проект "Выпуклая оболочка". Его реализация на языке Java с использованием пакета "Двумерная графика" (R2Grapics).
6. Схема построения цикла с помощью инварианта на примерах расширенного алгоритма Евклида, быстрого возведения в степень и вычисления логарифма без использования разложения в ряд.
7. Применение схемы инварианта цикла в алгоритме бинарного поиска. Реализация множества с использованием бинарного поиска на языке Java.
8. Оценка снизу минимального числа операций в произвольном алгоритме сортировки. Алгоритмы пирамидальной сортировки, сортировки слиянием и быстрой сортировки.
9. Ссылояные реализации. Реализации Л1 и Л2-списков на языке Java.
10. Идея реализации множества с помощью хеширования. Два способа реализации множества с помощью хеширования: внешнее разрешение коллизий с помощью вектора множеств, использование дополнительного массива ("кучи"). Ссылочная реализация вектора множеств на языке Java и и хеш-реализация множества на его основе.
11. Проект "Текстовый редактор" (class TextEdit), реализация на языке Java с использованием Л2-списка строк.
12. Формальные грамматики (рассматриваются только контекстно свободные грамматики). Левые и правые выводы. Дерево вывода. Детерминированные языки. Лемма о разрастании для КС-языков.
13. Конечные автоматы. Детерминированные и недетерминированные КА. Построение детерминированного КА, эквивалентного заданному недетерминированному. Язык, задаваемый КА. Лемма о разрастании для автоматных языков. Регулярные выражения. Теорема Клини о совпадении классов автоматных и регулярных языков.
14. LEX, его реализация на языке Java: JLex. Примеры написания сканеров с использованием JLex.
15. Метод определения принадлежности заданной цепочки языку, заданному формальной грамматикой, и восстановления вывода цепочки: LR-разбор. Определение понятий ситуации грамматики и состояния разбора. Состояния LR(0)-разбора и LR(1) разбора. Построение множества возможных состояний и переходов. Построение таблиц для LR(0) и LR(1) разбора. Алгоритм работы парсера.
16. YACC, его реализация на языке Java: CUP. Примеры построения парсеров с использованием CUP. Проект "Интерпретатор формул".