 \documentclass[12pt, leqno]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}        % Кодировка входного документа;
                                    % при необходимости, вместо cp1251
                                    % можно указать cp866 (Alt-кодировка
                                    % DOS) или koi8-r.

\usepackage[english,russian]{babel} % Включение русификации, русских и
                                    % английских стилей и переносов
%%\usepackage{a4}
%%\usepackage{moreverb}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol}
\usepackage{verbatim}
\usepackage{listings}
\usepackage{algorithm2e}

\usepackage{tabto} %Табуляция
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning,trees}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}
\usepackage{indentfirst}  % абзацный отступ после заголовка
\usepackage{enumitem} %Item tricks


%% \voffset-5mm
%% \def\baselinestretch{1.44}
\renewcommand{\theequation}{\arabic{equation}}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}}
\newtheorem{Lemma}{Лемма}
\theoremstyle{definiton}
\newtheorem{Remark}{Замечание}
%%\newtheorem{Def}{Определение}
\newtheorem{Claim}{Утверждение}
\newtheorem{Cor}{Следствие}
\newtheorem{Theorem}{Теорема}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}
\theoremstyle{definition}
\newtheorem{Example}{Пример}

%% \newenvironment{Example} % имя окружения
%% {\par\noindent{\bf Пример.}} % команды для \begin
%% {\hfill$\scriptstyle\qed$} % команды для \end






%\date{22 июня 2011 г.}
\let\leq\leqslant
\let\geq\geqslant
\def\MT{\mathrm{MT}}
%Обозначения ``ажуром''
\def\BB{\mathbb B}
\def\CC{\mathbb C}
\def\RR{\mathbb R}
\def\SS{\mathbb S}
\def\ZZ{\mathbb Z}
\def\NN{\mathbb N}
\def\FF{\mathbb F}
%греческие буквы
\let\epsilon\varepsilon
\let\es\varnothing
\let\eps\varepsilon
\let\al\alpha
\let\sg\sigma
\let\ga\gamma
\let\ph\varphi
\let\om\omega
\let\ld\lambda
\let\Ld\Lambda
\let\vk\varkappa
\let\Om\Omega
\def\first{\mathrm{ FIRST} }
\def\follow{\mathrm{ FOLLOW} }
\let\yield\Rightarrow
\def\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\let\w\omega

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}
\def\PP{{\mathsf{P}}}
\def\NP{{\mathsf{NP}}}
\def\NPc{{\mathsf{NP}}\text{-}{\rm c}}
\def\coNP{{\rm co}\text{-}{\mathsf{NP}}}
\def\DTIME{{\mathsf{DTIME}}}
\def\NTIME{{\mathsf{NTIME}}}
\def\HALT{{\rm{HALT}}}
\def\SAT{{\rm{SAT}}}
\def\3SAT{{\rm{3\text{-}SAT}}}
\def\2SAT{{\rm{2\text{-}SAT}}}
\def\UNSAT{{\rm{UNSAT}}}
\def\LL{{\mathrm{LL}}}
\def\poly{{\rm{poly}}}
\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .  }\setcounter{subproblem}{0} }
\def\prp{\medskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }
\def\prstar{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem^*}\negmedspace .$  }\setcounter{subproblem}{0} }
\def\prdag{\medskip\noindent\stepcounter{problem}{\bf Задача $\bf{\theproblem}^{\dagger}$.  }\setcounter{subproblem}{0} }
\def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem .  }\setcounter{subproblem}{0} }
%\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem .  } }
%\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .*   }
\def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem .  } }
%прочее
\def\quotient{\backslash\negthickspace\sim}

\begin{document}
\centerline{\LARGE Задание 4}

\medskip

\begin{center}
	{\Large Сложность вычислений: классы $\PP$, $\NP$ и $\coNP$ }
\end{center}

\bigskip

{\bf Литература: }
\begin{enumerate}

\item Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. \\ {\it Алгоритмы. Построение и анализ. }\\  2-е изд. М.: Вильямс, 2005.

