Список заданий по АСД сем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>