\documentclass[12pt]{extreport}
\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{indentfirst}
\usepackage{verbatim}
\usepackage{tikz} %Рисование автоматов
\usetikzlibrary{automata,positioning}
\usepackage{multicol} %Несколько колонок
\usepackage{graphicx}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[stable]{footmisc}

\usepackage[linesnumbered]{algorithm2e}   

%% \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}{Теорема}
\theoremstyle{definition}
\newtheorem{Example}{Пример}
\newtheorem*{known}{Теорема}
\def\proofname{Доказательство}
\theoremstyle{definition}
\newtheorem{Def}{Определение}

%% \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\abstractname{}

\def\R{{\cal R}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}

%классы сложности
\def\REG{{\mathsf{REG}}}
\def\CFL{{\mathsf{CFL}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%% Enumerations %%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Rnum}[1]{\expandafter{\romannumeral #1\relax}}
\newcommand{\RNum}[1]{\uppercase\expandafter{\romannumeral #1\relax}}

%%%%%%%%%%%%%%%%%%%%% EOF Enumerations %%%%%%%%%%%%%%%%%%%%%

\usepackage{xparse}
\usepackage{ifthen}
\usepackage{bm} %%% bf in math mode
\usepackage{color}
%\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{Gray555}{HTML}{555555}
\definecolor{Gray444}{HTML}{444444}
\definecolor{Gray333}{HTML}{333333}


\newcounter{problem}
\newcounter{uproblem}
\newcounter{subproblem}
\newcounter{prvar}

\def\beforPRskip{
	\bigskip
	%\vspace*{2ex}
}

\def\PRSUBskip{
	\medskip
}


\def\pr{\beforPRskip\noindent\stepcounter{problem}{\bf \theproblem .\;}\setcounter{subproblem}{0}}
\def\pru{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^\circ$\!\!.\;}\setcounter{subproblem}{0}}
\def\prstar{\beforPRskip\noindent\stepcounter{problem}{\bf $\mathbf{\theproblem}^*$\negthickspace.}\setcounter{subproblem}{0}\;}
\def\prpfrom[#1]{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem~(№#1 из задания).  }\setcounter{subproblem}{0} }
\def\prp{\beforPRskip\noindent\stepcounter{problem}{\bf Задача \theproblem .  }\setcounter{subproblem}{0} }

\def\prpvar{\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem \;$\langle${\rm\Rnum{\theprvar}}$\rangle$.}\setcounter{subproblem}{0}\;}
\def\prpv{\beforPRskip\noindent\stepcounter{prvar}{\bf Задача \theproblem \,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$.  }\setcounter{subproblem}{0} }
\def\prv{\beforPRskip\noindent\stepcounter{prvar}{\bf \theproblem\,$\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}.\setcounter{subproblem}{0} }

\def\prpstar{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\bf\theproblem^*$\negthickspace.  }\setcounter{subproblem}{0} }
\def\prdag{\beforPRskip\noindent\stepcounter{problem}{\bf Задача $\theproblem^{^\dagger}$\negthickspace\,.  }\setcounter{subproblem}{0} }
\def\upr{\beforPRskip\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{\PRSUBskip\noindent\stepcounter{subproblem}{\sf \thesubproblem.}\;}
\def\prsubr{\PRSUBskip\noindent\stepcounter{subproblem}{\bf \asbuk{subproblem})}\;}
\def\prsubstar{\PRSUBskip\noindent\stepcounter{subproblem}{\rm $\thesubproblem^*$\negthickspace.  } }
\def\prsubrstar{\PRSUBskip\noindent\stepcounter{subproblem}{$\text{\bf \asbuk{subproblem}}^*\mathbf{)}$}\;}

\newcommand{\bracketspace}[1]{\phantom{(}\!\!{#1}\!\!\phantom{)}}

\DeclareDocumentCommand{\Prpvar}{ O{null} O{} }{
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{1}{\bf Задача \theproblem
% 	\ifthenelse{\equal{#1}{null}}{  }{ {\sf $\bm\langle$\bracketspace{#1}$\bm\rangle$}}
%	~\!\!(\bracketspace{{\rm\Rnum{\theprvar}}}).  }\setcounter{subproblem}{0}
%	\;(\bracketspace{{\rm\Rnum{\theprvar}}})}\setcounter{subproblem}{0}
%
	\,{\sf $\bm\langle$\bracketspace{{\rm\Rnum{\theprvar}}}$\bm\rangle$}
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}}.

}
%\DeclareDocumentCommand{\Prpvar}{ O{level} O{meta} m }{\prpvar}


\DeclareDocumentCommand{\Prp}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача \theproblem
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

\DeclareDocumentCommand{\Pr}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf\theproblem
	~\!\! \ifthenelse{\equal{#1}{null}}{\!\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.}

%\DeclareDocumentCommand{\Prp}{ O{level} O{meta} }

\DeclareDocumentCommand{\Prps}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^* $
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}

\DeclareDocumentCommand{\Prpd}{ O{null} O{null} }{\setcounter{subproblem}{0}
	\beforPRskip\noindent\stepcounter{problem}\setcounter{prvar}{0}{\bf Задача $\bm\theproblem^\dagger$
	~\!\!\! \ifthenelse{\equal{#1}{null}}{\!}{{\sf(\bracketspace{#1})}}
	 \ifthenelse{\equal{#2}{null}}{\!\!}{{\sf [\color{Gray444}\,\bracketspace{{\fontfamily{afd}\selectfont#2}}\,]}}}.
}


\def\prend{
	\bigskip
%	\bigskip
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% EOF Problems macros  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%\usepackage{erewhon}
%\usepackage{heuristica}
%\usepackage{gentium}

\usepackage[portrait, top=3cm, bottom=1.5cm, left=3cm, right=2cm]{geometry}

\usepackage{fancyhdr}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0pt}
\lhead{\fontfamily{fca}\selectfont {Основные алгоритмы 2018} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 4}
%\rhead{\small 01.09.2016}
\cfoot{}

\usepackage{titlesec}
\titleformat{\section}[block]{\Large\bfseries\filcenter {\setcounter{problem}{0}}  }{}{1em}{}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Обозначения и операции %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
                                                                    
\newcommand{\divisible}{\mathop{\raisebox{-2pt}{\vdots}}}           
\let\Om\Omega


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Shen Macroses %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\w}[1]{{\hbox{\texttt{#1}}}}
\usepackage{wrapfig}
\def\bin{\mathrm{bin}}



\begin{document}	
	\SetKwFunction{SX}{SX}     
	\SetKwFunction{F}{F}

\begin{comment}
	
	\begin{figure}[h]
		\begin{multicols}{2}
%			\begin{center}
\hspace{2em}
				\begin{algorithm}[H]%algorithm2e
					\SetKwInOut{Input}{Вход}\SetKwInOut{Output}{Выход}
					\SetKwProg{Fn}{Function}{ :}{end}
					\SetKwFunction{F}{F}
						\SetKwFunction{KwPrint}{print}
				\Fn{$\F(x,m)$}{ 	

					$a = \SX(m)$\;$y = 1$\;  

					\For{ i = 1 to a.size}{

						\uIf{ $a[i] == X$}{
						 $y = y \times x$\;	
					   }\Else{            
				%		\If{$ a[i] == S$}{

						 $y = y \times y$\;

						}
					}   

					\KwRet{y}\;
				}	
				\end{algorithm}
				
				\noindent {\tt функция} $RandomQsort(A[1..n])$

				{\tt if} $n>1$

				 \hspace{4mm} $x = A[RandomInteger(1, n)]$ 

				 \hspace{4mm} ($x$ - случайный элемент из $A$)

				 \hspace{4mm} $Partition(A, x)\to B[1..k-1]$ $x$ $C[1..n-k]$

				 \hspace{4mm} (разбили $A$ на массивы меньше $x$, и больше $x$)

				 \hspace{4mm} $RandomQsort(B[1..k-1])$

				 \hspace{4mm} $RandomQsort(C[1..n-k])$

				 \hspace{4mm} return $B[1..k-1]$ $x$ $C[1..n-k]$ 

				{\tt endif}
				
		\end{multicols}
	\end{figure}                        
\end{comment}	
	
\pr Опишем преобразование~$\SX(m)$ двоичной записи числа $m$. Каждая единица заменяется на $SX$, а ноль на $S$, после чего вычёркивается первую слева $S$. Так $\bin(5) = 101 \to$\newline$\to XSSX $. Алгоритм вычисления функции $\F$ от положительных целых чисел $(x,m)$ задан псевдокодом:\\
\vspace*{-2em}
%На вход алгоритма поступают числа $x$ и $m$. Алгоритм сначала преобразует двоичную запись числа $m$, заменяя $1$ на $SX$, а $0$ на $X$ и вычёркивает первую слева $S$. Так $\bin(5) = 101 \to XXSX $.  Далее алгоритм действует согласно псевдокоду: %После преобразования, алгоритм читает получившуюся последовательность $a$ слева направо и выполняет следующие действия.
\begin{wrapfigure}{l}{0.45\textwidth}
%\vspace{-1cm}	
\begin{algorithm}[H]%algorithm2e
	\SetKwInOut{Input}{Вход}\SetKwInOut{Output}{Выход}
	\SetKwProg{Fn}{Function}{ :}{end}
	\SetKwFunction{F}{F}
		\SetKwFunction{KwPrint}{print}
\Fn{$\F(x,m)$}{ 	

	$a = \SX(m)$\;$y = 1$\;  
	
	\For{ i = 1 to a.size}{
	
		\uIf{ $a[i] == X$}{
		 $y = y \times x$		
	   }\Else{            
%		\If{$ a[i] == S$}{
		
		 $y = y \times y$
		
		}
	}   
	
	\KwRet{y}
}	
\end{algorithm}
\vspace{-3cm}
\end{wrapfigure} 

%\vspace*{3em}                  

\prsub Вычислите $\F(3, 5)$.

\prsub Какую математическую функцию реализует данный алгоритм? 

\prsub Докажите корректность данного алгоритма (нужно доказать, что алгоритм действительно реализует отгаданную функцию).

\prsub Оцените время работы алгоритма, считая, что арифметические операции стоят $O(1)$.


	\prend
	\prend
	\prend
	\medskip
%\end{comment}	

	\pr На прямой задано $n$ отрезков, причем известно, что они образуют систему строго вложенных отрезков (их можно упорядочить так, чтобы каждый строго содержался в следующем). Отрезки заданы координатами концов $[l_i, r_i]$ (и могут быть даны в неупорядоченном виде). Предложите асимптотически эффективный алгоритм (с точки зрения количества арифметических операций), который находит все точки прямой, которые покрыты ровно $2n/3$ отрезками.

	\pr Рассмотрим детерминированный алгоритм поиска порядковой статистики за линейное время из параграфа 9.3 Кормена. Какая асимптотика будет у алгоритма, если делить элементы массива на группы по семь, а не по пять?

	\pr Дан массив длины $n$, состоящий только из нулей и единиц. Предложите линейный алгоритм сортировки данного массива.

	\pr Предложите полиномиальный от длины входа алгоритм решения сравнения  $$a\cdot x + b\equiv 0\pmod M$$ (На вход дают целые числа $a,b,M$ в двоичной системе исчисления).

	\pr\prsub Оцените глубину стека (рекурсивных вызовов) при работе быстрой сортировки в худшем случае.

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

	\prstar Запишите рекурентное соотношение для сложности и докажите по индукции, что трудоемкость алгоритма Randomized-Qsort (см. следующую страницу) равна $O(n\log n)$.

%	\smallskip
%\begin{comment}
	

\newpage

\begin{figure}[h]

	
	
	\noindent {\tt функция} $RandomQsort(A[1..n])$

	{\tt if} $n>1$

	 \hspace{4mm} $x = A[RandomInteger(1, n)]$ 

	 \hspace{4mm} ($x$ - случайный элемент из $A$)

	 \hspace{4mm} $Partition(A, x)\to B[1..k-1]$ $x$ $C[1..n-k]$

	 \hspace{4mm} (разбили $A$ на массивы меньше $x$, и больше $x$)

	 \hspace{4mm} $RandomQsort(B[1..k-1])$

	 \hspace{4mm} $RandomQsort(C[1..n-k])$

	 \hspace{4mm} return $B[1..k-1]$ $x$ $C[1..n-k]$ 

	{\tt endif}
\end{figure}	

\prstar Запишите рекурентное соотношение для сложности и докажите по индукции, что трудоемкость алгоритма Randomized-Selection поиска $k$-й порядковой статистики равна $O(n)$.

\smallskip

\noindent {\tt функция} $RandomSelection(A[1..n], k)$

{\tt if} $n==1$

 \hspace{4mm} return $A[1]$

{\tt else}

 \hspace{4mm} $x = A[RandomInteger(1, n)]$ 
 
 \hspace{4mm} ($x$ - случайный элемент из $A$)
 
 \hspace{4mm} $Partition(A, x)\to B[1..l-1]$ $x$ $C[1..n-l]$
 
 \hspace{4mm} (разбили $A$ на массивы меньше $x$, и больше $x$)
 
 \hspace{4mm} {\tt if} $l == k$
 
 \hspace{4mm}\hspace{4mm} return $x$

 \hspace{4mm} {\tt if} $k < l$

 \hspace{4mm}\hspace{4mm} return $RandomSelection(B[1..l-1], k)$

 \hspace{4mm} {\tt if} $k > l$

 \hspace{4mm}\hspace{4mm} return $RandomSelection(C[1..n - l], k - l)$


%\end{comment}	
\end{document}
  