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 = n*(n+1)/2 t(N) ={1+t(N-1) gdy N>1, 0 gdy N=1} Drzewo rekursji: N 1 (N-1) 1 (N-2) 1 … 2 1 1 0 Suma = N-1

Zadanie 2

Oszacować asymptotycznie dokładnie podaną niżej fun­kcje. Udowodnić prawdziwość oszacowania za pomocą twierdzenia o granicy.

g(n) = 1 Dowód: Wystarczy pokazać takie liczby a oraz b, żeby a < lim (f(n)/g(n)) < b (Możliwe, że w definicji są nierówności słabe <=, jednak jeśli pokażę coś dla mocniejszego warunku to i dla słabszego zadziała) a=sqrt(2) b=sqrt(3) Bo: Rozpiszmy wartość pod pierwiastkiem jako 2+logn/n. Logarytm dąży do nieskończoności wolniej niż n, dlatego logn/n w granicy =0. Wartość pod pierwiastkiem wpada między 2 i 3, dlatego sam pierwiastek między sqrt(2) i sqrt(3)

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. Propozycja modyfikacji: Dla wykładnika m algorytm rec_power wykonał 10 mnożeń, zaś dla wykładnika zwiększonego o 1 wykonał 6 mnożeń. Określić m.

Uważam, że nie istnieje m spełniające takie warunki. Zauważmy, że dla algorytmu rec_power W(n)/B(n)=W(x)/B(x)=2. (asymptotyczne ograniczenia ze względu na liczbę bitów wykładnika czy też jego dziesiętną postać mają się do siebie jak 2/1) W(n) i B(n) to funkcje ściśle rosnące, oraz NIEOKREŚLONE w tych samych punktach - dane nie mogą być optymistyczne i pesymistyczna zarazem. Gdyby zmodyfikować treść - m=63.

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 bezsensowne ponieważ pojęcia złożoności dotyczą algorytmów, a nie problemów abstrakcyjnych.

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ć: 1,2,3,4,5,6,7,8,9,10 (10 porównań - każdy element porównujemy z wartownikiem) Dane te są optymistyczne.. Wykonano 3(n-1)=27 przypisań. (Nie wiem czemu - wzór z wykładu 4.

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ń = 5(3?5,2?4,1?4,5?6,4?6) Liczba wzajemnych przestawień = 0 Dlaczego? Drzewo utworzone z tablicy spełnia warunek kopca

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) = b/e*(4n+2^(e+1)-2)=16(4n+6)=16*206 t'(n)=8(4n+30)=8*230 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 „Prawda”. Złożoność wzrosła wykładniczo.................... Dlaczego? Czynnik 1/e ma większe znaczenie dla małych liczb niż wykładniczy exp(e)

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?

Skoro ma być to specyficzny bucketsort z wykładu, to liczby poddawane działaniu tego algorytmu mają znajdować się w przedziale [0,1). Ponieważ pierwszy element ciągu - 1 nie znajduje się w ww przedziale algorytm nie może być wykonany.

---