\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Madrid}       % or try default, Darmstadt, Warsaw, ...
  \usecolortheme{default} % or try albatross, beaver, crane, ...
  \usefonttheme{professionalfonts}    % or try default, structurebold, ...
  \setbeamertemplate{navigation symbols}{}
  \setbeamertemplate{caption}[numbered]
}

\usepackage[russian]{babel}
\usepackage[english]{babel}
\usepackage[russian]{babel}
\usepackage{chemfig}
\usepackage[version=3]{mhchem}
\usepackage[unicode, pdftex]{hyperref}

% Строчки выше можно вообще не трогать

% Эти строчки позволяют использовать окружения для определений свойств и т.д. на русском языке
\newtheorem{df}{Определение}
\newtheorem{property}{Свойство}
\newtheorem{ex}{Пример}
\newtheorem{thm}{Теорема}

% On Overleaf, these lines give you sharper preview images.
% You might want to `comment them out before you export, though.
\usepackage{pgfpages}
\pgfpagesuselayout{resize to}[%
  physical paper width=8in, physical paper height=6in]

% Название доклада. Можно стереть и указать свое
\title[Алгоритмы перебора комбинаторных объектов]{Алгоритмы перебора комбинаторных объектов}

% Имя автора доклада
% Первый аргумент отвечает за имя, появляющееся в нижней строке
\author[Наумов Н.А.]{Наумов~Н.~А. \\nanaumov@edu.hse.ru}
% Дата выступления
\date{25 марта 2021 г.}
\begin{document}
\begin{frame}
  \titlepage
\end{frame}
\begin{frame}{Напоминание}
    \begin{df}
        Комбинаторные объекты (англ. combinatorial objects) — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
    \end{df}


    \begin{df}
        Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются упорядоченными (англ. ordered).
    \end{df}
\end{frame}

\begin{frame}{Примеры комбинаторных объектов}
    \begin{itemize}
        \item Битовые вектора (последовательности нулей и единиц)
        \item Перестановки -  упорядоченный набор чисел 1,2,…,n, обычно трактуемый как биекция на множестве {1,2,…,n}, которая числу i ставит соответствие i-й элемент из набора.
        \item Размещение из n по k ($A^{k}_n$) — упорядоченный набор из k различных элементов некоторого n-элементного множества.
        \item Сочетания из n по k ($C^{k}_{n}$) — набор k элементов, выбранных из данных n элементов.
        \item $n!$ представление числа - представление целого неотрицательного числа m в виде последовательности ($d_{0}, d_{1}, ... , d_{n-1}$), такая что $0 \leq d_{i} \leq i$, $i \in [0, n-1]$ и \newline \begin{center}
            $m = d_{n-1}\cdot(n-1)! + d_{n-2}\cdot(n-2)! + ... + d_{0}\cdot(0)!$
        \end{center}
    \end{itemize}
\end{frame}

\begin{frame}{Алгоритм нахождения $n!$ представления числа}
Введем неформальное описание алгоритма нахождения $n!$-ого представления числа
\begin{itemize}
    \item Шаг 0. $d_{0} = 0; q_{0} = m$
    \item Шаг 1. Делим $q_{0}$ на 2, находим остаток от деления на $d_1$ и частное от деления $q_1$ = $\lfloor q_{0}/2 \rfloor$. При этом имеем $0 \leq d_1 < 2$
    \item Шаг $i$. Делим $q_{i-1}$ на $i+1$, полагаем $d_i$ - остаток от деления $\lfloor q_{i-1}/{i+1} \rfloor$. При этом $0 \leq d_i < i+1$
    \item Шаг n-1. На заключительном шаге находим остаток $d_{n-1}$ от деления $q_{n-2}$ на $n$ и частное $q_{n-2}$ на $n$
\end{itemize}
\end{frame}
\begin{frame}{Реализация алгоритма $n!$ представления числа}

\includegraphics[width = 300, height = 200]{1.png}

\end{frame}

\begin{frame}{Перестановки в лексикографическом порядке}
    Введем неформальное описание алгоритма.
    \begin{itemize}
        \item Создаем массив размерности $n+1$, в котором будем проводить изменения
        \item В $a_1, a_2, ..., a_n$ записываем текущую пораздаемую перестановку из $S_n$
        \item Значение $a_0$ не изменяется и равно 0, поэтому всегда справедливо, что $a_0 < a_1$.
        \item Это неравенство гарантирует нахождение самой правой позиции $i \geq 0$ такой, что $a_i < a_{i+1}$.
        \item Алгоритм заканчивает работу, когда i = 0;
    \end{itemize}
\end{frame}

\begin{frame}{Реализация алгоритма генерации перестановок}
    \includegraphics[width = 270, height = 230]{2.png}
\end{frame}

\begin{frame}{Создание всех бинарных векторов заданной длины $n$}
Введем неформальное описание алгоритма создания всех бинарных векторов заданной длины
    \begin{itemize}
        \item Создаем вектор длины ($b_n, b_{n-1}, ..., b_0$), все элементы приравниваем к 0
        \item Просматриваем вектор b справа налево, ищем самую правую позицию $i$, такую, что $b_i$ = 0.
        \item Запишем в эту $i$-ую позицию 1, а все элементы $b_j, j < i$, стоящие справа от $b_i$, полагаем равными 0.
        \item $b_n$ изменяется только на самой последней итерации и становится равным единице.
        \item Когда $b_n$ = 1, то алгоритм заканчивает работу
    \end{itemize}
\end{frame}

\begin{frame}{Реализация алгоритма создания бинарных векторов длины $n$}
    \includegraphics[width = 300, height = 200]{3.png}
\end{frame}
\begin{frame}{Создание всех сочетаний из $n$ по $k$}
Введем неформальное описание алгоритма создания всех сочетаний $n$ по $k$
    \begin{itemize}
        \item Создаем массив длины n и заполняем его элементами таким образом, что $a_0 = 1, a_1 = 2,..., a_{n-1} = n$
        \item Пока у нас будет существовать следующее сочитание, будем его выводить
        \item Определим, как понять, существует ли следующее сочетание
        \begin{itemize}
            \item Просматривая сочетания справа налево, находим первый элемент, который можно увеличить. Этот элемент увеличиваем (берем следующий возможный элемент), а все элементы после
него, заменяем на натуральные числа, следующие за новым элементом.
        \end{itemize}
    \end{itemize}
\end{frame}
\begin{frame}{Алгоритм создания всех сочетаний из $n$ по $k$}
    \includegraphics[width = 300, height = 200]{4.png}
\end{frame}
\begin{frame}{Дополнительная функция}
    \includegraphics[width = 300, height = 170]{5.png}
\end{frame}
\begin{frame}{Создание всех размещений из $n$ по $k$}
    Введем неформальное описание алгоритма создания всех размещений из $n$ по $k$
    \begin{itemize}
        \item Создаем массив длины n и заполняем его элементами таким образом, что $a_0 = 1, a_1 = 2,..., a_{n-1} = n$
        \item Пока у нас будет существовать следующее размещение, будем его выводить
        \item Определим, как понять, существует ли следующее размещение
        \begin{itemize}
            \item Для начала, нужно найти первый элемент справа (Обозначим его $a_j$), который меньше следующего за ним ($a_i < a_{i+1}$)
            \item Если таких элементов нет, то возможные размещения закончились
            \item Иначе мы ищем первый элемент в множестве, который меньше чем ${a_j}$
            \item После нахождения меняем их местами и сортируем оставшуюся часть последовательности
            \item Выполняем эти действия до тех пор, пока $(j > k-1)$
        \end{itemize}
    \end{itemize}
\end{frame}
\begin{frame}{Алгоритм создания всех размещений из $n$ по $k$}
    \includegraphics[width = 300, height = 200]{6.png}
\end{frame}
\begin{frame}{Дополнительная функция}
    \includegraphics[width = 300, height = 200]{7.png}
\end{frame}

\begin{frame}{Создание всех правильных скобочных последовательностей длины $2 \cdot n$}
    Введем неформальное описание алгоритма поиска всех скобочных правильных последовательностей
    \begin{itemize}
        \item Если количество открытых скобок меньше чем $n$, то вызываем функцию рекурсивно, увеличивая количество открытых скобок и добавляя в строку открытую скобку
        \item Далее проверяем, если разность между количеством открытых и закрытых скобок больше 0, то вызываем функцию рекурсивно, но добавляем к строке закрытую скобку и увеличиваем количество закрытых скобок.
        \item Если количество открытых и закрытых скобок равно $2 \cdot n$, то выводим скобочкую последовательность
    \end{itemize}
\end{frame}

\begin{frame}{Алгоритм создания всех правильных скобочных последовательностей длины  $2\cdot n$}
    \includegraphics[width = 300, height = 150]{8.png}
\end{frame}

\begin{frame}{Список источников}
\begin{itemize}
    \item \small{\url{http://fit.nsu.ru/data_/courses/niu/daio_komb_alg_uchpos.pdf}}
    \item \small{\url{http://shujkova.ru/sites/default/files/lec6.pdf}}
    \item \small{{http://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные объекты}}

\end{itemize}

\end{frame}
\begin{frame}{Заключение}
    \begin{center}
        \Huge{Спасибо за внимание}
    \end{center}
\end{frame}
\end{document}