Algorytmy i struktury danych - ...

[ Pobierz całość w formacie PDF ]
Kierunek: informatyka, studia dzienne magisterskie
Algorytmy i struktury danych, sem.I
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
.
a
3
b
2
1
4
2
1
4
c
3
2
3
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
a
c
3
f
h
2
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 -
  [ Pobierz całość w formacie PDF ]