1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
% 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{enumitem}
\setlist[enumerate]{label=\arabic*.}
\renewcommand{\thesection}{Задача \arabic{section}.}
\let\oldforall\forall
\renewcommand{\forall}{\; \oldforall}
\let\oldexist\exists
\renewcommand{\exists}{\; \oldexist}
\setlist[enumerate]{label=\Roman*.}
\usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023},
pdftitle={Домашна работа 1 по ДАА},
pdfsubject={},
pdfkeywords={},
colorlinks=true,
urlcolor=blue]{hyperref}
\title{\vspace{-1.5cm}Домашно №1 по ДАА на Компютърни Науки}
\author{Камен Димитров Младенов, Група 6}
\date{27 Март 2023}
\begin{document}
\maketitle
\section{Доказателство}
\textbf{I.} Ще докажем, че $n^{1 + \lg n} \preceq T(n)$ с индукция по n.
По дефиниция, това е същото като да докажем, че съществува положителна константа $c_1$ и положително $n_0$, такова че за всяко $n \geq n_0$, $T(n) \geq c_1 n^{1+\lg n}$.
Индуктивното предположение е, че
\begin{align*}
T\left(\frac{n}{2}\right) \geq c_1 \left(\frac{n}{2}\right)^{1+\lg \frac{n}{2}}
\end{align*}
Тогава
\begin{align*}
T(n) = n^2 T\left(\frac{n}{2}\right)+1 & \geq n^2 . c_1 \left(\frac{n}{2}\right)^{1+\lg \frac{n}{2}} + 1 && \\
& = n^2 c_1 \frac{n^{\lg n}}{2^{\lg n}} + 1 & \text{// } & \lg \frac{n}{2} = \lg n - \lg 2 \\
& = c_1 n^{1+\lg n} \frac{n}{2^{\lg n}} + 1 && \\
& = c_1 n^{1+\lg n} + 1 & \text{// } & \frac{n}{2^{\lg n}} = \frac{n}{n} = 1 \\
& \geq c_1 n^{1+\lg n} \text{ за всеки избор на } c_1 > 0 \text{ и } n_0 > 0 &&
\end{align*}
\textbf{II.} Ще засилим твърдението и ще докажем, че $T(n) \preceq n^{1+\lg n} - 1$ с индукция по n, тоест че $\exists c_2 > 0 \exists n_0 > 0 \forall n \geq n_0 : T(n) \leq c_2 n^{1 + \lg n} - 1$
Индуктивното предположение е, че
\begin{align*}
T\left(\frac{n}{2}\right) \leq c_2 \left(\frac{n}{2}\right)^{1 + \lg \frac{n}{2}} - 1
\end{align*}
И тогава
\begin{align*}
T(n) = n^2 T\left(\frac{n}{2}\right)+1 & \leq n^2 \left( c_2 \left(\frac{n}{2}\right)^{1 + \lg \frac{n}{2}} - 1 \right) + 1 & \\
& = c_2n^{\lg n + 1} - n^2 + 1 & \text{// От I.} \\
& = c_2n^{\lg n + 1} - 1 - n^2 + 2 & \\
& \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$ е целочислено.
\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}{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, z = \sum\limits_{j=0}^{-1}(1 + 3j(j+1)) = 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{Решение}
$\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[1..n]$. Тоест, $\textsc{SomeAlg}(A, 1, n)$ ще сортира целия масив $A[1..n]$.
Ще докажем коректността на алгоритъма с индукция по $h-l$ (което се явява дължината на нашия подмасив минус едно).
\textit{База:} $h-l <= 0$. В този случай, подмасивът или има само един елемент или е празен. И в двете ситуации, подмасивът е сортиран. Условието на ред 1 спира изпълнението на алгоритъма, без да е променил подмасива.
\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]$ помежду си.
На ред 4, $t$ става една трета от дължината на подмасива, закръглена надолу.
Разглеждаме два случая относно условието на ред 5:
\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
В подмасива, елементите от $\Gamma$ ще се съдържат в $\alpha, \beta$ и/или $\gamma$.
На ред 6 сортираме $\alpha\beta$, което означава че всички елементи от $\Gamma$, които са били в $\alpha\beta$, сега се съдържат само в $\beta$.
На ред 7 сортираме $\beta\gamma$, което означава че всички елементи от $\Gamma$ се намират в $\gamma$ и са сортирани.
На ред 8 сортираме всички останали елементи, които са в $\alpha\beta$ (и са по-малки от тези в $\gamma$). \newline
Така целия подмасив е вече сортиран.
\end{enumerate}
\hfill
Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2 до 5 той извършва работа, която не зависи от входа, тоест константа работа $c$, докато на редове 6 до 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде:
\begin{gather*}
T(n) = 3T\left(\frac{2}{3}n\right) + c \text{, тогава} \\
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{Мастър Теоремата}]{\text{1 случай на}} T(n) \asymp n^{\log_\frac{3}{2} 3}
\end{gather*}
Проф. Дълбоков е прав, понеже ако $l \geq h$ то $h - l \leq 0$ и на ред 4: $t \leq 0$. Условието на ред 5 никога няма да бъде изпълнено и алгоритъмът ще завърши без да извърши рекурсивни извиквания.
\end{document}
|
