\documentclass[12pt]{article}

\usepackage{cmap}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb}
\usepackage[russian]{hyperref}
\usepackage{enumerate}
\usepackage{datetime}
%\usepackage{minted}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{color}

\sloppy
\voffset=-20mm
\textheight=235mm
\hoffset=-25mm
\textwidth=180mm
\headsep=12pt
\footskip=20pt

% Основные математические символы
\newcommand{\N}{\mathbb{N}}   % Natural numbers
\newcommand{\R}{\mathbb{R}}   % Ratio numbers
\def\EPS{\varepsilon}         %
\def\SO{\Rightarrow}          % =>
\def\EQ{\Leftrightarrow}      % <=>
\def\t{\texttt}               %
\def\O{\mathcal{O}}           %
\def\NO{\t{\#}}               % #
\renewcommand{\le}{\leqslant} % <=, beauty
\renewcommand{\ge}{\geqslant} % >=, beauty
\def\XOR{\text{ {\raisebox{-2pt}{\ensuremath{\Hat{}}}} }}
\newcommand{\q}[1]{\langle #1 \rangle}               % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}        %
\newcommand{\sfrac}[2]{{\scriptstyle\frac{#1}{#2}}}  % Очень маленькая дробь
\newcommand{\mfrac}[2]{{\textstyle\frac{#1}{#2}}}    % Небольшая дробь
\newcommand{\score}[1]{{\bf\color{red}{(#1)}}}

% Отступы
\def\makeparindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}
\def\down{\vspace*{\baselineskip}}
\def\LINE{\vspace*{-1em}\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}}

\lhead{Алгоритмы, осень 2015/16}
\chead{}
\rhead{Практика \NO{1}}
\renewcommand{\headrulewidth}{0.4pt}

\lfoot{}
\cfoot{\thepage\t{/}\pageref*{LastPage}}
\rfoot{}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\BeginConspect}{
  \pagestyle{fancy}
  \setcounter{page}{1}
}

\newenvironment{MyList}{
  \begin{enumerate}[1.]
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{4pt}
}{       
  \end{enumerate}
}
\newenvironment{InnerMyList}[1][0pt]{
  \vspace*{-0.5em}
  \begin{enumerate}[1.]
  \setlength{\parskip}{#1}
  \setlength{\itemsep}{0pt}
}{
  \end{enumerate}
}

\newcommand{\Section}[1]{
  \refstepcounter{section}
  \addcontentsline{toc}{section}{\arabic{section}. #1} 
  {\LARGE \bf \arabic{section}. #1} 
  \vspace{1em}
  \makeparindent\unskip
}
\newcommand{\Subsection}[1]{
  \refstepcounter{subsection}
  \addcontentsline{toc}{subsection}{\arabic{subsection}. #1} 
  {\Large \bf \arabic{subsection}. #1} 
  \makeparindent\unskip
}

\begin{document}

\renewcommand{\dateseparator}{--}
\begin{center}
  {\Large\bf 
   Первый курс, осенний семестр \\
   Практика по алгоритмам \NO{1}\\
   \vspace*{0.5em} 
   Асимптотика и рекуррентные соотношения\\
   \vspace*{0.5em} 
   7 сентября}\\
  \vspace{0.5em}
  {Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\LINE
\vspace{1em}

\tableofcontents

\pagebreak
\BeginConspect

\pagebreak
\Section{Новые задачи}
\vspace*{-1em}
\begin{MyList}
  %\setlength{\itemsep}{2pt}
  \item {\bf Простые задачи на асимптотику.}\\
    Найдите короткую запись через $\Theta$. \\
    Если такой не существует, объяснить, почему, и записать через $O$.
    \begin{InnerMyList}
      \item $2n$
      \item $2n+1$
      \item $n^2 + 5n + 1$
      \item $\frac{n^2+3}{7n+1}$
      \item $n(2 + \sin n)$
      \item $\frac{\arctg n}{n} + \frac{\log \log n}{\log n}$
      \item Докажите: $\forall f, g > 0 \colon f + g = \Theta(\max(f, g))$
      \item $\mfrac{P(n)}{Q(n)}, deg\,p > deg\,q > 0$
    \end{InnerMyList}
  \item {\bf Истина или ложь?}\\
    Проверьте корректность, докажите.
    \begin{InnerMyList}
      \item $2^{n+3} = \Theta(2^n)$
      \item $2^{2n+1} = \Theta(2^n)$
      \item $g(n) = \O(f(n)) \SO 2^{g(n)} = \O(2^{f(n)})$
      \item $g(n) = o(f(n)) \SO 2^{g(n)} = o(2^{f(n)})$
      \item $g(n) = \O(f(n)) \SO \log{g(n)} = \O(\log{f(n)})$
      \item $g(n) = o(f(n)) \SO \log{g(n)} = o(\log{f(n)})$
      \item $f(n) + g(n) = \Theta(\frac{f(n) + g(n)}{2})$
      \item $n^2 = \O(2^n)$
      \item $\mfrac{n}{\log n} = \omega(\log n)$ (А если $\Omega$?)
      \item $\mfrac{n}{\log n} = \Theta(0.5 \cdot n)$
    \end{InnerMyList}

  \item {\bf Рекуррентность}
    \begin{InnerMyList}
      \item $T(n) = 2T(\mfrac{n}{2}) + 1$
      \item $T(n) = 3T(\mfrac{n}{2}) + n^2$
      \item $T(n) = 5T(\mfrac{n}{2}) + n$
      \item $T(n) = 2T(\mfrac{n}{2}) + n\log n$
      \item $T(n) = 3T(\mfrac{n}{3}) + n$
      \item $T(n) = T(n{-}1) + T(n{-}1) + 1$
    \end{InnerMyList}

  \item {\bf Дополнительные задачи}
    \begin{InnerMyList}
      \item 
        Найдите короткую запись через $\Theta$. \\
        Если такой не существует, объяснить, почему, и записать через $O$.\\
        $f(n) = n(1 + \sin n)$
      \item $T(n) = T(\mfrac{n}{2}) + 1$
      \item $T(n) = T(\mfrac{n}{2}) + n$
      \item $T(n) = T(\mfrac{n}{\log n}) + \log n$
      \item $T(n) = T(\mfrac{n}{2}) + T(\mfrac{n}{3}) + 1$
    \end{InnerMyList}

\end{MyList}

\pagebreak
\input 150907-analysis.tex
\vspace*{1em}
\input 150907-sinus.tex

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

\Subsection{Обязательная часть}

\begin{enumerate}
    \item {\bf Истина или ложь?}\\
      Проверьте корректность, докажите.\\
      \score{0.5} за каждый пункт.
      \begin{InnerMyList}
        \setcounter{enumii}{10}
        \item $n^{logn} = \O(1.1^n)$
        \item $\frac{n^3}{n^2 + n \log n} = \O(n \log n)$
        \item $f(n) = \O(f(\frac{n}{2}))$
        \item $f(n) + o(f(n)) = \Theta(f(n))$
        \item $\log n! = \Theta(n \log n)$
      \end{InnerMyList}

  \item {\bf Рекуррентность.}\\
    Во всех задачах предполагается, что $\forall x \le 1, T(x) = 1$\\
    \score{0.5} за каждый пункт.
    \begin{InnerMyList}
      \setcounter{enumii}{6}
      \item $T(n) = T(\mfrac{n}{2}) + T(\mfrac{n}{3}) + n$
      \item $T(n) = 4T(\mfrac{n}{2}) + n \log^2 n$
      \item $T(n) = 2T(\mfrac{n}{3}) + 1$
      \item $T(n) = T(n{-}1) + T(n{-}2)$
      \item $T(n) = T(n - 1) + n$
    \end{InnerMyList}

    \item \score{3} {\bf Заполнить табличку.}\\
        $A = O(B)$? $A = o(B)$? и т.д.
        За каждый неправильный ответ ${-}0.1$ балл.
$$
	\begin{array}{|cc|c|c|c|c|c|}
		\hline
		A & B & O & o & \Theta & \omega & \Omega \\
		\hline
		n & n^2 & + & + & - & - & - \\
		\lg^k n & n^{\epsilon} & & & & & \\
		n^k & c^n & & & & & \\
		\sqrt{n} & n^{\sin n} & & & & & \\
		2^n & 2^{n \slash 2} & & & & & \\
		n^{\lg m} & m^{\lg n} & & & & & \\
		\lg (n!) & \lg(n^n) & & & & & \\
		\hline
	\end{array}
$$
    \item \score{6} {\bf Упорядочить функции в порядке возрастания.}\\
          Если какие-то функции равны ($f = \Theta(g)$), указать это.
          Здесь $\lg n$ --- двоичный логарифм, $\ln n$ --- натуральный логарифм.
          За каждый неправильный ответ ${-}0.1$ балл.

$$
	\begin{array}{cccccc}
		\lg(\lg^* n) & 2^{lg^* n} & (\sqrt{n})^{\lg n} & n^2 & n! & (\lg n)! \\
		(3 \slash 2)^n & n^3 & \lg^2 n & \lg n! & 2^{2^n} & n^{1 \slash \lg n} \\
		\ln \ln n & \lg^* n & n \cdot 2^n & n^{\lg \lg n} & \ln n & 1 \\
		2^{\ln n} & (\lg n)^{\lg n} & e^n & 4^{\lg n} & (n + 1)! & \sqrt{\lg n} \\
		\lg^* \lg n & 2^{\sqrt{2 \lg n}} & n & 2^n & n \lg n & 2^{2^{n + 1}}					
	\end{array}
$$
    Примечание: $\lg^*(n) = \left\{
    \begin{array}{ll}
        0 & \text{ если } n \leq 1;\\
        1 + \lg^*(\lg n) & \text{ иначе}
    \end{array}
    \right.$

\pagebreak
	\item {\bf Посчитать точно.}\\
      \score{0.5} за каждый пункт
      \begin{InnerMyList}
	    \item $\sum_{k = 0}^\infty \frac{1}{2^k}$ 
	    \item $\sum_{k = 0}^\infty \frac{(-1)^k}{2^k}$
      \end{InnerMyList}
\end{enumerate}

\vspace{0.5em}
%\pagebreak
\Subsection{Дополнительная часть}

\begin{enumerate}
    \item {\bf Истина или ложь?}\\
      Проверьте корректность, докажите.\\
      \score{0.5} за каждый пункт.
      \begin{InnerMyList}
        \setcounter{enumii}{15}
        \item $n^n = \O(n!)$
        \item $n \log n - \log n! = \Theta(n)$
      \end{InnerMyList}
    \item {\bf Рекуррентность.}\\
      Во всех задачах предполагается, что $\forall x \le 1, T(x) = 1$\\
      \score{0.5} за каждый пункт.
      \begin{InnerMyList}
        \setcounter{enumii}{11}
        \item $T(n) = T(n{-}1) + T(n{-}2) + 1$
        \item $T(n) = T(n{-}1) + T(n{-}3)$
        \item $T(n) = T(\mfrac{n}{2}) \cdot T(\mfrac{n}{3})$
      \end{InnerMyList}
\end{enumerate}

\end{document}