Please wait
#algorithm #russian #homework
{}\documentclass{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{tikz}
\usepackage{amscd}
\usepackage[inline]{enumitem}
\usepackage{amsmath}
\usepackage{dsfont}
\usepackage{indentfirst}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{epigraph}
\usepackage{icomma}
\renewcommand{\thesection}{\arabic{section}}
\renewcommand{\baselinestretch}{1.0}
\renewcommand\normalsize{\sloppypar}
\newcommand{\BP}{\mathbb{P}}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.1in}
\setlength{\oddsidemargin}{-0.3in}
\setlength{\textwidth}{7in}
\setlength{\parindent}{0ex}
\setlength{\parskip}{1ex}
\title{Домашнее задание на третью неделю}
\author{Бельденова Камила, 675}
\date{28 февраля 2018}
\begin{document}
\maketitle
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
1&2&4&5&6&7&8&9&$\Sigma$\\
\hline
&&&&&&&&\\
\hline
\end{tabular}
\\\\
\begin{enumerate}
\item[\textbf{Задача 1.}] Докажите следующие свойства полиномиальной сводимости:
($i$) Рефлексивность: $A\leq_p A$; транзитивность: если $A\leq_p B$ и $B\leq_p C$, то $A\leq_p C$;
($ii$) Если $B\in\mathcal{P}$ и $A\leq_p B$, то $A\in\mathcal{P}$;
($iii$) Если $B\in\mathcal{NP}$ и $A\leq_p B$, то $A\in\mathcal{NP}$.
\smallskip
\begin{center}
Решение
\end{center}
($i$) Рефлексивность довольно очевидна. Для этого нам достаточно рассмотреть функцию $f(x)=x$ (вычислимая за полиномиальное время функция). Видно, что $x \in A \Leftrightarrow f (x)=x \in A$, а значит согласно определению $A\leq_p A$.\\
Теперь докажем транзитивность. Если $f$ сводит $A$ к $B$, а $g$ сводит $B$ к $C$, то $f \circ g$ сводит $A$ к $C$ : $x \in A \Leftrightarrow f(x) \in B \Leftrightarrow g(f(x)) \in C $. При этом если и $f$, и $g$ вычисляются за полиномиальное время, то $f \circ g$ также вычисляется за полиномиальное время.\\
($ii$) Характеристическая функция $\chi_A$ представляется как композиция $\chi_B \circ f$. Если $B \in P$, то $\chi_B$ вычисляется за полиномиальное время, а если $A\leq_p B$, то соответсвующая $f$ также вычисляется за полиномиальное время. Это значит, что их композиция (т.~е. $\chi_A$) тоже вычисляется за полиномиальное время~$\Leftrightarrow A \in \textbf{P}$.\\
($iii$) Если $\chi_B$ вычисляется недетерминированной машиной за полиномиальное время, а $f$ (детерминированно) вычисляется за полиномиальное время, то $\chi_A=\chi_B \circ f$ тоже вычисляется недетерминированной машиной за полиномиальное время.\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 2.}] Докажите, что следующие языки принадлежат классу $\mathcal{P}$. Считайте, что графы заданы матрицами смежности.
($i$) Язык двудольных графов, содержащих не менее $2018$ треугольников (троек попарно смежных вершин);
($ii$) Язык несвязных графов без циклов;
($iii$) Язык квадратных $\{0; 1\}$-матриц порядка $n\geq 3000$, в которых есть квадратная подматрица порядка $n-2018$, заполненная одними единицами.
($iv$) Язык $L(a, m)$, зависящий от параметров $a, m \in \mathbb{N}$, определяемый следующим образом: $$L = \{x_0, x_1, \ldots\}; x_0 = a ( mod~m ); x_{i+1} = x_i^{2018} ( mod~m ).$$
\smallskip
\begin{center}
Решение
\end{center}
($i$) Вспомним определение двудольного графа. Двудольный граф~---~граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств. Согласно определению в двудольных графах не может быть трех попарно смежных вершин, а значит множество графов, имеющих не менее $2018$ треугольников, пусто $\Rightarrow$ язык принадлежит классу $\mathcal{P}$.\\
($ii$) Проверим граф на связность с помощью поиска в глубину, сложность работы составляет $O(M)$, то есть линейна по количеству ребер. Произведём серию поисков в глубину в графе, т.~е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе~---~в чёрный. Если после прохода алгоритма не все вершины окрашены в какой-то из цветов, то граф несвязный, значит можно продолжать его исследовать, иначе~---~он не принадлежит языку. Для каждого связного куска проверим граф на ацикличность, это также проверяется с помощью поиска в глубину. Если в течение поиска в глубину мы пытаемся пойти в серую вершину, то это означает, что мы нашли цикл (если граф неориентированный, то случаи, когда в течение поиска в глубину из какой-то вершины мы пытаемся пойти в предка, не считаются), и граф не принадлежит нашему языку.
Язык принадлежит классу $\mathcal{P}$.\\
($iii$) Будем проверять матрицу "лобовым" алгоритмом:\\
\begin{tabbing}
ЦИКЛ $i,j = 1..2018$\\
~~~~start:\\
~~~~count$ = 0$;\\
~~~~ЦИКЛ $k,l = 1..(n - 2018)$\\
~~~~ЕСЛИ $(A[k+i,l+j] == 1)$ \\
~~~~count $+=1$ \\
~~~~ИНАЧЕ GOTO(start)\\
ЕСЛИ count == (n-2018)*(n-2018)\\
~~~~ОТВЕТ(Принадлежит языку)\\
ИНАЧЕ\\
~~ОТВЕТ(Не принадлежит языку)\\
\end{tabbing}
Как видим, алгоритм содержит $2$ цикла, работающих в худшем случае по $(n-2018)$ раз, внутри которых происходят операции $O(1)$, значит, итоговая сложность алгоритма~---~$O(n^2)$.
\\
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 4.}] Докажите, что классы $\mathcal{P}$ и $\mathcal{NP}$ замкнуты относительно операции $*$~---~звезды Клини (была в ТРЯПе). Для языка $NP$ приведите также и сертификат принадлежности слова из $\Sigma^*$ языку $L^*$, где $L\in\mathcal{NP}$.
\smallskip
\begin{center}
Решение
\end{center}
\textbf{(1)} Сначала докажем замкнутость класса $\mathcal{P}$ относительно заданной операции: \\
Пусть $p$~---~разрешитель языка $L$, работающий за полиномиальное время. Построим разрешитель $q$ для языка $L^{*}:$
\begin{tabbing}
$n = |w|$;\\
endPoses = $\{0\}$~---~места, где могут заканчиваться слова из $L$\\
for(i=1..n)\\
~~~~for $(j \in$ endPoses)\\
~~~~~~~~if(p(w[j+1..i])) \{\\
~~~~~~~~~~~~if $(i=n)$\\
~~~~~~~~~~~~~~~~return true;\\
~~~~~~~~~~~~endPoses $\cup = \{i\}$\\
~~~~~~~~\}\\
return false;\\
\end{tabbing}
Худшая оценка времени работы разрешителя $q$ равна $n^2O(p(w))$. Т.~к. в множестве endPoses может быть максимум $n$ элементов, значит, итерироваться по множеству можно за $O(n)$, если реализовать его на основе битового массива, например. При этом операция добавления элемента в множество будет работать за $O(1)$. Итого, разрешитель $q$ работает за полиномиальное время (т.~к. произведение полиномов есть полином). Значит, $L^{*} \in P$.
\textbf{(2)} Теперь докажем замкнутость класса $\mathcal{NP}$ относительно заданной операции: \\
Предъявим предикат $M(x,y)$, который проверяет правильность сертификата $y$ для языка $L^{*}$.\\
Сертификатом $y^{*}$ для слов из $L^{*}$ будут:\\
$(i)$ позиции, на которых находятся начала слов, принадлежащих $L$;\\
$(ii)$ сертификаты $y$ для каждого из этих слов.\\
Далее нужно проверить, что каждая часть входного слова принадлежит языку $L$, это делается предикатом $R(x_{i},y_{i})$, что является $\mathcal{NP}$ задачей (по условию); проход по всем подсловам~---~линейная операция от длинны входа $\Rightarrow$ полученный предикат~---~$\mathcal{NP}$.
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 5.}] Покажите, что классу $NP$ принадлежит язык несовместных систем линейных уравнений с целыми коэффициентами от $2018$ неизвестных, и постройте соответствующий сертификат $y$ и проверочный предикат $R(x, y)$. Один из возможных способов заключается в применении теоремы Фредгольма.
\smallskip
\begin{center}
Решение
\end{center}
Вспомним, что критерием совместности СЛАУ является равенство рангов расширенной и исходной матриц.\\
Сертификатом будет число линейно независимых (далее ЛНЗ) строк в обоих матрицах, их номера и разложения по ним остальных строк.\\
Предикатом $R(x,y)$ будет проверка на то, что данные в сертификате строки действительно являются ЛНЗ, приведение матрицы к верхнетреугольному виду и проверка на наличие "$0$" на главной диагонали. Если сертификат верен, то нужно сравнить количество ЛНЗ строк в исходной и расширенной матрицах. Если оно не одинаково, то система несовместна.
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 6.}] Покажите, что язык разложения на множители $$L_{factor} = \{(N,M)\in\mathbb{Z}^2 \mbox{ }|\mbox{ } 1<M<N\mbox{ и } N \mbox{ имеет делитель } d, 1<d\leq M\}$$ лежит в пересечении $\mathcal{NP}\cap co-\mathcal{NP}$.
\smallskip
\begin{center}
Решение
\end{center}
Покажем, что данный язык $\mathcal{L} \in \mathcal{P} \Rightarrow \mathcal{L} \in \mathcal{NP}\cap co-\mathcal{NP}$.\\
Алгоритм проверки принадлежности слова к $L_{factor}$ такой:\\
\begin{tabbing}
for$(i = 2; i < M; i++) \{$\\
~~~~$if (N \mod i == 0) \{$\\
~~~~~~~~printf("Слово принадлежит $L_{factor}$");\\
~~~~~~~~return OK;\\
~~~~\} \\
\} \\
printf("Слово не принадлежит $L_{factor}$");\\ return BAD;\\
\end{tabbing}
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 7.}] Язык ГП состоит из описаний графов, имеющих гамильтонов путь. Язык ГЦ состоит из описаний графов, имеющих гамильтонов цикл (проходящий через все вершины, причем все вершины в этом цикле, кроме первой и последней, попарно различны). Постройте явные полиномиальные сводимости ГЦ к ГП и ГП к ГЦ.
\smallskip
\begin{center}
Решение
\end{center}
Вспомним определение полиномиальной сводимости: $L_1 \leq_p L_2$, если существует всюду определенная функция $f: \{0,1\}^{*} \rightarrow \{0,1\}^{*} $, вычислимая за полиномиальное время, такая что $x \in L_1 \Leftrightarrow f (x) \in L_2$\\
Рассмотрим сводимость ГЦ в ГП:\\
Пусть нам задан граф $x$, в котором есть гамильтонов цикл, тогда найдем этот цикл и построим граф $f(x)$ отбрасыванием одного ребра, учавствующего в построении цикла; таким образом получим граф, в котором будет самонеперсекающийся путь, проходящий через все вершины. Алгоритм нахождения гамильтонова цикла принадлежит $\mathcal{NP}$ (сертификатом будет последовательность вершин, образующая гамильтонов цикл, проверка линейна).\\
В обратную сторону~---~сводимость ГП к ГЦ:\\
Аналогично, по заданному графу найдем в нем гамильтонов путь ($\mathcal{NP}$ задача), далее построим $f(x)$ добавлением к исходному графу одного ребра, соединяющего начальную вершину пути с конечной.\\
Т.~к. сводимость ГП к ГЦ~---~обратное сведение от ГЦ к ГП, то приведенное преобразование удовлетворяет определению сводимости.
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 8.}] Рассмотрим $n$ точек плоскости, заданных своими парами декартовых координат $(x, y)$. Требуется найти их выпуклую оболочку, т.~е. наименьшее по включению выпуклое множество, содержащее все эти $n$ точек. Выпуклой оболочкой будет некоторый многоугольник, причем все его вершины~---~некоторые из этих точек, а остальные лежат внутри. Вывести на экран нужно вершины этого многоугольника по порядку обхода периметра (начиная с любой из них).
Рассмотрим модель вычисления, в которой за $1$ такт можно делать одну из трёх операций: сравнивать два числа, складывать числа и возводить число в квадрат. Покажите, что в этой модели вычислений задача сортировки массива сводится к задаче построения выпуклой оболочки $n$ точек плоскости за линейное время.
\smallskip
\begin{center}
Решение
\end{center}
Мы рассмотрим метод Грэхема с улучшениями Эндрю. С его помощью можно построить выпуклую оболочку за время $O(n \log n)$ с использованием только операций сравнения, сложения и умножения. Алгоритм является асимптотически оптимальным (доказано, что не существует алгоритма с лучшей асимптотикой).\\
Сам алгоритм:\\
Найдём $A$ и $B$~---~самую левую и самую правую точки (если таких точек несколько, то возьмём самую нижнюю среди левых, и самую верхнюю среди правых). Понятно, что и $A$, и $B$ обязательно попадут в выпуклую оболочку. Дальше, проведём через эти точки прямую $AB$,тем самым разделив множество всех точек на верхнее и нижнее подмножества $S_1$ и $S_2$ (точки, лежащие на прямой, можно отнести к любому из подмножеств~---~они всё равно не войдут в оболочку). Точки $A$ и $B$ отнесём к обоим множествам. Теперь построим для $S_1$ верхнюю оболочку, а для $S_2$~---~нижнюю, и объединив их, получим ответ. Чтобы получить, например, верхнюю оболочку, нужно отсортировать все точки по абсциссе, потом пройтись по всем точкам, рассматривая на каждом шаге кроме самой точки две предыдущие, вошедшие в оболочку. Если текущая тройка точек образует не правый поворот (это легко проверить с помощью понятия "ориентированной площади"), то ближайшего соседа нужно удалить из оболочки. В итоге, останутся только точки, входящие в выпуклую оболочку.\\
Итак, алгоритм состоит в \textbf{сортировке всех точек} по абсциссе и двух (в худшем случае) обходах всех точек, т.~е. требуемая асимптотика $O (n \log n)$ достигнута.\\
Но (по крайней мере, я так поняла), так как все операции, на которые опирается наш алгоритм (например, поиск самой левой и самой правой точек в начале представленного алгоритма), по условию занимают один такт для каждого элемента, то всего получаем $O(n)$ в нашей модели вычисления. Получили,что в этой модели вычислений задача сортировки массива свелась к задаче построения выпуклой оболочки $n$ точек плоскости за линейное время.
\end{enumerate}
\begin{enumerate}
\item[\textbf{Задача 9.}] Пусть $A\in\mathcal{NP}-complete$. Пусть машина имеет дополнительную функцию (оракул) за $1$ такт получать ответ, лежит ли слово $x$ в языке $A$. Тогда существует полиномиальный алгоритм, решающий задачу поиска для $A$. Докажите это утверждение.
\smallskip
\begin{center}
Решение
\end{center}
Есть такая лемма:\\
Пусть языки $A$ и $B$ лежат в $\mathcal{NP}$ и задаются верификаторами $W_{A}$ и $W_{B}$ соответсвенно. Пусть также $A$ сводится по Карпу к $B$. Тогда существуют верификаторы $V_{A}$ и $V_{B}$, для которых также имеет место сводимость по Левину.\\
Теперь приступим к доказательству утверждения.\\
В силу указанной леммы можно считать, что и $A$ сводится к $3SAT$, и $3SAT$ сводится к $A$ в смысле Левина. В большинстве случаев (в том числе в теореме Кука–Левина) это получается и без дополнительных конструкций. Поэтому достаточно свести $A$ к $3SAT$, решить задачу поиска для $3SAT$ и свести результат обратно.\\
Пусть дана формула $\varphi$, зависящая от переменных $p_1, \ldots p_n$. Вначале можно проверить выполнимость $\varphi$ (при помощи оракула), и если формула невыполнима, такой ответ и вернуть. Если же формула выполнима, рассмотрим формулы $\varphi_1'$ и $\varphi_1''$, полученные из $\varphi$ фиксацией значений $p_1= 0$ и $p_1 = 1$ соответственно. Хотя бы одна из них будет выполнима, какая именно, можно найти при помощи двух запросов к оракулу (или даже одного). Обозначим выполнимую формулу через $\varphi_1$ и применим к ней ту же процедуру рекурсивно. Так будут определяться значения всех переменных, пока не останется только одна. Это будет база рекурсии: значение последней переменной можно найти непосредственной подстановкой обоих вариантов.
\end{enumerate}
\end{document}
Our gallery is the easiest way to put your LaTeX templates, examples and articles online. Just create a free project and use the publish menu. It only takes a couple of clicks!
The LaTeX templates, examples and articles in the Overleaf gallery all come from our amazing community.
New content is added all the time. Follow us on twitter for the highlights!