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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
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}
|