New texs

1 files changed, 158 insertions, 0 deletions

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}