\item Sipser M. \\ {\it Introduction to the theory of computation}   

\item Arora S., Barak B. \\ {\it Computational Complexity: A Modern Approach}   

\item Hopcroft J., Ullman J.\\ {\it Introduction to Automata Theory, Languages, and Computation.}\\ 1-st edition, 1979.

\end{enumerate}


\emph{На всякий случай прежде всего обращу здесь внимание на то, что ближайший семинар пройдёт в понедельник 13 марта!}

Перед основным вспомогательным материалом, разделы которого вынесены в заглавие названия, я хочу напомнить базовые вещи из теории вычислений, раздел которой вы изучали в рамках курса <<теория формальных систем и алгоритмов>>. Этому посвящены первые два раздела данного задания.

Обращаю внимание, что в этих разделах приведены базовые определения, на обобщении которых мы определяем класс $\NP$ и полиномиальную $m$-сводимость. Задачи из этих разделов помечены символом $\dagger$ -- это означает, что они являются дополнительными и их можно не сдавать, однако их стоит прорешать, если на это хватает времени и сил. 

\section{Машины Тьюринга и формальные языки}

	Под формальным языком $L$ мы понимаем некоторое подмножество множества всех слов над алфавитом $\Sigma$. В этой теме слова «язык» и «задача» являются синонимами, поскольку речь идёт только о задачах распознавания, то есть задач проверки принадлежности слова языку. То есть задача перемножить два числа не является задачей в наших терминах в рамках этого раздела.
	
	Каждому языку мы ставим в соответствие машину Тьюринга, которая его распознаёт. 

\begin{Def} 

	\emph{Детерминированная Машина Тьюринга} $M$  имеет $l$ лент, $k$ головок, множество состояний $Q$, множество принимающих состояний $Acc \subset Q$,  входной алфавит $\Sigma$, функцию перехода $\delta : \Sigma^k\times Q \to \{0,+1,-1\}^k\times \Sigma^k\times Q  $ -- за такт работы машина меняет состояние, символы под каждой головкой и двигает каждую головку влево, вправо или оставляет её неподвижной. На машину могут быть наложены ограничения, например, полиномиальное время работы или полиномиальная память по входу. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово $x$. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово. 
		
\end{Def}


Будем говорить, что машина Тьюринга $M$ вычисляет функцию $M(x)$, которая равна $1$, в случае если машина $M$ на входе $x$ останавливается в принимающем состоянии, если машина $M$ на входе $x$ останавливается в не принимающем состоянии, то $M(x) = 0$, а если машина $M$ не останавливается на входе $x$, то функция $M(x)$ не определена.

$$
	M(x) = 
	\begin{cases}
		1, & M \text{ остановилась в принимающем состоянии на $x$;} \\
		0, & M \text{ остановилась в не принимающем состоянии на $x$;}\\ 
		\uparrow, & M \text{ не остановилась, функция не определена на $x$.}
	\end{cases}
$$


	 Машина $M$ \emph{принимает} язык $L$, если она принимает каждое слово из языка $L$, если машина $M$ принимает язык $L$ и к тому же все слова, принимаемые машиной $M$, лежат в языке $L$,  то будем говорить, что машина $M$ \emph{распознаёт} $L$. Язык, распознаваемый машиной $M$ будем обозначать $L(M)$.


\begin{Remark}
	Определение языка, распознаваемого машиной Тьюринга, при беглом взгляде кажется естественным, но на самом деле оно весьма коварно. На слова не из $L$ ограничений не накладывается, поэтому на них машина $M$ может и не останавливаться вовсе.
\end{Remark}


Языки, распознаваемые машинами Тьюринга, называются \emph{(рекурсив-но-)перечислимыми} языками или \emph{распознаваемыми} языками.

Будем говорить, что машина Тьюринга $M$ разрешает язык $L$, если она останавливается на всех входах и распознаёт язык $L$.

Языки разрешимые машинами Тьюринга образуют класс \emph{рекурсивных} языков, также называемыми \emph{разрешимыми}.
 


