====== AISD - Lista 2. ======
{{:aisd:10.lista02.pdf|Lista 2}}.
===== Zadanie 1. =====
===== Zadanie 2. =====
Sortujemy odcinki wg $k_j$, rosnaco. Wybieramy pierwszy, potem kolejny, ktory sie zmiesci po pierwszym.

Dowod: Mamy uporzadkowanie wg algorytmu: $U$. Zalozmy, ze istnieje lepsze, optymalne uporzadkowanie odcinkow $O$. Wezmy wtedy pierwszy odcinek, ktory jest rozny w tych dwoch uporzadkowaniach $O_i \ne U_i$. Jesli odcinek $O_i$ konczy sie wczesniej niz $U_i$ to bysmy go wybrali algorytmem. Jesli konczy sie w tej samej pozycji, to nieistotne gdzie sie zaczyna. Jesli konczy sie pozniej to moze albo zmniejszyc rozmiar zbioru, albo go nie zmienic. Rozwiazanie algorytmem jest wiec najlepsze.
===== Zadanie 3. =====
<code>
L <- sort(p_i \sum k_i);
$i = 0;
$max = 0;
for p in L {
	if (p \in poczatki) {
		$i++;
		$max = $i if ($i > $max);
	} else {
		$i--;
	}
}
return $max;
</code>
===== Zadanie 4. =====
Wytwarzanie ulamka egipskiego mniejszego od $\frac{x}{y}$ o najwiekszym mianowniku:
$\frac{x}{y} \rightarrow \frac{1}{\lceil y/x \rceil}$

Licznik $\frac{x}{y} - \frac{1}{\lceil y/x \rceil}$ bedzie malal, i bedzie $\ge 0$, wiec algorytm yieldowania ulamkow sie zatrzyma: $\frac{x}{y} - \frac{1}{\lceil y/x \rceil} = \frac{x \lceil y/x \rceil - y}{x\lceil y/x \rceil}$,\\
 sprawdzmy, czy $x \lceil y/x \rceil - y < x$: $x \lceil y/x \rceil - y < x \Leftrightarrow x \lceil y/x \rceil - x < y \Leftrightarrow \lceil y/x \rceil - 1 < y/x$ - x byl rozny od zero,\\
 bo gdyby byl zerem to algorytm by sie zatrzymal wczesniej. Also: $x \lceil y/x \rceil - y \ge 0$

[[http://en.wikipedia.org/wiki/Greedy_algorithm_for_Egyptian_fractions#Algorithm_and_examples|Kontrprzykład na optymalność zachłanności]].
===== Zadanie 5. =====
Wybierając krawędzie wg algorytmu, będziemy wybierali krawędzie należące do MST (dowod niewprost, dwa przypadki, blah blah).\\ Przeto nie będzie loops. Dodajemy krawędzie aż uzyskamy jedno spójne drzewo, przeto uzyskamy MST.

===== Zadanie 6. =====
[[http://www.rspq.org/pubs/j2.pdf]]

===== Zadanie 7. =====
<code>
Dane = $\{Leaf(w_i)\}$

minEL(X) - to funkcja która zwraca drzewo ze zbioru X, o najmniejszej wartości EL(X)

while(Dane.size > 1){
      Z = {Node(a,b) : $a,b \in Dane \ \wedge \ a \not= b$}
      Node(x,y) = minEL(Z)
      Dane = Dane \ {x,y}
      Dane u= {Node(x,y)}
}

return Dane[0]
</code>

D-d v3:
Niech Z będzie drzewem zwórconym przez algorytm zachłanny.
Niech O będzie drzewem optymalnym.

NIEWPROST:
$O \not= Z$

Niech $D_i$ oznacza zawartość zmiennej Dane z algorytmu zachłannego w i-tej iteracji pętli while, czyli $D_i$ jest lasem.

Weźmy najmniejsze takie j że $\exists_{d \in D_j}$ d nie jest poddrzewem O.
Zaówżmy że istnieje dokładnie jedno takie $d \in D_j$ gdyż w każdej iteracji algorytm zachłanny dodaje tylko jedno nowe drzewo do zmiennej Dane.

Niech Node(a,b) = d.

Wiemy że $a, b \in D_{j-1}$ i a,b są poddrzewami O.
[i]j > 0 bo $D_0$ musi się zawierać w O[/i]

Niech x,y będą poddrzewami z O takimi że t=Node(a,x), t'=Node(b,y) też są poddrzewami z O.

Niech m będzie głębokość poddrzewa t w O, a m' poddrzewa t' w O.
Bez straty ogólności załóżmy że $m \ge m'$


Zbudujmy sobie drzewo O', które będzie takie samo jak O z tym że w miejscu t wstawmy Node(a,b), a w miejscu t' wstawmy Node(x,y).

Ponieważ EL(Node(a,b)) < EL(Node(a,x)) oraz x znalazło się wyżej w drzewie, a y nie zmieniło pozycji więc:
EL(O) > EL(O')
SPRZECZNOŚĆ


===== Zadanie dodatkowe 8. =====

Każdy wierzchołek w grafie ma stopień co najmniej $n/2$, więc suma stopni dwóch dowolnych wierzchołków tego grafu to co najmniej $n$, co spełnia założenie [[http://en.wikipedia.org/wiki/Ore%27s_theorem|twierdzenia Ore]], więc graf jest hamiltonowski.
 
{{tag>[listy_zadan]}}