http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Golikovnik&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T13:53:05ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2021_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C&diff=81174Список заданий по ДМ 2021 осень2021-10-01T16:34:17Z<p>Golikovnik: Глубина схемы</p>
<hr />
<div># Постройте пример рефлексивного, симметричного, но не транзитивного отношения<br />
# Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения<br />
# Постройте пример отношения, которое не симметрично и не антисимметрично<br />
# Постройте пример отношения, которое симметрично и антисимметрично<br />
# Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.<br />
# Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?<br />
# Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?<br />
# Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?<br />
# Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?<br />
# Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричной их композиция?<br />
# Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?<br />
# Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность<br />
# Докажите, что $(RS)^{-1} = S^{-1}R^{-1}$.<br />
# Композицией функций $f : A \to B$ и $g : B \to C$ называется $g \circ f$, что $(g \circ f)(x) = g(f(x))$. Докажите, если $f$ и $g$ инъективны/сюръективны/биективны, то то же свойство верно и для их композиции.<br />
# Отношение $R \subseteq A \times B$ называется функциональным, если $R^{-1} R \subseteq I$. Правда ли, что если $R \subseteq A \times B$ и $S \subseteq B \times C$ функциональны, то $RS \subseteq A \times C$ функционально?<br />
# Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $a + d = b + c$ на ${\mathbb N} \times {\mathbb N}$ отношением эквивалентности?<br />
# Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?<br />
# Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?<br />
# Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?<br />
# СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.<br />
# Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде "и", "или" и "не" через стрелку Пирса<br />
# Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде "и", "или" и "не" через штрих Шеффера<br />
# Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргументов?<br />
# Можно ли "и", "или" и "не" выразить через функции из множества $\{x\oplus y, x = y\}$?<br />
# Можно ли "и", "или" и "не" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?<br />
# Медиана $\langle xyz\rangle$, также известная как функция большинства или функция голосования, равна 1, если из трех ее аргументов хотя бы два равны 1. Можно ли "и", "или" и "не" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?<br />
# Можно ли "и", "или" и "не" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?<br />
# Можно ли выразить "и" через "или"?<br />
# Можно ли выразить $\oplus$ через $=$?<br />
# Медиана $2n+1$ булевского значения равна 1 если и только если среди аргументов больше 1. Выразите медиану 5 через медиану 3<br />
# Выразите медиану $2n+1$ через медиану 3<br />
# Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и", "или", "не" - пороговые функции.<br />
# Приведите пример непороговой функции. Поясните, почему из предыдущего номера не следует, что любая функция является пороговой.<br />
# Рассмотрим булеву функцию $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$<br />
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.<br />
# Расссмотрим функцию $f$, построим ее СДНФ. Заменим в этой формуле все $\vee$ на $\wedge$ и наоборот. Получится СКНФ некоторой функции $g$. Для каких функций $f$ выполнено $f=g$?<br />
# Для каждого класса Поста проверьте, существует ли функция, которая лежит в этом классе Поста, но не лежит ни в одном из четырех других.<br />
# Для каждого класса Поста проверьте, существует ли функция, которая не лежит в этом классе Поста, но лежит в четырех остальных.<br />
# Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.<br />
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.<br />
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.<br />
# Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.<br />
# Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?<br />
# Какие симметричные булевы функции являются пороговыми?<br />
# Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций<br />
# Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.<br />
# Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану<br />
# Говорят, что формула находится в 2-КНФ (или форме Крома). если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Докажите, что если булеву функцию $f$ можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$<br />
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$, то булеву функцию $f$ можно задать в форме Крома.<br />
# Докажите, что если булеву функцию $f$ можно задать в форме Хорна, то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$<br />
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$, то булеву функцию $f$ можно задать в форме Хорна<br />
# Докажите, что $x_0\oplus x_1\oplus\ldots\oplus x_{2m} = \langle \neg x_0,s_1,s_2,\ldots,s_{2m}\rangle$, где $s_j=\langle x_0,x_j,x_{j+1},\ldots,x_{j+m-1},\neg x_{j+m},\neg x_{j+m+1},\ldots,\neg x_{j+2m-1}\rangle$, для удобства $x_{2m+k}$ обозначет то же, что и $x_k$ для $k \ge 1$.<br />
# Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).<br />
# Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.<br />
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.<br />
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$, используя не более 8 элементов. Элемент для "не" также считается.<br />
# Определим глубину схемы как максимальное число функциональных элементов на пути от входа до выхода в этой схеме. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.<br />
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$<br />
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.<br />
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.<br />
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.<br />
# Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$<br />
# Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\left((\gamma \succeq \alpha) \wedge (\gamma \succeq \beta)\right) \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$. <br />
# Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.<br />
# Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком. <br />
# Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).<br />
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.<br />
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.<br />
# Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.<br />
# Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?<br />
# Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.<br />
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.<br />
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.</div>Golikovnikhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2%D0%BA_2020_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0&diff=73247Список заданий по ДМ 2к 2020 весна2020-03-24T18:23:24Z<p>Golikovnik: </p>
<hr />
<div># Формальный степенной ряд $\exp(s) = e^s$ определен как $e^s=1+\frac{1}{1!}s+\frac{1}{2!}s^2+\frac{1}{3!}s^3+\ldots+\frac{1}{n!}s^n+\ldots$. Логично, что $e^{-s}=1-\frac{1}{1!}s+\frac{1}{2!}s^2-\frac{1}{3!}s^3+\ldots+(-1)^n\frac{1}{n!}s^n+\ldots$. Докажите, используя определение умножения для степенных рядов, что $e^se^{-s}=1$.<br />
# Формальный степенной ряд $(1+s)^\alpha$ определен как $(1+s)^\alpha=1+\frac{\alpha}{1}s+\frac{\alpha(\alpha-1)}{1 \cdot 2}s^2+\ldots+\frac{\alpha(\alpha-1)\ldots(\alpha-n+1)}{1 \cdot 2 \cdot\ldots\cdot n}s^n+\ldots$. Докажите, что $(1+s)^\alpha(1+s)^\beta=(1+s)^{\alpha+\beta}$.<br />
# Формальный степенной ряд $\cos(s)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {s^{2n}}{(2n)!}$, а $\sin(s)$ определен как $\sum_{n=0}^{\infty} (-1)^n \frac {s^{2n+1}}{(2n+1)!}$. Докажите, что $\sin^2(s) + \cos^2(s) = 1$.<br />
# Докажите, что $\sin(2s) = 2 \sin(s) \cos(s)$.<br />
# Пусть $B(s) = b_1s+b_2s^2+b_3s^3+\ldots+b_ns^n+\ldots$, причем $b_1\ne 0$. Пусть формальные степенные ряды $A(s)$ и $C(s)$ таковы, что $A(B(s)) = s$, $B(C(s))=s$. Докажите, что $A(s)=C(s)$ Этот ряд называется обратным к $B(s)$, обозначается как $B^{-1}(s)$.<br />
# Будем называть нулем степенной ряд $0(s) = 0 + 0s + 0s^2 + \ldots$. Докажите, что $A(s) \ne 0(s)$, $B(s) \ne 0(s)$, то $A(s)B(s) \ne 0(s)$.<br />
# Докажите, что $(A(s)B(s))' = A'(s)B(s) + A(s)B'(s)$.<br />
# Докажите, что $\int(A'(s)B(s) + A(s)B'(s)) = A(s)B(s) - A(0)B(0)$.<br />
# Найдите производящую функцию для последовательности $0 \cdot 1, 1 \cdot 2, 2 \cdot 3, 3 \cdot 4, \ldots, (n - 1) \cdot n, \ldots$.<br />
# Найдите производящую функцию для последовательности $1^2, 2^2, 3^2, \ldots, n^2, \ldots$.<br />
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0 + a_1, a_1 + a_2, \ldots, a_k+a_{k+1}$<br />
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, \sum\limits_{i=0}^ka_i,\ldots$<br />
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_1b, a_2b^2, \ldots, a_kb^k, \ldots$<br />
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, 0, a_1, 0, a_2, 0, a_3 \ldots$<br />
# Последовательность $a_0, a_1, a_2, \ldots, a_k, \ldots$ имеет производящую функцию $A(s)=a_0+a_1s+a_2s^2+\ldots$. Найдите производящую функцию последовательности $a_0, a_2, a_4, a_6 \ldots$<br />
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_1+\ldots+f_n=f_{n+2}-1$.<br />
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0+f_2+\ldots+f_{2n}=f_{2n+1}$.<br />
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_1+f_3+\ldots+f_{2n-1}=f_{2n}-1$.<br />
# Пользуясь производящей функцией для чисел Фибоначчи, докажите утверждение, что $f_0^2+f_1^2+f_2^2+\ldots+f_n^2=f_nf_{n+1}$.<br />
# Найдите производящую функцию для чисел "трибоначчи" $f_0=f_1=f_2=1$, $f_n = f_{n-1}+f_{n-2}+f_{n-3}$.<br />
# Найдите производящую функцию для последовательности, заданной рекуррентностью $f_0=f_1=f_2=1$, $f_n = f_{n-1}-2f_{n-3}$.<br />
# Производящая функция называется рациональной, если она представима в виде отношения двух многочленов. Для производящих функций каждой из следующих последовательностей выясните, является ли она рациональной, если да, приведите ее представление в таком виде. Последовательность # Последовательность $1, -2, 3, -4, 5, \ldots$.<br />
# Последовательность $0, 1, 8, 27, 64, 125, \ldots, k^3,\ldots$<br />
# Последовательность $1, 1, 4, 9, 25, \ldots, F_k^2,\ldots$<br />
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих три нуля подряд.<br />
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 010.<br />
# Найдите производящую функцию для строк над алфавитом $\{0, 1\}$, не содержащих подстроки 011.<br />
# Обозначим за $a_n$ количество способов разменять $n$ рублей монетами по $1$, $2$ и $5$ рублей (порядок монет важен). Постройте производящую функцию для $a_n$.<br />
# То же самое, что в предыдущем задании, но порядок монет не важен.<br />
# Несложно заметить, что производящая функция последовательности $a_n = n^m$ будет иметь вид $\frac {P_m(s)}{(1-s)^{m+1}}$. Выведите рекуррентное соотношение для коэффициентов многочленов $P_{m, k}$.<br />
# Оказывается, что коэффициенты $P_{m,k}$ также являются количеством некоторых комбинаторных объектов. Каких?<br />
# Найдите производящую функцию для замощений прямоугольника $2\times n$ доминошками и единичными клетками.<br />
# Найдите производящую функцию для замощений прямоугольника $2\times n$ уголками (квадратами $2\times 2$ с вырезанной одной клеткой) и единичными клетками. <br />
# Путь Моцкина - путь, начинающийся в точке $(0, 0)$, составленный из векторов $(1, 1)$, $(1, 0)$, $(1, -1)$, не опускающийся ниже оси $OX$ и заканчивающийся в точке $(n, 0)$. Напишите рекуррентное соотношение для числа путей Моцкина, найдите производящую функцию для числа таких путей.<br />
# Рассмотрим множество путей на прямой, начинающихся в 0, состоящих из шагов длины 1 вправо или влево. Будем называть такой путь блужданием. Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0.<br />
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в 0 и не заходящих в отрицательную полупрямую. <br />
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$.<br />
# Найдите рекуррентную формулу и производящую функцию для числа блужданий из $n$ шагов, оканчивающихся в фиксированной точке $N > 0$ и не заходящих в отрицательную полупрямую.<br />
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 5a_{n-1}-6a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.<br />
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-2}-a_{n-1}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.<br />
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 6a_{n-1}-9a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.<br />
# Петя заинтересовался, что будет, если последовательность, заданная линейным рекуррентным соотношением, имеет производящую фукнцию, в знаменателе которой стоит $Q(t)=(1-ct)(1+ct)$, ведь тогда асимптотическое поведение членов на четных и нечетных позициях разное. Разберитесь.<br />
# Последовательность задана рекуррентным соотношением $a_0=a_1=1$, $a_n = 2a_{n-1}-2a_{n-2}$. Оцените асимптотическое поведение $a_n$ при $n\to+\infty$.<br />
# Пусть рациональная производящая функция имеет вид $A(s) = \frac {P(s)}{Q(s)}$, где единственный минимальный по модулю корень $Q(s)$ равен $1 / \beta$ и имеет кратность $k$. Тогда $a_n \approx C \beta^n n^{k-1}$. Покажите, что $C = k \frac {(-\beta)^k P(1 / \beta)} {Q^{(k)}(1 / \beta)}$<br />
# Докажите, что если последовательность $a_n$ допускает представление в виде $a_n = \sum_i p_i(n)q_i^n$, где $p_i(n)$ - полиномы, и все $q_i$ различны, то такое представление единственно с точностью до порядка слагаемых.<br />
# Произведением Адамара двух производящих функций $A(t)$ и $B(t)$ называется призводящая функция для ряда $C(t) = a_0b_0+a_1b_1t+a_2b_2t^2+\ldots+a_nb_nt^n+\ldots$. Докажите, что если $A(t)$ и $B(t)$ являются отношениями двух полиномов, то таким же свойством обладает и $C(t)$.<br />
# Найдите произведение Адамара $\frac{1}{1-x}$ и $\frac{1}{1-2x}$.<br />
# Найдите произведение Адамара $\frac{1}{1-2x}$ и $\frac{1}{1-3x}$.<br />
# Найдите произведение Адамара $\frac{1}{1+3x-x^2}$ и $\frac{1}{1-2x}$.<br />
# Найдите произведение Адамара $\frac{1}{(1-3x)^2}$ и $\frac{1}{(1-2x)^2}$.<br />
# Пусть $A$ - семейство комбинаторных объектов. Пусть $M = MSet(A)$, а $P = Set(A)$. Докажите, что $M(t) = P(t)M(t^2)$.<br />
# Пусть $A$ - семейство комбинаторных объектов с производящей функцией $A(t)$. Пусть $\mathbb{N}$ - множество натуральных чисел, (вес числа $k$ равен $k$). Пусть $T \subset \mathbb{N}$, обозначим как $T(t)$ производящую функцию для множества $T$. Обозначим как $Seq_T(A)$ множество последовательностей элементов из $A$, где длина последовательности лежит в множестве $T$. Обозначим как $Z$ множество из одного элемента веса $1$. Обозначим как $C^T$ множество представлений в виде суммы, где порядок слагаемых важен и слагаемые выбраны из множества $T$. Осознайте, что $C^T = Seq(Seq_T(Z))$. Найдите производяющую функцию для $C^T$.<br />
# Докажите, что $\frac{1}{1-z}=\prod\limits_{j=0}^\infty(1+z^{2^j})$.<br />
# Обозначим за $B$ множество всех конечных подмножеств $A$, в которых все элементы имеют различный вес. Выведите производящую функцию $B(t)$.<br />
# Определим множество "неориентированных последовательностей" $B = USeq(A)$, как множество всех последовательностей элементов из $A$, где последовательность $L$ и $rev(L)$ считаются одинаковыми. Покажите, что $B(t) = \frac 12 \frac {1}{1 - A(t)} + \frac 12 \frac {1 + A(t)}{1 - A(t^2)}$<br />
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $k$ по $n$, где любые два выбранных числа отличаются как минимум на $t$. Исследуя ПФ, найдите количество таких сочетаний.<br />
# Зафиксируем числа $k$ и $t$. Найдите производящую функцию для числа сочетаний из $k$ по $n$, где расстояние между любыми соседними выбранными числами не больше $t$. Исследуя ПФ, найдите количество таких сочетаний.<br />
# Обозначим как $W$ множество всех слов над алфавитом $\{a, b\}$. Объясните равенство $W=Seq\{a\}\times Seq(\{b\}\times Seq\{a\})$. Проверьте равенство производящих функций.<br />
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, в которых нет более $k$ подряд идущих нулей или единиц.<br />
# Постройте производящую функцию для строк над алфавитом $\{0, 1\}$, содержащих заданную строку $s$ длины $k$ как подпоследовательность. Сделайте вывод об асимптотическом количестве таких строк.<br />
# Найдите производящую функцию для строк, содержащих заданный паттерн $p$ как подстроку.<br />
# Рассмотрим бесконечную случайную строку из $0$ и $1$. Докажите, что матожидание позиции первого вхождения строки $p$ длины $k$ равно $2^k c(\frac 12)$, где $c(z)$ - автокорреляционный многочлен. Указание: можно использовать формулу $EX = \sum\limits_{n=0}^{\infty} P(X > n)$.<br />
# Постройте производящие функции для разбиений на различные слагаемые и на нечетные слагаемые. Покажите, что они совпадают.<br />
# Постройте производящую функцию для разбиений на не больше, чем $k$ положительных слагаемых, порядок слагаемых не важен.<br />
# Обозначим как $P^T$ множество разбиений на слагаемые, где порядок слагаемых не важен, а слагаемые выбраны из множества $T$. Осознайте, что $P^T = MSet(Seq_T(Z))$. Найдите производяющую функцию для $P^T$.<br />
# Индекс Хирша. Докажите, что $\prod\limits_{n=1}^\infty\frac{1}{1-z^n}=\sum\limits_{n\ge 0}\frac{z^{n^2}}{((1-z)\cdots(1-z^n))^2}$.<br />
# Опишите класс помеченных объектов $seq(cyc(Z))$. Найдите его экспоненциальную производящую функцию.<br />
# Будем обозначать $seq_T$, $cyc_T$, $set_T$ соответственно последовательности, циклы и множества, размер которых принадлежит множеству $T$. Опишите класс помеченных объектов $set(cyc_{> 1}(Z))$. Найдите его экспоненциальную производящую функцию.<br />
# Для производящей функции из прошлого задания найдите явную формулу и асимптотическое поведение количества объектов веса $n$.<br />
# Опишите класс помеченных объектов $set(cyc_{1, 2}(Z))$. Найдите его экспоненциальную производящую функцию.<br />
# Сюръекции на $r$-элементное множество. Осознайте, что $seq_{=r}(set_{\ge 1}(Z))$ задаёт сюръекции на $r$-элементное множество. Найдите экспоненциальную производящую функцию.<br />
# Разбиения на $r$ множеств. Осознайте, что $set_{=r}(set_{\ge 1}(Z))$ задаёт разбиения на $r$ множеств. Найдите экспоненциальную производящую функцию. Что стоит при $z^n$?<br />
# Числа Белла. Число Белла $b_n$ равно числу разбиений $n$-элементного множества на подмножества (число подмножеств не фиксировано). Докажите, что экспоненциальная производящая функция для чисел Белла равна $e^{e^z-1}$. <br />
# Гиперболический синус $\mathrm{sh}\,z$ равен $\frac{1}{2}(e^{z}-e^{-z})$. Гиперболический косинус $\mathrm{ch}\,z$ равен $\frac{1}{2}(e^{z}+e^{-z})$. Рассмотрим разбиения $n$-элементного множества на непустые подмножества. Докажите, что для разбиений на нечетное число подмножеств экспоненциальная производящая функция равна $\mathrm{sh}(e^z-1)$.<br />
# Докажите, что для разбиений на четное число подмножеств экспоненциальная производящая функция равна $\mathrm{ch}(e^z-1)$.<br />
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит нечетное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{sh}\,z}$.<br />
# Докажите, что для разбиений на произвольное число подмножеств, каждое из которых содержит четное число элементов, экспоненциальная производящая функция равна $e^{\mathrm{ch}\,z-1}$. Почему здесь в показателе степени есть $-1$, а в предыдущем задании нет?<br />
# Обобщите четыре предыдущих задания. Как выглядят экспоненциальные производящие функции для разбиений на (не)четное число подмножеств, каждое из которых содержит (не)четное число элементов? (Необходимо дать четыре ответа для всех комбинаций)<br />
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из четных циклов<br />
# Постройте экспоненциальную производящую функцию для перестановок, состоящих из нечетных циклов.<br />
# Докажите, что для четного N количество перестановок, в которых все циклы четные, и количество перестановок, в которых все циклы нечетные, совпадают.<br />
# "Произведение с коробочкой": Обозначим $C = A^{\square} \star B$, как множество упорядоченных пар объектов из $A$ и $B$ со всеми возможными нумерациями, где атом с номером $1$ принадлежит первому элементу пары. Выведите формулу для $C_n$.<br />
# Докажите, что если $C = A^{\square} \star B$, то $C'(z) = A'(z) \cdot B(z)$.</div>Golikovnikhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85&diff=71324Персистентные структуры данных2019-05-30T08:19:10Z<p>Golikovnik: </p>
<hr />
<div>{{Определение<br />
|definition= '''Персистентные структуры данных''' (англ. ''persistent data structure'') — это структуры данных, которые при внесении в них каких-то изменений сохраняют все свои предыдущие состояния и доступ к этим состояниям.}}<br />
<br />
==Уровни персистентности==<br />
Есть несколько уровней персистентности:<br />
*частичная (англ. ''partial''),<br />
*полная (англ. ''full''),<br />
*конфлюэнтная (англ. ''confluent''),<br />
*функциональная (англ. ''functional'').<br />
<br />
В частично персистентных структурах данных к каждой версии можно делать запросы, но изменять можно только последнюю версию структуры данных.<br />
<br />
В полностью персистентных структурах данных можно менять не только последнюю, но и любую версию структур данных, также к любой версии можно делать запросы.<br />
<br />
Конфлюэнтные структуры данных позволяют объединять две структуры данных в одну (деревья поиска, которые можно сливать).<br />
<br />
Функциональные структуры данных полностью персистентны по определению, так как в них запрещаются уничтожающие присваивания, т.е. любой переменной значение может быть присвоено только один раз и изменять значения переменных нельзя.<br />
Если структура данных функциональна, то она и конфлюэнтна, если конфлюэнтна, то и полностью персистентна, если полностью персистентна, то и частично персистентна. Однако бывают структуры данных не функциональные, но конфлюэнтные.<br />
<br />
==Способы преобразования структур данных в персистентные==<br />
Есть несколько способов сделать любую структуру персистентной: <br />
*полное копирование (англ. ''full copy'') когда при любой операции изменения полностью копируется структура данных и в получившуюся новую копию вносятся изменения,<br />
* копирование пути (англ. ''path copying''),<br />
<br />
*метод «толстых» узлов (англ. ''fat node'').<br />
Рассмотрим для начала частичную персистентность. Для наглядности занумеруем разные версии структур данных. История изменений структуры данных линейна, в любой момент времени можно обратиться к любой версии структуры данных, но поменять возможно только последнюю версию (на рисунке она выделена синим цветом).<br />
<br />
[[Файл:Список версий.png]]<br />
<br />
Сформулируем, что такое структура данных. В нашем понимании структурой данных будет называться набор узлов, в которых хранятся какие-то данные, и эти узлы связаны ссылками. Пример структуры данных — [[Дерево поиска, наивная реализация|дерево]]. Рассмотрим, как методом копирования пути превратить дерево в персистентное.<br />
<br />
===Метод копирование пути===<br />
Пусть есть [[АВЛ-дерево |сбалансированное дерево поиска]]. Все операции в нем делаются за <tex>O(h)</tex>, где <tex>h</tex> — высота дерева, а высота дерева <tex>O</tex> <tex>(\log n)</tex>, где <tex>n</tex> — количество вершин. Пусть необходимо сделать какое-то обновление в этом сбалансированном дереве, например, добавить очередной элемент, но при этом нужно не потерять старое дерево. Возьмем узел, в который нужно добавить нового ребенка. Вместо того чтобы добавлять нового ребенка, скопируем этот узел, к копии добавим нового ребенка, также скопируем все узлы вплоть до корня, из которых достижим первый скопированный узел вместе со всеми указателями. Все вершины, из которых измененный узел не достижим, мы не трогаем. Количество новых узлов всегда будет порядка логарифма. В результате имеем доступ к обоим версиям дерева.<br />
<br />
[[Файл:Копирование пути.png]] <br />
<br />
Так как рассматривается сбалансированное дерево поиска, то поднимая вершину вверх при балансировке, нужно делать копии всех вершин, участвующих во вращениях, у которых изменились ссылки на детей. Таких всегда не более трех, поэтому ассимптотика <tex>O</tex> <tex>( \log n)</tex> не пострадает. Когда балансировка закончится, нужно дойти вверх до корня, делая копии вершин на пути. <br />
<br />
Этот метод хорошо работает на [[Стек|стеке]], двоичных ([[Декартово дерево |декартовых]], [[Красно- черное дерево | красно-черных]]) деревьях. Но в случае преобразования [[Очередь| очереди]] в персистентную операция добавления будет очень дорогой, так как элемент добавляется в хвост очереди, который достижим из всех остальных элементов. Также не выгодно применять этот метод и в случае, когда в структуре данных имеются ссылки на родителя.<br />
<br />
==== Реализация на основе дерева отрезков ====<br />
<br />
На основе дерева отрезков можно построить полностью персистентную структуру данных.<br />
<br />
Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели <tex>L</tex> и <tex>R</tex> для дочерних элементов. Кроме того, заведем массив <tex>roots[]</tex>, в котором <tex>roots[i]</tex> указывает на корень дерева отрезков версии <tex>i</tex><br />
<br />
Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[k]</tex>. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.<br />
<br />
Для того, чтобы изменить элемент в персистентном дереве отрезков, необходимо сделать следующие действия: спустимся в дереве от корня нужной версии до требуемого элемента, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы. При этом необходимо менять указатель на одного из детей на узел, созданный при предыдущем клонировании. После копирования корня, добавим новый корень в конец массива корней.<br />
<br />
[[Файл:persist.png]]<br />
<br />
Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.<br />
<br />
===Метод «толстых» узлов===<br />
Пусть в структуре данных есть узел, в котором нужно сделать изменения (например, на рисунке ниже в первой версии структуры данных в узле <tex>X</tex> есть поле <tex>a=3</tex>, а во второй версии это поле должно быть равно <tex>4</tex>), но при этом нужно сохранить доступ к старой версии узла <tex>X</tex> и не нужно экономить время. В таком случае можно хранить обе версии узла <tex>X</tex> в большом комбинированном узле. <br />
<br />
[[Файл:Метод толстых узлов.png|600px|центр]] <br />
<br />
В примере выше в этом «толстом» узле будет храниться первая версия <tex>V_1</tex>, у которой <tex>a=3</tex> и вторая версия <tex>V_2</tex>, у которой <tex>a=4</tex>. Если далее последуют еще какие-то изменения (например, поле <tex>b</tex> узла <tex>X</tex> станет равно <tex>5</tex>) добавим в толстый узел <tex>X</tex> еще одну версию — <tex>V_3</tex>.<br />
<br />
[[Файл:Список версий1.png|500px|центр]]<br />
<br />
Пусть нужно сделать запрос ко второй версии структуры данных (на рисунке выше это запрос <tex>X.a-?)</tex>. Чтобы сделать этот запрос, нужно зайти в узел <tex>X</tex> и найти в списке версий максимальную версию, которая меньше или равна версии запроса (в примере на рисунке это версия <tex>2</tex>), и в этой версии узла найти значение поля <tex>a</tex> (в примере <tex>a=4</tex>).<br />
Чтобы быстро найти нужную версию в списке версий, хранящихся в «толстом» узле, нужно хранить их в виде дерева. Тогда мы сможем за логарифм найти нужную версию и к ней обратиться. Значит, все операции, которые будут производиться на этой структуре данных, будут домножаться на логарифм от числа версий.<br />
<br />
Структура толстого узла может быть и другой: к каждой вершине можно хранить лог ее изменений, в который записывается версия, в которой произошло изменение, а также само изменение. Такая структура толстого узла рассмотрена ниже, в разделах об общих методах получения частично и полностью персистентных структур данных. Лог может быть организован по-разному. Обычно делают отдельный лог для каждого поля вершины. Когда что-то меняется в вершине, то в лог соответствующего поля записывается это изменение и номер версии, с которой данное изменение произошло. Когда нужно обратиться к старой версии, то двоичным поиском ищут в логе последнее изменение до этой версии и находят нужное значение. <br />
Метод ''fat node'' дает замедление <tex> \log t</tex>, где <tex>t</tex> — число изменений структуры данных; памяти требуется <tex>n+t</tex>, где <tex>n</tex> — число вершин в структуре данных.<br />
<br />
==Преобразование списка в персистентный за O(1)==<br />
Если скомбинировать методы ''path copiyng'' и ''fat node'', то получим универсальный метод, который позволит преобразовывать структуры данных в частично персистентные без дополнительного логарифма памяти и времени.<br />
Пусть мы имеем [[Список| двусвязный список]] и хотим внести в него какое-то изменение, например, добавить узел <tex>Z</tex> между узлами <tex>X</tex> и <tex>Y</tex>, то есть при переходе из версии <tex>1</tex> в версию <tex>2</tex> добавим в двусвязный список узел <tex>Z</tex>. <br />
Применим метод «толстых» узлов. Для этого в узлы <tex>X</tex> и <tex>Y</tex> добавим вторую версию и изменим ссылку, следующую из <tex>X</tex>, и предыдущую перед <tex>Y</tex>, как показано на рисунке.<br />
Этот алгоритм работает следующим образом. Например, текущая первая версия. Идем по списку слева направо от первого узла к узлу <tex>X</tex>, а затем нужно перейти к следующему узлу. В «толстом» узле <tex>X</tex> выбираем нужную (первую) версию и далее следуем по ссылкам.<br />
<br />
[[Файл:Список1.png|600px]]<br />
<br />
Пусть мы хотим добавить еще один элемент между узлами <tex>X</tex> и <tex>Y</tex>, но проблема в том, что у <tex>X</tex> и <tex>Y</tex> уже есть вторая версия, если будем добавлять еще новые версии, то получим дополнительный логарифм времени при обращении к узлу, как в рассмотренном выше методе "толстых" узлов. Поэтому более двух версий добавлять не будем. Используем метод копирования пути. Скопируем узлы <tex>X</tex> и <tex>Y</tex>, начиная с их третьей версии, и свяжем новые узлы с исходным списком. Для этого добавим вторые версии предыдущему перед <tex>X</tex> и последующему после <tex>Y</tex> узлам и свяжем эти узлы соответствующими ссылками. Так все версии остаются доступными.<br />
<br />
[[Файл:Список2.png|700px]]<br />
<br />
Будем называть узел полным, если у него есть вторая версия. Если мы хотим вставить новый элемент в середину списка (на рисунке ниже он обозначен зеленым цветом), мы должны склонировать все полные узлы слева и справа от места добавления нового узла, дойти до ближайших элементов, у которых нет второй версии и добавить им вторую версию. <br />
<br />
[[Файл:Аморанализ.png|700px]]<br />
<br />
Оценим амортизационное время работы такого алгоритма. У нас частично персистентная структура данных, изменять можно только ее последнюю версию. Примем функцию потенциала <tex>\Phi</tex> равной числу полных узлов в последней версии.<br />
# Амортизационная стоимость операции добавления:<br />
#* <tex>a_{empty} = t + \Delta\Phi = O(1) + 2 = O(1), </tex> так как если добавление узла не задевает полных узлов, то узел добавляется за константное время, а количество полных узлов увеличивается на <tex> 2 </tex>.<br />
#* <tex>a_{fat} = t + \Delta\Phi = O(1) + k - k + 2 = O(1), </tex> так как если узел влечёт изменения полных узлов, то сначала потратится <tex> k </tex> времени на копирование этих полных узлов, и в то же время потенциал уменьшится на <tex> k </tex>, а потом увеличится максимум на <tex> 2 </tex>.<br />
# Для любого <tex>i: \Phi_i = O(n),</tex> так как полных узлов не больше общего количества узлов в списке.<br />
<br />
Таким образом, [[Амортизационный анализ#Метод потенциалов|по теореме о методе потенциалов]], амортизационное время работы по добавлению элемента будет <tex>O(1)</tex>.<br />
<br />
==Общий метод построения частично персистентных структур данных==<br />
[[Файл:Частичная персистентность.png|мини|справа|500x300px| Пунктирные линии — обратные ссылки,<br> <tex>X</tex> — исходный узел, актуальный до версии <tex>10</tex>,<br> <br />
<tex>X'</tex> — склонированный узел, актуальный с версии <tex>11</tex>, с пустым списком изменений]]<br />
Применим методы, описанные выше, в общем случае для абстрактной структуры данных. <br />
<br />
Пусть есть структура данных, у каждого узла которой количество указателей на этот узел не больше некоторой константы <tex>P</tex>. При клонировании узла важно знать, откуда на этот узел идут указатели, чтобы затем их переставить. Поэтому необходимо в каждом узле хранить обратные ссылки на те узлы, которые ссылаются на клонируемый узел.<br />
Все узлы будут храниться в виде «толстых» узлов, в которых содержится начальная версия этого узла и список внесенных в него изменений (англ. ''change log'') длиной не больше <tex>2P</tex>.<br />
<br />
Пусть нужно внести изменение в структуру данных в узел <tex>X</tex>. Если есть место в списке изменений, просто вносим туда изменение: записываем номер версии, с которой начинается это изменение, в какое поле узла вносится изменение и какое именно. Если ''change log'' заполнен, то клонируем узел <tex>X</tex>: берем стартовую версию узла, производим в ней все изменения, записанные в ''change log'', добавляем последнее изменение и делаем версию со свободным списком изменений. Затем пройдем по обратным ссылкам от <tex>X</tex> и в ''change log'' каждого узла, ссылающегося на <tex>X</tex>, добавим изменение указателя начиная с этой версии структуры данных с <tex>X</tex> на <tex>X'</tex>.<br />
<br />
Оценим время работы этого алгоритма. Введем функцию потенциала, которая будет равна суммарному размеру всех списков изменений в последней версии. Посмотрим, как меняется суммарный размер списков изменений, когда мы совершаем одно изменение. Если ''change log'' был не полный, то мы просто добавляем туда один элемент, потенциал увеличится на единицу.<br />
Если ''change log'' был полный, то потенциал уменьшается на его размер, так как мы склонировали узел с пустым списком изменений. После этого мы пошли по обратным ссылкам (их было <tex>P</tex> штук) и добавили в <tex>P</tex> узлов по одному значению. Таким образом амортизированное время работы будет <tex>O(1)</tex>.<br />
<br />
==Получение полностью персистентных структур данных==<br />
Для полностью персистентных структур данных применить описанный выше метод преобразования не получится, так как история создания версий не линейна и нельзя отсортировать изменения по версиям, как в частично персистентных структурах данных. <br />
Пусть мы храним историю изменения версий в виде дерева. Сделаем[[Обход в глубину, цвета вершин| обход этого дерева в глубину]]. В порядке этого обхода запишем, когда мы входим, а когда выходим из каждой версии. Эта последовательность действий полностью задает дерево, сделаем из нее список. Когда после какой-то версии (на рисунке ниже это версия <tex>6</tex>) добавляется новая версия структуры данных (на рисунке версия <tex>8</tex>), мы вставляем два элемента в список (на рисунке это <tex>+8</tex> и <tex>-8</tex>) после входа, но до выхода из той версии, когда произошло изменение (то есть между <br />
элементами <tex>+6</tex> и <tex>-6</tex>). Первый элемент вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.<br />
<br />
[[Файл:Полная персистентность.png]] <br />
<br />
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex>\mathrm{insert After(p,q})</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>\mathrm{order(p,q)}</tex> (должен уметь отвечать на запросы вида "<tex>p</tex> лежит в этом списке до <tex>q</tex>"). <tex>\mathrm{order(p,q)}</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <tex>0</tex> иначе. Это список с поддержкой запроса о порядке [[List order maintenance|''List Order Maintenance'']], который обе эти операции делает за <tex>O(1)</tex>.<br />
<br />
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''. <br />
<br />
Когда есть запрос к какой-то версии, то нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную. Например, если приходит запрос к версии <tex>6</tex> на рисунке выше, то мы видим, что она в списке версий лежит после входа, но до выхода в версии <tex>1</tex>, <tex>2</tex> и <tex>4</tex>. Необходимо найти наибольшую из них. Список ''List Order Maintenance'' позволяет делать это за <tex>O(1)</tex> с помощью операции <tex>\mathrm{order(p,q)}</tex>. В примере это версия <tex>4</tex>. Так как ''change log'' каждого узла имеет константный размер, то поиск нужной версии в нем происходит за <tex>O(1)</tex>. <br />
<br />
В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле. <br />
<br />
[[Файл:Полностью персистентные сд.png|900x700px]]<br />
<br />
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй {{---}} после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.<br />
<br />
Оценим амортизационное время работы этого алгоритма. Введем функцию потенциала, равную числу полных узлов. Когда узел раздваивается, функция потенциала уменьшается на единицу, затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит, амортизационное время работы — <tex>O(1)</tex>.<br />
<br />
==Использование персистентных структур данных для решения геометрических задач==<br />
<br />
Персистентные структуры данных используются при решении геометрических задач. Примером может служить [[Локализация в ППЛГ методом полос (персистентные деревья)|Point location problem]] — задача о местоположении точки. Задачи такого рода решаются в ''offline'' и ''online''. В ''offline''-задачах все запросы даны заранее и можно обрабатывать их одновременно. В ''online''-задачах следующий запрос можно узнать только после того, как найден ответ на предыдущий.<br />
<br />
При решении ''offline''-задачи данный планарный граф разбивается на полосы вертикальными прямыми, проходящими через вершины многоугольников. Затем в этих полосах при помощи техники заметающей прямой ''(sweep line)'' ищется местоположение точки-запроса. При переходе из одной полосы в другую изменяется [[Дерево поиска, наивная реализация|сбалансированное дерево поиска]]. Если использовать частично персистентную структуру данных, то для каждой полосы будет своя версия дерева и сохранится возможность делать к ней запросы. Тогда ''Point location problem'' может быть решена в ''online''.<br />
<br />
== См. также ==<br />
* [[Персистентный стек]]<br />
* [[Персистентная очередь]]<br />
* [[Персистентный дек]]<br />
* [[List order maintance]]<br />
<br />
== Источники информации ==<br />
*[https://www.lektorium.tv/lecture/14321/ Дополнительные главы алгоритмов. Лекции Андрея Станкевича]<br />
*[http://logic.pdmi.ras.ru/csclub/node/2734/ Персистентные структуры данных. Лекции Павла Маврина]<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Персистентные структуры данных]]</div>Golikovnikhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D1%8B_%D1%81_%D0%BC%D0%B0%D0%B3%D0%B0%D0%B7%D0%B8%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D1%8C%D1%8E&diff=71314Автоматы с магазинной памятью2019-05-27T08:41:55Z<p>Golikovnik: /* Диаграммы переходов */</p>
<hr />
<div>==Недетерминированный автомат с магазинной памятью==<br />
{{Определение<br />
|definition= '''Автомат с магазинной памятью''' (автомат со стеком, англ. ''pushdown automaton'') {{---}} это набор <tex>A=\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow 2^{Q \times \Gamma^*}\rangle</tex>, где<br />
*<tex>\Sigma</tex> {{---}} входной алфавит на ленте,<br />
*<tex>\Gamma</tex> {{---}} стековый алфавит,<br />
*<tex>Q</tex> {{---}} множество состояний автомата,<br />
*<tex>s</tex> {{---}} стартовое состояние автомата,<br />
*<tex>T</tex> {{---}} множество допускающих состояний автомата,<br />
*<tex>z_0</tex> {{---}} маркер дна стека,<br />
*<tex>\delta</tex> {{---}} функция переходов.<br />
}}<br />
<br />
[[Изображение:PDAsmall.jpg|left|Рис. 1. Автомат с магазинной памятью]]<br />
С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> {{---}} текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека. <br />
<br />
Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Детерминированные автоматы с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами|детерминированные и недетерминированные автоматы со стеком неэквивалентны]].<br />
<br style="clear:both" /><br />
<br />
==Диаграммы переходов==<br />
<div class="tleft" style="clear:none">[[Файл:Transition1.png|400px|thumb|Рис. 2. Переход: с {{---}} символ, прочитанный с ленты; A {{---}} символ, вынутый из стека; <tex>\alpha</tex> {{---}} строка, помещаемая в стек.]]</div><br />
<div class="tleft" style="clear:none">[[Файл:Transition2.png|400px|thumb|Рис. 3. Переход по любому стековому символу, он же возвращается в стек.]]</div><br />
<div class="tleft" style="clear:none">[[Файл:Transition3.png|400px|thumb|Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.]]</div><br />
<br style="clear:both" /><br />
По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность|автоматом с допуском по пустому стеку]]). То есть, для <tex>\forall q \in Q,\forall c \in \Sigma \cup \{\varepsilon\} \Rightarrow \delta(q, c, z_0) \ni \langle p, \alpha \rangle </tex>, где <tex>p \in Q, \alpha \in \Gamma^*, \alpha = \alpha_1z_0</tex>.<br />
<br />
==Основные определения==<br />
{{Определение<br />
|definition=<br />
'''Мгновенное описание''' (англ. ''instantaneous descriptions'') {{---}} это набор <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> {{---}} текущее состояние, <tex>\alpha</tex> {{---}} остаток строки, <tex>\gamma</tex> {{---}} содержимое стека.<br />
}}<br />
{{Определение<br />
|definition=<br />
'''Переход за один шаг''' (англ. ''the "goes-to" relation'') обозначается как <tex>\langle q, \alpha, \gamma \rangle \vdash \langle r, \beta, \xi \rangle</tex>, где <tex>\alpha = c\beta</tex> (возможно, <tex>c=\varepsilon</tex>), <tex>\gamma = \chi\gamma', \xi = \eta\gamma'</tex>, <tex>\langle r, \eta \rangle \in \delta(q, c, \chi)</tex>.<br />
}}<br />
{{Определение<br />
|definition= '''Язык автомата с магазинной памятью''' (англ. ''language of a pushdown automaton'') <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>.<br />
}}<br />
<br />
==Пример недетерминированного МП-автомата==<br />
[[Изображение:PDAexample.png|300px|thumb|left|Рис. 5. Недетерминированный МП-автомат для языка <tex>0^n1^n</tex>.]]<br style="clear:both" /><br />
<br />
== См. также ==<br />
* [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]<br />
* [[ДМП-автоматы и неоднозначность]]<br />
<br />
== Источники информации ==<br />
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: МП-автоматы]]</div>Golikovnik