Если не оговорено противного, мы будем считать, что машина Тьюринга $M$ имеет одну ленту и одну головку.

\bigskip


Поскольку машины Тьюринга имеют конечное описание, то их описание можно закодировать. Будем обозначать $M_\alpha$ машину Тьюринга, описание которой закодирована строкой $\alpha$. Мы можем просто занумеровать все возможные описания машин Тьюринга и считать, что $\alpha$ -- натуральное число. Если же это неудобно, мы можем считать, что $\alpha$ есть просто строка, содержащая описание машины Тьюринга, и если описание некорректно, то будем считать, что $M_\alpha$ -- машина Тьюринга, распознающая пустой язык.


Из возможности кодирования описаний машин Тьюринга следует, что существует машина Тьюринга, которая получает на вход описание $\alpha$ и вход $x$ и проделывает работу машины $M_\alpha$ на входе $x$. Такую машину Тьюринга будем называть \emph{универсальной} и обозначать $UM$.


\section{Разрешимые и неразрешимые задачи}

Прежде чем говорить о сложности задачи надо доказать, что она разрешима. Это далеко не всегда так даже в очень естественных случаях.

\begin{Example} Пусть язык $L$ лежит в классе $\CFL$. Проверка условия $L \stackrel{?}{=} \Sigma^*$  -- неразрешимая задача.
\end{Example}
	
Одна из самых распространённых неразрешимых задач -- проблема останова. Под проблемой останова понимается язык $\HALT$ состоящий из описаний всех машин Тьюринга, останавливающихся на пустом входе.

\begin{Example}
	$$\HALT = \{ \alpha\, |\, M_\alpha(\eps) = 1 \} $$
\end{Example}

\upr Докажите что язык $ \HALT $ является неразрешимым. Если доказать самостоятельно не получается, обратитесь к литературе.

\bigskip

Язык $L$ называется \emph{перечислимым}, если существует такая МТ $M$, которая выводит все слова из языка. МТ $M$ может вообще говоря никогда не остановится, но если слово $w$ лежит в $L$, то машина $M$  должна вывести $w$ через некоторое, быть может очень большое, число тактов.


\upr Докажите, что данное здесь определение перечислимого языка согласовано с данным выше определением. 

\upr Докажите, что язык $\HALT$ является перечислимым.

\upr Докажите, что язык $L$ является разрешимым тогда и только тогда, когда языки $L$ и $\bar L$ перечислимы.


\prdag Докажите, что язык, состоящий из описаний МТ, не останавливающихся на некотором входе через более чем $2017$ шагов неразрешим.

\prdag Является ли разрешимым язык, состоящий из описаний МТ, которые делают меньше $2015$ шагов при обработке каждого входного слова?


Для того, чтобы доказать, что задача неразрешима, достаточно свести к ней неразрешимую задачу (например, $\HALT$). Напомним определение сводимости.

\begin{Def}
	Пусть для языка $A \subseteq \Sigma_1^*$ существует такая всюду-определённая вычислимая функция $f : \Sigma_1^* \to \Sigma_2^*$, что слово $x$ принадлежит $A$ тогда и только тогда, когда слово $f(x)$ принадлежит языку $B$. Будем говорить, что язык $A$ сводится к языку $B$ $m$-сводимостью и обозначать это как $A \leq_m B $. В формулах это выглядит как
%		$$ x \in A \iff f(x) \in B. $$
	
\end{Def}


\prp Верно ли, что разрешимый язык нельзя свести к неразрешимому? 


\section{Класс $\PP$}

Нас будет интересовать классификация языков. Под классом языков понимается некоторое множество языков. Как правило, классы языков задают ограничениями на модели вычислений, которые распознают языки из данного класса.

Если детерминированная машина Тьюринга $M$ распознаёт $L$, причём для каждого слова $x$ из $L$ она делает не более чем $O(n^c)$ тактов, то язык $L$ лежит в классе $\DTIME(O(n^c))$. Такую машину Тьюринга мы будем называть детерминированной полиномиальной или просто полиномиальной.

