\documentclass[a4paper, 12pt]{article}
\usepackage{cmap}           % Пакет для поиска в полученной pdf
\usepackage[utf8]{inputenc} % Ззамена кодировки файла на utf8
\usepackage[T2A]{fontenc}   % Подключение кодировки шрифтов
\usepackage[russian]{babel} % Использование русского языка
\usepackage[left=2cm, right=2cm, top=1cm, bottom=2cm]{geometry} % Изменение размеров полей
\usepackage{indentfirst}    % Красная строка в начале текста
\usepackage{amsmath, amsfonts, amsthm, mathtools, amssymb, icomma, units, yfonts}
\usepackage{amsthm} % Пакет для оформления теорем
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{esvect}
\usepackage{enumitem}
\usetikzlibrary{calc,matrix}


\newtheorem*{fulllemma}{Лемма}
\newtheorem*{sl1}{Следствие 1}
\newtheorem*{sl2}{Следствие 2}
\newtheorem*{scheme}{Утверждение 1}
\newtheorem*{n2}{Утверждение 2}
\newtheorem*{on1n}{Задача}
\newtheorem*{on2n}{Теорема}
\newtheorem*{o2ndivn}{Теорема}
\newtheorem*{existsFgthen2ndivn}{Теорема}

\renewcommand{\qedsymbol}{\textbf{Q.E.D.}}
\newcommand{\definition}{\underline{Определение:} }
\newcommand{\statement}{\underline{Утверждение:} }
\newcommand{\answer}{\underline{Ответ:} }

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}



\begin{document}
\title{Домашнее задание по Алгоритмам}
\author{Группа 157-1 \\ Гринберг Вадим}
\date{27 января 2016}

\maketitle

\definition{Две функции $f(x)$ и $g(x)$ называются асимптотически равными, если
    \[
        \lim\limits_{x \to \infty}\frac{f(x)}{g(x)} = 1
    \]

Обозначение: $f(x) \sim g(x)$.
}

\begin{on1n}
    Пусть две функции $f(x)$ и $g(x)$ асимптотически равны. Верно ли, что $f(x) \sim g(x) \Longrightarrow 2^{f(x)} \sim 2^{g(x)}$ для любых таких $f(x)$ и $g(x)$?
\end{on1n}

\answer{Нет, не верно.}

\begin{proof}

    Достаточно привести контр-пример:

    Пусть $f(x) = x^2 + x, \ g(x) = x^2$. Тогда:

    \[
        \lim\limits_{x \to \infty}\frac{f(x)}{g(x)} = \lim\limits_{x \to \infty}\frac{x^2 + x}{x^2} = \lim\limits_{x \to \infty}1 + \frac{x}{x^2} = \lim\limits_{x \to \infty}1 + \frac{1}{x} = 1, \text{так как} \lim\limits_{x \to \infty}\frac{1}{x} = 0.
    \]

    Значит, $f(x) \sim g(x)$ по определению. Рассмотрим теперь функции $2^{f(x)}$ и $2^{g(x)}$:

    \[
        \lim\limits_{x \to \infty}\frac{2^f(x)}{2^g(x)} = \lim\limits_{x \to \infty}\frac{2^{x^2 + x}}{2^{x^2}} = \lim\limits_{x \to \infty}\frac{2^{x^2 + x - x^2}}{1} = \lim\limits_{x \to \infty}\frac{2^{x}}{1} = \lim\limits_{x \to \infty}2^{x} = \infty.
    \]

    Получили в пределе отношения бесконечность, значит, $2^{f(x)} \nsim 2^{g(x)}$. Значит, не верно, что $2^{f(x)} \sim 2^{g(x)}$ для любых $f(x) \sim g(x)$.

\end{proof}

\begin{on1n}

    Вычислить:

    \[
        \lim\limits_{x \to \infty}\frac{log^{200}(x)}{x}
    \]

\end{on1n}

\begin{proof}[Решение:]
    $\ $

    Здесь у нас неопределённость вида $\langle \frac{\infty}{\infty} \rangle$. Так как функции в числителе и знаменателе обе дифференциируемы, то применим правило Лопиталя для вычисления предела:

    \[
        \lim\limits_{x \to \infty}\frac{log^{200}(x)}{x} = \lim\limits_{x \to \infty}\frac{(log^{200}(x))^{'}}{x^{'}} = \lim\limits_{x \to \infty}\frac{200 \cdot log^{199}(x) \cdot \frac{1}{x}}{1} = \lim\limits_{x \to \infty}\frac{200 \cdot log^{199}(x)}{x} =
    \]

    \[
        = \lim\limits_{x \to \infty}\frac{200 \cdot 199 \cdot log^{198}(x) \cdot \frac{1}{x}}{1} = \lim\limits_{x \to \infty}\frac{200 \cdot 199 \cdot log^{198}(x)}{x} = \ldots = \lim\limits_{x \to \infty}\frac{200! \cdot log(x) \cdot \frac{1}{x}}{1} =
    \]

    \[
        = \lim\limits_{x \to \infty}\frac{200! \cdot log(x)}{x} = \lim\limits_{x \to \infty}\frac{(200! \cdot log(x))^{'}}{x^{'}} = \lim\limits_{x \to \infty}\frac{200! \cdot \frac{1}{x}}{1} = \lim\limits_{x \to \infty}\frac{200!}{x} = 0.
    \]

    То есть, при достаточно больших $x$

    \[
        \lim\limits_{x \to \infty}\frac{log^{200}(x)}{x} = 0.
    \]

