Список заданий по АСД 2к 2016 весна

<wikitex>

1. Докажите лемму Галлаи: если при удалении любой вершины графа размер его максимального паросочетания не изменяется, то граф фактор-критический.
2. Докажите, что единственное множество Татта фактор-критического графа - пустое множество
3. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $D(G\setminus a)=D(G)$.
4. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $A(G\setminus a)=A(G)\setminus a$.
5. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $C(G\setminus a)=C(G)$.
6. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $\alpha'(G\setminus a)=\alpha'(G)-1$ ($\alpha'(G)$ - размер максимального паросочетания в $G$).
7. Докажите теорему Галлаи-Эдмондса о структурной декомпозиции.
8. Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $D(G)$, а в качестве другой - вершины множества $A$. Соединим вершины ребром, если из соответствующей компоненты в соответствующую вершину есть хотя бы одно ребро. Докажите, что для любого множества $S$ вершин из $A(G)$ множество $N(S)$ содержит больше вершин, чем $S$.
9. Докажите, что любое ребро, соединяющее вершины из $D(G)$ и $A(G)$, лежит в некотором максимальном паросочетании в $G$.
10. Докажите, что любое ребро, соединяющее вершины из $C(G)$ и $A(G)$, не лежит ни в одном максимальном паросочетании в $G$.
11. Будем говорить, что доля $X$ двудольного графа имеет запас, если для любого непустого $S \subset X$ выполнено $|N(S)| > |S|$. Могут ли обе доли двудольного графа иметь запас?
12. Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
13. Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
14. Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
15. Бордером строки называется строка, которая является одновременно ее префиксом и суффиксом. Периодом строки $s$ называется число $p$, такое что для всех допустимых $i$ выполнено $s[i+p]=s[i]$. Докажите, что если у строки длины $n$ есть border длины $k$, то у нее есть период $n - k$.
16. Докажите, что если у строки есть периоды $p$ и $q$, причем $p + q \le n$, то $gcd(p, q)$ также является периодом этой строки.
17. Что будет, если в предыдущем задании убрать условие $p + q \le n$?
18. Строки Фибоначчи. Определим $F_0 = \varepsilon$, $F_1 = b$, $F_2 = a$, $F_n = F_{n-1} F_{n-2}$. Докажите, что существует $k$ такое, что для $n \ge k$ выполнено $F_n^2$ - префикс $F_{n+2}$.
19. Докажите, что существует $k$ такое, что если $n \ge k$, то строка $F_n[1...|F_n|-2]$ - палиндром.
20. Определим строку Туе-Морса: $T_n = t_0t_1t_2...t_{2^n - 1}$, где $t_i = 0$, если двоичная запись числа $i$ содержит четное число единиц, и $t_i = 1$ в противном случае. Доказать, что не существует двух равных как строки подстрок строки $T_n$, имеющих пересекающиеся вхождения в $T_n$
21. Докажите, что для любого $u \ne \varepsilon$ и любого $n$ строка $u^3$ - не подстрока $T_n$
22. Разработать алгоритм восстановления строки по префикс-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
23. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
24. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит двоичный)
25. Вычислить $z$-функцию по префикс функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
26. Вычислить префикс функцию по $z$-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
27. Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
28. Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
29. Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
30. Найти число вхождений каждого из образцов в тексте за время O(длина текста + постр. автомата).
31. Найти последние вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата). Текст подается по одному символу слева направо и у вас нет памяти, чтобы его сохранить.
32. Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
33. Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
34. Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)
35. Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
36. То же, что и в предыдущем задании, но для каждого фиксированного $i$ надо научиться получать строку с нуля за $O(|s|)$.
37. Тандемный повтор - строка вида $a = bb$. Найти максимальный тандемный повтор за $O(n \log n)$, используя результат предыдущего задания. Указание: используйте алгоритм вида "разделяй и властвуй", разделите строку пополам, ответ либо лежит слева от точки деления, либо справа, либо пересекает ее.

</wikitex>