AISDE - Kolokwium 1 7 maja 2007
|
Tu podpisać:
|
Zadanie 1
Dane: liczba naturalna N Wynik: liczba naturalna S. Function S = Alg (N) If (N==1) S=1; Else S=N+Alg(N-1); End Dla podanego algorytmu narysować drzewo rekursji i napisać wzory analityczne na: wynik S, złożoność czasową t(N), gdy operacją dominującą jest dodawanie. |
S =
t(N) =
Drzewo rekursji:
|
Zadanie 2
Oszacować asymptotycznie dokładnie podaną niżej funkcje. Udowodnić prawdziwość oszacowania za pomocą twierdzenia o granicy.
|
g(n) = Dowód: |
Zadanie 3
Dla wykładnika m algorytm rec_power wykonał 10 mnożeń, zaś dla wykładnika zwiększonego o 1 wykonał 5 mnożeń. Określić m. |
m =
|
Zadanie 4
„Złożoność czasowa optymistyczna problemu abstrakcyjnego sortowania elementów zbioru uporządkowanego {a1, a2,..., an} jest Θ(n).”
Co można powiedzieć o tym zdaniu? Jest prawdziwe/fałszywe/bezsensowne. Dlaczego?
|
Zdanie jest ...................................................... ponieważ.......................................................... ......................................................................... ......................................................................... ......................................................................... ......................................................................... ......................................................................... ......................................................................... |
Zadanie 5
Algorytmem insertionsort z wartownikiem za pomocą 10 porównań posortowano ciąg 10-o-wyrazowy złożony z elementów zbioru <1, 10>. Jaką postać miał ten ciąg przed posortowaniem? Czy dane te są pesymistyczne, optymistyczne, pośrednie? Ile wykonano przypisań? |
Ciąg miał postać: ..........................................................................
Dane te są ........................................................
Wykonano ....................... przypisań. |
Zadanie 6
Ciąg 10-o wyrazowy złożony z elementów zbioru <1, 10> posortowano algorytmem insertionsort bez wartownika i algorytmem selectionsort. W obu przypadkach liczba operacji porównania elementów sortowanych wyniosła tyle samo. Jaką postać miał ten ciąg przed posortowaniem? Czy dla insertionsort są to dane pesymistyczne, optymistyczne, pośrednie? A co można powiedzieć o tych danych dla selectionsort? |
Ciąg miał postać: ..........................................................................
Dane te są ........................................................
W przypadku selectionsort ............................. ......................................................................... |
Zadanie 7
Tablicę [6,4,5,1,2,3] przekształcono w kopiec typu max za pomocą algorytmu buildheap. Ile porównań wykonał algorytm? Ile wykonano wzajemnych przestawień i dlaczego? |
Liczba porównań = Liczba wzajemnych przestawień = Dlaczego? ....................................................... ......................................................................... |
Zadanie 8
Algorytm quicksort wykonano dla danych a=[1,2,3,4,5,6]. Czy są to dane pesymistyczne, optymistyczne, pośrednie? Podać zawartość tablicy „a” i indeks „j” po pierwszym wykonaniu partition. Zakładając, że dla n danych partition wykonuje n porównań, określić złożoność quicksort dla tych danych. |
Są to dane ......................................................
Po pierwszym wykonaniu partition: a = [............................................................] j =
Złożoność wynosi ................................ |
Zadanie 9
Algorytmem radixsort posortowano n liczb 32 bitowych stosując podział na grupy e=2 bitowe. Podać złożoność czasową w funkcji n, jeżeli jedna operacja dominująca obejmuje wszystkie operacje wykonywane na każdej komórce użytych tablic. Jeżeli n=50, a rozmiar grupy zwiększono dwa razy, to które z podanych zdań są prawdziwe? Uzasadnić. |
Złożoność czasowa t(n) =
Złożoność zmalała wykładniczo .................... Złożoność wzrosła około 2 razy .................... Złożoność zmalała około 2 razy .................... Złożoność wzrosła wykładniczo.................... Dlaczego? ...................................................... ........................................................................ ........................................................................ |
Zadanie 10
Algorytmem bucketsort omawianym na wykładzie sortujemy ciąg {1,2,3,4,50}. Operacją dominująca są porównania elementów sortowanych. Czy podane dane są pesymistyczne? Ilu operacji porównania t wymagało to sortowanie? Ile kubełków jest niepustych? |
Czy dane pesymistyczne? .............................
t =
Liczba niepustych kubełków = |