\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{indentfirst}
\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 {Основные алгоритмы 2020} }
%\lhead{ \bf  {ТРЯП. } Семинар 1 }
%\chead{\fontfamily{fca}\selectfont {Вариант 1}}
\rhead{\fontfamily{fca}\selectfont Домашнее задание 2. Захаров Артемий Б05-906}
%\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{enumitem}

\begin{document}
	Задачи из Шеня убраны.\\
	\\
	\\


	\pr Докажите, что для произвольной константы $c>0$ функция $g(n) = 1+c+c^2+\ldots+c^n$ есть

	\begin{enumerate}[label=(\alph*)]
		\item $\Theta(1)$, если $c<1$;
		\item $\Theta(n)$, если $c=1$;
		\item $\Theta(c^n)$, если $c>1$.
	\end{enumerate}

	Решение:
	\begin{enumerate}[label=(\alph*)]
		\item если $c<1$ , то $g(n) = 1+c+c^2+\ldots+c^n \rightarrow \frac{1}{1-c}$ при $ n \rightarrow \infty $, тогда для $ f(n) = 1 $\\
		$ \exists n_0 =1 , C_1 = 1 , C_2= \frac{2}{1-c}  $ : $ 0 \leq 1 \leq \frac{1}{1-c} \leq \frac{2}{1-c} \Rightarrow g(n) = \Theta(1)$
		\item если $c=1$ , то $g(n) = 1+1+1^2+\ldots+1^n = n + 1 $ , тогда для $ f(n) = n $ \\
		$ \exists n_0 = 2 , C_1 = 1, C_2= 2  $ : $ 0 \leq n \leq n+1 \leq 2n \Rightarrow g(n) = \Theta(n)$
		\item если $c>1$ , то $g(n) = 1+c+c^2+\ldots+c^n = 1 * \frac{1-c^n}{1-c} = \frac{c^n-1}{c-1}$ ,тогда для $ f(n) = c^n $ \\
		$ \exists n_0 = 2 , C_1 = \frac{1}{c}, C_2= \frac{1}{c-1} $ : $ 0 \leq c^{n-1} \leq \frac{c^n-1}{c-1} \leq \frac{c^n}{c-1} \Rightarrow g(n) = \Theta(c^n)$
	\end{enumerate}


	\pr Дано три отсортированных по возрастанию массива, внутри каждого массива все элементы различные. Предложите линейный алгоритм нахождения числа различных элементов в объединении массивов.\\
	Решение: \\
	1) Алгоритм.\\
	Пусть $ a[n],b[m],c[k] $-массивы, данные по условию. Тогда для решения задачи будем использовать следующий алгоритм: сначала создадим четвертый массив $ d[p] $,затем при поступлении $ a[0],b[0],c[0] $ находим минимальный из них ($ q=min(a[0],b[0],c[0]) $)и записываем его в $ d[0] $. В том массиве в котором мы нашли минимальный из трех элементов перемещаем счетчик на 1 вправо и ищем минимальный уже между ними. Если какой то элемент из массивов равен предыдущему в массиве d, просто пропускаем и перемещаем счетчик. При этом, если размеры массивов не совпадают, то неопределенные элементы мы будем доопределять null-ом.

Рассмотрим работу алгоритма на $ i  $ шаге. В массиве d на $ i-1 $ лежит какое-то число $\ne NULL$. Пусть программа считывает на данном этапе $ (a[i_{1}],b[i_{2}],c[i_{3}]) $, далее находим минимум из этой тройки, пусть это $ a[i_{1}] $, далее сравниваем $ a[i_{1}] $ с $ d[i-1] $, если  $ a[i_{1}] \ne d[i-1] $, то $ d[i]:=a[i_{1}]  $ и программа переходит к следующему этапу, т.е. сравнивает между собой уже  $ (a[i_{1}+1],b[i_{2}],c[i_{3}]) $. Если же $ a[i_{1}] = d[i-1] $, то программа ищет минимум уже среди $b[i_{2}],c[i_{3}]) $ пусть это-$b[i_{2}]$, тогда аналогично сравниваем $b[i_{2}]$ с $ d[i] $, если  $ b[i_{2}] \ne d[i-1] $, то $ d[i]:=b[i_{2}]  $ и программа переходит к следующему этапу. Если же $ b[i_{2}] = d[i-1] $, то сравниваем $ c[i_{3}] $ с $ d[i-1] $, если $ c[i_{3}] \ne d[i-1] $, то $d[i] = c[i_{3}] $ , если же $(a[i_{1}]=b[i_{2}]=c[i_{3}])=d[i-1]\ne +\infty $,то переходим к следующему этапу, на котором ищем минимум уже среди $a[i_{1}+1],b[i_{2}+1],c[i_{3}+1]) $, при этом если на каком то этапе получается что $a[i_{1}]=b[i_{2}]=c[i_{3}]=NULL $, то программа завершает работу и выдает в качетсве ответа номер крайнего элемента в массиве d плюс один.

