[DAA/H1] Solved second exercise

2 files changed, 25 insertions, 0 deletions

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 3ab5c11..eb73c12 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 3164a75..a4f6581 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
@@ -83,6 +83,31 @@
 
 \section{Доказателство}
 
+Функцията връща $a^3$, ако $a > 0$ и $0$ иначе, където $a$ е целочислено.
+
+\hfill
+
+\textit{Инвариант на цикъла:} За всяко достигане на ред 4, стойностите на променливите $x, y, z$ са:
+\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) \\
+	& = 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. В същото време, при инварианта $6(0+1) = 6, 1+3.0.(0+1) = 1, 0^0 = 0$.
+
+\textit{Поддръжка:} Допускаме, че твърдението е изпълнено за $k$-тото нефинално изпълнение на ред 4 (където $i = k-1$). Разглеждаме следващото достигане на ред 4. $i$ приема стойността $k$. В цикъла, след завършването на текущата итерация:
+\begin{align*}
+	\text{От ред 5} \quad & z = (k-1)^3 + (1 + 3(k-1)k) = k^3 - 3k^2 + 3k - 1 + 1 + 3k^2 - 3k = k^3 \\
+	\text{От ред 6} \quad & y = (1 + 3(k-1)k) + (6k) = 1 + 3k^2 - 3k + 6k = 1 + 3(k+1)k \\
+	\text{От ред 7} \quad & x = (6k) + 6 = 6(k+1)
+\end{align*}
+
+В същото време, спрямо новото $i$ и според твърдението, $x = 6(k+1), y = 1+3k(k+1), z = k^3$.
+
+\textit{Терминация:} От условието на ред 4, цикъла ще завърши при $(a+1)$-ото изпълнение, когато $i = a$. То тогава, от инварианта, върнатата стойност на ред 10 ще бъде точно $z = a^3$.
+
 \section{Доказателство}
 
 \end{document}
\ No newline at end of file