1 files changed, 38 insertions, 0 deletions
diff --git a/prog/prog-2.tex b/prog/prog-2.tex
new file mode 100644
index 0000000..f8268c0
--- /dev/null
+++ b/prog/prog-2.tex
@@ -0,0 +1,38 @@
+\documentclass[11pt]{article}
+\usepackage{../intro}
+
+\lhead{\color{gray} \small \textit{Шарафатдинов Камиль 192}}
+\rhead{\color{gray} \small \textit{аисд-2}}
+\title{Алгоритмы и структуры данных 2}
+
+\usepackage{ctable}
+
+% -- Here bet  dragons --
+\begin{document}
+\maketitle
+\drawcat{50pt}
+\clearpage
+
+\newcommand{\funcname}[1]{
+    {\incons
+        \textbf{#1}}
+}
+
+\newcommand{\len}[1]{\mathrm{len}\!\left( #1 \right)}
+
+\dmquestion{1}
+
+    Посчитаем минимальное количество вершин, которое может иметь дерево с таким свойством, назовем это число $n(h)$. У корня есть левое и правое поддеревья, высота которых отличается не более, чем на $1$, поэтому в них вершин не меньше $n(h - 1)$ и $n(h - 2)$ то есть всего вершин не меньше $n(h - 1) + n(h - 2) + 1$.
+    Теперь нам нужна какая-то база для $n$, пусть она будет такая: $n(1) = 1, \ \ n(2) = 2$. Тогда видно, что $n(h) > F_h$, где $F_k$ - k-тое число Фибоначчи. Но так как $F_k = \Theta(\phi^k)$, то, логарифмируя, получаем, что $\log_\phi n(h) \geqslant h$, где $\phi$ - некоторая константа.
+
+\dmquestion{2}
+
+    Так как $E$ и $H$ соединены ребром, то хотя бы одна из них черная, а значит, чтобы не нарушать черной высоты, $D$ должна быть черной. $A$ также должна быть черной всегда. Для все остальных вершин есть раскраски, в которых они как черного, так и красного цвета:
+
+    \medskip
+
+    \center \includegraphics[scale=0.25]{rbt.jpg}
+
+    { \color{lightgray} Я бы честно нарисовал в tikz, но нет времени :(}
+
+\end{document}