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

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 4 семестр

1. Бордером строки называется строка, которая является одновременно ее префиксом и суффиксом. Периодом строки $s$ называется число $p$, такое что для всех допустимых $i$ выполнено $s[i+p]=s[i]$. Докажите, что если у строки длины $n$ есть border длины $k$, то у нее есть период $n - k$.
2. Докажите, что если у строки есть периоды $p$ и $q$, причем $p + q \le n$, то $gcd(p, q)$ также является периодом этой строки.
3. Что будет, если в предыдущем задании убрать условие $p + q \le n$?
4. Строки Фибоначчи. Определим $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}$.
5. Докажите, что существует $k$ такое, что если $n \ge k$, то строка $F_n[1...|F_n|-2]$ - палиндром.
6. Определим строку Туе-Морса: $T_n = t_0t_1t_2...t_{2^n - 1}$, где $t_i = 0$, если двоичная запись числа $i$ содержит четное число единиц, и $t_i = 1$ в противном случае. Доказать, что не существует двух равных как строки подстрок строки $T_n$, имеющих пересекающиеся вхождения в $T_n$
7. Докажите, что для любого $u \ne \varepsilon$ и любого $n$ строка $u^3$ - не подстрока $T_n$
8. Разработать алгоритм восстановления строки по префикс-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
9. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
10. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит двоичный)
11. Вычислить $z$-функцию по префикс функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
12. Вычислить префикс функцию по $z$-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
13. Как найти строку длины $m$ в строке длины $n$ с использованием z-функции и O(m) дополнительной памяти?
14. Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
15. Дана строка $s$. Посчитать матрицу $A: ||a_{ij}|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
16. Докажите, что в конечном автомате для поиска подстроки в строке длины $n$ лишь $O(n)$ ребер ведут не в начальное состояние. Как это помогает сэкономить память?
17. Алгоритм Саймона. Используя результат предыдущего задания, предложите алгоритм построения автомата за $O(n)$ (без множителя, зависящего от размера алфавита).
18. Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку. Время работы должно быть полиномом от длины $s$, и $L$.
19. Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку (по заданному модулю). Время работы должно быть полиномом от длины $s$, и $\log L$.
20. Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ вхождений $s$.
21. Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ непересекающихся вхождений $s$.
22. Это и следующее задание доказывают линейность алгоритма Апостолико-Джанкарло. Будем обозначать закешированные значения наибольшего суффикса образца, который заканчивается в i-й позиции текста как suf[i]. Будем называть отрезок текста [i-suf[i]+1 - i] покрытым. Докажите, что любые два покрытых отрезка в процессе работы алгоритма либо вложены, либо не пересекаются.
23. Используя результат предыдещего задания, докажите, что алгоритм Апостолико-Джанкарло работает линейное время.
24. Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
25. Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
26. Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
27. Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
28. Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
29. Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
30. Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)
31. Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос).
32. Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
33. Дано взвешенное дерево. Разбить вершины его на множество путей (каждая вершина принадлежит ровно одному пути), чтобы путь от любой вершины до любой переходил с одного пути на другой не более $O(\log n)$ раз.
34. Дано взвешенное дерево. Уметь отвечать на запросы "минимальное ребро на пути из $u$ в $v$" и "изменить весь ребра $uv$" за полином от логарифма.
35. Дано взвешенное дерево. Уметь отвечать на запросы "сумма ребер на пути из $u$ в $v$" и "изменить весь ребра $uv$" за $O(\log n)$.
36. Дан массив $a$. Посчитать массив $RMQ[i][j] = min(a[i] ... a[j])$ за $O(n^2)$.
37. Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
38. Свести задачу RMQ к задаче LCA линейного размера (указание: использовать декартово дерево)
39. Можно ли свести задачу RMQ к задаче RMQ$\pm 1$ так, чтобы размер получившегося массива был равен $n+C$, где $n$ - длина исходного массива, а $C$ - константа?
40. Докажите, что число различных как строки подстрок $s$ равно $n(n + 1) / 2$ - sum(lcp[i]).
41. Найти самую длинную строку $p$, такую, что она входит в строку $t$ дважды и не пересекаясь. Решение должно работать за $SA + O(n)$, где $SA$ - время построения суффиксного массива.
42. Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $SA + O(n)$
43. Пусть в алфавите есть ровно два символа. Построить такую строку $s$, что её суффиксный массив совпадает с данным, за $O(n)$.
44. Пусть $B(S)$ - множество бордеров $S$. Найти за $SA + O(n)$ сумму $\sum\limits_{i = 1}^{n} \sum\limits_{j = i}^{n} B(S[i..j])$.
45. Найти строку над алфавитом $\{0, 1\}$, в которой $\Omega(n^2)$ различных как строки подстрок.
46. Строка $s$ называется ветвящейся вправо в $t$, если существуют символы $c$ и $d$, такие что $c \ne d$ : $sc$ и $sd$ - подстроки $t$. Аналогично, ветвящаяся влево, если $cs$ и $ds$ - подстроки $t$. Найти самую длинную ветвящуюся влево и вправо подстроку $t$ за $SA + O(n)$.
47. Найти количество ветвящихся влево и вправо строк для строки $t$. Считать только разные строки.
48. Строка $s$ называется максимальным повтором в $t$, если 1) $s$ входит в $t$ не менее двух раз; 2) если $r$ входит в $t$ не менее двух раз, то $s$ - не является собственной подстрокой $r$. Доказать или опровергнуть, что все максимальные повторы равны по длине.
49. Найти все максимальные повторы за $O(SA + n + ans)$.
50. Петя забыл про спуск по счетчику в алгоритме Укконена. Привести пример строки, на которой полученный алгоритм будет работать дольше чем за $O(n)$.
51. Привести пример, когда в алгоритме Укконена в одной итерации спуск происходит по $\Omega(n)$ реберам.
52. Построить суффиксный массив по суффиксному дереву за $O(n)$.
53. Построить суффиксное дерево по суффиксному массиву за $O(n)$.
54. Определить число различных подстрок в строке с помощью суффиксного дерева за $ST + O(n)$. ($ST$ - время построения суффиксного дерева, суффиксный массив не использовать)
55. Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $ST + O(n)$
56. Найти максимальную подстроку в строке, имеющую два непересекающихся вхождения за $ST + O(n)$.
57. Найти строку максимальной длины, ветвящаяся влево и вправо за $ST + O(n)$.
58. Найти подпалиндром максимальной длины за ST + O(n).
59. Алгоритм Хьюи. Дано дерево, вершины которого раскрашенны в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы - $O(DCU)$.
60. Используя результат предыдущей задачи, найти наибольшую общую подстроку $k$ строк за $O(n + DSU)$.
61. Найти наибольший общий подпалиндром за $ST + O(DSU)$.
62. Найти наибольший максимальный повтор за $ST + O(n)$.
63. Матроид с выкинутым элементом. Пусть $M$ - матроид. Обозначим как $M\setminus x$ матроид, где из носителя выкинут элемент $x$. Множества, не содержавшие $x$, остаются независимыми. Формально, если $M = \langle X, I\rangle$, то $M\setminus x = \langle X \setminus x, \{A | A \in I, x \not\in A\}\rangle$. Докажите, что для любых $M$ и $x$ получившаяся конструкция $M\setminus x$ является матроидом.
64. Матроид, стянутый по элементу. Пусть $M$ - матроид. Обозначим как $M/x$ матроид, где из носителя выкинут элемент $x$. Независимыми объявляются множества, которые ранее содержали $x$, после удаления из них этого элемента. Формально, если $M = \langle X, I\rangle$, то $M/x = \langle X \setminus x, \{A \setminus x | A \in I, x \in A\}\rangle$. Докажите, что для любых $M$ и $x$, таких что $\{x\}\in I$ получившаяся конструкция $M/x$ является матроидом.
65. Прямая сумма матроидов. Пусть $M_1 = \langle X_1, I_1\rangle$ и $M_2=\langle X_2, I_2\rangle$ - матроиды с непересекающимися носителями ($X_1 \cap X_2 = \varnothing$). Обозначим как $M_1+M_2$ следующую конструкцию: $M_1 + M_2 = \langle X_1 \cup X_2, I = \{A \cup B|A \in I_1, B \in I_2\}$. Докажите, что сумма матроидов является матроидом.
66. Разноцветные множества. Пусть $X$ - множество элементов, каждый из которых раскрашен в некоторый цвет. Будем называть независимыми множества, в которых все элементы разного цвета. Докажите, что эта конструкция является матроидом. Используйте определение матроида.
67. Представьте конструкцию из предыдущего примера в виде прямой суммы универсальных матроидов.
68. Является ли алгоритм Прима вариантом алгоритма Радо-Эдмондса?
69. Является ли венгерский алгоритм вариантом алгоритма Радо-Эдмондса?
70. Образуют ли паросочетания в двудольном графе семейство независимых множеств некоторого матроида?
71. Рассмотрим кратчайшие пути из $s$ в $t$ в неориентированном невзвешенном графе. Назовем множество ребер независимым, если оно лежит на некотором кратчайшем пути. Образует ли эта конструкция семейство независимых множеств некоторого матроида?
72. Аксиома баз. Докажите, что если $B_1$ и $B_2$ - базы матроида, то для любого $x \in B_1 \setminus B_2$ найдется $y \in B_2 \setminus B_1$, такой что $B_1 \setminus x \cup y$ тоже база.
73. Обратная аксиома баз. Докажите, что если $B_1$ и $B_2$ - базы матроида, то для любого $y \in B_2 \setminus B_1$ найдется $x \in B_1 \setminus B_2$, такой что $B_1 \setminus x \cup y$ тоже база.
74. Двойственный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M^*$ следующую констркуцию: $M^* = \langle X, \{A | \exists B $ - база $M, A \cap B = \varnothing\}\rangle$. Докажите, что $M^*$ является матроидом.
75. Урезанный матроид. Пусть $M = \langle X, I \rangle$ - матроид. Обозначим как $M|_k$ следующую констркуцию: $M|_k = \langle X, \{A | A \in I, |A| \le k \}\rangle$. Докажите, что $M|_k$ является матроидом.
76. Докажите теорему об аксиоматизации циклами.
77. Докажите теорему о рангах.
78. Докажите теорему об аксиоматизации рангами.
79. Докажите теорему о замыкании.
80. Докажите теорему об аксиоматизации замыканиями.
81. Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксимомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
82. Будем называть два элемента $x$ и $y$ матроида параллельными, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
83. Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \ldots, x_n\}$. Пусть $Y = \left\{x_k \,|\, rank(\{x_1, \ldots, x_{k-1}, x_k\}) > rank(\{x_1, \ldots, x_{k-1}\})\right\}$. Докажите, что $Y$ независимо.
84. Какие универсальные матроиды являются матричными?
85. Докажите, что матроид Вамоса не является представимым ни над каким полем.
86. Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
87. Когда двойственный к графовому матроид является графовым?
88. Докажите лемму о паросочетании в графе замен (формулировка тут: [1], доказательство неправильное - неверный индукционный переход)
89. Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)
90. Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.
91. Предложите алгоритм построения максимальной независимой системы представителей.
92. Докажите, что длина кратчайшего пути из $S$ в $T$ в алгоритме построения базы пересечения матроидов не убывает.
93. Докажите, что число различных длин кратчайшего пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(\sqrt n)$.
94. Докажите, что сумма длин кратчайших пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(n \log n)$.
95. Игра Шеннона. Рассмотрим игру на связном графе с множеством ребер $E$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди добавляют себе ребра, не использованные на предыдущих ходах. В конце игры link выигрывает, если по его ребрам можно дойти от любой вершины до любой. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует два непересекающихся остовных дерева.
96. Игра Шеннона на произвольном матроиде. Рассмотрим игру на матроиде $M$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди выбирают себе элементы носителя, не использованные на предыдущих ходах. В конце игры link выигрывает, если его множество содержит базу матроида. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует две непересекающихся базы.
97. Пусть $M$ - невырожденная квадратная матрица над вещественными числами. Докажите, что для любого множества строк $R$ найдется множество столбцов той же мощности $C$, что миноры $R\times C$ и $\overline{R}\times \overline{C}$ - ненулевые (как $\overline T$ обозначено множество строк/столбцов, не входящих в $T$).
98. Задан двудольный граф, каждая вершина имеет вес. Требуется выбрать паросочетание, чтобы суммарный вес покрытых вершин был максимален. Решите эту задачу, не используя сведение к обычной задаче о назначениях.

</wikitex>