Крллмкнль. Пi, j Постройте алгоритм сложности O(n), вычисляющий массив P

Название	Пi, j Постройте алгоритм сложности O(n), вычисляющий массив P
Анкор	Крллмкнль
Дата	17.12.2021
Размер	149.09 Kb.
Формат файла
Имя файла	KR_4.pdf
Тип	Задача #307162

Вариант №1.
В задачах на построение алгоритма требуется также доказать правильность и оценить время работы. За переборный алгоритм ставится оценка 0 независимо от правильности алгоритма и наличия доказательства.
1. (6 баллов) Пyсть П — матрица перестановки. Представим ее массивом P : P [i] = j
⇔
П[i, j] = 1. Постройте алгоритм сложности O(n), вычисляющий массив P
0
, представляющий обратную к П матрицу.
2. (6 баллов) Докажите, что алгоритм моделирования НКА M корректен, то есть для каждого i множество построенных на шаге i состояний определяется равенством S
i
= {q : (q
0
, a
1
a
2
. . . a i
) `
∗
M
(q, ε)}.
3. (6 баллов) Покажите, как подсчитать число различных подстрок строки T за время O(m),
где m = |T |. Покажите, как перечислить по одной копии каждой из этих подстрок за время,
пропорциональное их суммарной длине.
4. (6 баллов) Докажите NP-полноту задачи КРАТЧАЙШИЙ ПУТЬ С ОГРАНИЧЕНИЯМИ
ПО ВЕСУ.
Вход: ориентированный граф G = (V, E), функция l(e) ≥ 0, задающая целочисленную длину рёбер из E, функция w(e) ≥ 0, задающая целочисленный вес рёбер из E, вершины s и t из V и положительные целые числа K и W.

Вопрос: существует ли в G простой путь из s в t веса не более W и длины не более K?
(Указание: к этой задаче сводится задача РАЗБИЕНИЕ.)
5. (3 балла) Постройте функцию отказов и ДКА для распознавания вхождения подслова y =
adadaad. Используя этот ДКА, найдите вхождение y в слово x = dadadadadaadd.
6. (3 балла) Для нагруженного графа G, представленного матрицей C, найдите гамильтонов путь, используя алгоритм 2MOD (с двойным обходом минимального остовного дерева). Срав- ните полученный результаты с длиной минимального пути.
C =









0 3
10 10 10 2
1 3
0 2
12 12 2
10 10 2
0 1
10 12 60 10 12 1
0 2
12 10 10 12 10 2
0 5
3 2
2 12 12 5
0 2
1 10 60 10 3
2 0










Вариант №2.
В задачах на построение алгоритма требуется также доказать правильность и оценить время работы. За переборный алгоритм ставится оценка 0 независимо от правильности алгоритма и наличия доказательства.
1. (6 баллов) Предположим, что существует алгоритм, вычисляющий произведение двух (5×5)- матриц, используя 50 операций умножения и 120 операций сложения. Алгоритм какой сложно- сти для умножения (n × n)-матриц можно было бы тогда получить? Будет ли он лучше метода

Штрассена?
2. (6 баллов) Как расширить алгоритм моделирования НКА M , чтобы он находил в слове x = a
1
. . . a n
наименьшее k такое, что для некоторого j подслово a j
. . . a k

принадлежит L(M ), и наименьшее из таких j?
3. (6 баллов) При заданном наборе S из k строк мы хотим найти все строки из S, которые являются подстроками других строк этого набора. Предполагая, что полная длина всех строк равна n, предложите для этой задачи алгоритм со временем O(n).
4. (6 баллов) Докажите NP-полноту задачи РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.
Вход: неориентированный граф G = (V, E), такой что для некоторого целого q: |V | = 3q.
Вопрос: можно ли разбить вершины графа G на q непересекающихся множеств V
1
, . . . , V
q
, каж- дое из которых содержит ровно 3 вершины, попарно соединённых ребрами, т.е. для каждого i = 1, . . . , q V
i
= {u i
, v i
, w i
} и (u i
, v i
), (v i
, w i
), (w i
, u i
) ∈ E?
(Указание: к этой задаче сводится задача 3-СОЧЕТАНИЕ.)
5. (3 балла) Постройте для заданного регулярного выражения R НКА M , допускающий язык
L(R), задаваемый R. Найдите с помощью алгоритма моделирования НКА все вхождения слов из L(R) в слово x.
R = a(bb + ab)
∗
(a + ba), x = babababbabba
6. (3 балла) Используя алгоритм четырёх русских, вычислите произведение булевых матриц
C = AB:
A =




1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 1




,
B =




1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0





Вариант №3.
В задачах на построение алгоритма требуется также доказать правильность и оценить время работы. За переборный алгоритм ставится оценка 0 независимо от правильности алгоритма и наличия доказательства.
1. (6 баллов) Предположим, что мы умеем перемножать две (4 × 4)-матрицы, используя k умножений. Какова тогда сложность умножения (n×n)-матриц (как при использовании метода

Штрассена)? При каком k это позволило бы улучшить оценку Штрассена?
2. (6 баллов) Как расширить алгоритм моделирования НКА M , чтобы он находил в слове x = a
1
. . . a n
наименьшее k такое, что для некоторого j подслово a j
. . . a k

принадлежит L(M ), и наибольшее из таких j?
3. (6 баллов) Наименьший k-повтор. По заданной строке S и числу k мы хотим найти крат- чайшую подстроку S, которая появляется в S ровно k раз. Покажите, как решить эту задачу за линейное время.
4. (6 баллов) Докажите NP-полноту задачи ЦЕЛОЧИСЛЕННЫЙ ПОТОК В СЕТИ С УМНОЖИ-
ТЕЛЯМИ.
Вход: сеть S = ((V, E), s, t, c : E → ω, h : V → ω), где c(e) — пропускная способность ребра e ∈ E,
h(v) — коэффициент увеличения потока в вершине v ∈ V , и граница потока B.
Вопрос: существует ли целочисленная потоковая функция f : E → ω такая, что
1) f (e) ≤ c(e) для всех e ∈ E;
2) для любой v ∈ V \ {s, t} имеет место равенство h(v)
P
(u,v)∈E
f (u, v) =
P
(v,u)∈E
f (v, u);
3)
P
(u,t)∈E
f (u, t) ≥ B.
(Указание: к этой задаче сводится задача РАЗБИЕНИЕ.)
5. (3 балла) Используя алгоритм Рабина-Карпа, найдите все вхождения слова y = 31 в слово x = 123142203158 (пусть простое число q = 11, мощность алфавита m = 10).
6. (3 балла) Используя алгоритм Штрассена, перемножьте две матрицы:
A =

2 6
−1 3

,
B =
4 5 3 6

Вариант №4.
В задачах на построение алгоритма требуется также доказать правильность и оценить время работы. За переборный алгоритм ставится оценка 0 независимо от правильности алгоритма и наличия доказательства.
1. (6 баллов) В доказательстве теоремы о связи задач умножения матриц и транзитивного за- мыкания графов матрица инцидентности графа с n = 2k вершинами X разбивалась на четыре подматрицы:
X =
A B
C
D

Пусть T (X) — матрица транзитивного замыкания:
T (X) =
E F
G H

Покажите, что G = T (D) × C × E, где T (D) — транзитивное замыкание матрицы D.
2. (6 баллов) Доказать корректность алгоритма Кнута-Морриса-Пратта, то есть то, что ДКА
M , построенный алгоритмом ПОДКА, на входе x = a
1
a
2
. . . a k
перейдёт в состояние j тогда и только тогда, когда b
1
b
2
. . . b j
— это самый длинный суффикс x, являющийся префиксом y = b
1
b
2
. . . b l
3. (6 баллов) Подстрока α называется префиксным повтором строки S, если α является пре- фиксом S и имеет вид α = ββ для некоторой строки β. Предложите линейный по времени алгоритм для отыскания наибольшего префиксного повтора входной строки S.
4. (6 баллов) Докажите NP-полноту задачи СЕЛЬСКИЙ ПОЧТАЛЬОН.
Сельский почтальон хочет минимизировать длину маршрута, который обязательно должен включить некоторые улицы, на которых проживают симпатичные девушки.
Вход: ориентированный граф G = (V, E), E
0
⊆ E — множество рёбер, c(e) — длина ребра e
(натуральное число), натуральное число B — длина пути.
Вопрос: существует ли в графе G цикл длины ≤ B, включающий все рёбра из E
0
?
(Указание: к этой задаче сводится задача ГАМИЛЬТОНОВ_ЦИКЛ.)
5. (3 балла) Вычислите используемые в алгоритме Бойера-Мура функции λ (Σ = {0, 1, 2}) и γ
для раcпознавания вхождения подслова y = 101001201 в текст методом Бойера-Мура. Исполь- зуя их, найдите вхождение y в слово x = 0112101001201012010.
6. (3 балла) С помощью алгоритма сжатия данных по Зиву-Лемпелю (с использованием суф- фиксного дерева) постройте сжатое представление для строки x = baabbcaabbcbb.

Вариант №5.
В задачах на построение алгоритма требуется также доказать правильность и оценить время работы. За переборный алгоритм ставится оценка 0 независимо от правильности алгоритма и наличия доказательства.
1. (6 баллов) В доказательстве теоремы о связи задач умножения матриц и транзитивного за- мыкания графов матрица инцидентности графа с n = 2k вершинами X разбивалась на четыре подматрицы:
X =
A B
C
D

Пусть T (X) — матрица транзитивного замыкания:
T (X) =
E F
G H

Покажите, что H = T (D) + T (D) × C × E × B × T (D), где T (D) — транзитивное замыкание матрицы D.
2. (6 баллов) Обобщите алгоритм Рабина-Карпа на случай, когда надо искать квадрат A раз- мером m × m в матрице S размером n × n (элементами квадрата и матрицы являются символы алфавита Σ = {a
1
, . . . , a r
}).
3. (6 баллов) Пусть задано циклическое слово S[1 . . . n], в котором за каждым символом S(i)
следует символ S((i + 1) mod n). Задача состоит в том, чтобы выбрать место разрезания этого слова i так, чтобы получившееся линейное слово S
i
= S(i) . . . S(n)S(1) . . . S(i − 1) было лекси- кографически минимальным среди всех таких линейных слов. Предложите алгоритм линейной сложности для линеаризации циклических слов.
4. (6 баллов) Докажите NP-полноту задачи ГАМИЛЬТОНОВО ПОПОЛНЕНИЕ.
Вход: неориентированный граф G = (V, E), число k > 0.

Вопрос: можно ли к E добавить k рёбер так, чтобы в графе появился гамильтонов цикл?
(Указание: к этой задаче сводится задача ГАМИЛЬТОНОВ_ЦИКЛ.)
5. (3 балла) Постройте с помощью алгоритма Укконена суффиксное дерево для слова x =
ababaab$.
6. (3 балла) Пусть требуется уложить в контейнеры единичного объёма 30m предметов с весами
(здесь ε > 0):
s(A
i
) = 0,5 + ε
(1 ≤ i ≤ 6m),
s(A
i
) = 0,25 + 2ε
(6m < i ≤ 12m),
s(A
i
) = 0,25 + ε
(12m < i ≤ 18m),
s(A
i
) = 0,25 − 2ε
(18m < i ≤ 30m).
Сколько контейнеров потребуется алгоритму, основанному на принципе «в первый подходящий в порядке убывания»? Покажите, что при оптимальной укладке достаточно 9m контейнеров, и оцените ошибку приближённого алгоритма.