Редактирование: Список заданий по ДМ

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
= Дискретная математика, алгоритмы и структуры данных, 1 семестр =
 
= Дискретная математика, алгоритмы и структуры данных, 1 семестр =
  
# Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
+
# Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
+
# Пусть $R$ и $S$ - симметричные отношения на A. Будет ли симметричным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
+
# Пусть $R$ и $S$ - транзитивные отношения на A. Будет ли транзитивным их а) объединение? б) пересечение?
# Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
+
# Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их а) объединение? б) пересечение?
 
# Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
 
# Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
 
# Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
 
# Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
Строка 12: Строка 12:
 
# Постройте пример рефлексивного, симметричного, но не транзитивного отношения
 
# Постройте пример рефлексивного, симметричного, но не транзитивного отношения
 
# Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
 
# Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
# Пусть $R$ - отношение на $A$. Рассмотрим $Tr(R)$ - пересечение всех транзитивных отношений на $A$, содержащих $R$. Докажите, что $Tr(R) = R^{+}$.
+
# Пусть $R$ - транзитивное антисимметричное отношение. Постройте минимальное отношение $S$, такое что $S^+ = R$
# Пусть $R$ - транзитивное антисимметричное отношение. Предложите способ за полиномиальное время построить минимальное отношение $S$, такое что $S^+ = R$.
 
 
# Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
 
# Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
# В каком случае транзитивное замыкание отношения будет отношением эквивалентности?
 
# В каком случае транзитивное замыкание отношения будет отношением частичного порядка?
 
# Выразите в явном виде "и", "или" и "не" через стрелку Пирса
 
# Выразите в явном виде "и", "или" и "не" через штрих Шеффера
 
 
# Является ли пара $\{x\to y, \neg x\}$ базисом?
 
# Является ли пара $\{x\to y, \neg x\}$ базисом?
 
# Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
 
# Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
Строка 31: Строка 26:
 
# Приведите пример непороговой функции
 
# Приведите пример непороговой функции
 
# Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
 
# Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
# Сколько существует самодвойственных функций от $n$ переменных?
 
# Приведите пример функции, которая лежит во всех пяти классах Поста.
 
# Приведите пример функции, которая лежит во всех пяти классах Поста и существенно зависит хотя бы от трех переменных.
 
 
# Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
 
# Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
 
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
 
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
Строка 43: Строка 35:
 
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
 
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
 
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
 
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$.
+
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
# Докажите, что не существует схем константной глубины для функций $x_1 \oplus ... \oplus x_n$.
+
# Постройте схему линейного размера для мультиплексора.
# Докажите, что не существует схемы константной глубины для сложения.
+
# Постройте схему линейного размера для дешифратора.
# Постройте схему из функциональных элементов с тремя входами: $x, y, z$ и одним выходом. Значение на выходе равно $x$, если $z=0$ и $y$, если $z=1$. Используйте базис из всех не более чем бинарных функций.
+
# Что получится, если в матричном умножителе заменить элементы "and" на элементы "or"?
# Мультиплексор - функциональная схема с $n = 2^k + k$ и одним выходом. Обозначим первые $2^k$ входов как $x_0, x_1, \ldots, x_{2^k-1}$, а оставшиеся $k$ как $y_0, y_1, \ldots, y_{k-1}$. Выход мультиплексора равен $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$. Постройте схему линейного от $n$ размера для мультиплексора.
 
# Дешифратор - функциональная схема с $k + 1$ входом и $n = 2^k$ выходами. Обозначим первые $k$ входов как $y_0, y_1, \ldots, y_{k-1}$, а последний как $z$. Обозначим выходы дешифратора как $x_0, x_1, \ldots, x_{2^k-1}$. Значение на выходах дешифратора 0 на всех выходах, кроме $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$, а на выходе $x_i$ равно значению $z$. Постройте схему линейного размера для дешифратора.
 
 
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
 
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
# На одном китайском заводе в матричном умножителе случайно использовали элементы "или" вместо "и". Можно ли из получившихся значений получить произведение исходных чисел (доступа к входам нет, есть только доступ к $n\times 2n$ выходам матричного псевдоумножителя).
+
# Докажите, что для сложения не существует схемы глубины $O(1)$
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
 
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n/n)$ элементов.
 
 
# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 1, ребра, на которых записан 0, называются ''разомкнутыми''. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
 
# Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами''). Зафиксируем некоторые значения переменным. Тогда ''замкнутыми'' называются ребра, на которых записана 1, ребра, на которых записан 0, называются ''разомкнутыми''. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
 
# Постройте контактную схему для функции "xor".
 
# Постройте контактную схему для функции "xor".
Строка 59: Строка 47:
 
# Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
 
# Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
 
# Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
 
# Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
# Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер.
+
# Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер
# Докажите, что любую булеву функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер.
+
# Докажите, что любую функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер
 
# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
 
# Как выглядит дерево Хаффмана для частот символов $1, 2, ..., 2^{n-1}$ (степени двойки) ?
 
# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
 
# Как выглядит дерево Хаффмана для частот символов $1, 1, 2, 3, ..., F_{n-1}$ (числа Фибоначчи)?
Строка 80: Строка 68:
 
# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
 
# Предложите семейство строк $S_1, S_2, \ldots, S_n, \ldots$, где $S_i$ имеет длину $i$, таких, что при их кодировании с помощью LZW длина строки увеличивается. Начальный алфавит $\{0, 1\}$.
 
# Разработайте алгоритм обратного преобразования Барроуза-Уиллера
 
# Разработайте алгоритм обратного преобразования Барроуза-Уиллера
# Разработайте алгоритм обратного преобразования Барроуза-Уиллера за $O(n)$
+
# Разработайте алгоритм обратного преобразования Барроуза-Уиллера за O(n)
 +
# Проанализируйте время работы алгоритма арифиметического кодирования
 
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
 
# Докажите, что для любого $c > 1$ существует распределение частот $p_1, p_2, .., p_n$, что арифметическое кодирование в $c$ раз лучше Хаффмана
 
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
 
# При арифметическом кодировании можно учитывать, что с учетом уже потраченных символов соотношения символов становятся другими и отрезок надо делить в другой пропорции. Всегда ли кодирование с таким уточнением лучше классического арифметического кодирования?
Строка 87: Строка 76:
 
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
 
# Разработайте оптимальный код исправляющий одну ошибку при пересылке 3 битов
 
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
 
# Разработайте код, исправляющий две ошибки, использующий асимптотически не более $2n$ бит для кодирования $2^n$ символьного алфавита (для $n > n_0$)
# Перечисление всех $2^n$ двоичных векторов длины $n$ называется кодом Грея, если в нем не повторяются никакие два вектора и любые два соседних вектора отличаются ровно в одном разряде. Докажите по индукции, что для любого $n$ существует код Грея.
+
# Докажите, что в зеркальном коде Грея $g_i = i \oplus \lfloor i / 2\rfloor$
# Докажите, что последовательность $g_i = i \oplus \lfloor i / 2\rfloor$ образует код Грея.
+
# Докажите, что в зеркальном коде Грея при переходе от $g_i$ к $g_{i+1}$ меняется тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$
# Построим последовательность $g_i$ следующим образом: пусть $g_0 = 0$ и при переходе от $g_i$ к $g_{i+1}$ будем менять тот же бит, который меняется с 0 на 1 при переходе от $i$ к $i+1$. Докажите, что получившаяся последовательность является кодом Грея.
 
 
# Разработайте код Грея для k-ичных векторов
 
# Разработайте код Грея для k-ичных векторов
 
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
 
# При каких $a_1, a_2, ..., a_n$ существует обход гиперпараллелепипеда $a_1 \times a_2 \times ... \times a_n$, который переходит каждый раз в соседнюю ячейку и бывает в каждой ячейке ровно один раз?
Строка 98: Строка 86:
 
# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
 
# Докажите, что для достаточно больших $n$ существует код Грея, который отличается от любого, полученного из зеркального перестановкой столбцов, отражением и циклическим сдвигом строк
 
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
 
# Код Грея назвается монотонным, если нет таких слов $g_i$ и $g_j$, что $i < j$, а $g_i$ содержит на 2 или больше единиц больше, чем $g_j$. Докажите, что существует монотонный код Грея
 +
# Докажите корректность следующего алгоритма построения цепного кода. Начинаем со строки из $n$ нулей. Каждый раз пытаемся жадно приписать 1, если слово из последних $n$ символов уже встречалось раньше, то приписываем 0. Заканчиваем, когда все $2^n$ слов получены.
 
# Докажите, что $\sum_{k=0}^n C_n^k = 2^n$
 
# Докажите, что $\sum_{k=0}^n C_n^k = 2^n$
 
# Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$
 
# Докажите, что $\sum_{k=0}^n (-1)^kC_n^k = 0$
 +
# Используйте предыдущее задание для альтернативного доказательства формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы.
 +
# Предложите алгоритм получения по перестановке ее таблицы инверсий за $O(n \log n)$.
 +
# Предложите алгоритм получения перестановке по ее таблице инверсий.
 +
# Предложите алгоритм получения перестановки по ее таблице инверсий за $O(n \log n)$.
 
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
 