2) Корректность.\\
Алгоритм корректен, т.к. в результате его работы получается отсортированный по возрастанию массив множества элементов, которое является объединением множеств элементов исходных массивов. Не добавить какой-либо элемент в массив d алгоритм не может, тк элемент не добавляется в массив только в том случае, если равный ему элемент уже есть в массиве d. Размер d - число различных элементов в объединении массивов. \\
Так же стоит добавить , что для поиска , именно , количества , не обязательно использовать массив , можно просто завести счётчик и хранить в пременной значение d[i-1] на i-том шаге. \\
3) Оценка.\\
Алгоритм линеен, тк содержит не более $ n+m+k $ шагов, при этом на каждом шаге выполняется константное число операций.



	\pr  На вход подаётся последовательность чисел $a_1, b_1, a_2, b_2, \ldots, a_n, b_n$. Постройте онлайн-алгоритм, который вычисляет сумму~$\sum\limits_{ i\neq j} a_i\times b_j$.\\
	Решение: \\1)Алгоритм. В начале $ sum = 0 $ ( $ sum = \sum\limits_{ i\neq j}^k a_i\times b_j $ ) , $ sum(a) = 0 $ ( $ sum(a) =  \sum\limits_{i=1}^{k} a_i$ ) , $ sum(b) = 0 $ ( $ sum(b) =  \sum\limits_{j=1}^{k} b_i$ ) . На каждом $k$-том шаге алгоритм будет прибавлять к $ sum $  произведения $a_k * sum(b)$ ( $ sum(b) = \sum\limits_{i=1}^{k-1} b_i $ ) и $b_k *sum(a) $ ( $sum(a) = \sum\limits_{i=1}^{k-1} a_i$ ) , далее он будет увеличивать $sum(a)$ и $ sum(b) $ : $sum(a) = sum(a) + a_k $ , $sum(b) = sum(b) + b_k $ .
\\
	2)Корректность. Докажем по индукции: Для n = 2 - верно . Допустим верно для n , тогда для n + 1 тоже должно быть верно. Для n+1 : $ sum = \sum\limits_{ i\neq j}^n a_i\times b_j + a_{n+1} * \sum\limits_{j=1}^{n} b_i + b_{n+1} *\sum\limits_{i=1}^{n} a_i = a_1*\sum\limits_{j \neq 1}^{n+1} b_j + a_2*\sum\limits_{j \neq 2}^{n+1} b_j + ... + a_n*\sum\limits_{j \neq n}^{n+1} b_j + a_{n+1}*\sum\limits_{j \neq n+1}^{n+1} b_j = \sum\limits_{ i\neq j}^{n+1} a_i\times b_j $ - верно \\
	3)Оценка: \\
	По памяти - константное число переменных $ \Rightarrow $  $ \theta(1) $\\
	По времени - за каждый шаг алгоритм выполняет константное число операций $ \Rightarrow $ зависит только от числа шагов $ \Rightarrow $ $ \theta(n) $


	\pr Дана последовательность целых чисел $a_1,a_2,\dots,a_n$. Необходимо найти её самую длинную строго возрастающую подпоследовательность.
	Предложите \prsubr $O(n^2)$ алгоритм (докажите его корректность и асимптотику);\\
	Решение: \\1) Алгоритм :\\
	int c  , maxlength = 1 , length = 1  ; ( c - будет хранить значение $ a_{i-1} $ , maxlenght - будет хранить максимальную длину ,lenght - будет хранить текущую длину )\\
	for( int i = 1 ; i $ \leq $ n-1 ; i++ ) $ \lbrace $\\
	c = $ a_i $;\\
	\\
	for( int j = i+1 ; j $ \leq $ n ; j++ ) $ \lbrace $\\
		if( с > $ a_{j} $)$ \lbrace $ length++ ; с = $a_{i}$; $ \rbrace $\\
	$ \rbrace $\\
	\\
	if( lenght > maxlength)$ \lbrace $ maxlength = length ;$ \rbrace $\\
	$ \rbrace $\\
	cout << maxlenth ;\\
2) Корректность: Алгорит пройдётся по всем строго возрастающим подпоследовательностям , и выведет максимальную дилину $ \Rightarrow $ алгоритм корректен\\
3) Оценка по времени : по времени получается $ f(n) = \sum\limits_{i = 1}^{n-1} ( const_2 * \sum\limits_{j = i}^{n} const_1 )= \theta(n^2) $ \\
т.к $ \sum\limits_{j = i}^{n} const_1 = const_1 * ( n - i ) = const_1 * n - const_1 * i $  тогда  $ \sum\limits_{i = 1}^{n-1} (const_2 *const_1 * n - const_2 *const_1 * i) = const_2 *const_1 * \frac{n^2}{2} - const_2 *const_1 * (n-1) = f(n) $ \\
$ \exists n_0 = 3 , C_1 = const_2 *const_1*\frac{1}{6} , C_2 = const_2 *const_1*\frac{1}{2} : C_1*n^2 \leq f(n) \leq C_2 * n^2  $


	\prstar На вход подаётся последовательность натуральных чисел $x_1, \ldots x_n$ в которой один из элементов встречается строго больше, чем $\frac{n}{2}$ раз. Постройте алгоритм, который находит этот элемент, и при этом может использовать в качестве внешней памяти только стек (в который можно помещать только элементы последовательности), операции со стеком стоят $O(1)$ времени; в оперативной памяти программа использует $O(1)$ битов памяти и $O(1)$ регистров (в каждом из которых может храниться число $x_i$).

	Числа $x_i$ идут потоком данных на вход и каждое доступно для считывания только один раз~"--- вернуться  обратиться к прочитанным ранее числам можно, только если сохранить их в памяти.

	\prstar Дано натуральное $N$. Подсчитайте количество решений неравенства $a^2 + b^2 + c^2 + d^2 <$\linebreak$< N$ в~натуральных (неотрицательных целых) числах, не используя операций с~вещественными числами. Требуется предложить линейный (с асимптотикой $O(N)$) алгоритм.


\end{document}