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 fun­kcje. 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 pra­wdziwe/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, opty­mistyczne, 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, opty­mistyczne, 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 =

---