Примеры дополнительных задач на экзамене

1. Реализовать "class Polynom" на Java, представляющий многочлен произвольной степени с вещественными коэффициентами от одной переменной. Реализовать конструктор

       public Polynom(int degree, double coeff[])
   

   и методы сложения, умножения и получения степени многочлена

       public Polynom add(Polynom p)
       public Polynom multiply(Polynom p)
       public int degree()
   

2. Реализовать "class Substitution" на Java, представляющий подстановку (т.е. биективное отображение конечного множества в себя) произвольного порядка порядка n. Реализовать конструктор класса и методы умножения (композиции) подстановок, вычисления обратной подстановки и действия подстановки на элемент множества:

       public Substitution(int n, int s[]) // Constructor
       public Substitution multiply(Substitution s)
       public Substitution Inverse()
       public int map(int i)
   

3. Пример на использование нитей: написать консольную программу на Java, которая запускает 2 нити. Первая 10 раз печатает слово "Орел", в промежутках между печатью ждет случайное время, распределенное в в интервале от нуля до одной секунды; после этого нить завершает работу. Вторая работает так же, но печатает слово "Решка".
4. Создать графическое приложение, представляющее собой пустое окно с полоской меню. Полоска меню содержит меню "Color", в котором 4 пункта: "Red", "Green", "Blue", "Quit". Первоначально окно белого цвета. При выборе одного из первых трех пунктов меню окно окрашивается в соответствующий цвет. При выборе "Quit" приложение завершает работу.
5. Дан Л2-список символов. Заменить в нем любую группу пробелов на один пробел. (Написать программу на псевдокоде.)
6. Переставить последний элемент Л1-списка в начало. (Написать программу на псевдокоде.)
7. Даны два множества. Получить их симметрическую разность. (Написать программу на псевдокоде.)
8. Реализовать 2 стека, ограниченных в совокупности, на базе одного массива.
9. Реализовать Л2-список на базе двух стеков.
10. По аналогии с алгоритмом быстрого возведения в степень, написать алгоритм умножения двух чисел, использующий только сложение, вычитание, удвоение и деление пополам, а также проверку четности числа. Требуется выписать инвариант цикла. Число операций должно линейно зависеть от числа цифр в записи числа.
11. Выписать детерминированную КС-грамматику языка, состоящего из цепочек, представляющих собой корректные описания переменной с фиксированным именем "a" в языке Си. Основной тип всегда "int", можно добавлять любое количесто символов "*", задающих указатель, и пустых квадратных скобок, задающих массив. Для указания порядка операций можно использовать круглые скобки. Описание заканчивается символом ";". Примеры цепочек языка:

        int a;
        int *a;
        int *a;
        int a[];
        int a[][];
        int *a[];
        int (*a)[];
        int *((*a)[]);
    

    Операция добавления квадратных скобок должна иметь более высокий приоритет, чем "*", как это принято в Си. Так, описание "int *a[];" должно трактоваться как "массив указателей", а не "указатель на массив" (т.е. как бы подразумеваются скобки "int *(a[]);").
12. Выписать грамматику языка целых десятичных констант со знаком. Знак не обязателен. Все числа, кроме нуля, не могут начинаться с цифры ноль, так, цепочка 0123 не принадлежит языку. Примеры цепочек, принадлежащих языку:

        0
        -12
        +1034
        +0
        10001
    

13. У недетерминированного конечного автомата
    все вершины начальные, вершина 3 -- конечная. Построить эквивалентный ему детерминированный конечный автомат (эквивалентный -- задающий тот же самый язык).
14. Будет ли регулярным язык, состоящий из всех десятичных констант без знака, которые делятся на 2001?
15. Доказать, что язык, состоящий из всех цепочек вида

        (((...()...)))
    

    где число открывающих скобок равно числу закрывающих, не является регулярным.
16. Будет ли регулярным язык, состоящий из всевозможных цепочек из нулей и единиц, в которых число нулей равно числу единиц?
17. По регулярному выражению

        a*(ab)*b*
    

    построить детерминированный конечный автомат, задающий тот же самый язык.
18. Для грамматики

        S: N
        N: a | Na
    

    где "a" -- терминал, построить систему LR(0)-состояний. Будет ли эта грамматика LR(0)-грамматикой?
19. Построить систему LR(1) состояний для грамматики из предыдущей задачи.
20. Для грамматики

        S: F
        F: a | (F+F)
    

    где "a" -- терминал, построить систему LR(0)-состояний. Будет ли эта грамматика LR(0)-грамматикой?