Zestaw zadań.
1. Określić niezmienniki pętli i dokonaj analizy poprawności (częściowej, całkowitej)
algorytmu, liniowego przeszukiwania tablicy ze względu na wystąpienie elementu o
kluczu x. Wyznaczyć wrażliwość pesymistyczną i oczekiwaną algorytmu.
2. Dokonać analizy poprawności algorytmu Euklidesa wyznaczania WD (ajwiększego
Wspólnego Dzielnika) dwóch liczb naturalnych a, b. Do zbudowania niezmienników
iteracji skorzystaj z następujących własności: WD(a,b)=WD(a-b,b); WD(a,b)=
WD(b,a); WD(a,a)=a
3. Zbudować stabilny algorytm sortowania „przez wybór” oraz algorytm sortowania
„bąbelkowego” o optymistycznej złożoności obliczeniowej.
4. Znaleźć rekurencyjnie minimalny i maksymalny element tablicy. Zastosować technikę
„dziel i rządź”. Dokonać analizy złożoności obliczeniowej algorytmu.
5. Obliczyć rekurencyjnie wartość log(n!).
6. Wyznaczyć wartość n-tego wyrazu ciągu Fibonacciego metodą programowania
dynamicznego. Wyznaczyć złożoność obliczeniową algorytmu.
7. Zbudować rekurencyjny algorytm, który dla danego znaku sprawdzi czy występuje w
danym napisie, obliczy liczbę jego wystąpień oraz usunie jego wystąpienia.
8. Wypełnić „po spirali” dwuwymiarową tablicę wartościami tworzącymi ciąg arytmetyczny
o zadanym wyrazie początkowym i zadanej różnicy ciągu. Rozpatrzyć przypadek
wypełnienia zaczynając od dowolnego elementu skrajnego oraz środkowego. Zbudować
algorytm iteracyjny i rekurencyjny.
9. Sprawdzić rekurencyjnie, czy określone słowo i zdanie są palindromami.
10. Zaprojektować algorytm działający w czasie O(n), który dla danego zbioru S parami
różnych n kluczy oraz liczby dodatniej k<=n wyznacza k liczb w S, które są najbliższe
medianie zbioru S.
11. Zastosować rekurencję do wygenerowania wszystkich n! permutacji zbioru X={1, 2, ...,
n} w porządku leksykograficznym (antyleksykograficznym).
12. Zbudować algorytm rekurencyjny do rozwiązania tzw. problemu ”wież Hanoi”.
13. Metodą podstawiania rozwiązać równania rekurencyjne. Za pomocą indukcji udowodnić
ich poprawność:
T(n) = 2T(n-1) + 1
dla n ≥ 2,
T(1) = 2
T(n) = 2T(n-1) + n
dla n > 1,
T(1) = 1
14. Rozwiązać równania rekurencyjne zakładając, że T(1)=1, natomiast dla n>1zachodzi:
T(n) = 2T(n/2) + (n-1)
T(n) = nT(n-1) + n!
T(n) = 8T(n/2) + n
3
15. Uporządkować pod względem tempa wzrostu następujące funkcje:
16. Dla rekurencyjnego algorytmu sortowania „szybkiego” (Quick_sort) podać i rozwiązać
równanie rekurencyjne. Określić złożoność pesymistyczną i optymistyczną algorytmu.
17. Udowodnić, że złożoność obliczeniowa procedury podziału (Partition) algorytmu
Quick_sort jest rzędu O(n).
18. Wykazać, że złożoność algorytmu Quick_sort wynosi Θ(nlgn), gdy wszystkie elementy
tablicy mają taką samą wartość oraz Θ(n
2
), gdy uporządkowanie początkowe jest
odwrotne względem kryterium sortowania.
19. Udowodnić, że złożoność obliczeniowa algorytmu sortowania kopcowego Heap_sort
wynosi O(nlgn).
20. Wykazać, że n-elementowy kopiec ma wysokość lgn oraz, że istnieje co najwyżej n/2
h+1
węzłów o wysokości h.
21. Przedstawić tablicową reprezentację kopca. Utworzyć algorytmy (oraz podać ich
złożoność obliczeniową) do realizacji operacji: Insert, DeleteMax, Max.
22. Utworzyć procedury poprawiające kopiec „w dół” i „w górę”.
23. Zbudować algorytm sortowania przez scalanie (Merge_sort) i zastosować do
posortowania elementów tablicy. Podać równanie rekurencyjne i złożoność obliczeniową
algorytmu.
24. Przedstawić algorytm o liniowej złożoności obliczeniowej, który dwa ciągi liczb
posortowanych niemalejąco łączy w jeden posortowany ciąg.
25. Zastosować ideę algorytmu Shella do posortowania elementów tablicy, wykorzystać
elementy algorytmu Insert_Sort. Przedstawić analizę złożoności obliczeniowej algorytmu
sortowania Shella.
26. Dokonać analizy algorytmu sortowania Shella pod kątem stabilności.
27. Wstawić na n-tą pozycję listy nowy element. Założyć można, że lista posiada co najmniej
n elementów.
28. Pojedyncza, niepusta lista jednokierunkowa zakończona jest cyklem. Wyznaczyć ilość
elementów w cyklu.
29. Wyznaczyć liczbę elementów listy cyklicznej, mając wskaźnik do jednego z elementów
listy.
30. Dwie pojedyncze listy jednokierunkowe zawierają niepowtarzające się liczby naturalne
posortowane rosnąco. Przekształcić te listy w jedną listę, której elementy są posortowane
rosnąco. Listy wejściowe są usuwane z pamięci.
31. W liście jednokierunkowej usunąć powtarzające się elementy. Założyć można, ze lista jest
niepusta.
32. W dwuwymiarowej tablicy większość elementów jest równa zero. Utworzyć strukturę
dynamiczną (wskaźnikową) przechowującą w sposób efektywny (pod względem
wykorzystania pamięci) zawartość tablicy.
;
;
;
;
lg
/
;
lg
;
;
2
;
;
lg
lg
lg
)
2
/
3
(
)
2
/
(
2
2
n
n
n
n
n
n
n
n
n
n
n
n
n
33. Lista jednokierunkowa reprezentuje wielomian zadanego stopnia o współczynnikach
całkowitych. Elementy na liście ułożone są według rosnących potęg. Obliczyć różnicę
dwóch wielomianów zadanego stopnia i znaleźć reprezentację listową.
34. Wyznaczyć rekurencyjnie długość listy.
35. Dla danych wskaźników x, y wskazujących elementy dwóch rozłącznych list cyklicznych
wstawić listę wskazywaną przez y do listy po elemencie wskazywanym przez x.
36. W liście dwukierunkowej zwolnić każdy parzysty węzeł.
37. Złączyć dwie posortowane listy wykorzystując pojęcie wartownika.
38. Odwróć kolejność elementów listy dwukierunkowej.
39. Ustawić elementy na stosie w porządku rosnącym, używając jednego pomocniczego stosu
i kilku zmiennych.
40. Podać rekurencyjne algorytmy przechodzenia drzewa BST w porządku preorder, inorder
oraz postorder.
41. Utworzyć drzewo BST z uporządkowanej tablicy.
42. Wyznaczyć liczbę węzłów w drzewie binarnym, liczbę liści i wysokość drzewa.
43. Usunąć wszystkie liście z drzewa binarnego.
44. Zbudować algorytm, który dla danej pary kluczy przejrzy drzewo BST i wypisze
wszystkie klucze znajdujące się między nimi.
45. Przekształć drzewo BST w linię oraz linię w drzewo zrównoważone.