\documentclass{beamer}
\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\inputencoding{utf8}
\usepackage{amssymb,amsfonts,amsmath,mathtext}
\usepackage{graphicx}
\usetheme{Hannover}
\begin{document}

\section{Алгоритм Сдвига-Или.   Особенности.}

\begin{frame}{Алгоритм Сдвига - Или}

    \begin{block}{
            \begin{center}Особенности\end{center}}
        \begin{enumerate}

            \item [-] Хорош, если длина образца <= размера компьютерного слова.

            \item [-] Время на пред. обработку O(s+m)

            \item [-] Среднее время поиска O(n)
            \item [-] Худшее время поиска O(n)
        \end{enumerate}
    \end{block}

\end{frame}

\section{Алгоритм Сдвига - Или. Суть алгоритма.}
\begin{frame}{Алгоритм Сдвига - Или}

    \begin{block}{\begin{center}Алгоритм\end{center}}


            Пусть R - битовый массив размера m. Вектор R i - значение массива R после обработки очередного символа. Он содержит информацию обо всех совпадениях префиксов х, которые кончаются на позиции i в тексте (0<=j<=m-1):
            \begin{enumerate}
                \item[-]  R i = 0, если x[ 0, j ] = y[ i - j, i ]
                \item[-] R i = 1, в противоположном случае.


        \end{enumerate}
    \end{block}

\end{frame}


\section{Алгоритм Сдвига - Или. Суть алгоритма.}
\begin{frame}{Алгоритм Сдвига - Или}

    \begin{block}{\begin{center}Алгоритм\end{center}}
           Вектор R i+1 может быть вычислен по R i следующим образом. Для всех R i [j] = 0

        \begin{enumerate}

            \item [-] R i+1 [ j+1 ] = 0, если x[ j+1 ] = y[ i+1 ]
            \item [-] R i+1 [ j+1 ] = 1 в противоположном случае
            \item [] И
            \item [-] R i+1 [ 0 ] = 0, если x[ 0 ] = y[ i+1 ]
            \item [-] R i+1 [ 0 ] = 1 в противоположном случае
             \item []  Если R i+1 [ m-1 ] = 0, тогда мы нашли совпадение.

        \end{enumerate}
    \end{block}

\end{frame}

\section{Алгоритм Сдвига - Или. Суть алгоритма.}
\begin{frame}{Алгоритм Сдвига - Или}

    \begin{block}{\begin{center}Алгоритм\end{center}}
    Переход от R i к R i+1 можно очень быстро вычислить следующим образом. Для каждого a из S, пусть S a - битовый массив размера m такой что:
    \begin{enumerate}

    \item [-] Для 0 <= j <= m - 1, S a = 0 <=> x[ j ] = a
    \end{enumerate}

     Массив S a обозначает позиции символа a в образце x. Каждый S a может быть вычислен перед процессом поиска. Тогда процесс вычисления R i+1 укорачивается до двух операций: СДВИГА и ИЛИ:
    \begin{enumerate}

            \item [-] R i+1 = SHIFT( R i ) OR S y[ i+1 ]
    \end{enumerate}



    \end{block}

\end{frame}



\section{Алгоритм Сдвига - Или. Суть алгоритма. }
\begin{frame}{Алгоритм Сдвига - Или}
    \begin{figure}[h]

\centering

\includegraphics[width=0.8\linewidth]{sotab1.png}

\caption{Один из прримеров визуализации}

\label{fig:mpr}

\end{figure}
\end{frame}

 \section{Алгоритм Бойера-Мура-Хорспула}
\begin{frame}{Алгоритм Бойера-Мура-Хорспула}

    \begin{block}{\begin{center}Особенности\end{center}}
        \begin{enumerate}

            \item [-] Легок в реализации. Так же эффективен, как и БМ.

            \item [-] Время на пред. обработку O(s+m)

            \item [-] Среднее время поиска O(n+m)
            \item [-] Худшее время поиска O(n*m)

        \end{enumerate}
    \end{block}

\end{frame}

\section{Алгоритм Бойера-Мура-Хорспула}
\begin{frame}{Алгоритм Бойера-Мура-Хорспула}

    \begin{block}{\begin{center}Алгоритм\end{center}}

        Пусть задан массив srt длинны N и массив pattern длинны M, причем M<N. Поиск строки обнаруживает первое вхождение pattern в str. Оба массива содержат символы, так что str можно считать некоторым текстом или строкой, а pattern  - образом, первое вхождение в строку которого необходимо найти.

    \end{block}

\end{frame}

\section{Алгоритм Бойера-Мура-Хорспула}
\begin{frame}{Алгоритм Бойера-Мура-Хорспула}

    \begin{block}{\begin{center}Этапы работы алгоритма:\end{center}}
        \begin{enumerate}

            \item [-] Формирование таблицы d, используемой при сдвиге образа по строке

            \item [-] Поиск образа в строке

        \end{enumerate}
    \end{block}

\end{frame}

\section{Алгоритм Бойера-Мура-Хорспула}
\begin{frame}{Алгоритм Бойера-Мура-Хорспула}

    \begin{block}{\begin{center}Алгоритм\end{center}}

        Сравнение символов начинается с конца образа, а не с начала. Эффективность алгоритма обусловлена тем, что удается пропускать те части текста, которые заведомо не учавствуют в успешном сопоставлении.

    \end{block}

\end{frame}

\section{Алгоритм Бойера-Мура-Хорспула}
\begin{frame}{Алгоритм Бойера-Мура-Хорспула}

    \begin{block}{\begin{center}Алгоритм\end{center}}

        Происходит сканирование слева направо, сравнение в режиме «чёрного ящика». Как и в примитивном алгоритме, совмещается начало текста и шаблона, проводится сравнение обычной процедурой «сравнить участки памяти». Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо. Эти «несколько» выбираются в соответствии с удалением символа от конца шаблона pattern.

    \end{block}

\end{frame}

\end{document}