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

2015-02-12T19:36:35Z

46.165.196.137:

<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$.
</wikitex>

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

2015-02-12T19:35:31Z

46.165.196.137:

<wikitex>
= Дискретная математика, алгоритмы и структуры данных, 2 семестр =
# Постройте массив, в котором сортировка выбором делает максимальное число обменов
# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
# Найдите минимальное число сравнений для сортировки 4 элементов
# Найдите минимальное число сравнений для сортировки 5 элементов
# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
</wikitex>

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

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

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