# Коды Грея для перестановок. Предложите способ перечисления перестановок, в котором соседние перестановки отличаются обменом двух соседних элементов (элементарной транспозицией).
 
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
 
# Коды Грея для сочетаний. Предложите способ перечисления сочетаний, в котором соседние сочетания отличаются заменой одного элемента.
# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
+
# Коды Грея для размещений. Предложите способ перечисления сочетаний, в котором соседние размещения отличаются заменой одного элемента в одной позиции.
# Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
+
# Чему равно число перестановок с заданным циклическим классом?
# Предложите альтернативное доказательство формулы включения-исключения: посчитайте для каждого элемента, сколько раз он будет посчитан в правой части формулы и используйте формулу $\sum_{k=0}^n (-1)^kC_n^k = 0$.
+
# Степенью перестановки $\pi$ называется минимальное $k$, такое что $\pi^k=i$, где $i$ - тождественная перестановка. Как связана степень перестановки с ее циклическим классом?
# Предложите алгоритм получения по перестановке ее таблицы инверсий за $O(n \log n)$.
+
# Предложите алгоритм поиска перестановки из $n$ элементов с максимальной степенью за $O(n^3)$.
# Предложите алгоритм получения перестановки по ее таблице инверсий за $O(n \log n)$.
 
 
# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами
 
# Максимумом в перестановке называется элемент, который больше своих соседей (одного, если он первый или последний, обоих иначе). Выведите рекуррентную формулу для числа перестановок $n$ элементами с $k$ максимумами
 
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
 
# Подъемом в перестановке называется пара соседних элементов, таких что $a_{i-1} < a_i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ подъемами
 
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
 
# Неподвижной точкой в перестановке называется элемент $a_i = i$. Выведите рекуррентную формулу для числа перестановок $n$ элементов с $k$ неподвижными точками
 +
# Рассмотрим коды Грея для перестановок и коды Грея для их таблиц инверсий. Есть ли между ними связь?
 +
# Сочетание с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок не важен. Чему равно число сочетаний с повторениями из $n$ по $k$?
 +
# Размещение с повторениями - это способ выбрать из $n$ элементов $k$, причем один элемент можно выбирать несколько раз. Порядок выбора важен. Чему равно число размещений с повторениями из $n$ по $k$?
 
# Докажите, что числа Стирлинга 1 рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней
 
# Докажите, что числа Стирлинга 1 рода образуют матрицу переходов в линейном пространстве полиномов базиса возрастающих факториальных степеней к базису обычных степеней
 
# Докажите, что числа Стирлинга 2 рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней
 
# Докажите, что числа Стирлинга 2 рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней
Строка 118: Строка 113:
 
# Докажите, что число триангуляций правильного $n$-угольника равно $n-2$-му числу Каталана.
 
# Докажите, что число триангуляций правильного $n$-угольника равно $n-2$-му числу Каталана.
 
# Установите явное взаимно-однозначное соответствие между объектами из предыдущих трех заданий и правильными скобочными последовательностями.
 
# Установите явное взаимно-однозначное соответствие между объектами из предыдущих трех заданий и правильными скобочными последовательностями.
 +
# Разбиение на слагаемые это представление $n$ в виде суммы набора невозрастающих положительных целых чисел. Например, есть 5 разбиений числа 4: $4$, $3+1$, $2+2$, $2+1+1$ и $1+1+1+1$. Укажите способ подсчитать число разбиений числа на слагаемые за $O(n^2)$.
 
# Укажите способ подсчитать число разбиений числа на слагаемые за $O(n \sqrt{n})$
 
# Укажите способ подсчитать число разбиений числа на слагаемые за $O(n \sqrt{n})$
# Решите с помощью ДП задачу о наибольшей общей подстроке за $O(n^2)$
 
# Решите с помощью ДП задачу о наибольшей общей возрастающей подпоследовательности за $O(n^3)$
 
# Решите с помощью ДП задачу о наибольшей общей возрастающей подпоследовательности за $O(n^2)$
 
# Докажите, что минимальное число невозрастающих подпоследовательностей, на которые можно разбить заданную последовательность, равно длине ее наибольшей возрастающей подпоследовательности
 
# Решите задачу о наибольшей возрастающей подпоследовательности за $O(n \log n)$ без дерева отрезков
 
# Решите с помощью ДП задачу о наибольшей пилообразной подпоследовательности (последовательность называется пилообразной, если никакие ее три подряд идущих элемента не образуют ни возрастающую, ни убывающую последовательность)
 