%\prp На семинаре я дал определение, в котором требовал остановки полиномиальной МТ на любом входе за полиномиальное число шагов. Докажите, что данное здесь определение эквивалентно определению с семинара. То есть, необходимо доказать, что множество языков, распознаваемых полиномиальными в этих двух смыслах машинами Тьюринга совпадают.


Класс $\PP$ состоит из объединения всех языков, лежащих в $\DTIME(O(n^c))$, то есть

$$
 \PP = \bigcup_{c \geq 0} \DTIME(O(n^c))
$$


\prdag Покажите, что в определении класса $\PP$ неважно сколько лент и головок у машины Тьюринга $M$. То есть, если язык $L$ распознаётся за полиномиальное время машиной Тьюринга $M$ с $k$ лентами и $l$ головками, то он распознаётся и некоторой машиной $M^\prime$ с одной лентой и одной головкой.

\bigskip

Оказывается, что разумные модели вычислений полиномиально-эквивалентны. Поэтому, когда нужно проверить, что язык принадлежит классу $\PP$, достаточно найти алгоритм на вашем любимом языке программирования, который разрешает язык за полиномиальное время.


\section{Недетерминированные машины Тьюринга}


Определение недетерминированной машины Тьюринга получается из определения детерминированной подобно тому как из определения ДКА получается определение НКА: достаточно заменить функцию переходов на отношение переходов и добавить  квантор существования в условие приёма слова. То есть, недетеринированная машина Тьюринга $M$ принимает слово $x$, если существует последовательность переходов, которая приводит машину $M$ на слове $x$ в принимающее состояние. 


\bigskip

\upr Покажите, что детереминированные и недетерминированные машины Тьюринга распознают один и тот же класс языков. 

\bigskip

Если недетерминированная машина Тьюринга $M$ распознаёт язык $L$, причём для каждого слова $x$ из $L$ она делает не более чем $O(n^c)$ тактов, то язык $L$ лежит в классе $\NTIME(O(n^c))$. Такую машину Тьюринга мы будем называть недетерминированной полиномиальной.

Таким образом, аналогично определению класса $\PP$, получим определение класса $\NP$:

$$
 \NP = \bigcup_{c \geq 0} \NTIME(O(n^c))
$$


\section{Класс $\NP$}

