AISD - 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.

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;

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

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.

Zadanie 7.

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]

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 twierdzenia Ore, więc graf jest hamiltonowski.

 
aisd/10.lista02.txt · ostatnio zmienione: 2010/03/31 01:21 przez drx
 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Recent changes RSS feed