Ваpиант 1

 

1.(15) Предположим, что существует алгоритм, вычисляющий произведение двух 5х5 матриц, используя 50 операций умножения и 120 операций сложения. Алгоритм какой cложности для умножения       N x N матриц можно было бы тогда получить?

2.(20) Доказать, что алгоритм моделирования НКА М корректен, т.е. для каждого i множество построенных на шаге i состояний

     Si = {q | (q0;a1a2...ai) ├(q, е )}.

 

3. (15) Построить позиционное  дерево и найти двоичный вектор Bv для каждой его вершины для слова  x = abcaba$.

Определить с помощью дерева все позиции, в которых входит в х символ а.

 

4. (20) Докажите NP-полноту задачи ГАМИЛЬТОНОВ ПУТЬ МЕЖДУ ДВУМЯ ВЕРШИНАМИ.

Вход: неориентированный граф G= (V, E), и две вершины s и t.

Вопрос: существует ли в G путь из s в t, проходящий через все вершины по одному разу.

 

5.(15) Используя приближенный полиномиальный алгоритм, решите следующую задачу о рюкзаке с ошибкой < 25%:

S={5, 15, 20, 10, 7, 9}, B=34.

 

 

6.(20) Модифицировать алгоритм нахождения замыкания множества атрибутов X правилами из F методом "прямой волны" так, чтобы для каждого а из ЗАМЫКАНИЕ(X,F) выдавалась линейная программа его вычисления. (Эта линейная программа - список номеров правил, по которым вычисляется а).

 

7. (10) Приведите определение следующих понятий, сопроводив

примерами:

   "вычислительная модель (по Тыугу), синтез программ в ней".

 

      Ваpиант 2

1. (15) Предположим, что существует алгоритм, вычисляющий произведение двух 4х4 матриц, используя 30 операций умножения и 120 операций сложения. Алгоритм какой сложности для умножения     N x N матриц можно было бы тогда получить?

 

2.(15) Используя метод "прямой волны" синтезировать программу-терм для следующей системы зависимостей (вычислительной  модели):

     1) A = 180 -B;       5) S = a*b* Sin(A) ;

     2) B = 180 - A;      6) S1 = a*b*Cos(A);

     3) S = 2S1 + S2;     7) S1 = b*hCos(A)/2

     4) S = a*h;          8) S2 = h*(a - b*Cos(A)).

                          9) S2 = S - 2S1;

    Задача: по B, a и b найти S2.

 

3.(20) Как расширить алгоритм моделирования НКА М, чтобы он находил в слове

x= a1 ... an наименьшее k такое, что для некоторого j слово aj ... ak принадлежит L(M),  и  наименьшее из таких j.

 

4. (20) Пусть y = b1 b2 ... bn. Доказать, что ДКА М, построенный для регулярного выражения I*y c помощью функции отказов работает корректно, т.е. для любого слова a1 ... ak

     (0; a1...ak) ├ (j,e )  <=> b1...bj - суффикс слова a1 ... ak, но при i > j слово  b1...bi не является суффиксом слова a1...ak.

 

5.(15) Для экземпляра задачи ВЕРШИННОЕ_ПОКРЫТИЕ

G=({1,2,3,4}, {(1,2),(1,3),(2,4),(3,4)}), k=2,

построить эквивалентный экземпляр задачи ОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ и для некоторого 2-покрытия указать соответствующий гамильтонов цикл.

 

6. (20) Доказать, что следующая задача является NP-полной. ГАМИЛЬТОНОВО ПОПОЛНЕНИЕ: по графу G=(V,E)  и числу k>0 определить, можно ли к E добавить k ребер, чтобы в графе появился гамильтонов цикл.     

 

7. (10) Приведите определение следующего понятия, сопроводив примерами:

 "абстрактная мера сложности вычислений"

 

 

     Ваpиант 3

 

 

1.(15)  Используя алгоритм 4Р, вычислить произведение булевых

         матриц С = A*B:

          1  1  1  0          1  1  0  1

  A =     1  1  0  1     B =  0  0  0  1

          0  0  1  1          1  0  1  0

          1  0  0  1          0  1  1  1

 

