Каждый билет состоит из задачи, которую нужно сделать за компьютером в течение часа, и теоретического вопроса (ответ на который, как правило, также состоит в решении простых задач на данную тему). Первая задача, как правило, состоит в модификации одного из проектов, рассмотренных в курсе.
Реализовать исполнитель "Записная книжка" со следующими операциями:
Структуры данных: последовательного доступа -- стек, очередь, дек, двусвязный и односвязный списки; прямого доступа -- массив (вектор), динамический массив, матрица, множество, нагруженное множество. Реализация стека на базе массива.
Основы языка Java. Типы, операции. Классы, члены классов, методы, константы. Статические члены и методы. Наследование классов и интерфейсы. Пакеты. Соглашения об именах. Исключения (Exception), использование нитей (Thread), примеры. Основные отличия объектно-ориентированных языков от традиционных на примере языков Java (объектно-ориентированный язык) и C или C++ (традиционный язык).
Текстовый редактор: добавить команду "открыть файл". Файл открывается в том же окне. Если текст в окне менялся, то перед открытием нового файла редактор должен спросить у пользователя, нужно ли сохранить текущий текст; кроме того, если имя файла для текущего текста не было задано (текст "noname"), то редактор должен попросить выбрать директорию и имя файла для сохранения текста. Открытие файла и сохранение должны использовать стандартный файловый диалог.
Применение схемы инварианта цикла в алгоритме бинарного поиска. Реализация множества с использованием бинарного поиска на языке Java.
Выпуклая оболочка: добавить метод "Угол, под которым выпуклая оболочка видна из точки (вх: t): Вещественное число".
Формальные грамматики (рассматриваются только контекстно свободные грамматики). Левые и правые выводы. Дерево вывода. Детерминированные языки. Лемма о разрастании для КС-языков.
Текстовый редактор: добавить команду "открыть файл". Новый файл должен открываться в новом окне. Работы редактора должна завершаться при закрытии последнего окна.
Схема построения цикла с помощью инварианта на примерах расширенного алгоритма Евклида, быстрого возведения в степень и вычисления логарифма без использования разложения в ряд.
Выпуклая оболочка: добавить метод "Центр тяжести вершин: Точка".
Обработка событий в Java Developer Kit (JDK) версии 1.1. Интерфейсы типа "Listener" и классы типа "Adapter". Создание полоски меню и выполнение команд, выбранных с помощью меню, для окон типа "Frame". Закрытие окна типа "Frame". Обработка нажатий на клавиши и других событий, связанных с управляющими элементами окон, примеры.
Тектовый редактор: реализовать команду "найти парную скобку", которая должна выполняться по нажатию Ctrl+A. При этом, если курсор стоит на скобке, он должен перемещаться на парную скобку. Скобка может быть круглой, квадратной или фигурной, открывающей или закрывающей. Если команда не может быть выполнена, курсор должен оставаться на месте.
Оценка снизу минимального числа операций в произвольном алгоритме сортировки. Алгоритмы пирамидальной сортировки, сортировки слиянием и быстрой сортировки.
Выпуклая оболочка: добавить метод "Точка (вх: t) лежит внутри: Да/нет".
Ссылочные реализации. Реализации Л1 и Л2-списков на языке Java.
Интерпретатор формул: дана алгебраическая функция, запись которой включает переменную "x", вещественные константы, знаки четырех арифметических операций и круглые скобки. Вычислить значение ее производной в заданной точке. (Решение должно использовать CUP -- Java-аналог YACC.)
Идея реализации множества с помощью хеширования. Два способа реализации множества с помощью хеширования: внешнее разрешение коллизий с помощью вектора множеств, использование дополнительного массива ("кучи"). Ссылочная реализация вектора множеств на языке Java и хеш-реализация множества на его основе.
Интерпретатор формул: запись полиномиальной функции включает переменную "x", целые константы, знаки операций "+", "-", "*" (нет деления) и круглые скобки. Напечатать ее запись без скобок, т.е. в виде многочлена. (Решение должно использовать CUP -- Java-аналог YACC.)
Конечные автоматы. Детерминированные и недетерминированные КА. Построение детерминированного КА, эквивалентного заданному недетерминированному. Язык, задаваемый КА. Лемма о разрастании для автоматных языков.
Интерпретатор формул: напечатать обратную польскую запись арифметической формулы. (Решение должно использовать CUP -- Java-аналог YACC.)
Библиотека Java Developer Kit (JDK), версия 1.1. Приложения и аплеты, графический интерфейс (пакет jawa.awt). Создание окна верхнего уровня (Frame) приложения. Вложенные окна, абстрактные классы "Container" и "Component" и их конкретные реализации. Интерфейс "LayoutManager" и конкретные классы, реализующие его. Создание и размещение управляющих элементов в окнах (клавиш, текстовых полей, радио-кнопок и т.д.), примеры.
JLex: напечатать все вещественные константы, соответствующие стандарту языка C (или Java), содержащиеся в заданном файле.
Реализация дека (очереди) на базе массива. Непрерывные реализации множества и нагруженного множества на базе массива (последовательный и бинарный поиск, битовая реализация). Реализация циклов "для каждого элемента" в JDK 1.1: интерфейс Enumeration, методы типа "elements".
Стековый калькулятор: добавить вычисление НОД двух чисел (с помощью алгоритма Евклида), возведение в целую степень и возведение в целую степень по модулю m (с помощью алгоритма быстрого возведения в степень).
Метод определения принадлежности заданной цепочки языку, заданному формальной грамматикой, и восстановления вывода цепочки: LR-разбор. Определение понятий ситуации грамматики и состояния разбора. Состояния LR(0)-разбора и LR(1) разбора. Построение множества возможных состояний и переходов. Построение таблиц для LR(0) и LR(1) разбора. Алгоритм работы парсера.
Интерпретатор формул: добавить операцию возведения в степень "^", выполняемую справа налево и имеющую приоритет, более высокий, чем умножение; добавить также квадратные и фигурные скобки.
Регулярные выражения. Теорема Клини о совпадении классов автоматных и регулярных языков.