\documentclass[12pt]{article}

%Конспект третий лекции
%Авторы: Михаил Никанов, Ольга Черникова

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
%\usepackage{enumerate}
%\usepackage{hologo}
%\usepackage{color}
%\usepackage{picture}

\linespread{0.95}


\sloppy
\voffset=-20mm
\textheight=220mm
\hoffset=-15mm
\textwidth=170mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}

\newenvironment{MyTabbing}{
\t\bgroup
%\vspace*{-\baselineskip}
\begin{tabbing}
aaaa\=aaaa\=aaaa\=aaaa\kill
}{
\end{tabbing}
\t\egroup
}

\begin{document}

\begin{center}
  {\Large \bf Лекция по алгоритмам \t{\#3}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: преобразование операций} \\
  \vspace{0.5em}
  {\Large 16 сентября} \\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\vspace{1em}
\tableofcontents
\pagebreak


\section{Доказательства нижней границы времени работы сортировок произвольных объектов.}

Докажем, что любая сортировка произвольных объектов сделает не меньше $n\log n$ сравнений. Тогда асимптотика сортировки будет $\Omega (n \log n)$.\\
Пусть мы сделали $k \le n \log n$ сравнений. Рассмотрим строчку $01010011101011100\ldots$, где 1 - больше, 0 - меньше, для каждого из $k$ сравнений. Мы можем получить не более $2^k$ различных строк длины $k$, т.к. результат каждого сравнения увеличивает количество вариантов не более чем в 2 раза. Таким образом $2^k < n!$, а значит найдется два различных входа, для которых соответствующие им строчки совпадут. Выходит, что $k$ должен быть не меньше $n \log n$, а сортировка имеет асимптотику $\Omega (n \log n)$.

\section{Структуры данных}
Мы знаем: стек, очередь, хеш-таблицу, сортировку, бинарный поиск, списки, вектора с удвоением.\\
\linebreak
Напишем небольшой язык программирования.\\
Нам нужно уметь:
\begin{enumerate}
  \item Считать от переменной значение val[variable].
  \item Разбирать выражения. ($1+3*4 - (3+4)*2$)
  \item if, for... 
  \item functions... Хотя кому это надо?
\end{enumerate}

\subsection {Переменные и значения}
Воспользуемся хеш-таблицей. Единственное, чему нам надо научиться - преобразовывать название переменной(строчку) в число. Заведем хеш-функцию:
String -> (hash). $Hash(string) = 0\ldots 2^{64} = \sum\limits_{i}{s_i * 179^i}$\\
\vspace{0.3em}

\subsection {Разбор выражения стеком за O(n)}
Пусть есть несколько операций $(+, -, *, /)$ числа и переменные (последовательности цифр, букв и подчеркиваний). Также должен быть задан приоритет на операции. В случае равного приоритета предполагается, что выражение левоассоциативно. Разобьем исходную строчку на лексемы:\\
 $\cdots  + \cdots  * \cdots$ \\
Начнем вычислять. Воспользуемся двумя стеками: значения и операции. Лексемы добавляем в значения, операции - в операции. При очередной операции смотрим на последнюю операцию в стеке. Если у нее приоритет больше, сразу выполним. 
Т.е. нужно достать из стека операций операцию, из стека значений 2 переменные, посчитать, и добавить результат в стек значений. Текущую операцию в любом случае добавляем в стек. Когда выражение закончится, в стеке все еще могут быть какие-то операции и лексемы. Выполним их в обратном порядке. \\
\vspace{0.15em}
Усовершенствуем алгоритм для выражения со скобками. Пусть мы дошли до открывающейся скобки. Добавим ее. Теперь, когда мы считаем операции, делаем это только до скобки. Когда встретим закрывающую скобку, выполняем все до первый открывающийся скобки, и удаляем ее. Для удобства можно добавить открывающую скобку в начало и закрывающую в конец всего выражения. Заметим, что если после завершения работы алгоритма что-то осталось в стеке, то исходное выражение не корректно. Таким образом, выражение невозможно посчитать тогда, когда:
\begin{enumerate}
  \item Идут несколько операций подряд (++). Унарный минус обрабатывается отдельно.
  \item Несколько лексем идут подряд.
  \item Для какой-то закрывающейся скобки не нашлось открывающейся.
  \item В конце стек операций не пуст.
\end{enumerate}
\vspace{0.4em}
Как считывать лексему?
\begin{enumerate}
  \item пробел: пропускаем
  \item цифра: пока цифра - лексема
  \item операторы: пропускаем.
  \item Унарный минус приходит только тогда, когда наш алгоритм ожидает оператор. После закрывающей скобки наш алгоритм ожидает оператор.
\end{enumerate}

\subsection{if, for...}
Мы то знаем, что все конструкции подобного вида, это на самом деле нагромождение всевозможных выражений. Так что по большому случаю нам нужно:
\begin{enumerate}
  \item Проверить скобочную последовательности на корректность. ПСП - это то, что можно получить удаляя значения из выражения. Если скобки одного типа, то достаточно считать баланс. Если несколько видов, то эта задача решается стеком, в который будем добавлять открывающиеся скобки и пытаться удалить последнюю, по приходу закрывающей.
  \item Для каждой скобки найти позицию парной. Для этого храним в стеке и скобку и позицию. Теперь, когда мы удаляем очередную скобку из стека, мы знаем позицию и открывающей и закрывающей скобки.
  \item Осталось обрабатывать работу с переменными. Старое решение с хеш-таблицей тоже подходит, но проще взять все запросы (на присвоение), отсортировать все имена переменных и хранить вместе с ними их значения. Тогда несколько подряд идущих имен изменяют значение у одной переменной. Единственный тонкий момент - это фиксированный порядок выполнения операций. Для этого, при присвоении текущей переменной - другую, придется найти ее бинпоиском и обновить до актуального состояния. Преимущество данного алгоритма в том, что он детерминирован, и мы не используем дополнительную память.\\
\end{enumerate}

\section{Теория. Преобразование операций.}

{.}

Merge(A, B) = (A объединить B)

Add(A, x) = (A объединить с {x})

\subsection{ Merge $\to$ Add}

Дано: Мультимножество. Умеем сливать две структуры. Хотим научиться добавлять элемент.

Создаем  множество, которое состоит из одного элемента, который хотим добавить. Сливаем два множества. 
Время работы Add = Merge


\subsection{Add $\to$ Merge}


Дано: Мультимножество. Умеем добавлять элемент. Хотим научиться объединять два мультимножества.

\begin{MyTabbing}
Merge(A, B) считаем, что в А элементов меньше, чем в В.  Size(A) <= Size(B)\\
\> for x in A \\
\>\> Add(B, x) \\
\>return B \\
\end{MyTabbing}

Суммарное время работы: $\sum Merge \le O(N\log N) Add$, где N общее количество элементов. 

Рассмотрим элемент x. Каждый раз, когда к нему применяют Add, он оказывает в множестве хотя бы в два раза большем. Значит, каждый элемент будет рассмотрен не более $\log N$ раз. 

\subsection{Find $\to$ Delete}

Дано: Множество. Умеем находить элемент. Хотим научиться удалять. 

Для каждого элемента множества будем хранить флаг, удален элемент или нет. 
<val, isDeleted>

\begin{MyTabbing}
Delete(x):\\
\>Find(x).isDeleted = 1\\
\end{MyTabbing}

Время работы: Delete = Find

\subsection{build, get $\to$ Merge $\to$ Add}

Дано: Множество. Необходимо отвечать на запросы, которые не меняют элементы. Умеем из элементов создать структуру. Хотим научиться сливать два множества и добавлять элемент. 

Пусть наше множество состоит из N элементов. Тогда представим наше множество в виде $\log N$  множеств. 
$N = \sum^{\log N}_{i = 1} 2^{k_i}$ 

(N = 7) $\to$ (1) + (2) + (4) 

Теперь, что бы ответить на запрос в таком представление, нужно ответить на запрос в каждом кусочке. 

\begin{MyTabbing}
NewGet()\\
\>for i = 1... $\log N$\\
\>\>get($A_i$)\\
\end{MyTabbing}

Время работы NewGet = $\log N$ get

\begin{MyTabbing}
Merge()\\
\> while существует $size(A_i) == size(A_j)$ \\
\>\>Build($A_i$, $A_j$)\\
\end{MyTabbing}

Время работы Merge $\le Build(N\log N)$, так как каждый элемент будет участвовать в построение максимум $\log N$ раз, так как он каждый раз переезжает в более большое множество. 

\subsection{Итог}

Мы умеем делать:

\begin{enumerate}
\item Add $\to$ Merge
\item Merge $\to$ Add
\item Find  $\to$ Delete
\item build, get  $\to$ Add
\end{enumerate}

{\bf Замечание:} 
    Find $\to$ Delete используется в хэш таблице с открытой адресацией. 

\section{Хеш-таблица с открытой адресацией}

Каждому элементу сопоставляем ячейку в массиве. 
Если на этом месте уже что-то написано, то ищем ближайшую свободную справа. 
Элементы не удаляем явно, а ставим пометку, что он удален. 

$2n \le M$, где M - размер хэштабдицы, а n - количество элементов в структуре. 

\begin{MyTabbing}
Index(x) \\
\>i = x\%M \\
\>while(ht[i] != x and !empty[i]) \\
\>\>i = (i + 1)\%M \\
\> return i \\
\end{MyTabbing}

Когда элементов в таблице, в том числе удаленных, стало больше, чем свободных ячеек, перестроим таблицу.

\end{document}
