WEJSCIÓWKA 1 (weryfikacja algorytmu + rzędy funkcji) ASD 2002/2003

 

1. Niech n będzie liczbą naturalną, x prwną liczba rzeczywistą,  a a1, ... an, ciągiem liczb rzeczywistych .

begin i := n;   s := an; j := 1;

while i >0 do  j := j+1; s := s*x + a i-1;  i := i-1; j := j+1 od;

end

(a) Co robi powyższy algorytm? (1p)

(b) Znaleźć niezmiennik pętli wyrażający zależność między zmiennymi j oraz i.(2p)

 

2.  Niech n będzie liczbą naturalną, x prwną liczba rzeczywistą,  a a1, ... an, ciągiem liczb rzeczywistych .

begin i := n;   s := an; j := 1;

while i >0 do  j := j+1; s := s*x + a i-1;  j := j+1 od;

end

(a) Ile mnożeń wykona ten program dla n=100? (1p)

(b) Znaleźć niezmiennik pętli wyrażający zależność między zmiennymi n oraz i.(2p)

 

3. Niech n będzie liczbą naturalną, x prwną liczba rzeczywistą,  a a1, ... an, ciągiem liczb rzeczywistych .

begin i := n;   s := an; p :=x; j :=1;

while i >0 do  j := j+1; s := s*x + a i-1;  p := p*x; i := i-1; j := j+1 od;

end

(a) Ile mnożeń wykona ten program dla n=100? (1p)

(b) Znaleźć niezmiennik pętli wyrażający zależność między zmiennymi p oraz j.(2p)

 

4. Porównać rzędy następujących funkcji i, o ile nie są to funkcje tego samego rzędu, zaznaczyć funkcję, która ma większy rząd :

(a) (100 n log n + 2n +100)/(n+1)                   2 ln n                           (1p)

(b) 10*4  lg n                                                    1000*3  lg n                   (1p)

 

5. Porównać rzędy następujących funkcji i, o ile nie są to funkcje tego samego rzędu, zaznaczyć funkcję, która ma większy rząd:

(a) (100 n3 + 2n +100)/(n3+1)             (n3+1)*(n-1)               (1p)

(b) 10*2 10 lg n                                                 3n +n3                           (1p)

 

6. Porównać rzędy następujących funkcji i, o ile nie są to funkcje tego samego rzędu,  zaznaczyć funkcję, która ma większy rząd:

(a) (100 n2 + 2n +100)/(n+1)              (n+1)*(n-1)     (1p)

(b) 10*2 lg n                                         3n +n3               (1p)

 

Wejściówka 2  (Wyszukiwanie + notacja asymptotyczna) ASD2002/2003  

 

 

1.      (a)Jaka metoda poszukiwań danego elementu x, w n-elementowym ciągu uporządkowanym, zapewnia minimalny koszt wyszukiwania i (b) jaki jest rząd kosztu tej metody?

2.      Oceń prawdziwość podanych równości

2 n+1 = O(2n)

4lg2n = O(42lgn)

n2 = O(4 n)

 

3.      (a)Jaka jest wysokość drzewa turniejowego zbudowanego dla znalezienia drugiego co do wielkości elementu w danym k elementowym zbiorze? (b) Jaka jest złożoność algorytmu turniej?

4.      Oceń prawdziwość podanych równości

3 n+1 = O(2n)

52n = O(n!)

n2 = O(lg 4 n)

 

5.      (a)Ile porównań wykona optymalny algorytm wyszukiwania równoczesnego minimum i maksimum zastosowany do ciągu 5 6 2 1 8 4?  (b)Jaka jest złożoność tego algorytmu?

6.      Oceń prawdziwość podanych równości

4 (lg n)+1 = O(n2)

log 52n = O(lg n)

n4 = O(4 n)

 

WEJSCIÓWKA 3 (wyszukiwanie) ASD 2002/2003

 

1.      Jaki jest koszt znalezienia drugiego co do wielkości elementu w ciągu n-elementowym metodą turnieju?   

2.      Ile dokładnie porównań trzeba wykonać dla znalezienia 3go co do wielkości elementu w zbiorze 6,2,3,7,1,5,9,8 metodą Hoare?

3.      Załóżmy, że algorytm A ma złożoność T(n) = 2lg n. Czas wykonania tego algorytmu dla danych rozmiaru 64 wynosi t jednostek czasu. Jaki jest czas wykonania tego algorytmu dla danych 8 razy większych?

 

 

4.      Jaką liczbę porównań wykonuje algorytm SPLIT(rozdzielania zbiorów) zastosowany do ciągu n elementowego? 

5.      Ile dokładnie porównań trzeba wykonać dla znalezienia 4go co do wielkości elementu w zbiorze 6,2,3,7,1,5,9,8 metodą Hoare?

6.      Załóżmy, że algorytm A ma złożoność T(n) = 3n2. Czas wykonania tego algorytmu dla danych rozmiaru 6 wynosi t jednostek czasu. Jaki jest czas wykonania tego algorytmu dla danych 4 razy większych?

 

 

7.      Jaka jest złożoność algorytmy Hoare wyszukiwania k-tego co do wielkości elementu w ciągu n-elementowym?   

8.      Ile dokładnie porównań trzeba wykonać dla znalezienia 7go co do wielkości elementu w zbiorze 6,2,3,7,1,5,9,8 metodą Hoare?

9.      Załóżmy, że algorytm A ma złożoność T(n) = 2n3. Czas wykonania tego algorytmu dla danych rozmiaru 8 wynosi t jednostek czasu. Jaki jest czas wykonania tego algorytmu dla danych 2 razy większych?

 

Wejściówka 4 (sortowanie) ASD 2002/2003

 

1.Dana jest tablica T o elementach 5,7,3,8,4. Wypisz stan tej tablicy po każdej z kolejnych iteracji algorytmu insertion sort i policz liczbę wykonanych porównań.

2.Wypisz kolejne pary elementów porównywanych w trakcie realizacji algorytmu selection sort zastosowanego do ciągu 5,7,3,8,4.

Jaki jest koszt algorytmu sortowania przez scalanie zastosowanego do  k-elementowego ciągu.

 

3.Dana jest tablica T o elementach 4,10,1,12,3. Wypisz stan tej tablicy po każdej z kolejnych iteracji algorytmu insertion sort  i policz liczbę wykonanych porównań.

4.Wypisz kolejne pary elementów porównywanych w trakcie realizacji algorytmu selection sort zastosowanego do ciągu 4,10,1,12,3.

Jaki jest koszt w najgorszym przypadku algorytmu sortowania szybkiego sortowania  zastosowanego do  k-elementowego ciągu.

 

5.Dana jest tablica T o elementach 3,4,1,5,2. Wypisz stan tej tablicy po każdej z kolejnych iteracji algorytmu insertion sort i policz liczbę wykonanych porównań.

6.Wypisz kolejne pary elementów porównywanych w trakcie realizacji algorytmu selection sort zastosowanego do ciągu 3,4,1,5,2.

7.Jaki jest koszt średni algorytmu sortowania przez wybór zastosowanego do  p-elementowego ciągu.