Advertisement
HabKaffee

Untitled

Sep 17th, 2021
97
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. \documentclass{beamer}
  2.  
  3. \mode<presentation>
  4. {
  5. \usetheme{Madrid} % or try default, Darmstadt, Warsaw, ...
  6. \usecolortheme{default} % or try albatross, beaver, crane, ...
  7. \usefonttheme{professionalfonts} % or try default, structurebold, ...
  8. \setbeamertemplate{navigation symbols}{}
  9. \setbeamertemplate{caption}[numbered]
  10. }
  11.  
  12. \usepackage[russian]{babel}
  13. \usepackage[english]{babel}
  14. \usepackage[russian]{babel}
  15. \usepackage{chemfig}
  16. \usepackage[version=3]{mhchem}
  17. \usepackage[unicode, pdftex]{hyperref}
  18.  
  19. % Строчки выше можно вообще не трогать
  20.  
  21. % Эти строчки позволяют использовать окружения для определений свойств и т.д. на русском языке
  22. \newtheorem{df}{Определение}
  23. \newtheorem{property}{Свойство}
  24. \newtheorem{ex}{Пример}
  25. \newtheorem{thm}{Теорема}
  26.  
  27. % On Overleaf, these lines give you sharper preview images.
  28. % You might want to `comment them out before you export, though.
  29. \usepackage{pgfpages}
  30. \pgfpagesuselayout{resize to}[%
  31. physical paper width=8in, physical paper height=6in]
  32.  
  33. % Название доклада. Можно стереть и указать свое
  34. \title[Алгоритмы перебора комбинаторных объектов]{Алгоритмы перебора комбинаторных объектов}
  35.  
  36. % Имя автора доклада
  37. % Первый аргумент отвечает за имя, появляющееся в нижней строке
  38. \author[Наумов Н.А.]{Наумов~Н.~А. \\nanaumov@edu.hse.ru}
  39. % Дата выступления
  40. \date{25 марта 2021 г.}
  41. \begin{document}
  42. \begin{frame}
  43. \titlepage
  44. \end{frame}
  45. \begin{frame}{Напоминание}
  46. \begin{df}
  47. Комбинаторные объекты (англ. combinatorial objects) — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
  48. \end{df}
  49.  
  50.  
  51. \begin{df}
  52. Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются упорядоченными (англ. ordered).
  53. \end{df}
  54. \end{frame}
  55.  
  56. \begin{frame}{Примеры комбинаторных объектов}
  57. \begin{itemize}
  58. \item Битовые вектора (последовательности нулей и единиц)
  59. \item Перестановки - упорядоченный набор чисел 1,2,…,n, обычно трактуемый как биекция на множестве {1,2,…,n}, которая числу i ставит соответствие i-й элемент из набора.
  60. \item Размещение из n по k ($A^{k}_n$) — упорядоченный набор из k различных элементов некоторого n-элементного множества.
  61. \item Сочетания из n по k ($C^{k}_{n}$) — набор k элементов, выбранных из данных n элементов.
  62. \item $n!$ представление числа - представление целого неотрицательного числа m в виде последовательности ($d_{0}, d_{1}, ... , d_{n-1}$), такая что $0 \leq d_{i} \leq i$, $i \in [0, n-1]$ и \newline \begin{center}
  63. $m = d_{n-1}\cdot(n-1)! + d_{n-2}\cdot(n-2)! + ... + d_{0}\cdot(0)!$
  64. \end{center}
  65. \end{itemize}
  66. \end{frame}
  67.  
  68. \begin{frame}{Алгоритм нахождения $n!$ представления числа}
  69. Введем неформальное описание алгоритма нахождения $n!$-ого представления числа
  70. \begin{itemize}
  71. \item Шаг 0. $d_{0} = 0; q_{0} = m$
  72. \item Шаг 1. Делим $q_{0}$ на 2, находим остаток от деления на $d_1$ и частное от деления $q_1$ = $\lfloor q_{0}/2 \rfloor$. При этом имеем $0 \leq d_1 < 2$
  73. \item Шаг $i$. Делим $q_{i-1}$ на $i+1$, полагаем $d_i$ - остаток от деления $\lfloor q_{i-1}/{i+1} \rfloor$. При этом $0 \leq d_i < i+1$
  74. \item Шаг n-1. На заключительном шаге находим остаток $d_{n-1}$ от деления $q_{n-2}$ на $n$ и частное $q_{n-2}$ на $n$
  75. \end{itemize}
  76. \end{frame}
  77. \begin{frame}{Реализация алгоритма $n!$ представления числа}
  78.  
  79. \includegraphics[width = 300, height = 200]{1.png}
  80.  
  81. \end{frame}
  82.  
  83. \begin{frame}{Перестановки в лексикографическом порядке}
  84. Введем неформальное описание алгоритма.
  85. \begin{itemize}
  86. \item Создаем массив размерности $n+1$, в котором будем проводить изменения
  87. \item В $a_1, a_2, ..., a_n$ записываем текущую пораздаемую перестановку из $S_n$
  88. \item Значение $a_0$ не изменяется и равно 0, поэтому всегда справедливо, что $a_0 < a_1$.
  89. \item Это неравенство гарантирует нахождение самой правой позиции $i \geq 0$ такой, что $a_i < a_{i+1}$.
  90. \item Алгоритм заканчивает работу, когда i = 0;
  91. \end{itemize}
  92. \end{frame}
  93.  
  94. \begin{frame}{Реализация алгоритма генерации перестановок}
  95. \includegraphics[width = 270, height = 230]{2.png}
  96. \end{frame}
  97.  
  98. \begin{frame}{Создание всех бинарных векторов заданной длины $n$}
  99. Введем неформальное описание алгоритма создания всех бинарных векторов заданной длины
  100. \begin{itemize}
  101. \item Создаем вектор длины ($b_n, b_{n-1}, ..., b_0$), все элементы приравниваем к 0
  102. \item Просматриваем вектор b справа налево, ищем самую правую позицию $i$, такую, что $b_i$ = 0.
  103. \item Запишем в эту $i$-ую позицию 1, а все элементы $b_j, j < i$, стоящие справа от $b_i$, полагаем равными 0.
  104. \item $b_n$ изменяется только на самой последней итерации и становится равным единице.
  105. \item Когда $b_n$ = 1, то алгоритм заканчивает работу
  106. \end{itemize}
  107. \end{frame}
  108.  
  109. \begin{frame}{Реализация алгоритма создания бинарных векторов длины $n$}
  110. \includegraphics[width = 300, height = 200]{3.png}
  111. \end{frame}
  112. \begin{frame}{Создание всех сочетаний из $n$ по $k$}
  113. Введем неформальное описание алгоритма создания всех сочетаний $n$ по $k$
  114. \begin{itemize}
  115. \item Создаем массив длины n и заполняем его элементами таким образом, что $a_0 = 1, a_1 = 2,..., a_{n-1} = n$
  116. \item Пока у нас будет существовать следующее сочитание, будем его выводить
  117. \item Определим, как понять, существует ли следующее сочетание
  118. \begin{itemize}
  119. \item Просматривая сочетания справа налево, находим первый элемент, который можно увеличить. Этот элемент увеличиваем (берем следующий возможный элемент), а все элементы после
  120. него, заменяем на натуральные числа, следующие за новым элементом.
  121. \end{itemize}
  122. \end{itemize}
  123. \end{frame}
  124. \begin{frame}{Алгоритм создания всех сочетаний из $n$ по $k$}
  125. \includegraphics[width = 300, height = 200]{4.png}
  126. \end{frame}
  127. \begin{frame}{Дополнительная функция}
  128. \includegraphics[width = 300, height = 170]{5.png}
  129. \end{frame}
  130. \begin{frame}{Создание всех размещений из $n$ по $k$}
  131. Введем неформальное описание алгоритма создания всех размещений из $n$ по $k$
  132. \begin{itemize}
  133. \item Создаем массив длины n и заполняем его элементами таким образом, что $a_0 = 1, a_1 = 2,..., a_{n-1} = n$
  134. \item Пока у нас будет существовать следующее размещение, будем его выводить
  135. \item Определим, как понять, существует ли следующее размещение
  136. \begin{itemize}
  137. \item Для начала, нужно найти первый элемент справа (Обозначим его $a_j$), который меньше следующего за ним ($a_i < a_{i+1}$)
  138. \item Если таких элементов нет, то возможные размещения закончились
  139. \item Иначе мы ищем первый элемент в множестве, который меньше чем ${a_j}$
  140. \item После нахождения меняем их местами и сортируем оставшуюся часть последовательности
  141. \item Выполняем эти действия до тех пор, пока $(j > k-1)$
  142. \end{itemize}
  143. \end{itemize}
  144. \end{frame}
  145. \begin{frame}{Алгоритм создания всех размещений из $n$ по $k$}
  146. \includegraphics[width = 300, height = 200]{6.png}
  147. \end{frame}
  148. \begin{frame}{Дополнительная функция}
  149. \includegraphics[width = 300, height = 200]{7.png}
  150. \end{frame}
  151.  
  152. \begin{frame}{Создание всех правильных скобочных последовательностей длины $2 \cdot n$}
  153. Введем неформальное описание алгоритма поиска всех скобочных правильных последовательностей
  154. \begin{itemize}
  155. \item Если количество открытых скобок меньше чем $n$, то вызываем функцию рекурсивно, увеличивая количество открытых скобок и добавляя в строку открытую скобку
  156. \item Далее проверяем, если разность между количеством открытых и закрытых скобок больше 0, то вызываем функцию рекурсивно, но добавляем к строке закрытую скобку и увеличиваем количество закрытых скобок.
  157. \item Если количество открытых и закрытых скобок равно $2 \cdot n$, то выводим скобочкую последовательность
  158. \end{itemize}
  159. \end{frame}
  160.  
  161. \begin{frame}{Алгоритм создания всех правильных скобочных последовательностей длины $2\cdot n$}
  162. \includegraphics[width = 300, height = 150]{8.png}
  163. \end{frame}
  164.  
  165. \begin{frame}{Список источников}
  166. \begin{itemize}
  167. \item \small{\url{http://fit.nsu.ru/data_/courses/niu/daio_komb_alg_uchpos.pdf}}
  168. \item \small{\url{http://shujkova.ru/sites/default/files/lec6.pdf}}
  169. \item \small{{http://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные объекты}}
  170.  
  171. \end{itemize}
  172.  
  173. \end{frame}
  174. \begin{frame}{Заключение}
  175. \begin{center}
  176. \Huge{Спасибо за внимание}
  177. \end{center}
  178. \end{frame}
  179. \end{document}
Advertisement
RAW Paste Data Copied
Advertisement