Приведём более наглядное эквивалентное определение класса $\NP$. Под записью $M(x,y)$ мы понимаем, что на вход 
машине $M$ подали строки $x$ и $y$, записанные через разделитель, например $M(x,y) = M(x\#y)$.

Напомним, что в случае когда мы рассматриваем соответствующую машине Тьюринга $M$ вычислимую функцию $M(\cdot)$ одного аргумента, запись $M(x) = 1$ означает, что машина $M$ принимает слово $x$ или что то же самое, что слово $x$ принадлежит языку, распознаваемому машиной $M$: $x \in L(M)$.

\begin{Def}
	Язык $L$ лежит в классе $\NP$, если существуют полином $p(n) : \NN \to \NN$ и (детерминированная) полиномиальная МТ $M$, такие что
	\begin{align*}
	 x \in L\Leftrightarrow \exists y \in \Sigma^{p(|x|)}\ M(x,y) = 1.
	\end{align*}
	Слово $y$ мы будем называть \emph{сертификатом} для слова $x$. 
\end{Def}

\upr Покажите, что два определения класса $\NP$ эквивалентны.

\prp Пусть мы не накладываем полиномиального ограничения на сертификат, но при этом машина $M$ является полиномиальной по длине входного слова $x$.
 

То есть, для языка $L$ есть машина $M(x,y)$ полиномиальная по длине входа $|x|$ и 
\begin{align*}
 x \in L\Leftrightarrow \exists y \in \Sigma^*\ M(x,y) = 1.
\end{align*}
Верно ли, что $L \in \NP$? Если да, то как найти полиномиальный по $x$ сертификат $y$?



\section{Сводимости}

Довольно часто в сложности вычислений мы сталкиваемся со следующей ситуацией: оказывается, что мы умеем решать задачу $A$, если мы уже умеем решать задачу $B$. Или наоборот, задача $B$ является сложной (или даже неразрешимой), если задача $A$ является сложной (неразрешимой).

Для описания таких отношений между языками мы пользуемся сводимостью. В этом задании мы будем говорить об $m$-сводимости или сводимости по Карпу.


\begin{Def}
	Пусть для языка $A \subseteq \Sigma_1^*$ существует такая всюду-определённая полиномиально-вычислимая функция $f : \Sigma_1^* \to \Sigma_2^*$, что слово $x$ принадлежит $A$ тогда и только тогда, когда слово $f(x)$ принадлежит языку $B$. Будем говорить, что язык $A$ сводится к языку $B$ полиномиальной $m$-сводимостью (сводимостью по Карпу) и обозначать это как $A \leq^p_m B $.
\end{Def} 

Для краткости, мы будем говорить вместо «сводится $m$-сводимостью» и «сводится полиномиальной $m$-сводимостью» «сводится» и «полиномиально сводится».

\upr Покажите, что если задача $\HALT$ сводится к задаче $A$, то задача $A$ является неразрешимой.

\upr Покажите, что если задача $A$ сводится полиномиально к задаче $B$ и задача $B$ лежит в классе $\PP$, то и задача $A$ лежит в классе $\PP$.

\bigskip

Задача $A$ является $\NP$-полной, если задача $A$ лежит в $\NP$ и любая задача $B \in \NP$ полиномиально сводится к $A$
Класс $\NP$-полных задач мы будем обозначать  $\NPc$. Формально

$$
 L \in \NPc \Leftrightarrow L \in \NP,\ \forall A \in \NP: A \leq^p_m L.
$$

Факт существования $\NP-$полных задач установили независимо друг от друга Левин и Кук. В ближайшее время изучение $\NP-$полных задач будет нашим основным полем деятельности.

Определение $\NP$-полного языка состоит из двух частей. Первую из них, о том, что любой язык из класса $\NP$ сводится к языку $A$ выделяют в отдельное определение -- такие языки называются $\NP$-трудными. Таким образом, язык $A$ является $\NP$-полным, если он является $\NP$-трудным и принадлежит классу $\NP$.


Помимо классов $\NP$ и $\NPc$ нас также будет интересовать класс $\coNP$, состоящий из языков, являющихся дополнением к языкам из $\NP$. То есть, если язык $L$ лежит в классе $\NP$, то язык $\bar L$ лежит в классе $\coNP$ 




	


\section{$\NP$-полные задачи}


Приведём пример $\NP$-полной задачи.

\begin{Example}
	Язык $\SAT$ состоит из всех выполнимых булевых формул $\phi$, заданных в конъюнктивной нормальной форме.
	$$
		\SAT = \{ \phi\,|\, \exists y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 1 \}
	$$
\end{Example}

\begin{known}[Кук, Левин]
	Язык $\SAT$ является $\NP$-полным.
\end{known}

\upr Изучить доказательство теоремы Кука-Левина. Ознакомиться с ним я рекомендую в книжке Сипсера.

На семинаре мы говорили о языке $\3SAT$, который состоит из выполнимых булевых формул, каждый дизъюнкт которых содержит ровно три переменных. Пример такой формулы:
$$ 
	\phi = (x_1\vee x_2 \vee \neg x_3) \wedge (\neg x_4 \vee x_5 \vee x_1).
$$

\prp Показать, что из теоремы Кука-Левина следует, что $\3SAT \in \NPc$

\prp Показать, что $\2SAT \in \PP$.

\bigskip

Также нам интересен класс $\coNP$, состоящий из языков, дополнение которых лежит в $\NP$.


Определим язык $\UNSAT$ как язык состоящий из невыполнимых булевых формул, заданных КНФ. То есть
$$
	\UNSAT = \{ \phi\,|\, \forall y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 0 \}
$$

\upr Показать, что язык $\UNSAT$ лежит в классе $\coNP$.


Полнота языка в классе относительно сводимостей осмыслена не только в случае $\NP$-полных языков. В учебных целях мы будем пользоваться полиномиальной $m$-сводимостью также в классе $\PP$ и $\coNP$.
Разумеется, полнота относительно полиномиальной сводимости в классе $\PP$ выглядит нелепо -- в реальной жизни класс $\PP$ исследуют относительно более осмысленной сводимости -- сводимости на логарифмической памяти. 
Относительно этой сводимости, например, полна задача о проверки пустоты языка, заданного КС-грамматикой. То есть, любая задача из класса $\PP$ сводится к задаче о пустоте языка, заданного КС-грамматикой на логарифмической памяти. Подробнее об этом можно почитать, например, в книжке Хопкрофта-Ульмана «Introduction to Automata Theory, Languages, and Computation» 1979-го года -- второе здание этой книги, выпущенное совместно с Мотвани многие из вас изучали в курсе ТРЯП, но второе издание сильно упрощено и сжато. 

\prp Верно ли, что любой язык из класса $\PP$ является полным относительно полиномиальной $m$-сводимости?

\prdag Докажите, что язык $\UNSAT$ является полным в классе $\coNP$ относительно полиномиальной $m$-сводимости.



\section{О сложности вычислений}

 Соотношение между классами $\PP$, $\NP$ и $\NPc$ $\coNP$ представляет собой центральный вопрос сложности вычислений.
Задача $\PP \stackrel{?}{\neq} \NP$ является основной в сложности вычислений и, по-видимому, безнадёжно трудной. Эта задача стала своего рода наследником теоремы Ферма, в том плане, что регулярно (хотя и не столь часто как в случае теоремы Ферма), находятся люди, которые «доказывают», что $\PP = \NP$ или обратное. Интерес к проблеме подогревается институтом Клэя, обещавшим за решение этой задачи $\$ 1\ 000\ 000$.  Тем не менее, недавно была предпринята первая серьёзная попытка действительно доказать, что $\PP \neq \NP$. Так что возможно мы всё же доживём до решения этого вопроса.


Сообщество верит, что $\PP \neq \NP$ и довольно многие результаты доказываются по модулю этой гипотезы. Более того, сложность этого вопроса используется на практике, в частности в криптографии. В этом курсе мы непосредственно с этим столкнёмся при изучении RSA-алгоритма шифрования. Тем не менее, то что задача лежит в $\NP$ и даже в $\NPc$ ещё вовсе не означает что её частный случай, \emph{экземпляр}  трудно решить. Это означает лишь, что задача трудна только для некоторых входов.


\section{Домашнее задание}

\emph{На всякий случай прежде всего обращу здесь внимание на то, что ближайший семинар пройдёт в понедельник 13 марта!}


Поскольку у нас пропал семинар 23-го февраля, блок из задач получился большим. Я разбил его на две части — вторая скорее нужна для подготовки к контрольной.  В первой части много базовых задач: блок задач 20-24 посвящён различным сводимостям, которые стоит освоить, но из-за нехватки времени их можно решать и после семинара в четверг на следующей неделе. Но не стоит оставлять их все на потом.

\subsection*{Часть I:}
Сдать до 15-го марта. Часть задач из блока \underline{20-24} можно прислать до 22 марта.

\textbf{Базовые задачи:} 3, 6, 7 из этого текста;  КДЗ 2017: 18, \underline{20-24}.

\textbf{Дополнительные задачи:} 5 из этого текста;  КДЗ 2017: 15, 16, 17.  

\subsection*{Часть II:}

Бонусная часть, которую стоит прорешать перед контрольной, и можно прислать по-желанию до 22 марта.

\textbf{Базовые задачи:} КДЗ 2017:  28-29.

\textbf{Дополнительные задачи:} КДЗ 2017: 25.





\end{document}