From 7b51d34e8db14ddffba4ff006d36fd61a6f6363d Mon Sep 17 00:00:00 2001 From: syn Date: Fri, 17 Apr 2020 22:00:51 +0300 Subject: New texs --- alg/alg-1.tex | 56 ++++++++++++++++++-- prog/prog-1.tex | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 209 insertions(+), 5 deletions(-) create mode 100644 prog/prog-1.tex diff --git a/alg/alg-1.tex b/alg/alg-1.tex index 9587e4b..e6b2058 100644 --- a/alg/alg-1.tex +++ b/alg/alg-1.tex @@ -13,6 +13,25 @@ \dmquestion{1} + $\ord(g) = \ord(g^{-1})$, потому что: + + {\narrower + $\ord(g^{-1}) \leqslant \ord(g)$: + \[ + (g^{-1})^{\ord(g)} = + e(g^{-1})^{\ord(g)} =\\ + (g)^{\ord(g)} (g^{-1})^{\ord(g)} = + (gg^{-1})^{\ord(g)} = e + \] + + Аналогично, $\ord(g^{-1}) \geqslant \ord(g)$. + + } + + Поэтому, $\ord(g^k) = \ord(g^{-k})$, + поэтому дальше будем считать, что $k \geqslant 0$. + \medskip\medskip + Докажем, что если $\ord(g) = m$, то \[ n \divby m \Leftrightarrow g^n = e @@ -51,23 +70,50 @@ \] Возьмем какой-то элемент $h_0 \in H$ так, что $h_0 \neq e$. - Построим последовательность $\{h_i\}$ хитрым образом, докажем, что она конечна и последний ее элемент $h_n$ порождает $H$. + Теперь построим некоторую последовательность $\{h_i\}$, + докажем, что она конечна и последний ее элемент $h_n$ порождает $H$. + \medskip\medskip Пусть $\cycle{h_i} \neq H$ (иначе $H = \cycle{h_i}$ и все доказано), тогда возьмем какой-нибудь элемент $h$ из $H$, но не из $\cycle{h_i}$. - Так как уравнение \[ x \deg(h) + y \deg(h_i) = \gcd(\deg(h), \deg(h_i)) \] - всегда имеет решение $(x, y)$ в целых числах, то $g^{\gcd(\deg(h),\ \deg(h_i))}$ обязан лежать в $H$. + всегда имеет решение $(x, y)$ в целых числах, то $g^{\gcd(\deg(h),\ \deg(h_i))} \in H$. Тогда пусть по построению $h_{i + 1} = g^{\gcd(\deg(h),\ \deg(h_i))}$. Заметим, что $\cycle{h_{i + 1}} \in H$, поскольку $H$ - группа. - Очевидно, что $\gcd(\deg(h), \ \deg(h_i)) \leqslant \deg(h_i)$. Но так как $h \notin \cycle{h_i}$, то $\deg(h)\ \nodivby \deg(h_i)$, а значит $\gcd(\deg(h), \ \deg(h_i)) < \deg(h_i)$. + Очевидно, что \[\gcd(\deg(h), \ \deg(h_i)) \leqslant \deg(h_i).\] + + Но так как $h \notin \cycle{h_i}$, то $\deg(h)\ \nodivby \deg(h_i)$, а значит $\gcd(\deg(h), \ \deg(h_i)) < \deg(h_i)$. - Значит, $h_i > h_{i + 1}$, поэтому $|\{h_n\}| < \infty$. Значит, в какой-то момент перестанет выполняться предположение о том, что $\cycle{h_i} \neq H$, что и требовалось. + Поэтому, $\deg(h_i) > \deg(h_{i + 1})$, значит порядок элементов в последовательности строго убывает + и ограничен 1, значит $|\{h_n\}| < \infty$. + Значит, в какой-то момент перестанет выполняться предположение о том, что $\cycle{h_i} \neq H$, что и требовалось. \dmquestion{4} + + В этой задаче я считаю, что + \[ + (\sigma \circ \tau) (i) = \sigma(\tau(i)) + \] + + Левый смежный класс по $H$ -- это все перестановки, переставляющие единичку к какое-то одно одинаковое место. Формально, пусть $g \in S_n, \ g(1) = k$, тогда + \[ + gH = \{\sigma \suchthat \sigma(1) = k\} + \] + + Докажем включение $\supseteq$, а равенство будет следовать из равномощности левой и правой частей: + \[ + \frac{|G|}{|\{\sigma \suchthat \sigma(1) = k\}|} = n = \frac{|G|}{|H|} = \frac{|G|}{|gH|} + \] + + Итак, зафиксировав $g$, мы хотим показать, что $\forall \sigma \suchthat \sigma(1) = k$ найдется такая $\tau \in H$, что $g \tau = \sigma$. То есть $\tau = g^{-1}\sigma$. То есть мы хотим просто доказать, что $g^{-1}\sigma \in H$, то есть $(g^{-1}\sigma)(1) = 1$. Но по условию, $g^{-1}(\sigma(1)) = g^{-1}(k) = 1$, что и требовалось. + + Применяя абсолютно аналогичные рассуждения, получаем, что правый смежный класс по $H$ -- все перестановки, отправляющие какое-то одно число в единичку: + \[ + g^{-1}(1) = k \Rightarrow Hg = \{\sigma \suchthat \sigma^{-1}(1) = k\} + \] \end{document} diff --git a/prog/prog-1.tex b/prog/prog-1.tex new file mode 100644 index 0000000..9669425 --- /dev/null +++ b/prog/prog-1.tex @@ -0,0 +1,158 @@ +\documentclass[11pt]{article} +\usepackage{../intro} + +\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}} +\rhead{\color{gray} \small \textit{аисд-1}} +\title{Алгоритмы и структуры данных 1} + +\usepackage{ctable} + +% -- Here bet dragons -- +\begin{document} +\maketitle +\drawcat{50pt} +\clearpage + +\newcommand{\funcname}[1]{ + {\incons + \textbf{#1}} +} + +\newcommand{\len}[1]{\mathrm{len}\!\left( #1 \right)} + +\dmquestion{1} + + Понятно, что \funcname{Insert} и \funcname{Increment} работают за $O(1)$ всегда. + + Если в \funcname{RemoveLargeElements} мы попадаем в цикл, то все работает за $O(\mathrm{len}(list))$, поскольку мы пробегаем весь лист и делаем что-то константное (подразумевается, что удаление работает за константу), что и является худшим случаем. + +\medskip + + Докажем, что амортизированно \funcname{RemoveLargeElements} работает за $O(1)$. + + Давайте в \funcname{Insert} и \funcname{Increment} класть в банк по $20$ монеток (функции при этом все еще будут работать за константу). + + Когда мы вызовем \funcname{RemoveLargeElements}, мы проверим самое первое условие. Если оно не выполнено, мы сразу вернемся и не потратим монеток. Если же оно выполнено, то мы имеем следующее неравенство: + \begin{align*} + maxItem > \left\lceil \frac{\mathrm{len}(list)}{3} \right\rceil\\ + maxItem \cdot 3 + 3 > \mathrm{len}(list) + \end{align*} + + Тогда за максимальный элемент мы инкрементировали $\frac{maxItem - 1}{2}$ раз, а значит, в банке за этот элемент лежит + \[ + 20 + \frac{maxItem - 1}{2} \cdot 20 = 10 + maxItem \cdot 10 + \] монет. + + Их, конечно же, больше, чем $\mathrm{len}(list)$ штук (даже больше, чем в $3$ раза больше), поэтому нам их хватит, чтобы оплатить цикл (на самом деле монет там лежит $O(\mathrm{len}(list))$, поэтому выбрав подходящее количество монет вместо $20$, мы можем оплатить любой линейный цикл). Заметим, что этот самый большой элемент сразу же и удалится, поэтому мы можем смело тратить эти монеты и мы не трогали монеты, отданные за другие элементы. + + Поэтому $n$ операций над этой структурой работают за $O(n)$ по времени. + +\dmquestion{2} + + Примерно алгоритм: будем использовать два стека для ``симуляции очереди'': один стек растет ``в одну'' сторону, а другой в другую (назовем эти два стека главными). Середина очереди в среднем будет на стыке между двумя стеками, а если нам надо будет сделать \funcname{pop\_*} с той стороны, с которой стек пуст, мы за $O(\mathrm{len}(queue))$ перекинем примерно половину элементов в пустой стек с помощью третьего стека (назовем его вспомогательным). Во все остальное время третий стек будет пустым. + \medskip\medskip\medskip + + Будем хранить банк монеток, а при каждом \funcname{push\_*} класть в банк $3$ монетки. Мне нужен будет такой инвариант: в банке всегда есть столько монеток: + \[ + 3 \cdot \max( \len{main\_stack_1}, \len{main\_stack_2} ) + \] + + Понятно, что после \funcname{push\_*} такой инвариант сохраняется. Теперь покажем, что он сохраняется и для \funcname{pop\_*}. + + Если нам надо сделать \funcname{pop\_*} с той стороны, с которой главный стек еще не пуст, то просто запомним для этого стека \funcname{top()}, сделаем \funcname{pop()} и вернем запомненное значение. Количество монет в банке не поменялось. + + Теперь если нам надо сделать \funcname{pop\_*} с той стороны, с которой стек пуст, + то перекинем примерно половину элементов в пустой стек из непустого. + Назовем пустой главный стек $s_e$, а непустой - $s_f$. Тогда, так как $s_e$ пуст, + то по инварианту в банке не меньше $3\cdot \len{s_f}$ монеток. + Для удобства, если $\len{s_f}$ нечетно, то засунем в $s_f$ фиктивный элемент. + + Итак, мы хотим перекинуть ровно половину элементов из непустого стека в пустой, сохранив порядок. сделаем это с помощью третьего стека. + + Изначально у нас три стека: + + \begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|} + \hline + 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ + \hline + + \hline + &&&&&&&\\ + \hline + + \hline + &&&&&&&\\ + \hline + \end{tabular} + \medskip + + Потратим $\frac{1}{2}\cdot \len{s_f}$ монеток + + \begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|} + \hline + 1 & 2 & 3 & 4 & & & &\\ + \hline + + \hline + &&&&&&&\\ + \hline + + \hline + 8 & 7 & 6 & 5 & &&&\\ + \hline + \end{tabular} + \medskip + + И ещё $\frac{1}{2}\cdot \len{s_f}$ монеток + + \begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|} + \hline + &&& & & & &\\ + \hline + + \hline + 4 & 3 & 2 & 1 &&&&\\ + \hline + + \hline + 8 & 7 & 6 & 5 &&&&\\ + \hline + \end{tabular} + \medskip + + В последний раз $\frac{1}{2}\cdot \len{s_f}$ монеток + + \begin{tabular}[t]{|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|p{5pt}|} + \hline + 5 & 6 & 7 & 8 & & & &\\ + \hline + + \hline + 4 & 3 & 2 & 1 &&&&\\ + \hline + + \hline + &&& &&&&\\ + \hline + \end{tabular} + \medskip + + Мы потратили $\frac{3}{2} \len{s_f}$ монет и осталось столько же. Но так как теперь длина каждого из кусков в два раза меньше, то инвариант сохранился. + + Таким образом, \funcname{pop\_*} тоже амортизированно выполняется за $O(1)$. + +\clearpage + +\dmquestion{3} + + Посчитаем для данной длины $n$ максимальную возможную стоимость $k$ бинпоиска на этом массиве. + То есть при всевозможных входных данных длины $n$ мы запустим бинпоиск, который будет работать $k_i$ шагов и возьмем $k = \sup k_i$. + Понятно, что $k = O(\log n)$ + { + \color{gray} + здесь надо доказать асимптотику бинпоиска, но я притворюсь, что это мы уже знаем. + } + + Теперь выдадим каждому элементу $k$ монеток и на каждый бинпоиск будем тратить монетки, принадлежащие элементу. который мы нашли. Нам всегда хватит столько монеток, потому что бинпоиск на массиве меньшего размера, очевидно, занимает не больше операций, чем на массиве большего размера. Тогда все вместе будет работать за $n * k = O(n \log n)$ + +\end{document} -- cgit v1.2.1-18-gbd029