diff options
2 files changed, 221 insertions, 0 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf | bin | 0 -> 60601 bytes | |||
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex | 221 |
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf Binary files differnew file mode 100644 index 0000000..170f0e2 --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex new file mode 100644 index 0000000..1cb065b --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex @@ -0,0 +1,221 @@ +% 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<int> rebuild(vector<int> invvec) { + vector<int> 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<int, int> 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}
\ No newline at end of file |