2. (25) Как расширить алгоритм моделирования НКА М, чтобы он находил в слове   x= a1 ... an наименьшее k такое, что для некоторого j подслово aj ... ak принадлежит L(M),  и   наибольшее из таких j.

 

3. (20) Пусть даны два слова-образца y1 и y2. Предложить алгоритм, который распознает входит ли одно из этих слов в слово x= a1...an за время

n + O( |y1| + |y2|).

Указание: использовать функцию отказов, совпадающую на общем префиксе слов y1 и y2. Рассмотреть пример: y1=abbabca,  y2 = abbabba.

4. (15) Доказать, что самое длинное повторяющееся подслово слова x соответствует внутренней вершине позиционного дерева T(x)  с наибольшей глубиной.

 

5.(20) Какое уравнение в словах соответствует следующей 3-КНФ:

    Ф =(X or ¬Y or Z) & (¬X or ¬Y or U) & (Y or ¬Z or ¬U) ?

Найдите соответствие между некоторым набором значений переменных, на котором Ф истинна и решением уравнения в словах.

 

6. (15) Используя метод "прямой волны", вычислить замыкание для следующей системы зависимостей F и набора исходных атрибутов Х = {S2,B, a},

     F:

     1) A = 180 -B;       5) S = ab Sin(A) ;

     2) B = 180 - A;      6) S1 = aCos(A)bSin(A)/2;

     3) S = 2S1 + S2;     7) S1 = bhCos(A)/2

     4) b = aCos(A);      8) h = bCos(A)

 

7. (10) Какова связь задач обращения матриц, вычисления определителя,

решения систем линейных уравнений с задачей умножения матриц.

 

 

     Ваpиант 4

1. (15) Пусть при вычислении произведения булевых матриц можно использовать операции над двоичными векторами. Показать, что  алгоритм 4Р можно с использованием таких операций выполнить за  O(n*n/log(n)) шагов.

2. (25) Пусть M - недетерминированный конечный автомат,                  x = a1 ... an.

Модифицировать алгоритм моделирования НКА так, чтобы  находить все

подслова слова x, принадлежащие языку, допускаемому М.

3. (20) Пусть y = b1 b2 ... bn. Доказать, что алгоpитм ФОТ, вычисляющий фyнкцию отказов f(j), pаботает коppектно.

 

4.(20) Построить с помощью алгоpитма ППД позиционное  дерево для слова  x = bababba$. Определить с его помощью все позиции, в которых  в х входит подслово ab.

 

5. (20) Пусть требуется уложить в контейнеры 30m предметов с весами:

        s(Ai)= 0.5 + ε     (1  <= i <= 6m)

        s(Ai)= 0.25 + 2ε   (6m  < i <= 12m)

        s(Ai)= 0.25 + ε    (12m < i <= 18m)

        s(Ai)= 0.25 - 2ε   (18m < i <= 30m)

Сколько контейнеров потребуется алгоритму, основанному на принципе «в первый подходящий в порядке убывания»? Покажите, что при оптимальной укладке достаточно 9m контейнеров и оцените ошибку приближенного алгоритма.

 

6. (15) Используя метод "прямой волны", вычислить замыкание для следующей системы зависимостей F и набора исходных атрибутов Х = {B, a,h},

     F:

     1) A = 180 -B;       5) S2 = aS1 Sin(A) ;

     2) B = 180 - A;      6) S1 = abCos(A)bSin(A)/2;

     3) S = 2S1 + S2;     7)  S1 = bhCos(A)/2

     4) S1 = ah;

Построить линейную программу, вычисляющую S.

 

7. (10) Приведите определение следующего понятия, сопроводив

примерами:

   «сложностные классы P, PSPACE, NP, NPSPACE»

Каковы известные соотношения между этими классами.

 

     Ваpиант 5

1. (20) Пyсть П - матpица пеpестановки. Пpедставим ее массивом P:

P[i] = j <=> П[i,j] = 1.

