Kierunek: informatyka, studia dzienne magisterskie
Algorytmy i struktury danych, sem.I
- 1 -
A
Algorytmy i struktury
danych
Imi i nazwisko
1. Dane jest jednorodne, liniowe równanie rekurencyjne:
a
n
= -a
n-1
+12a
n-2
, a
1
= 10, a
0
= 1
Znajd 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.
c
h
d
a
f
g
b
e
i
1
3
2
1
4
2
1
2
4
1
3
2
2
2
4
5
3
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.
a
b
c
d
g
g
f
h
e
g
i
g
j
k
2
4
2
1
2
2
1
2
2
2
5
6
3
5
3
3
8
2
3
4
2
5
6
3
2
