% Document MUST be built with XeLaTeX! \documentclass[11pt,a4paper]{article} \usepackage[margin=1.5cm]{geometry} % Поддръжка на български език % Thanks to https://tex.stackexchange.com/a/136926 \usepackage{fontspec} \defaultfontfeatures{Ligatures=TeX} \setmainfont{CMU Serif} \setsansfont{CMU Sans Serif} \usepackage[bulgarian,english]{babel} \usepackage{amsmath} % Математически символи \usepackage{amssymb} \usepackage{mathtools} \usepackage{amsfonts} % Още математически символи \usepackage{cancel} % Зачертаване \usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове \usepackage{indentfirst} % Индентация на параграф след секция \usepackage{color} \usepackage{listings} % Въведение на код \lstset{ language=C++, numbers=left, mathescape=true, basicstyle=\ttfamily, tabsize=4 } \usepackage{enumitem} \setlist[enumerate]{label=\arabic*.} \renewcommand{\thesection}{Задача \arabic{section}.} \renewcommand{\thesubsection}{\alph{subsection})} \renewcommand{\thesubsubsection}{$\cdot$} % Мерси https://tex.stackexchange.com/a/184755 \makeatletter \renewcommand*{\@alph}[1]{% \ifcase#1\or а\or б\or в\or г\or д\or е\or ж\or з\or и\or й\or к\or л\or м\or н\or о\or п\or р\or с\or т\or у\or ф\or х\or ц\or ч\or ш\or щ\or ъ\or ю\or я\or \else\@ctrerr\fi } \makeatother \let\oldforall\forall \renewcommand{\forall}{\; \oldforall} \let\oldexist\exists \renewcommand{\exists}{\; \oldexist} \setlist[enumerate]{label=\Roman*.} \usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023}, pdftitle={Домашна работа 2 по ДАА}, pdfsubject={}, pdfkeywords={}, colorlinks=true, urlcolor=blue]{hyperref} \title{\vspace{-1.5cm}Домашно №2 по ДАА на Компютърни Науки} \author{Камен Димитров Младенов, Група 6} \date{9 Април 2023} \begin{document} \maketitle \section{Решение} \subsection{Ляв фрагмент} Цикъла ще извърши точно $m . n = n . n . n = n^3$ итерации. Тоест за $c > 0, f(n) = n^3 + c \asymp n^3$ по дефиниция. \subsection{Централен фрагмент} Алгориътма ще приключи директно ако $n < 10$. Иначе се изпълнява останалата част на алгоритъма. Условието на цикъла на ред 4 никога няма да е вярно, понеже $6 \ngtr 8$. Тялото на цикъла с условие на ред 7 ще се изпълни точно един път: при първо достигане на условието $n - j = n - 6 \geq 10 - 6 = 4 > 1$, на ред 8 $j$ става $n$ и на второто достигане на условието $n - j = n - n = 0 \ngtr 1$. От това единствено изпълнение имаме рекурентно извикване: \begin{align} g(n-1) + g(n-2) \end{align} Тялото на цикъла с условие на ред 10 ще се изпълни точно един път: към момента $j = n$ и при първо достигане на условието, $n \geq n$. Oт ред 11 $j$ става $2$ и при второ достигане на условието, $2 = j \ngeq n$ понеже $n \geq 10$. От това единствено изпълнение имаме рекурентно извикване: \begin{align} g(n-j) = g(n-2) \end{align} \begin{align*} & \text{От (1) и (2): } g(n) = g(n-1) + 2g(n-2) + c \\ & \text{Характеристично уравнение: } x^n = x^{n-1} + 2x^{n-2} \quad x^2 - x - 2 = 0 \quad \text{с корени } \{-1, 2\}_M \\ & \text{Нехомогенната част е константа и няма корени.} \quad g(n) = c_1 (-1)^n + c_2 2^n \implies g(n) \asymp 2^n \end{align*} \subsection{Десен фрагмент} Алгоритъма ще приключи директно ако $n < 2$. Иначе разглеждаме останалата част на алгоритъма. От редове 4 и 7 имаме две еднакви рекурентни извиквания: \begin{align} h\left( \frac{n}{3} \right) \end{align} Ще покажем, че тялото на цикъла с условие на ред 5 ще се изпълни точно \begin{align} \left\lfloor \lg n \right\rfloor \text{ на брой пъти.} \end{align} Ако допуснем, че $n = 2^k$ за някое $k \in \mathbb{N}$, то тогава $i$ последователно ще придобие стойностите $2^1, 2^2, ..., 2^k$, тоест цикъла ще се изпълни $k = \log_2 n \in \mathbb{N}$ на брой пъти. \newline Ако $n \neq 2^k$ за което и да е $k \in \mathbb{N}$, то тогава съществува $k' \in \mathbb{N}$, такова че $2^{k'} < n < 2^{k' + 1}$ и тогава $i$ придобива стойностите $2^1, 2^2, ..., 2^{k'}$. Понеже $k' < \lg n < k' + 1$, то цикъла ще се изпълни $k' = \left\lfloor \lg n \right\rfloor \in \mathbb{N}$ на брой пъти. \begin{align*} & \text{От (3) и (4): } h(n) = 2 \, h\left( \frac{n}{3} \right) + \left\lfloor \lg n \right\rfloor \\ & \text{Тогава за } a = 2, b = 3, f(n) = c \quad \text{За } \varepsilon = \frac{1}{2}, f(n) \preceq \frac{n^{\log_3 2}}{\sqrt{n}}, \log_3 2 - \frac{1}{2} > 0 \xRightarrow[\text{Мастър Теоремата}]{\text{1 случай на}} h(n) \asymp n^{\log_3 2} \end{align*} \section{Решение} \subsection{Инверсен вектор} Инверсния вектор е $(4, 1, 1, 0, 2, 3, 0, 0, 0)$ \subsection{Алгоритъм} \begin{lstlisting} vector rebuild(vector invvec) { vector result; for (int i = 0; i < result.size(); i++) result[i] = i + 1; for (int i = invvec.size() - 1; i >= 0; i--) { for (int j = i; invvec[i] > 0; j++) { swap(result[j], result[j+1]); invvec[i]--; } } return result; } \end{lstlisting} От дефинициите, инверсният вектор съдържа броя инверсии за всяко $j$ от $1$ до $n$. Алгоритъмът \texttt{rebuild} използва сортиран вектор (масив) в който създава инверсиите от исканата пермутация. Инверсния вектор се итерира в обратен ред Нека $f(n)$ да бъде функция по големина на входа, която определя сложността по време на \texttt{rebuild}. Циклите с условия на редове 3 и 5 ще се изпълнят $n$ на брой пъти (поотделно). За всяка итерация на цикъла с условие на ред 5, вътрешния цикъл с условие на ред 6 ще се изпълни, в най-лошия случай, точно $n - i - 1$ на брой пъти, колкото е максималния брой елементи, по-големи от $i$-тия (от числото $i+1$). Тоест: \begin{align*} f(n) & = n + \sum_{i = 0}^{n-1} (n - 1 - i) + c = n + \sum_{i = 0}^{n-1} (n - 1) - \sum_{i = 0}^{n-1} i + c = n + (n-1)(n-1) - \frac{(n-1)n}{2} + c \\ & = n + n^2 -2n + 1 - \frac{1}{2}n^2 + \frac{1}{2}n + c = \frac{1}{2}n^2 - \frac{1}{2}n + 1 + c \end{align*} $f(n) \asymp n^2$ \section{Решение} \subsection{Алгоритъм} Понеже масивът е двойно индексиран, ще го наричам матрица. Нека преиндексираме входната матрица на алгоритъма: $M[0..(n-1),0..(m-1)]$, и нека $M.n$ връща $n$ и $M.m$ връща $m$. \begin{lstlisting} bool isinteresting(matrix M) { for (int i = 1; i < M.n; i++) { for (int j = 1; j < M.m; j++) { if (M[i-1, j-1] + M[i, j] > M[i-1,j] + M[i,j-1]) return false; } } return true; } \end{lstlisting} Доказателство за коректност: \subsubsection{Лема за вътрешния цикъл} По отношение на едно изпълнение на външния цикъл, ефектът на вътрешния цикъл е, че $M[i,0..(m-1)]$ са проверени и не нарушават "интересността" на матрицата. \textbf{Доказателство:} По отношение на едно изпълнение на външния цикъл: \textbf{Инвариант на вътрешния цикъл:} За всяко изпълнение на ред 3, $M[i,0..(j-1)]$ са проверени и не нарушават интересността. \begin{enumerate}[label=\arabic*.] \item \textbf{База: } При първото изпълнение на ред 3, $j = 1$ и $M[i,0]$ запазва интересността, понеже не съществува валидно $q < 0$ и неравенството се свежда до $M[0,0] \leq M[0,0]$. \item \textbf{Поддръжка: } Да допуснем, че твърдението е вярно за някое нефинално достигане на ред 3. \end{enumerate} \subsubsection{Инвариант на външния цикъл} За всяко достигане на ред 3, подматрицата $M'[0..\min\{n-1, d\}, 0..\min\{m-1, d\}]$ е интересна. \hfill Доказателство за сложност по време: \subsubsection{Формула} \subsubsection{Доказателство} \subsection{Доказателство} \subsection{Обяснение} \subsection{Алгоритъм} \end{document}