# Докажите, что произведение длины наибольшей возрастающей подпоследовательности и наибольшей убывающей подпоследовательности перестановки не меньше $n$
 
# Будем говорить, что строки a и b образуют пару подстрок строки c, если c можно представить как xaybz, где x, y и z - произвольные строки. Решите с помощью ДП задачу о наибольшей общей паре подстрок.
 
# Задача о редакционном расстоянии: найдите последовательность действий для превращения строки $s$ в строку $t$ с помощью операций вставки, удаления и замены символа. Длины строк $m$ и $n$, соответственно. Требуется решить задачу за $O(mn)$ с памятью $O(m + n)$.
 
# Решите задачу о редакционном расстоянии, если помимо операций вставки, удаления и замены символа можно использовать операцию обмена местами двух соседних символов. Стоимость всех операций одинаковая.
 
# Решите битоническую задачу о комивояжере: найдите во взвешенном графе гамильтонов цикл минимального веса, который удовлетворяет дополнительно следующему свойству: сначала номера посещенных вершин возрастают, а затем убывают. Время $O(n^2)$.
 
# Задача о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Решите задачу за время $O(nc)$ с памятью $O(c)$.
 
# Задача о рюкзаке без ограничения на число одинаковых предметов: дано $n$ типов предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Каждого предмета можно брать несколько (любое количество) экземпляров. Решите задачу за время $O(nc)$ с памятью $O(c)$.
 
# Непрерывная задача о рюкзаке: дано $n$ жидкостей, у каждой жидкости есть доступное количество $w_i$ и стоимость единицы жидкости $v_i$, размер рюкзака $c$, требуется выбрать для каждой жидкости число $0 \le x_i \le w_i$, чтобы суммарной стоимости выбранных жидкостей $\sum x_iv_i$ была максимальна и суммарное объем взятых жидкостей $\sum x_i$ был не более $c$.
 
# Задача о рюкзаке, большой рюкзак: дано $n$ типов предметов, у предмета $i$-го типа есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, предметов каждого типа можно взять любое количество, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$. Докажите, что если максимальный вес предмета $z$, то следует взять предметов с максимальным отношением $c_i/w_i$ с суммарным весом хотя бы $c - z^2$.
 
# Решите задачу о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$, время $O(2^{n/2} \cdot poly(n))$, память $O(2^{n/2})$
 
# Решите с помощью ДП задачу о наибольшей подпоследовательности-палиндроме
 
# Рассмотрим задачу: расставить знаки +, * и скобки в выражении таким образом, чтобы его значение было минимальным по модулю. Приведите контрпример к решению на базе ДП, в котором для каждого подотрезка хранится минимальное и максимальное положительное и отрицательное значение, достижимое на этом отрезке?
 
# Решите с помощью ДП задачу о наибольшей общей подпоследовательности-палиндроме
 
# Решите задачу о рюкзаке: дано $n$ предметов, у каждого предмета есть вес $w_i$ и стоимость $v_i$, размер рюкзака $c$, требуется выбрать предметы максимальной суммарной стоимости с весом не более $c$, время $O(2^{n/2} \cdot poly(n))$, память $O(2^{n/2})$
 
# Решите задачу: найти в дереве минимальное множество вершин, чтобы расстояние от любой вершины до одной из выбранных было не более $d$
 
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетные слагаемые
 
# Выведите рекуррентную формулу для числа разбиений числа $n$ на нечетное число слагаемых
 
# Выведите рекуррентную формулу для числа разбиений числа $n$ на различные слагаемые
 
# Решите задачу о гамильтоновом пути в графе за $O(2^nn)$ (считайте, что $n$ не превышает размер слова в архитектуре компьютера).
 
# Чему равна вероятность, что две случайно вытянутые кости домино можно приложить друг к другу по правилам домино?
 
# Чему равна вероятность, что на двух брошенных честных игральных костях выпадут числа, одно из которых делит другое?
 
# Чему равна вероятность, что если вытянуть из колоды две случайные карты, одной из них можно побить другую (одна из мастей назначена козырем, картой можно побить другую, если они одинаковой масти или если одна из них козырь)?
 
# Чему равна вероятность, что на двадцати брошенных честных монетах выпадет поровну нулей и единиц?
 
# Приведите пример событий, независимых попарно, но зависимых в совокупности
 
# Приведите пример трех событий, для которых $P(A \cap B \cap C) = P(A)P(B)P(C)$, но которые не являются независимыми, причем вероятности всех трех событий больше 0
 
# Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(C) > 0$ выполнено $P(A \cap B|C) = P(A|C)P(B|C)$
 
