AISDE  Kolokwium 1 Tu podpisać:
Zadanie 1
Dane: tablica X o długości N.
Wynik: tablica X o długości N. X(i)=
Function X = Alg (X)
N=length(X);
K=1; W(N)=
While (K<=N)
For I =1 : K
X(I) = 2*X(I) B(N)=
End
K=K+1;
End
End A(N)=
Dla podanego algorytmu napisać wzory na i-
ty element wyniku X, je\
eli znana jest i-ta
dana xi oraz na zło\
oność czasową pesymis-
tycznÄ… W(N), optymistycznÄ… B(N), oczeki-
waną A(N). Za operację dominującą przyjąć
mno\
enie.
Zadanie 2
Wykazać z granicy, \
e
n3(n + log2 n) +1 = Åš(n2 )
Zadanie 3
Wykonano algorytm Euclid (a, 13) z funkcją Liczba wywołań rekurencji =
modulo. Dobrać tak a > 13, by były to dane
pesymistyczne. Ile razy w tym przypadku NWD =
zostanie wywołana rekurencja? Jaki wynik
NWD zwróci algorytm?
Zadanie 4
Posortowanie rosnÄ…ce tablicy a=[100, 30, 40, Ä„ (wsk) =
10, 60] sprowadzi siÄ™ do wykonania na niej
pewnej permutacji Ä„. JakÄ… tablice otrzymamy, a(Ä„(wsk(1)))=
je\
eli tÄ™ samÄ… permutacjÄ™ Ä„ zastosujemy do
tablicy wsk=1 : 5. Określić elementy: a(Ą(wsk(5)))=
a(Ä„(wsk(1))), a(Ä„(wsk(5))).
Zadanie 5
Problem wie\
Hanoi mo\
na rozwiązać algo-
rytmem rekurencyjnym o zło\
oności t(n)
opisanej równaniem:
1 n = 1
Å„Å‚
t(n) =
òÅ‚2t(n -1) +1 n > 1
ół
Zaproponować ogólną postać rozwiązania t(n)
i określić jego postać konkretną metodą pods-
tawienia.
Zadanie 6
Tablica a=[10, 3, 6, 8, 7, 4, 2, 5] nie spełnia Na początku: [10, 3, 6, 8, 7, 4, 2, 5]
właściwości kopca na jednej pozycji, zloka- Po 1 kroku:
lizować tę pozycję i przywrócić właściwość Itd.
kopca algorytmem heapify. Wypisać ciąg
wartości tablicy a po kolejnych przestawie-
niach elementów wykonanych przez heapify.
Zadanie 7
Uzupełnij zdania określając klasę zło\
oności, np. liniowa, kwadratowa, wykładnicza:
Oczekiwana zło\
oność czasowa selectionsort jest................................................
Optymistyczna zło\
oność czasowa insertionsort jest............................................
Pesymistyczna zło\
oność czasowa quicksort jest..................................................
Optymistyczna zło\
oność rekurencyjnego potęgowania jest ...............................
Oczekiwana zło\
oność czasowa heapsort jest .....................................................
Pesymistyczna zło\
oność czasowa radixsort jest .................................................
Pesymistyczna zło\
oność czasowa bucketsort jest ...............................................
Optymistyczna zło\
oność czasowa bucketsort jest ...............................................
Zadanie 8
Mamy do posortowania liczby a=[15,12,3,0] Na poczÄ…tku: a=[15,12,3,0]
algorytmem radixsort przy b=4 i e=2. Pokazać Po 1 przebiegu:
zawartość tablicy a po kolejnych przebiegach Itd.
algorytmu.
Zadanie 9
Algorytmem bucketsort sortujemy n=100 E=
liczb. Ile wynosi wartość oczekiwana E liczby W=
elementów w jednym kubełku przy zało\
eniu
rozkładu równomiernego danych? Ile wynosi Porównania występują w ...............................
pesymistyczna liczba porównań W? Gdzie ........................................................................
występują porównania?
AISDT  Kolokwium 1 Tu podpisać:
Zadanie 1.
Krzywa zamknięta o długości x stanowi brz-
eg pewnej figury płaskiej o powierzchni S.
S
Problem znalezienia wszystkich mo\
liwych S
figur o obwodzie x stanowi problem abstrak-
cyjny Q(x, S), tzn. x i S sÄ… w relacji dwuargu-
mentowej. Zinterpretować tę relację na płasz-
czyz
nie (x, S). Wskazówka: Jaka figura o
x
obwodzie x ma największe pole powierzchni?
Czy relacja Q jest w tym przypadku funkcjÄ…? Odp.:
Zadanie 2
Dane: tablica X o długości N.
Wynik: tablica X o długości N. X(i)=
Function X = Alg (X)
N=length(X);
For I = 1: N W(N)=
K=1;
While K<= I
X(I) = 3*X(I) B(N)=
K=K+1;
End
End
End A(N)=
Dla podanego algorytmu napisać wzory na i-
ty element wyniku X, je\
eli znana jest i-ta
dana xi oraz na zło\
oność czasową pesymis-
tycznÄ… W(N), optymistycznÄ… B(N), oczeki-
waną A(N). Za operację dominującą przyjąć
mno\
enie.
Zadanie 3
W tablicy a=1:100 szukamy sekwencyjnie li-
czby x losowanej z rozkładem określonym Ogólnie A=
instrukcjÄ… x=ceil(49*rand). Ile wynosi w tym
przypadku wartość oczekiwana liczby porów-
nań (czyli zło\
oność oczekiwana A algorytmu Liczbowo A=
search)? Podać wzór ogólny dla tego przypa-
dku i wynik liczbowy.
Zadanie 4
Procedura merge dokonuje scalenia dwóch Na początku: [3, 5, 7 | 1, 4, 6]
ciągów posortowanych znajdujących się w Po 1 kroku:
następującej tablicy: a=[3, 5, 7 | 1, 4, 6]. Itd.
Wypisać zawartość tej tablicy po kolejnych
przestawieniach wykonanych przez merge.
Zadanie 5
ZÅ‚o\
oność pewnego algorytmu  dziel i zwy-
ciÄ™\
aj wykonujÄ…cego w istocie sekwencyjne
przeszukanie całej tablicy daje się opisać
równaniem:
Å„Å‚
ôÅ‚0 n d" 1n
t(n) =
òÅ‚t(n) + t( ) +1 n > 1
ôÅ‚
ół 2 2
Zaproponować postać t(n) i znalez
ć to rozwią-
zanie metodÄ… podstawienia lub z drzewa
rekurencji.
Zadanie 6
Element E prawidłowego kopca typu max Pozycja parent(E)=
znajduje się na pozycji 11. Długość heapsize
tego kopca wynosi 21. Wskazać pozycje, na Pozycja left(E)=
których znajdują się: parent elementu E, lewy
potomek elementu E, największy element Pozycja maksymalnego elementu kopca=
kopca. Podać wysokość kopca H. H=
Zadanie 7
Dane dla algorytmu partition w tablicy a o dł- E{J}=
ugości 10 stanową realizacje zmiennej loso-
wej o rozkładzie równomiernym. Partition
zwraca tablicÄ™ a odpowiednio uporzÄ…dkowanÄ… V=
oraz indeks podziału J. Ile wynosi wartość
oczekiwana J w tym przypadku? Jednym z
wyników partition dla pewnej realizacji da- J=
nych jest tablica a =[7,3,6,1,2,5,4,10,8,9].
Podać w tym przypadku wartość elementu
dzielącego V i indeks podziału J.
Zadanie 8
Algorytmem bucketsort sortujemy n=100 li- E=
czb. Ile wynosi wartość oczekiwana E liczby B=
elementów w jednym kubełku przy zało\
eniu
rozkładu równomiernego? Ile wynosi opty- Porównania występują w ...............................
mistyczna liczba porównań B? Gdzie w tym ........................................................................
algorytmie występują porównania?
Zadanie 9
Wykazać z granicy, \
e
log2 n2 (log2 n +1) = Åš(log2 n)