Добавлеие 4 и 5 лабораторныхHEADmaster

1 files changed, 120 insertions, 0 deletions

diff --git a/reports/lab4/lab4.tex b/reports/lab4/lab4.tex
new file mode 100644
index 0000000..b4d2a4a
--- /dev/null
+++ b/reports/lab4/lab4.tex
@@ -0,0 +1,120 @@
+\documentclass[spec, och, labwork]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+
+\begin{definition}
+    NP-полная задача "--- в теории алгоритмов задача с ответом <<да>> или
+    <<нет>> из класса NP, к которой можно свести любую другую задачу из этого
+    класса за полиномиальное время (то есть при помощи операций, число которых
+    не превышает некоторого полинома в зависимости от размера исходных данных).
+    Таким образом, NP-полные задачи образуют в некотором смысле подмножество
+    <<типовых>> задач в классе NP: если для какой-то из них найден
+    <<полиномиально быстрый>> алгоритм решения, то и любая другая задача из
+    класса NP может быть решена так же <<быстро>>.
+\end{definition}
+
+\begin{definition}
+    Алфавитом называется всякое конечное множество символов (например, $\{0,
+    1\}$ или $\{a, b, c\}$). Множество всех возможных слов (конечных строк,
+    составленных из символов этого алфавита) над некоторым алфавитом $\Sigma$
+    обозначается $\Sigma_*$. Языком $L$ над алфавитом $\Sigma$ называется всякое
+    подмножество множества $\Sigma_*$, то есть $L \subset \Sigma_*$.
+\end{definition}
+
+\begin{definition}
+    Пусть $L_1$ и $L_2$ "--- два языка над алфавитом $\Sigma$. Язык $L_1$
+    называется сводимым (по Карпу) к языку $L_2$, если существует функция, $f :
+    \Sigma_* \to \Sigma_*$, вычислимая за полиномиальное время, обладающая
+    следующим свойством: $x \in L_1$ тогда и только тогда, когда $f(x) \in L_2$.
+    Сводимость по Карпу обозначается как $L_1 \leq_p L_2$ или $L_1 \propto L_2$.
+\end{definition}
+
+\begin{definition}
+    Язык $L_2$ называется NP-трудным, если любой язык из класса NP сводится к
+    нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в
+    классе NP.
+\end{definition}
+
+Неформально говоря, то что задача A сводится к задаче B, означает, что задача A
+«не сложнее» задачи B (так как, если мы можем решить B, то можем решить и A.
+Таким образом, класс NP-трудных задач включает NP-полные задачи и задачи,
+которые <<сложнее>> их (то есть те задачи, к которым могут быть сведены
+NP-полные задачи). Класс NP включает NP-полные задачи и задачи, которые «легче»
+их (то есть те задачи, которые сводятся к NP-полным задачам).
+
+Из определения следует, что, если будет найден алгоритм, решающий некоторую
+(любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в
+классе P, то есть будут решаться за полиномиальное время.
+
+\begin{definition}
+    Тавтологией называется булева формула, принимающая значение 1 на всех
+    наборах значений её переменных.
+\end{definition}
+
+Теорема Кука "--- Левина (также просто теорема Кука) утверждает, что задача о
+выполнимости булевой формулы в КНФ (ВЫП) является NP-полной.
+
+Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной
+работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных
+задач. Независимо в то же время эта теорема была доказана советским математиком
+Леонидом Левиным.
+
+В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к
+ВЫП. С. Кук (S. Cook) определил класс NP задач распознавания свойств следующим
+образом. Задача принадлежит классу NP, если:
+\begin{enumerate}
+    \item
+        решением задачи является один из двух ответов: <<да>> или <<нет>>
+        (задача распознавания свойств);
+    \item
+        требуемый ответ может быть получен на недетерминированном вычислительном
+        устройстве за полиномиальное время.
+\end{enumerate}
+
+Этот класс, как позже показал Р. Карп (R. Karp) в свою очередь содержит в себе
+другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые
+в пределах этого класса одна к другой.
+
+После появления результатов Кука была доказана NP-полнота для множества других
+задач. При этом чаще всего для доказательства NP-полноты некоторой задачи
+приводится полиномиальное сведение задачи ВЫП к данной задаче, возможно в
+несколько шагов, то есть с использованием нескольких промежуточных задач.
+
+\begin{theorem}
+    ВЫП "--- язык булевых формул из $n$ переменных, для которых существует
+    подстановка, при которой формула истинна.
+
+    \begin{equation*}
+        \text{ВЫП} = \{ \varphi ~ | ~ \exists ~ x : \varphi(x) = 1 \}
+    \end{equation*}
+\end{theorem}
+\begin{proof}
+    $\text{ВЫП} \in \text{NP}$, потому что можно написать недетерминированную
+    программу $p$, которая распознает язык ВЫП. Она будет недетерминированно
+    выбирать подстановку, проверять, истинна ли формула при такой подстановке, и
+    выдавать ответ.
+\end{proof}
+
+Сведения задачи ВЫП к задаче NP-полноты языка, состоящего из булевых функций, не
+являющихся тавтологиями можно добиться с помощью вычислимой полиномиальной
+функции.
+
+Допустим, с помощью некоторой функции $\varphi(x_1, \dots, x_n, \dots)$ можно
+получить кортеж $(0, 1, 1, 1, \dots)$. Зададим функцию $\nu(x_1, \dots, x_n,
+\dots)$, что для такого входа мы будем получать все кортежи вида $(1, 0, 0, 0,
+\dots)$, $(0, 1, 0, 0, \dots)$ и т.д.
+
+Для кортежей с большим количеством нулей, функция $\nu$ задаётся аналогичным
+образом.
+
+Получаем, что задача имеет сложность
+\begin{equation*}
+    \sum_{i = 0}^\infty C_n^i \cdot \sum_{i = 0}^\infty C_n^{n - i} =
+    \sum_{i = 0}^\infty C_n^i \cdot C_n^{n - i} =
+    \sum_{i = 0}^\infty (C_n^i)^2
+\end{equation*}
+где $C_n^k$ "--- биномиальный коэффициент.
+
+\end{document}