
 \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 Задача $\mathbf\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 Задание 6}

\medskip

\begin{center}
	{\Large Сортировки }
\end{center}

\bigskip

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

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

%\item {\bf [ДПВ]} {\em  Дасгупта С., Пападимитриу Х., Вазирани У.}\\ Алгоритмы.\\ М.: МЦНМО, 2014.  


\end{enumerate}



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

\subsection*{Базовые задачи}

\emph{Напоминаю, что в этом разделе находятся задачи, которые крайне желательно научиться решать.}

\prp Есть $n$ монет, среди которых одна фальшивая. Настоящие монеты все имеют одинаковый вес, а фальшивая легче. За одно взвешивание можно сравнить по весу любые две монеты. Докажите, что фальшивую монету можно найти за $\lfloor \frac{ n}{2} \rfloor$ взвешиваний.


\prp Докажите, что в условиях предыдущей задачи для нахождения фальшивой монеты необходимо  $\lfloor \frac{ n}{2} \rfloor$ взвешиваний.

\smallskip

\noindent\textsl{Указание.} Для доказательства нижней оценки разбейте монеты на классы, после чего предъявите стратегию противника, которая будет выдавать результаты взвешивания в зависимости от того какие монеты участвуют во взвешивании. Укажите как изменяется разбиение монет на классы в результате каждого ответа. Можете также решить задачу используя модель разрешающих деревьев.

Для этого вам поможет следующая задача.

\medskip
\noindent\textbf{Задача 42 (iii)} из КДЗ-2017.
\medskip


Подробнее про разрешающие деревья и метод противника можно прочесть по ссылке \href{http://www.mi.ras.ru/~podolskii/files/20162017/chapter13.pdf}{http://www.mi.ras.ru/~podolskii/files/20162017/chapter13.pdf}.

%\medskip
%\noindent Задачи №\textbf{39-40} из \href{https://dl.dropboxusercontent.com/u/31418200/amv/2014/amv2014prog-new-2010\%20\%282\%29.pdf}{задания прошлого года}.

\medskip
\noindent\textbf{Задача 35 (i)} из КДЗ-2017.
\medskip



\subsection*{Дополнительные задачи}

\emph{Напоминаю, что в этом разделе находятся задачи, которые стоит решать, если Вы претендуете на оценку <<хорошо>> и выше.}

\medskip
\noindent\textbf{Задача 35 (ii)} из КДЗ-2017.
\medskip

         
\medskip
\noindent\textbf{Задача 43} из КДЗ-2017.   
\medskip

\prdag В клетках шахматной доски написали в каком-то порядке числа от $1$ до $64$, каждое по одному разу. Про любое множество клеток доски мы можем спросить, какие числа на них стоят, и нам выдают полный список. За какое наименьшее количество вопросов можно понять, где какие числа стоят? 

\medskip

Обсуждённый нами алгоритм быстрой сортировки не применим на практике. Дело в том, что для реализации рекурсивных вызовов компиляторы используют стек вызовов процессора, глубина которого ограничена -- при рекурсивном вызове значение переменных окружения кладётся в стек, после чего происходит рекурсивный вызов процедуры. По возврату из рекурсии, компилятор извлекает данные из стека и продолжает выполнение процедуры.

\prp Оцените глубину стека, в худшем случае при работе быстрой сортировки.

\prp Измените алгоритм быстрой сортировки так, чтобы глубина стека в худшем случае была $\Theta(\log n)$.

\end{document}