ASD ep 08 2003 D 1

Algorytmy i Struktury Danych (grupa D)

Egzamin poprawkowy PJWSTK 8 września 2003

Zadanie 1

(a) Przy każdej z wymienionych funkcji zmiennej naturalnej n, n>0, napisz jej oszacowanie (w możliwie najprostszej postaci) przy pomocy notacji 0 :

f, (n) = (Ig n) Vn + Ig n! f₂(n) = 2" + 3" + n fj(n) = lg(3^+lg(2")    f₄(n) =1000 n² + (1/I000)n³

(b) Uporządkuj wyżej wymienione funkcje, wypisując tylko ich numery, w porządku rosnących rzędów:

(c) Niech f będzie funkcją określoną w zbiorze liczb naturalnych większych od zera, f(n) = (n^: + Ig n + 3Vn +100)( n+1). Oceń. czy podane ograniczenia funkcji są, czy nie są poprawne:

f(n) = CXn^4)	tak	nie
f(n) = £2 (n)	tak	nic
f(n) = 0(lg n)	tak	nic

Zadanie 2

Niech M będzie macierzą incydencji pewnego niezorientowanego grafu G. którego wierzchołki zostały ponumerowane od 1 do 5. Element M(i.j) macierzy M jest wagą krawędzi od wierzchołka i do wierzchołka j.

(a)    Narysuj ten graf oraz jego minimalne drzewo rozpinające, otrzymane w wyniku zastosowania algorytmu Kruskala.

(b)    Wypisz kolejkę krawędzi i podaj kolejność w jakiej są akceptowane krawędzie tego drzewa.

(c) Jaki byłby koszt drzewa rozpinającego dla spójnego grafu o n wierzchołkach i dokładnie n-1 krawędziach? Zakładamy, że f jest funkcją kosztu dla krawędzi. Odpowiedź uzasadnij.

M:

Graf:

Drzewo rozpinające

0	2	0	3	2
2	0	3	4	2
0	3	0	3	4
3	4	3	0	3
2	2	4	3	0

Zadanie 3

Niech M będzie macierzą sąsiedztwa (incydencji), o której mowa w poprzednim zadaniu, (a) Zbuduj drzewo prefiksowego kodu Huffmana dla wag z macierzy M:

Drzewo Kodowe: