Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit537f74d46862f96f8370a212749791bdf3034514 (patch)
Author
 Syndamia <kamen@syndamia.com>
2023-03-27 16:51:28 +0300
Committer
 Syndamia <kamen@syndamia.com>
2023-03-27 16:51:28 +0300
Files1398f4daed543615ce600cebc6485cdec9f7c4ce
uni-projects-537f74d46862f96f8370a212749791bdf3034514.tar
uni-projects-537f74d46862f96f8370a212749791bdf3034514.tar.gz
uni-projects-537f74d46862f96f8370a212749791bdf3034514.zip
Parent559d014561979fbb7d7bb693d87147ff61c156ed (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.pdfbin59909 -> 60095 bytes
-rw-r--r--Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex21
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf
index 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
Binary files differ
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