# Доказать или опровергнуть, что для независимых событий $A$ и $B$ и события $C$, где $P(A) > 0$, $P(B) > 0$ выполнено $P(C|A \cap B) = P(C|A)P(C|B)$
 
# Рассмотрим множество костей домино (неупорядоченные пары $(i, j)$, где $i$ и $j$ от 0 до 6, всего костей 28). Можно ли вероятностное пространство костей домино естественным образом представить как прямое произведение вероятностных пространств?
 
# Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $P(A) = P(B)$
 
# Доказать или опровергнуть: если $P(A|B) = P(B|A)$, то $A$ и $B$ независимы
 
# Доказать или опровергнуть: если $P(A|C) = P(B|C)$, то $P(C|A) = P(C|B)$
 
# Доказать или опровергнуть: если $A$ и $B$ независимы, то $\Omega \setminus A$ и $\Omega \setminus B$ независимы
 
# Можно ли ввести равномерное распределение на натуральных числах?
 
# Приведите пример бесконечного вероятностного простанства
 
# Можно ли конструкцию с произведением вероятностных пространств распространить на бесконечное множество пространств?
 
# Докажите, что если $f$ и $g$ независимы, то для любых $a$ и $b$ события $[f = a]$ и $[g = b]$ независимы
 
# Докажите, что для независимых случайных величин $E\xi\eta =E\xi E\eta$.
 
# Докажите, что математическое ожидание равно $E\xi = \sum\limits_{a\in\mathbb{R}}aP(\xi=a)$. Здесь сумма берется по не более чем счетному числу возможных значений случайной величины.
 
# Дисперсией случайной величины называется $D\xi=E(\xi-E\xi)^2$. Докажите, что дисперсия равна $D\xi=E\xi^2-(E\xi)^2$
 
# Докажите, что дисперсия суммы независимых случайных величин равна сумме их дисперсий.
 
# Найдите математическое ожидание и дисперсию значения на нечестной монете
 
# Найдите математическое ожидание и дисперсию значения на честной игральной кости
 
# Найдите распределение, математическое ожидание и дисперсию следующей случайной величины: число бросков честной монеты до первого выпадения 1.
 
# Ковариацией случайных величин $\xi$ и $\eta$ называют величину $Cov(\xi, \eta)=E((\xi-E\xi)(\eta-E\eta))$. Чему равна ковариация независимых случайных величин?
 
# Корреляцией случайных величин $\xi$ и $\eta$ называют величину $corr(\xi, \eta) = Cov(\xi, \eta) / \sqrt{D\xi D\eta}$. Докажите, что корреляция случайных величин лежит в диапазоне от -1 до 1
 
# Докажите или опровергните, что корреляция случайных величин равна 0 тогда и только тогда, когда они независимы
 
# Докажите, что корреляция случайных величин равна 1 тогда и только тогда, когда они линейно зависимы $(f = cg)$ и $c > 0$ (если $c < 0$, то корелляция равно -1)
 
# Случайные величины f, g и h называются независимыми в совокупности, если для любых a, b и c события [f <= a], [g <= b] и [h <= c] независимы. Приведите пример независимых попарно, но не независимых в совокупности случайных величин
 
# Найдите математическое ожидание числа инверсий в перестановке чисел от 1 до $n$
 
# Найдите математическое ожидание числа подъемов в перестановке чисел от 1 до $n$
 
# Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
 
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )"
 
# Дает ли следующий метод равномерную генерацию всех перестановок? "p = [1, 2, ..., n];  for i from 1 to n: swap(p[random(1..n)], p[random(1..n)] )"
 
# Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$)
 
# Докажите, что для монеты энтропия максимальна в случае честной монеты
 
# Докажите, что для n исходов энтропия максимальна если они все равновероятны
 
# Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $n H(x) + O(\log n)$, где $n$ - длина строки $x$, $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, константа в $O$, не зависит от слова $x$ (но может зависеть от выбранного языка программирования)
 
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$
 
# Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
 
# Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
 
# Что можно сказать про $H(A | A)$?
 
# Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
 
# Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически равно отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
 
# Пусть $f$ и $g$ - непрерывные возрастающие функции, причем $\lim\limits_{x\to-\infty}f(x)=0$,  $\lim\limits_{x\to-\infty}g(x)=0$,  $\lim\limits_{x\to+\infty}f(x)=1$,  $\lim\limits_{x\to+\infty}g(x)=1$, кроме того считайте, что вы можете вычислять $f(x)$, $g(x)$, $f^{-1}(x)$ и $g^{-1}(x)$. У вас есть случайная величина с функцией распределения $f(x)$. Как вам получить случайную величину с функцией распределения $g(x)$?
 
 
</wikitex>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)