Викиконспекты - Вклад участника [ru]

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

2015-03-02T11:00:16Z

179.43.147.155:

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

# Бордером строки называется строка, которая является одновременно ее префиксом и суффиксом. Периодом строки $s$ называется число $p$, такое что для всех допустимых $i$ выполнено $s[i+p]=s[i]$. Докажите, что если у строки длины $n$ есть border длины $k$, то у нее есть период $n - k$.
# Докажите, что если у строки есть периоды $p$ и $q$, причем $p + q \le n$, то $gcd(p, q)$ также является периодом этой строки.
# Что будет, если в предыдущем задании убрать условие $p + q \le n$?
# Строки Фибоначчи. Определим $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}$.
# Докажите, что существует $k$ такое, что если $n \ge k$, то строка $F_n[1...|F_n|-2]$ - палиндром.
# Определим строку Туе-Морса: $T_n = t_0t_1t_2...t_{2^n - 1}$, где $t_i = 0$, если двоичная запись числа $i$ содержит четное число единиц, и $t_i = 1$ в противном случае. Доказать, что не существует двух равных как строки подстрок строки $T_n$, имеющих пересекающиеся вхождения в $T_n$
# Докажите, что для любого $u \ne \varepsilon$ и любого $n$ строка $u^3$ - не подстрока $T_n$
# Разработать алгоритм восстановления строки по префикс-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
# Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
# Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит двоичный)
# Вычислить $z$-функцию по префикс функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
# Вычислить префикс функцию по $z$-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
# Как найти строку длины $m$ в строке длины $n$ с использованием z-функции и O(m) дополнительной памяти?
# Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
# Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
# Докажите, что в конечном автомате для поиска подстроки в строке длины $n$ лишь $O(n)$ ребер ведут не в начальное состояние. Как это помогает сэкономить память?
# Алгоритм Саймона. Используя результат предыдущего задания, предложите алгоритм построения автомата за $O(n)$ (без множителя, зависящего от размера алфавита).
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку. Время работы должно быть полиномом от длины $s$, и $L$.
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку (по заданному модулю). Время работы должно быть полиномом от длины $s$, и $\log L$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ вхождений $s$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ непересекающихся вхождений $s$.
# Это и следующее задание доказывают линейность алгоритма Апостолико-Джанкарло. Будем обозначать закешированные значения наибольшего суффикса образца, который заканчивается в i-й позиции текста как suf[i]. Будем называть отрезок текста [i-suf[i]+1 - i] покрытым. Докажите, что любые два покрытых отрезка в процессе работы алгоритма либо вложены, либо не пересекаются.
# Используя результат предыдещего задания, докажите, что алгоритм Апостолико-Джанкарло работает линейное время.
# Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
# Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
# Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
# Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
# Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)

</wikitex>

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

2015-03-02T10:51:10Z

179.43.147.155:

<wikitex>
= Дискретная математика, алгоритмы и структуры данных, 2 семестр =
# Постройте массив, в котором сортировка выбором делает максимальное число обменов
# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
# Найдите минимальное число сравнений для сортировки 4 элементов
# Найдите минимальное число сравнений для сортировки 5 элементов
# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
# Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
# Предложите алгоритм определения глубины сортирующей сети за $O(k)$, где $k$ - число компараторов.
# Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного
# Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной
# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
# Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны
# Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$
# Как найти $s$-й по величине элемент в куче при малых $s$?
# Предложите массив, который при превращении в кучу с помощью алгоритма за $O(n)$ требует выполнить максимальное число обменов.
# Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.
# В массиве есть $k$ элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \log n$ действий
# Докажите, что нельзя проверить, есть ли в куче два одинаковых элемента быстрее, чем за $\Omega(n \log n)$.
</wikitex>