\documentclass{beamer}
\usepackage{graphics}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{listings}

\title{Курсовой проект "Крисс Кросс"}
\author{Пётр Лавренюк}
\institute{СПБ ГУАП кафедра 51}
\date{}

\begin{document}

\setbeamertemplate{footline}[page number]

	\defverbatim[colored]\listing{
		\begin{lstlisting}
		path\crisscross.exe arg1 arg2
		\end{lstlisting}
	}

	\begin{frame}[noframenumbering]
		\titlepage
		\thispagestyle{empty}
	\end{frame}


	\begin{frame}
		\frametitle{Содержание}
		    \begin{itemize}
		    	\item Постановка задачи
		    	\item Исследование и анализ задачи
		    	\item Алгоритм
		    	\item Детали реализации
		    	\item Пример работы программы
		    	\item Итоги
		    \end{itemize}
	\end{frame}

	\begin{frame}
		\frametitle{Постановка задачи}

		Формулировка задания:
		\\
		Реализовать программу, которая по набору слов создает решетку кроссворда. Решетка
		должна быть компактная и красивая, а также иметь максимум пересечений. На вход
		программа берет список слов, на выходе записывает решетку в текстовый файл.
	\end{frame}

	\begin{frame}
		\frametitle{Исследование и анализ задачи}
		Основные замечания/требования:
		\begin{itemize}
			\item Максимальное количество пересчений
			\item Слова не должны слипаться
			\item Слова не должны накладываться друг на друга
			\item Сделать полный перебор слов
			\item Реализовать "слепые зоны"
		\end{itemize}
	\end{frame}

	\begin{frame}
		\frametitle{Алгоритм}
		1. Подсчет общего количества слов в словаре
		\\2. Выделение динамической памяти под все необходимые массивы
		\\3. Начинаем перебор с функции startalgo - ставится i-тое слово из списка в центр сетки по горизонтали.
		\\4. В теле startalgo() ищем все слова которые можно поставить по вертикале по отношению к первому слову, ставим и начинаем новую ветку рекурсии.
		\\5. Начинаем примерять и вставлять слова по горизонтали и вертикале, каждая вставка слова начинает новую рекурсивную ветку.
		\\6. Когда в ветке все слова использованы, подсчитываем число пересечений. Если число пересечений больше максимального, копируем в буффер.
		\\7. Выводим в файл.
	\end{frame}

	\begin{frame}
		\frametitle{Детали реализации}
		Для удобства данная курсовая работа реализована на C++, с использованием классов, а также типа enum, который используется в функции void pastit(....,direct dir), как параметр указывающий направление вставки слова.\\
		Так называемые "слепые зоны" реализуются по методу вставки вокруг слова символов, для вертикальных слов - "1", для горизонтальных "2" , а также для всех типов слов в начале и в конце - "3".
	\end{frame}

	\begin{frame}
		\frametitle{Сложность алгоритма}
		Алгоритм по своей сути является полным перебором. И его сложность :
		$$
		O (n*n^2)
		$$
	\end{frame}

	\begin{frame}{C++}
		\frametitle{Формат ввода данных}
		Словарь храниться в файле формата ".txt". Каждое слово начинается с новой строки.
		\\Запуск программы осуществляется вводом команды:
		\listing
		где первый аргумент - файл со словарем
		\\второй аргумент - файл куда будет сохранен результат
	\end{frame}

	\begin{frame}
		\frametitle{Примеры работы программы}
		\begin{figure}[h!]
			\begin{minipage}[h]{0.47\linewidth}
				\includegraphics[scale=0.7]{1st.png}
			\end{minipage}
			\begin{minipage}[h]{0.47\linewidth}
				\includegraphics[scale=0.7]{2nd.png}
			\end{minipage}
		\end{figure}
	\end{frame}

		\begin{frame}
			\frametitle{Итоги}
			\begin{itemize}
				\item Использование динамического программирование
				\item Анализ и исследование поставленной задачи
				\item Реализация и оптимизация самописного алгоритма
			\end{itemize}
		\end{frame}

\end{document}