Постpойте алгоpитм сложности O(n), вычисляющий массив P', пpедставляющий обpатнyю к П матpицy.

 

2. (15) Построить для заданного регулярного выражения R НКА M, допускающий язык L(R), задаваемый R. Найти с его помощью первое вхождение слова из L(R) в слово x.

R = a(aa + bb)*(b +aa) , x= abaaabba.

 

3. (20) Пусть y = b1 b2 ... bn. Доказать, что алгоpитм ФОТ, вычисляет фyнкцию отказов f(j) за линейное вpемя O(n).

 

4. (20) Построить с помощью алгоpитма ППД позиционное  дерево   для слова       x = aabaab$. Определить с его помощью все позиции, в которых  в х входит подслово ab.

 

5. (20) Для экземпляра задачи ОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ

G=(V={1,2,3,4,5}, E= {(1,2),(1,3),(2,4),(4,3),(3,5),(5,1))

построить эквивалентный экземпляр G' задачи НЕОРИЕНТ_ГАМИЛЬТОНОВ_ЦИКЛ

и для некоторого гамильтонова цикла в G указать соответствующий

гамильтонов цикл в G'.

 

6. (15) Используя алгоритм быстрого замыкания, вычислить замыкание

для следующей системы зависимостей F и набора исходных атрибутов Х = { b,f},

     F:  1) a,b,c -> d;   4) e,f -> c;

         2) b,c,d -> a;   5) f,e  -> d;

         3) g,b   -> e;   6) b,f  -> g.

Какая линейная программа вычисляет атрибут a?

 

7. (10) Сформулируйте теорему о существовании сколь угодно сложных

предикатов и теорему об ускорении для произвольных мер сложности.

 

     Ваpиант 6

1.(15) Используя алгоритм Штрассена для подходящего кольца (какого?),

  вычислить произведение булевых   матриц С = A*B:

    1  0  1  0          0  1  1  0

A = 0  1  0  1     B =  1  0  0  0

    1  0  1  1          1  0  1  0

    1  0  1  0          0  1  1  1

 

 

3. (15) Используя алгоритм моделирования, проверить принимается ли слово x=baaac НКА М.

     M= ({q1,q2,q3,q4,q5,q6,q7},{a,b,c},

программа:{ q1 a -> q2; q1  -> q3; q2 b -> q4; q3 b -> q5;

q3 b -> q2; q3 -> q4; q4 a -> q5; q4 -> q6;

q5 a -> q6; q5 a -> q3; q6 c -> q7},

нач. состояние - q1,   мн-во заключительных состояний = {q7}).

 

3. (15)  Построить функцию отказов и ДКА для раcпознавания вхождения подслова   y = cdcc. Используя этот ДКА, найти  вхождение у в слово x = dcddcdccc.

 

4.(20) Какая задача КЛИКА соответствует следующей 3-КНФ:

Ф =(X or ¬Y or Z) & (¬X or ¬Y or U) & (Y or ¬Z or ¬U) ?

Найдите соответствие между некоторым набором значений переменных,

на котором Ф истинна и кликой в построенном графе.

 

5. (15) Используя алгоритм быстрого замыкания, вычислить замыкание для следующей системы зависимостей F и набора исходных атрибутов Х = { e,f},

     F:  1) a,b,c -> d;   4) e,f -> c;

         2) c,d -> b;     5) f,e  -> d;

         3) g,b -> k;     6) b,f  -> g.

 

6. (20) Уплотненным позиционным деревом  (УПД) для слова           Х =x1...xn$ назовем дерево, полученное из позиционного дерева склеиванием цепей: каждый путь, в котором у всех вершин (кроме, быть может, первой и последней) имеется по одному сыну заменяется на одно ребро из первой вершины этого пути в последнюю,  которому приписывается слово, соответствующее всему пути. Показать, что

   а) у каждой внутренней вершины УПД имеется хотя бы 2 сына;

   б) число всех вершин УПД =О(n).

 

7. (10) Приведите определение следующих понятий, сопроводив

примерами:

  "функция отказов, эвристика  безопасного суффикса".