\end{proof}

\begin{answer}
    \[
        \lim\limits_{x \to \infty}\frac{log^{200}(x)}{x} = 0.
    \]
\end{answer}

\begin{on1n}

    Возьмём функцию

    \[
        f(n) = 1 + c + c^2 + \ldots + c^n = \sum\limits_{i = 0}^{n}c^i, \ c > 0.
    \]

    Придумать универсальную оценку $\Theta(f(n))$ или доказать, что её не существует.

\end{on1n}

\answer{Её не существует.}

\begin{proof}

   Рассмотрим два случая:

   \begin{enumerate}
       \item $c \neq 1$

        Вычислим сумму по формуле геометрической прогрессии:

        \[
            f(n) = 1 + c + c^2 + \ldots + c^n = \sum\limits_{i = 0}^{n}c^i = \frac{1 \cdot (c^{n + 1} - 1)}{c - 1} = \frac{c^{n + 1} - 1}{c - 1}.
        \]

        В случае, если $ c > 1 \ : \ O(\frac{c^{n + 1} - 1}{c - 1}) = O(\frac{c^{n + 1}}{c}) = O(c^{n + 1}) = O(c^n)$ -- получили величину экспоненциального от $n$ размера.

        Если $c < 1$:

        \begin{itemize}
            \item $c \to 0 \Longrightarrow$

            \[
                \frac{c^{n + 1} - 1}{c - 1} \to \frac{-1}{-1} = 1
            \]

            -- линейная величина $\Theta(1)$.
            \item $c \to 1 \Longrightarrow$

            \[
                \lim\limits_{c \to 1}\frac{c^{n + 1} - 1}{c - 1} = \text{по правилу Лопиталя} = \lim\limits_{c \to 1}\frac{(c^{n + 1} - 1)^{'}}{(c - 1)^{'}} =
            \]

            \[
                = \lim\limits_{c \to 1}\frac{(n + 1) \cdot c^{n}}{1} = \lim\limits_{c \to 1}(n + 1) \cdot c^{n} = (n + 1) \cdot 1 = n + 1
            \]

            Получили $O(n + 1) = O(n)$ -- величину полиномиального от $n$ размера.
        \end{itemize}

       \item $c = 1$

        В этом случае наша сумма равна:

        \[
            f(n) = \underbrace{1 + 1 + 1 + \ldots + 1}_\text{n} = n.
        \]

       Получили $\Theta(n)$ -- величину полиномиального от $n$ размера.

   \end{enumerate}

   Таким образом, мы получили несколько возможных оценок в зависимости от $c$. Тогда в общем случае для нашей функции $f(n) = \sum\limits_{i = 0}^{n}c^{i}$ имеем:

   \begin{itemize}
       \item $O(f(n)) = $ максимальная оценка $ = O(c^n)$.
       \item $\Omega(f(n)) = $ минимальная оценка, в данном случае можем взять как $\Omega(f(n)) = \Theta(1) = \Omega(1)$, так и $\Omega(f(n)) = \Theta(n) = \Omega(n)$. Будем считать, что нижняя оценка для $f(n)$ равна $\Omega(n)$.
   \end{itemize}

   По определению:

    \[
        \Theta(f(n)) = \{g(n) \ | \ \exists c_1 > 0, \exists c_2 > 0, \exists n_0 \in \N: \forall \ n \geq n_0 \Rightarrow c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)\}.
    \]

    Но в данном случае у нас функции $\Omega(n)$ и $O(c^n)$. А для них не существует таких констант $c_1 > 0 $ и $c_2 > 0$, что

    \[
        c_1 \cdot \Omega(n) \sim c_2 \cdot O(c^n).
    \]

    Значит, для

    \[
        f(n) = 1 + c + c^2 + \ldots + c^n = \sum\limits_{i = 0}^{n}c^i, \ c > 0
    \]

    не существует универсальной оценки $\Theta(f(n))$.

\end{proof}

\end{document}