Kierunek: informatyka, studia dzienne magisterskie
Algorytmy i struktury danych, sem.I
Algorytmy i struktury
A
danych
Imię i nazwisko
1. Dane jest jednorodne, liniowe równanie rekurencyjne:
an = -an-1 +12an-2, a1 = 10, a0 = 1
Znajdz
rozwiązanie tego równania.
2. Skorzystaj z metody rekurencji uniwersalnej i podaj dokładne asymptotyczne oszacowania dla następujących rekurencji:
(a) T(n) = 9T(n/3) + n
(b) T(n) = T(2n/3) + 1
(c) T(n) = 3T(n/4) + n lg n
3. Dla poniższego ważonego grafu nieskierowanego wyznaczyć minimalne drzewo rozpinające (MST),
posługując się algorytmem Kruskala.
3
a b
2
1 4
2 1
4
3 2 3
c
h d e i
2
4
2
1
5
1
f g
2
4. Przypuśćmy, że w dyskretnym problemie plecakowym kolejność przedmiotów uporządkowanych rosnąco według
ciężaru jest taka sama, jak przy uporządkowaniu malejącym według wartości. Podaj efektywny algorytm znajdujący
optymalne rozwiązanie dla tej wersji problemu plecakowego i uzasadnij jego poprawność.
5. Dla poniższej sieci połączeń między miastami wyznaczyć minimalną ścieżkę z miasta a do k, posługując strategią
programowania dynamicznego. Podaj wszystkie optymalne rozwiązania.
g
6 3
2
4
e j
b
5
6 2
2
2
3 2
a c f h k
5
3
1 2 1
2
3
d
g i
8 2
5
2 2
3
4
g g
- 1 -
Kierunek: informatyka, studia dzienne magisterskie
Algorytmy i struktury danych, sem.I
6. Udowodnij, że
{(x > 0) '"
'" (y > 0)}
'"
'"
spec
z�!
�!0;
�!
�!
u�!
�!x;
�!
�!
repeat
z�!
�!z + y;
�!
�!
u�!
�!u - 1;
�!
�!
until u = 0
endspec
{z�!
�!x*y}
�!
�!
- 2 -