\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}

%% \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 {Основные алгоритмы 2021} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 1}
%\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}}}}


\begin{document}
	


\SetKwFunction{HW}{HelloWorld}   
 
	\pr Определим $f(n)$ как количество выводов <<Hello, World!>> следующей функцией (на входе $n$).  Оцените асимптотику роста $f(n)$. 

% \begin{figure}[h]
\begin{algorithm}%algorithm2e
	\SetKwFunction{KwPrint}{print}
	\SetKwFunction{KwFn}{Fn}
	\SetKwInOut{Input}{Вход}\SetKwInOut{Output}{Выход}
	\SetKwProg{Fn}{Function}{:}{end}

%	\SetKwFunction{HW}{HelloWorld}
%	\Multiply($x,y$){ %\tcc*[h]{Рекурсивный алгоритм умножения ([\textbf{ДПВ}] раздел 1.1.2)}
\Fn{\HW{$n$}}{ %\tcc*[h]{}

	
	\uIf{$n > 2020$}{
					   \HW{$\lfloor n/4 \rfloor$}\; 
						\KwPrint{"Hello, World!"}\;
						\HW{$\lfloor n/4 \rfloor$}\;
						\For{$i = 1$ \KwTo $2020$}
						{
						\KwPrint{"Hello, World!"}\;
						}
						\HW{$\lfloor n/4 \rfloor$}\;
	}
	\Else{  
		\For{$i = 1$ \KwTo $n$}{
				\KwPrint{"Hello, World!"}\;
		}	 
	}
}	
	
\end{algorithm}
%\end{figure}
\vspace*{-2ex}
	

\pr На доске написан массив положительных целых чисел. За шаг можно брать любые два различных числа и вычитать из большего меньшее. Процесс остановится, когда на доске все числа будут одинаковыми. 

\prsub Докажите, что процесс всегда останавливается. 

\prsub Чему будут равны оставшиеся числа?

\prend


\pr Предположим, удалось установить, что любое число можно возвести в квадрат за $O(n)$, где $n$ -- длина числа в двоичной записи. Докажите, что тогда любые два числа можно перемножать за $O(n)$, где $n$ -- длина максимального из чисел в двоичной записи.

\prend
               
\Pr[null][ДПВ 1.33] Постройте эффективный алгоритм для вычисления НОК и оцените его сложность. В данной задаче используется модель вычислений с атомарными битовыми операциями (т.\,е. время выполнения арифметических действий пропорционально длине чисел).                                    

\pr Дан массив $a_1, \dots, a_n$. Найдите $\sum\limits_{i\neq j}a_i\cdot a_j$ за линейное от $n$ количество арифметических операций.

\prend

\pr Найдите $\Theta$-асимптотику рекуррент, считая что $T(n) = \Theta(1)$ при малых $n$: 

\prsubr $T(n) = 36T(\frac{n}{6})+n^2$;\quad \prsubrinline $T(n) = 3T(\frac{n}{3})+n^2$;\quad \prsubrinline $T(n) = 4T(\frac{n}{2})+\frac{n}{\log n}$.

\prend

\pr На вход подаётся числовой массив $A$ из $n$ элементов. Требуется найти число инверсий в массиве, т.\,е. пар индексов $(i,j)$, таких что $i<j$ и $a[i] > a[j]$.

\smallskip

\ukaz Модифицируйте алгоритм сортировки слиянием. %Представьте, что число инверсий уже известно для каждой половины массива. Как найти число инверсий в самом массиве, зная инверсии для его половин?

\prend

\pr Докажите, что если $T_1(n) = aT_1(\frac{n}{b})+ f(n)$,\; $T_2(n) = aT_2(\frac{n}{b})+ g(n)$ и $f(n) = \Theta(g(n))$, то $T_1(n) = \Theta(T_2(n))$.

\prend

\pagebreak

\textsl{В случае, когда в рекуррентных соотношениях возникают округления, задачу можно решать считая, что их нет, т.\,е. считать, что на вход $T(n)$ могут подаваться дробные параметры. Это облегчит задачу. Однако для того, чтобы лучше разобраться в теме, рекомендуем решать задачи с учётом округлений.}

\pr Найдите $\Theta$-асимптотику рекуррентной последовательности $T(n)$, считая что $T(n)$ ограничено константой при достаточно малых $n$:

\prsubr $T(n) = 3T(\lfloor {n}/4\rfloor) + T(\lceil {n}/6\rceil) + n$;

\prsubr $T(n)=T(\lfloor \alpha n\rfloor)+T( \lfloor(1-\alpha)n\rfloor)+\Theta(n)$\quad  ($0 < \alpha < 1$);

\prsubr $T(n)=T(\lfloor n/2\rfloor)+2\cdot T(\lfloor n/4\rfloor)+\Theta(n)$;

\prsubr $T(n) = 27T(\frac{n}{3})+\frac{n^3}{\log^2 n} $.

                                                                                                              
\pr На вход подаются натуральные числа $n, p$, $n < p, p$ -- простое. Предложите алгоритм, который за $O(n + \log p)$ арифметических операций вычисляет массив длины $n$ ($i$ пробегает значение от $1$ до $n$):

\prsubr $\w{invfac[}i\w{]} = (i!)^{-1}\pmod p$;

\prsubrstar $\w{inv[}i\w{]} = (i)^{-1}\pmod p$.

\prstar Оцените трудоемкость рекурсивного алгоритма, разбивающего исходную задачу размера $n$ на $n$ задач размеров $\lceil \frac n 2 \rceil$ каждая, используя для этого $\Theta(n)$ операций. 

\prsub Можно считать $n$ степенью двойки.                

\prsub Решите для произвольного $n$.

\end{document}
  