\documentclass[fullscreen=true,unicode,bookmarks=false]{beamer}
\usetheme{Boadilla}
%\includeonlyframes{SumSubsetShow}
%\includeonlyframes{OtherPProblems}

\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{tikz}

\theoremstyle{definition}
\newtheorem{mydefinition}{Определение}
\newtheorem{historylabel}{Историческая метка}
\newtheorem{myexample}{Пример}
\newtheorem{myproblem}{Задача}

\newtheorem{given}{Дано}
\newtheorem{subproblems}{Подзадачи}
\newtheorem{init}{Начальные условия}
\newtheorem{recur}{Рекуррентные соотношения}
\newtheorem{dynprogtable}{Таблица ответов к подзадачам}
\theoremstyle{remark}
\newtheorem{remark}{Замечание}

\newcommand{\bZ}{{\mathbb Z}}
\newcommand{\bZpositiv}{{\mathbb Z^+}}
\newcommand{\bZnonnegativ}{{\mathbb Z^{\ge0}}}
\renewcommand{\emptyset}{\ensuremath{\varnothing}}
\newcommand{\qu}{\text{\textquestiondown}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\DeclareMathOperator{\logOR}{or}
\DeclareMathOperator{\logAND}{and}
\DeclareMathOperator{\Time}{Time}
\DeclareMathOperator{\Length}{Length}
\DeclareMathOperator{\Max}{Max}
\DeclareMathOperator{\NPclass}{NP}
\DeclareMathOperator{\Pclass}{P}
\newcommand{\mysim}[1]{\stackrel{#1}{\sim}}
\newcommand{\notmysim}[1]{\stackrel{#1}{\nsim}}

\tikzstyle{thinarrow}=[densely dashed,very thin]

\title[Динамическое программирование]{Метод~динамического~программирования
и~его~приложения~к~NP-трудным~задачам}
\subtitle{Краткий ознакомительный доклад}
\author{Е. А. Максименко}
\institute[ЮФУ]{Южный федеральный университет}

\hypersetup{pdfkeywords={динамическое программирование,
dynamic programming, применения, псевдополиномиальные алгоритмы,
NP-сильные задачи в строгом смысле}}

\AtBeginSubsection[] {
\begin{frame}{План доклада}
\tableofcontents[currentsection,currentsubsection]
\end{frame}
}

\begin{document}

\begin{frame}[label=titlepage]
\titlepage
\end{frame}

\begin{frame}{Пояснение}

Эта презентация подготовлена для доклада на учебном семинаре
<<Методы решения NP-трудных задач>>
(руководитель семинара~--- М.~Г.~Адигеев).

\medskip
Участникам семинара хорошо знакома
идея метода динамического программирования (ДП),
поэтому в презентации сразу приведены примеры
практических задач, решаемых методом ДП,
и затронута тема применения ДП к NP-трудным задачам.
К сожалению, не рассказано о приближённом решении
задачи о рюкзаке с помощью метода масштабирования.

\medskip
Составитель презентации благодарен
участникам семинара за внимание и поправки.

\end{frame}

\begin{frame}{План доклада}
\tableofcontents
\end{frame}

\section{Примеры задач из класса P, решаемых методом ДП}

\subsection{Расстояние редактирования}

\begin{frame}{Расстояние редактирования}
\framesubtitle{Элементарные операции редактирования строк}

\begin{block}{}
\begin{itemize}
\item Замена одного символа на другой:
\[
  \text{параш\alert{у}т}\mapsto\text{параш\alert{ю}т},\quad
  \text{со\alert{н}}\mapsto\text{со\alert{м}},\quad
  \text{\alert{к}ультур}\mapsto\text{\alert{м}ультур}
\]
\item Вставка одного символа:
\[
  \text{кецаль}\mapsto\text{ке\alert{т}цаль},\quad
  \text{шик}\mapsto\text{\alert{п}шик},\quad
  \text{бор}\mapsto\text{бор\alert{щ}}
\]
\item Удаление одного символа:
\[
  \text{куз\alert{д}ра}\mapsto\text{кузра},\quad
  \text{\alert{ш}лак}\mapsto\text{лак},\quad
  \text{медвед\alert{ь}}\mapsto\text{медвед}
\]
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Расстояние редактирования}
\framesubtitle{Определение}

\begin{block}{Автор понятия}
В. И. Левенштейн, Институт прикл. мат. им. М. В. Келдыша, 1965.
\end{block}

\begin{mydefinition}
\emph{Расстояние редактирования} между строками $s_1$ и $s_2$~---\\
минимальное число элементарных операций редактирования,\\
необходимое для превращения $s_1$ в $s_2$.
\end{mydefinition}

\begin{myexample}
$d(\text{пусто},\text{окулист})=5$:\\
$\text{пусто} \mapsto \text{пуст} \mapsto
\text{куст} \mapsto \text{окуст} \mapsto
\text{окулст} \mapsto \text{окулист}$,\\
причём более короткой цепочки не существует.
\end{myexample}

\end{frame}


\begin{frame}{Расстояние редактирования}
\framesubtitle{Алгоритм вычисления методом ДП}

\begin{given}
Строка $s$ длины $m$, строка $t$ длины $n$.
\end{given}

\begin{subproblems}
$D[i,j] = d(s[1 \ldots i], t[1\ldots j])$
\qquad($0\le i\le m$, $0\le j\le n$).
\end{subproblems}

\begin{init}
$D[i,0] = i$\quad($0\le i\le m$)\qquad
$D[0,j] = j$\quad($0\le j\le n$)
\end{init}

\begin{recur}
$D[i,j]=\min(D[i-1,j] + 1,$\\
$\phantom{D[i,j]=\min(}D[i,j-1] + 1,$\\
$\phantom{D[i,j]=\min(}D[i-1,j-1] + (s[i] \ne t[j]))$.
\end{recur}

\end{frame}

\begin{frame}{Расстояние редактирования}
\framesubtitle{Демонстрация работы алгоритма}

\begin{columns}[T]
\begin{column}{4cm}
\begin{block}{Пример}
$d(\text{ГРОМ},\text{ГОРОД})=\,?$
\end{block}
\begin{block}{Ответ}<visible@23->
$d(\text{ГРОМ},\text{ГОРОД})=2$.\\
\bigskip\noindent%
ГРОМ $\mapsto$ \\
ГОРОМ $\mapsto$ \\
ГОРОД
\end{block}
\end{column}

\begin{column}{7cm}
\begin{dynprogtable}
\begin{tikzpicture}
\action<visible@1->{\node at (0,5) {\emptyset};}
\action<visible@1->{\node at (1,5) {Г};}
\action<visible@1->{\node at (2,5) {О};}
\action<visible@1->{\node at (3,5) {Р};}
\action<visible@1->{\node at (4,5) {О};}
\action<visible@1->{\node at (5,5) {Д};}

\action<visible@1->{\node at (-1,4) {\emptyset};}
\action<visible@2-|alert@3>{\node(00) at (0,4) {0};}
\action<visible@2-|alert@3,4>{\node(01) at (1,4) {1};}
\action<visible@2-|alert@4,5>{\node(02) at (2,4) {2};}
\action<visible@2-|alert@5,6>{\node(03) at (3,4) {3};}
\action<visible@2-|alert@6,7>{\node(04) at (4,4) {4};}
\action<visible@2-|alert@7>{\node(05) at (5,4) {5};}

\action<visible@1->{\node at (-1,3) {Г};}
\action<visible@2-|alert@3,8>{\node(10) at (0,3) {1};}
\action<visible@3-|alert@4,8,9>{\node(11) at (1,3) {0};}
\action<visible@4-|alert@5,9,10>{\node(12) at (2,3) {1};}
\action<visible@5-|alert@6,10,11>{\node(13) at (3,3) {2};}
\action<visible@6-|alert@7,11,12>{\node(14) at (4,3) {3};}
\action<visible@7-|alert@12>{\node(15) at (5,3) {4};}

\action<visible@1->{\node at (-1,2) {Р};}
\action<visible@2-|alert@8,13>{\node(20) at (0,2) {2};}
\action<visible@8-|alert@9,13,14>{\node(21) at (1,2) {1};}
\action<visible@9-|alert@10,14,15>{\node(22) at (2,2) {1};}
\action<visible@10-|alert@11,15,16>{\node(23) at (3,2) {1};}
\action<visible@11-|alert@12,16,17>{\node(24) at (4,2) {2};}
\action<visible@12-|alert@17>{\node(25) at (5,2) {3};}


\action<visible@1->{\node at (-1,1) {О};}
\action<visible@2-|alert@13,18>{\node(30) at (0,1) {3};}
\action<visible@13-|alert@14,18,19>{\node(31) at (1,1) {2};}
\action<visible@14-|alert@15,19,20>{\node(32) at (2,1) {1};}
\action<visible@15-|alert@16,20,21>{\node(33) at (3,1) {2};}
\action<visible@16-|alert@17,21,22>{\node(34) at (4,1) {1};}
\action<visible@17-|alert@22>{\node(35) at (5,1) {2};}

\action<visible@1->{\node at (-1,0) {М};}
\action<visible@2-|alert@18>{\node(40) at (0,0) {4};}
\action<visible@18-|alert@19>{\node(41) at (1,0) {3};}
\action<visible@19-|alert@20>{\node(42) at (2,0) {2};}
\action<visible@20-|alert@21>{\node(43) at (3,0) {2};}
\action<visible@21-|alert@22>{\node(44) at (4,0) {2};}
\action<visible@22->{\node(45) at (5,0) {2};}

\action<visible@2-|alert@2>{\draw[->](00)--(10);}
\action<visible@2-|alert@2>{\draw[->](10)--(20);}
\action<visible@2-|alert@2>{\draw[->](20)--(30);}
\action<visible@2-|alert@2>{\draw[->](30)--(40);}

\action<visible@2-|alert@2>{\draw[->](00)--(01);}
\action<visible@2-|alert@2>{\draw[->](01)--(02);}
\action<visible@2-|alert@2>{\draw[->](02)--(03);}
\action<visible@2-|alert@2>{\draw[->](03)--(04);}
\action<visible@2-|alert@2>{\draw[->](04)--(05);}

\action<visible@3-|alert@3,23>{
  \draw[->](00)--(11);
  \draw<3>[->,thinarrow](01)--(11);
  \draw<3>[->,thinarrow](10)--(11);
}

\action<visible@4-|alert@4,23>{
  \draw<4>[->,thinarrow](01)--(12);
  \draw<4>[->,thinarrow](02)--(12);
  \draw[->](11)--(12);
}

\action<visible@5-|alert@5>{
  \draw<5>[->,thinarrow](02)--(13);
  \draw<5>[->,thinarrow](03)--(13);
  \draw[->](12)--(13);
}

\action<visible@6-|alert@6>{
  \draw<6>[->,thinarrow](03)--(14);
  \draw<6>[->,thinarrow](04)--(14);
  \draw[->](13)--(14);
}

\action<visible@7-|alert@7>{
  \draw<7>[->,thinarrow](04)--(15);
  \draw<7>[->,thinarrow](05)--(15);
  \draw[->](14)--(15);
}


\action<visible@8-|alert@8>{
  \draw<8>[->,thinarrow](10)--(21);
  \draw[->](11)--(21);
  \draw<8>[->,thinarrow](20)--(21);
}

\action<visible@9-|alert@9>{
  \draw[->](11)--(22);
  \draw<9>[->,thinarrow](12)--(22);
  \draw<9>[->,thinarrow](21)--(22);
}

\action<visible@10-|alert@10,23>{
  \draw[->](12)--(23);
  \draw<10>[->,thinarrow](13)--(23);
  \draw<10>[->,thinarrow](22)--(23);
}

\action<visible@11-|alert@11>{
  \draw<11>[->,thinarrow](13)--(24);
  \draw<11>[->,thinarrow](14)--(24);
  \draw[->](23)--(24);
}

\action<visible@12-|alert@12>{
  \draw<12>[->,thinarrow](14)--(25);
  \draw<12>[->,thinarrow](15)--(25);
  \draw[->](24)--(25);
}


\action<visible@13-|alert@13>{
  \draw<13>[->,thinarrow](20)--(31);
  \draw[->](21)--(31);
  \draw<13>[->,thinarrow](30)--(31);
}

\action<visible@14-|alert@14>{
  \draw[->](21)--(32);
  \draw<14>[->,thinarrow](22)--(32);
  \draw<14>[->,thinarrow](31)--(32);
}

\action<visible@15-|alert@15>{
  \draw[->](22)--(33);
  \draw[->](23)--(33);
  \draw[->](32)--(33);
}

\action<visible@16-|alert@16,23>{
  \draw[->](23)--(34);
  \draw<16>[->,thinarrow](24)--(34);
  \draw<16>[->,thinarrow](33)--(34);
}

\action<visible@17-|alert@17>{
  \draw<17>[->,thinarrow](24)--(35);
  \draw<17>[->,thinarrow](25)--(35);
  \draw[->](34)--(35);
}

\action<visible@18-|alert@18>{
  \draw<18>[->,thinarrow](30)--(41);
  \draw[->](31)--(41);
  \draw<18>[->,thinarrow](40)--(41);
}

\action<visible@19-|alert@19>{
  \draw<19>[->,thinarrow](31)--(42);
  \draw[->](32)--(42);
  \draw<19>[->,thinarrow](41)--(42);
}

\action<visible@20-|alert@20>{
  \draw[->](32)--(43);
  \draw<20>[->,thinarrow](33)--(43);
  \draw<20>[->,thinarrow](42)--(43);
}

\action<visible@21-|alert@21>{
  \draw<21>[->,thinarrow](33)--(44);
  \draw[->](34)--(44);
  \draw<21>[->,thinarrow](43)--(44);
}

\action<visible@22-|alert@22,23>{
  \draw[->](34)--(45);
  \draw<22>[->,thinarrow](35)--(45);
  \draw<22>[->,thinarrow](44)--(45);
}

%% way: (0,0)--(1,1)--(1,2)--(2,3)--(3,4)--(4,5)
%% 

\end{tikzpicture}
\end{dynprogtable}
\end{column}
\end{columns}

\end{frame}

\subsection{Другие примеры}

\begin{frame}{Кратчайший путь в бесконтурном графе}
\framesubtitle{Постановка задачи}

\begin{myproblem}
\begin{description}
\item[Дано:] орграф $G=(V,E)$, в котором нет петель и контуров,\\
весовая функция $w\colon E\to\bZpositiv$ (<<длины дуг>>),\\
вершины $s,f\in V$.\\
\item[Найти:] длину кратчайшего пути от $s$ к $f$.
\end{description}
\end{myproblem}

\pause

\begin{remark}
На множестве $V$ можно ввести такую нумерацию
$\{v_1,\ldots,v_n\}$, что $(v_i,v_j)\notin E$ при $i>j$.
\end{remark}

\pause

\begin{remark}
Можно считать, что величина $w[i,j]=w(v_i,v_j)$
определена при всех $(i,j)\colon i<j$,
но может принимать значение $+\infty$.
\end{remark}

\end{frame}



\begin{frame}{Кратчайший путь в бесконтурном графе}
\framesubtitle{Алгоритм решения методом ДП}

\begin{given}
$w[i,j]$\quad($1\le i<j\le n$),\quad $s,f$\quad($1\le s<f\le n$)
\end{given}

\pause

\begin{subproblems}
$D[j]$~--- длина кратчайшего пути из $s$ в $j$.
\end{subproblems}

\pause

\begin{init}
$D[s] = 0$
\end{init}

\pause

\begin{recur}
$\displaystyle D[j] = \min_{s\le i<j} (D[i]+w[i,j])$
\qquad($s<j\le f$)
\end{recur}

\end{frame}



\begin{frame}[label=LongestCommonSubsequence]{Самая длинная
общая подпоследовательность}

\begin{block}{Самая длинная общая подпоследовательность}
\begin{description}
\item[Дано:]
$m\in\bZpositiv$,\quad $n\in\bZpositiv$,\\
$a_i\in\bZ$\quad($1\le i\le m$),\qquad
$b_i\in\bZ$\quad($1\le i\le n$).
\item[Найти:]
$k\in\bZ$, $k\ge0$,\qquad $i_1,\ldots,i_k$,\quad $j_1,\ldots,j_k$:\\
$1\le i_1<i_2<\ldots<i_k\le m$,\quad $1\le j_1<j_2<\ldots<j_k\le n$,\\
$a_{i_1}=b_{j_1},\quad a_{i_2}=b_{j_2},\quad\ldots,\quad a_{i_k}=b_{j_k}$,\\
$k\to\max$.
\end{description}
\end{block}

\pause

\begin{myexample}
\begin{description}
\item[Дано:]
$m=5$, $a=(1,4,2,7,2)$,\quad $n=4$, $b=(3,4,7,2)$.
\item[Ответ:]
$k=3$:\quad
$(1,\alert{4},2,\alert{7},\alert{2})$,\quad
$(3,\alert{4},\alert{7},\alert{2})$.
\end{description}
\end{myexample}

\end{frame}

\begin{frame}{Глобальное соответствие между цепочками}
\framesubtitle{Происхождение задачи}

\begin{block}{Практическая важность задачи}
В биоинформатике важно оценивать близость цепочек нуклеотидов (ДНК)
либо цепочек протеинов (пептиды, белки).
\end{block}

\pause

\begin{block}{Авторы алгоритма}
Saul Needleman, Christian Wunsch\quad 1970.\\
Предложили алгоритм, основанный на методе ДП,\\
для поиска наилучшего глобального соответствия между цепочками.
\end{block}

\end{frame}

\begin{frame}{Глобальное соответствие между цепочками}
\framesubtitle{Описание задачи}

\begin{block}{Матрица похожести нуклеотидов и штраф за разрыв}
\[
  S=\left(\begin{array}{c|cccc}
   & \mathrm{A} & \mathrm{G} & \mathrm{C} & \mathrm{T} \\ \hline
  \mathrm{A} & 10 & -1 & -3 & -4 \\
  \mathrm{G} & -1 & 7 & -5 & -3 \\
  \mathrm{C} & -3 & -5 & 9 & 0 \\
  \mathrm{T} & -4 & -3 & 0 & 8
  \end{array}\right),
  \qquad
  g=-5.
\]
\end{block}

\pause

\begin{block}{Пример оценки соответствия между двумя цепочками}
\begin{itemize}
\item
Цепочки: AGACTAGTTAC, CGAGACGT
\item
Соответствие:\\
\texttt{AGACTAGTTAC}\\
\texttt{CGA{-}{-}{-}GACGT}
\item
Оценка:
$-3+7+10-3\cdot 5+7+(-4)+0+(-1)+0=1$.
\end{itemize}
\end{block}

\end{frame}

\begin{frame}{Глобальное соответствие между цепочками}
\framesubtitle{Алгоритм Нидлмана-Вунша}

\begin{given}
$S\in\bZ^{4\times 4}$, $g\in\bZ$,\\
$m\in\bZpositiv$, $A\in\{\mathrm{A},\mathrm{G},\mathrm{C},\mathrm{T}\}^m$,\quad
$n\in\bZpositiv$, $B\in\{\mathrm{A},\mathrm{G},\mathrm{C},\mathrm{T}\}^n$.
\end{given}

\pause

\begin{subproblems}
$F[i,j]$~--- максимальная оценка среди соответствий\\
между $A[1,\ldots,i]$ и $B[1,\ldots,j]$
\qquad ($0\le i\le m$, $0\le j\le n$).
\end{subproblems}

\pause

\begin{init}
$F[0,j]=g\cdot j$\quad ($0\le j\le n$),\qquad
$F[i,0]=g\cdot i$\quad ($0\le i\le m$).
\end{init}

\pause

\begin{recur}
$F[i,j]=\max(F[i-1,j-1]+S[A[i],B[j]], F[i,j-1]+g, F[i-1,j]+g)$.
\end{recur}

\end{frame}


\begin{frame}{Разбиение текста на строки}

\begin{block}{Описание задачи}
Простейший случай:
слова нельзя переносить, все символы имеют одинаковую ширину.
Даны длины слов: $L_1,L_2,\ldots,L_n$
и число $M$~--- максимальная ширина строки.

Ищется цепочка индексов: $1=i_1\le i_2\le\ldots\le i_m=n+1$.\\
В $k$-ю строку помещаются слова от $i_k$-го до $i_{k+1}-1$.\\
$s_k$~--- ширина текста в $k$-й строке, учитывая пробелы:
\[
  s_k=i_{k+1}-i_k+\sum_{i=i_k}^{i_{k+1}-1}L_i.
\]
Нужно выбрать индексы $i_1,i_2,\ldots,i_m$ так, чтобы
\[
  s_k\le M\quad(1\le k\le m),\qquad
  \sum_{k=1}^{m-1}(M-s_k)^3\to\min.
\]
\end{block}

\end{frame}

\section{Псевдополиномиальные алгоритмы}

\subsection{Определение}

\begin{frame}{Псевдополиномиальные алгоритмы: определение}

\begin{block}{Задачи с числовыми параметрами}
Пусть $\Pi$~--- распознавательная задача с числовыми параметрами.\\
С каждой индивидуальной задачей $I$ из $\Pi$ связаны два числа:
\begin{itemize}
\item $\Length(I)$~--- длина входных данных\\
(число символов, используемых для записи входных данных);\\
\item $\Max(I)$~--- максимальный по абсолютной величине\\
числовой параметр среди входных данных задачи $I$.
\end{itemize}
\end{block}

\pause

\begin{mydefinition}
Пусть $\Pi$~--- задача с числовыми параметрами.
Алгоритм $A$ решения задачи $\Pi$ называют \emph{псевдополиномиальным}
(по времени), если существует такой многочлен $P$ от двух переменных,
что для любой индивидуальной задачи $I$ из $\Pi$
\[
  \Time(A,I)\le P(\Length(I),\Max(I)).
\]
\end{mydefinition}

\end{frame}

\subsection{Поиск подмножества с заданной суммой}

\begin{frame}{Поиск подмножества с заданной суммой}
\framesubtitle{Постановка задачи}

\begin{myproblem}
\begin{description}
\item[Дано:] 
$n\in\bZpositiv$,\quad $a_i\in\bZpositiv$\quad($1\le i\le n$),\quad
$m\in\bZpositiv$.
\item[Вопрос:]
$\displaystyle\qu\ \exists I\subset\{1,\ldots,n\}\colon\sum_{i\in I}a_i=m\ ?$
\end{description}
\end{myproblem}

\pause

\begin{myexample}
\begin{description}
\item[Дано:]
$n=6$,\quad $a=(5,2,7,5,4,3)$,\quad $m=15$.
\item[Ответ:]
$1$ (да).
\end{description}
\end{myexample}

\pause

\begin{myexample}
\begin{description}
\item[Дано:]
$n=5$,\quad $a=(2,3,2,10,20)$,\quad $m=19$.
\item[Ответ:]
$0$ (нет).
\end{description}
\end{myexample}

\end{frame}

\begin{frame}{Поиск подмножества с заданной суммой}
\framesubtitle{Алгоритм решения методом ДП}

\begin{given}
$n\in\bZpositiv$,\quad $a_i\in\bZpositiv$\quad($1\le i\le n$),\quad
$m\in\bZpositiv$.
\end{given}

\pause

\begin{subproblems}
$\displaystyle Q[k,s]
=\biggl(\exists\ I\subset\{1,\ldots,k\}\colon\sum_{i\in I}a_i=s\biggr)$\qquad
($0\le k\le n$,\quad $0\le s\le m$)
\end{subproblems}

\pause

\begin{init}
$Q[k,0]=1$\quad($0\le k\le n$)\qquad $Q[0,s]=0$\quad($1\le s\le m$)
\end{init}

\pause

\begin{recur}
$Q[k,s]=Q[k-1,s]\quad\vee$\\
$\phantom{Q[k,s]=\,}(a[k]\le s\quad\wedge\quad Q[k-1,\,s-a[k]])$
\end{recur}

\end{frame}


\begin{frame}[label=SumSubsetShow]{Поиск подмножества с заданной суммой}
\framesubtitle{Демонстрация работы алгоритма}

\begin{columns}[T]
\begin{column}{3cm}
\begin{block}{Пример}
$n=4$\\
$a=(3,6,2,3)$\\
$m=7$
\end{block}
\begin{block}{Ответ}<visible@35->
$0$ (нет)
\end{block}
\end{column}

\begin{column}{7cm}
\begin{dynprogtable}
\begin{tikzpicture}[xscale=0.8,yscale=0.8]
\action<visible@1->{\node at (-1,5) {s:};}
\action<visible@1->{\node at (0,5) {0};}
\action<visible@1->{\node at (1,5) {1};}
\action<visible@1->{\node at (2,5) {2};}
\action<visible@1->{\node at (3,5) {3};}
\action<visible@1->{\node at (4,5) {4};}
\action<visible@1->{\node at (5,5) {5};}
\action<visible@1->{\node at (6,5) {6};}
\action<visible@1->{\node at (7,5) {7};}

\action<visible@1->{\node at (-1,4) {\emptyset};}
\action<visible@2-|alert@2,3,6>{\node(00) at (0,4) {1};}
\action<visible@2-|alert@2,4,7>{\node(01) at (1,4) {0};}
\action<visible@2-|alert@2,5,8>{\node(02) at (2,4) {0};}
\action<visible@2-|alert@2,6,9>{\node(03) at (3,4) {0};}
\action<visible@2-|alert@2,7,10>{\node(04) at (4,4) {0};}
\action<visible@2-|alert@2,8>{\node(05) at (5,4) {0};}
\action<visible@2-|alert@2,9>{\node(06) at (6,4) {0};}
\action<visible@2-|alert@2,10>{\node(07) at (7,4) {0};}

\action<visible@1->{\node at (-1,3) {$3$};}
\action<visible@3-|alert@3,11,17>{\node(10) at (0,3) {1};}
\action<visible@4-|alert@4,12,18>{\node(11) at (1,3) {0};}
\action<visible@5-|alert@5,13>{\node(12) at (2,3) {0};}
\action<visible@6-|alert@6,14>{\node(13) at (3,3) {1};}
\action<visible@7-|alert@7,15>{\node(14) at (4,3) {0};}
\action<visible@8-|alert@8,16>{\node(15) at (5,3) {0};}
\action<visible@9-|alert@9,17>{\node(16) at (6,3) {0};}
\action<visible@10-|alert@10,18>{\node(17) at (7,3) {0};}

\action<visible@1->{\node at (-1,2) {$6$};}
\action<visible@11-|alert@11,19,21>{\node(00) at (0,2) {1};}
\action<visible@12-|alert@12,20,22>{\node(11) at (1,2) {0};}
\action<visible@13-|alert@13,21,23>{\node(12) at (2,2) {0};}
\action<visible@14-|alert@14,22,24>{\node(13) at (3,2) {1};}
\action<visible@15-|alert@15,23,25>{\node(14) at (4,2) {0};}
\action<visible@16-|alert@16,24,26>{\node(15) at (5,2) {0};}
\action<visible@17-|alert@17,25>{\node(16) at (6,2) {1};}
\action<visible@18-|alert@18,26>{\node(17) at (7,2) {0};}

\action<visible@1->{\node at (-1,1) {$2$};}
\action<visible@19-|alert@19,27,30>{\node(00) at (0,1) {1};}
\action<visible@20-|alert@20,28,31>{\node(11) at (1,1) {0};}
\action<visible@21-|alert@21,29,32>{\node(12) at (2,1) {1};}
\action<visible@22-|alert@22,30,33>{\node(13) at (3,1) {1};}
\action<visible@23-|alert@23,31,34>{\node(14) at (4,1) {0};}
\action<visible@24-|alert@24,32>{\node(15) at (5,1) {1};}
\action<visible@25-|alert@25,33>{\node(16) at (6,1) {1};}
\action<visible@26-|alert@26,34>{\node(17) at (7,1) {0};}

\action<visible@1->{\node at (-1,0) {$3$};}
\action<visible@27-|alert@27>{\node(00) at (0,0) {1};}
\action<visible@28-|alert@28>{\node(11) at (1,0) {0};}
\action<visible@29-|alert@29>{\node(12) at (2,0) {1};}
\action<visible@30-|alert@30>{\node(13) at (3,0) {1};}
\action<visible@31-|alert@31>{\node(14) at (4,0) {0};}
\action<visible@32-|alert@32>{\node(15) at (5,0) {1};}
\action<visible@33-|alert@33>{\node(16) at (6,0) {1};}
\action<visible@34-|alert@34>{\node(17) at (7,0) {0};}
\end{tikzpicture}
\end{dynprogtable}
\end{column}
\end{columns}
\end{frame}

\begin{frame}{Поиск подмножества с заданной суммой}
\framesubtitle{Псевдополиномиальность алгоритма, основанного на ДП}

\begin{given}
$n\in\bZpositiv$,\quad $a_i\in\bZpositiv$\quad($1\le i\le n$),\quad
$m\in\bZpositiv$.
\end{given}

\pause

\begin{block}{Величины $\Max$ и $\Length$ для данной задачи}
$\displaystyle\Max(I)=\max(m,n,\max_{1\le i\le n}a_i)$;\\
$\displaystyle\Length(I)
=\lceil\log_2 n+1\rceil+\lceil\log_2 m+1\rceil
+\sum_{i=1}^n\lceil\log_2 a_i+1\rceil$.
\end{block}

\pause

\begin{block}{Псевдополиномиальность, но не полиномиальность}
Время работы алгоритма пропорционально $nm$.\\
$nm \le \Max(I)\cdot\Length(I)$.\\
$nm$ нельзя ограничить сверху многочленом от $\Length(I)$.
\end{block}

\end{frame}

\subsection{Задача о рюкзаке}

\begin{frame}{Задача о рюкзаке}

\begin{myproblem}
\begin{description}
\item[Дано:] 
$n\in\bZpositiv$~--- число предметов;\\
$p_i\in\bZpositiv$\quad($1\le i\le n$)~--- стоимости предметов;\\
$w_i\in\bZpositiv$\quad($1\le i\le n$)~--- веса предметов;\\
$c\in\bZpositiv$~--- ограничение на суммарный вес.
\item[Найти:]
$I\subset\{1,\ldots,n\}\colon\quad
\sum_{i\in I}w_i\le c,\quad
\sum_{i\in I}p_i\to\max$.
\end{description}
\end{myproblem}

\end{frame}

\subsection{Разбиение на классы похожести с минимизацией мусора}

\begin{frame}{Разбиение на классы похожести с минимизацией мусора}
\framesubtitle{Отношение <<похожести>> целых чисел}

\begin{block}{Отношение $r$-похожести на множестве $\bZ$}
Пусть $r\in\bZpositiv$.
Определим бинарное отношение $\mysim{r}$ на $\bZ$:
\[
  x\mysim{r}y\qquad\iff\qquad |x-y|\le r.
\]
Рефлексивно и симметрично. На всём $\bZ$ не является транзитивным:
\[
  0\mysim{r}r,\quad r\mysim{r}2r,\quad 0\notmysim{r}2r.
\]
\end{block}

\pause

\begin{block}{Пример таких $r\in\bZpositiv$ и $A\subset\bZ$,
что $\mysim{r}$ транзитивно на $A$}
Отношение $\mysim{5}$ транзитивно на $\{3,4,10,11,15\}$.\\
Классы эквивалентности: $\{3,4\}$ и $\{10,11,15\}$.
\end{block}

\end{frame}

\begin{frame}{Разбиение на классы похожести с минимизацией мусора}
\framesubtitle{Формулировка задачи}

\begin{myproblem}
\begin{description}
\item[Дано:]
$r\in\bZpositiv$, $n\in\bZpositiv$, $a_i\in\bZ$ ($1\le i\le n$).
\item[Найти:]
$G\subset\{1,\ldots,n\}\colon$\\
$\mysim{r}$ транзитивно на
$\{a_i\colon i\in\{1,\ldots,n\}\setminus G\}$,\\
$|G|\to\min$.
\end{description}
\end{myproblem}

\pause

\begin{myexample}
\begin{description}
\item[Дано:]
$r=10$, $n=8$, $a=(1,1,9,11,20,22,30,40)$.
\item[Ответ:]
$G=\{4,6\}$\\
($\mysim{10}$ транзитивно на $\{1,9,20,22,40\}$).
\end{description}
\end{myexample}

\end{frame}


\section{Задачи, NP-полные в сильном смысле}

\subsection{Определение задач, NP-полных в сильном смысле}

\begin{frame}{Определение задач, NP-полных в сильном смысле}

\begin{block}{Подзадача с p-ограниченными числовыми параметрами}
Пусть $\Pi$~--- задача с числовыми параметрами, $p\in\bZ[x]$.\\
$\Pi_p=\{I\in\Pi\colon \Max(I)\le p(\Length(I))\}$.
\end{block}

\pause

\begin{mydefinition}
Пусть $\Pi$~--- задача с числовыми параметрами.\\
$\Pi$ называется \emph{NP-полной в сильном смысле},\\
если $\Pi\in\NPclass$ и существует такой многочлен $p\in\bZ[x]$,\\
что задача $\Pi_p$ является NP-полной.
\end{mydefinition}

\pause

\begin{block}{Связь с псевдополиномиальными алгоритмами}
Если $\NPclass\ne\Pclass$ и задача $\Pi$
является $\NPclass$-полной в сильном смысле,\\
то задачу $\Pi$ нельзя решить псевдополиномиальным алгоритмом.
\end{block}

\end{frame}

\subsection{Задача коммивояжёра}

\begin{frame}{Задача коммивояжёра}
\framesubtitle{Формулировка задачи}

\begin{mydefinition}
\emph{Гамильтонов цикл}~--- цикл,
проходящий через каждую вершину графа ровно один раз.
\end{mydefinition}

\pause

\begin{myproblem}
\begin{description}
\item[Дано:] полный неориентированный граф $G=(V,C_V^2)$\\
функция $w\colon C_V^2\to\bZpositiv$ (длины рёбер),\\
$s\in\bZpositiv$.
\item[Вопрос:] \qu\ $\exists$ в $G$ гамильтонов цикл, длина которого $\le s$\ ?
\end{description}
\end{myproblem}

\pause

\begin{block}{NP-полнота в сильном смысле}
Задача коммивояжёра NP-полная даже при ограничении $w_{i,j}\le 2$.
\end{block}

\end{frame}

\subsection{3-разбиение}

\begin{frame}{3-разбиение}

\begin{myproblem}
\begin{description}
\item[Дано:]
$m\in\bZ^+$, $b\in\bZ^+$,\\
$a_i\in\bZ^+$\quad($1\le i\le 3m$),\\
причём
$\displaystyle\frac{b}{4}<a_i<\frac{b}{2}
\quad\forall i\in\{1,\ldots,3m\}$ и
$\displaystyle\sum_{i=1}^{3m}a_i=mb$.
\item[Вопрос:]
\qu\ $\exists$ разбиение $P=\{P_1,\ldots,P_m\}$ множества $A\colon$\\
$\forall k\in\{1,\ldots,m\}\quad\sum_{i\in P_k}a_i=b$\ ?
\end{description}
\end{myproblem}

\pause

\begin{block}{NP-полнота в сильном смысле}
$3$-разбиение является NP-полной задачей при ограничении $a_i\le 12^4 m^4$.
\end{block}

\end{frame}

\begin{frame}{Источники}

\begin{thebibliography}{2}

\beamertemplatearticlebibitems
\bibitem{Wikipedia}
Википедия, свободная энциклопедия.\\
\url{http://en.wikipedia.org} и \url{http://ru.wikipedia.org}.


\beamertemplatebookbibitems
\bibitem{GareyJohnson}
\textsc{Гэри~М., Джонсон~Д.}
Вычислительные машины и труднорешаемые задачи.~---
М.: <<Мир>>, 1982.
\end{thebibliography}

\end{frame}

\end{document}
