diff options
| Commit | 537f74d46862f96f8370a212749791bdf3034514 (patch) | |
|---|---|---|
| Author | 2023-03-27 16:51:28 +0300 | |
| Committer | 2023-03-27 16:51:28 +0300 | |
| Files | 1398f4daed543615ce600cebc6485cdec9f7c4ce | |
| uni-projects-537f74d46862f96f8370a212749791bdf3034514.tar uni-projects-537f74d46862f96f8370a212749791bdf3034514.tar.gz uni-projects-537f74d46862f96f8370a212749791bdf3034514.zip | ||
| Parent | 559d014561979fbb7d7bb693d87147ff61c156ed (diff) | |
[DAA/H1] More minor tweaks and fixes
2 files changed, 11 insertions, 10 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf | bin | 59909 -> 60095 bytes | |||
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex | 21 |
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf Binary files differindex e398cba..de29aab 100644 --- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex index 1d48737..b631e3d 100644 --- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex +++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex @@ -14,7 +14,7 @@ \usepackage{amsmath} % Математически символи \usepackage{amssymb} -\DeclareMathOperator{\cotg}{cotg} \DeclareMathOperator{\arccotg}{arccotg} +\usepackage{mathtools} \usepackage{amsfonts} % Още математически символи \usepackage{cancel} % Зачертаване \usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове @@ -40,8 +40,7 @@ colorlinks=true, urlcolor=blue]{hyperref} -\title{\vspace{-1.5cm}Домашно №1 по Дизайн и анализ на алгоритми на специалност Компютърни -науки, 2 поток, летен семестър 2022/2023г.} +\title{\vspace{-1.5cm}Домашно №1 по ДАА на Компютърни Науки} \author{Камен Димитров Младенов, Група 6} \date{27 Март 2023} @@ -83,6 +82,8 @@ & \leq c_2n^{\lg n + 1} - 1 \text{ за всеки избор на } c_2 > 0 \text{ и } n_0 \geq \sqrt{2} & \end{align*} +От $n^{1 + \lg n} \preceq T(n)$ и $T(n) \preceq n^{1+\lg n} - 1 \preceq n^{1+\lg n}$, следва че $T(n) \asymp n^{1+\lg n}$ + \section{Доказателство} Функцията връща $a^3$, ако $a > 0$ и $0$ иначе, където $a$ е целочислено. @@ -93,11 +94,11 @@ \begin{align*} x & = 6(i+1) \\ y & = 1+\sum_{j=0}^i6j = 1+3i(i+1) \\ - z & = \sum_{j=0}^{i-1}1 + 3j(j+1) = i + 3 \sum_{j=0}^{i-1}j(j+1) = i + 3 \left( \sum_{j=0}^{i-1} j^2 + \sum_{j=0}^{i-1} j \right) \\ + z & = \sum_{j=0}^{i-1}(1 + 3j(j+1)) = i + 3 \sum_{j=0}^{i-1}j(j+1) = i + 3 \left( \sum_{j=0}^{i-1} j^2 + \sum_{j=0}^{i-1} j \right) \\ & = i + 3 \left( \frac{(i-1)i(2(i-1)+1)}{6} + \frac{(i-1)i}{2} \right) = i + 3 \left( \frac{2i^3-2i^2}{6} \right) = i^3 \end{align*} -\textit{База:} При първото достигане на ред 4, $i = 0$ и променливите $x, y, z$ имат стойностите, зададени на ред 2. В същото време, при инварианта $x = 6(0+1) = 6, y = 1+3.0.(0+1) = 1, y = \sum_{j=0}^{-1}1 + 3j(j+1) = 0$. +\textit{База:} При първото достигане на ред 4, $i = 0$ и променливите $x, y, z$ имат стойностите, зададени на ред 2. В същото време, при инварианта $x = 6(0+1) = 6, y = 1+3.0.(0+1) = 1, z = \sum\limits_{j=0}^{-1}(1 + 3j(j+1)) = 0$. \textit{Поддръжка:} Допускаме, че твърдението е изпълнено за $k$-тото нефинално изпълнение на ред 4 (където $i = k-1$). Разглеждаме следващото достигане на ред 4. $i$ приема стойността $k$. В цикъла, след завършването на текущата итерация: \begin{align*} @@ -120,7 +121,7 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[ \textit{База:} $h-l <= 0$. В този случай, подмасивът или има само един елемент или е празен. И в двете ситуации, подмасивът е сортиран. Условието на ред 1 спира изпълнението на алгоритъма, без да е променил подмасива. -\textit{Индукционно предположение:} Допускаме, че за някои $l', h'$, $\textsc{SomeAlg}(A, l'', h'')$ сортира подмасива $A[l''..h'']$ за всички $l'' \leq l', h'' \leq h'$. +\textit{Индукционно предположение:} Допускаме, че за някои $1 \leq l' \leq n, 1 \leq h' \leq n$, $\textsc{SomeAlg}(A, l'', h'')$ сортира подмасива $A[l''..h'']$ за всички $1 \leq l'' \leq l', 1 \leq h'' \leq h'$. \textit{Индукционна стъпка:} Разглеждаме $h - l > h' - l'$. Редове 2 и 3 "сортират" първия и последния елемент в подмасива $A[l..h]$ помежду си. @@ -129,7 +130,7 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[ \begin{enumerate} \item Ако $t = 0$, то дължината на подмасива може да бъде само 2. Тогава двата елемента ще бъдат двата "крайни" елемента и от редове 2 и 3, подмасивът ще бъде сортиран. \item Иначе, ако подмасивът има повече от 2 елемента. \newline - За удобство, обозначаваме $\alpha = A[l..(l+t-1)], \beta = A[(l+t)..(h-t-1)], \gamma = A[(h-t)..h]$ (всяка съседна трета от масива) и нека $\Gamma$ да бъдат най-големите $(h-l)/3$ елемента (елементите които ще бъдат в $\gamma$ след сортиране). От индукционно предположение, можем да сортираме всяка трета поотделно, както и съседни трети ($\alpha\beta, \beta\gamma$).\newline + За удобство, обозначаваме $\alpha = A[l..(l+t-1)], \beta = A[(l+t)..(h-t-1)], \gamma = A[(h-t)..h]$ (всяка съседна трета от масива) и нека $\Gamma$ да бъдат най-големите $(h-l)/3$ елемента (елементите които ще бъдат в $\gamma$ след сортиране). От индукционно предположение, можем да сортираме всяка трета поотделно, както и съседни трети ($\alpha\beta$ и $\beta\gamma$).\newline В подмасива, елементите от $\Gamma$ ще се съдържат в $\alpha, \beta$ и/или $\gamma$. На ред 6 сортираме $\alpha\beta$, което означава че всички елементи от $\Gamma$, които са били в $\alpha\beta$, сега се съдържат само в $\beta$. На ред 7 сортираме $\beta\gamma$, което означава че всички елементи от $\Gamma$ се намират в $\gamma$ и са сортирани. @@ -137,13 +138,13 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[ Така целия подмасив е вече сортиран. \end{enumerate} -Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2, 3, 4 и 5 той извършва работа, която не зависи от входа, тоест константа работа $c$, докато на редове 6, 7 и 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде: +Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2 до 5 той извършва работа, която не зависи от входа, тоест константа работа $c$, докато на редове 6 до 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде: \begin{align*} T(n) = 3T\left(\frac{2}{3}n\right) + c \end{align*} -От 1ви случай на мастър теоремата: +Тогава: \begin{align*} - a = 3, b = \frac{3}{2}, f(n) = c \preceq \frac{n^{\log_\frac{3}{2} 3}}{n^\varepsilon} \implies T(n) \asymp n^{\log_\frac{3}{2} 3} + a = 3, b = \frac{3}{2}, f(n) = c \quad \text{За } \varepsilon = 1, f(n) \preceq \frac{n^{\log_\frac{3}{2} 3}}{n}, \log_\frac{3}{2} 3 - 1 > 0 \xRightarrow[]{\text{1 случай на Мастър Теоремата}} T(n) \asymp n^{\log_\frac{3}{2} 3} \end{align*} \end{document}
\ No newline at end of file |
