Algorytmy i Struktury Danych - wyłącznie Przykładowe tematy Egzaminu

Temat 1

O(1) dla n<a

Dana jest funkcja opisująca czas działania algorytmu: T(n) =

2T(n/2)+ O(n) dla n>a

Omówić składniki tej funkcji oraz algorytmy, których czas realizacji spełnia rzeczoną zależność. Temat 2

Na przykładzie problemu plecakowego, omówić klasę zagadnień, którego jest on reprezentantem. Temat 3 Scharakteryzować notacje O, Θ oraz Ω i podać ich własności.

Omówić przyczynę powstania notacji. Jakie korzyści dają notacje ? Temat 4

Podać algorytm realizujący tablicę Pascala. Omówić klasę zagadnień, której jest przedstawicielem. Temat 5. Omówić problematykę złożoności obliczeniowej i przedstawić sposoby jej obliczania. Temat 6

Omówić metody wyznaczania ciągu liczb Fibonacciego. Przeanalizować złożoność obliczeniową. Temat 7

Przestawić równania rekurencyjne opisujące złożoność obliczeniową. Podać sposoby ich rozwiązania. Podać przykłady algorytmów, które można nimi opisać.

Temat 8 Scharakteryzować metody projektowania algorytmów. Podać kryteria ich wyboru. Temat 9 Omówić strategię projektowania algorytmów metodą "dziel i zwyciężaj". Załączyć przykłady algorytmów. Podać sugestie stosowania tej strategii.

Temat 10. Omówić problematykę algorytmów zachłannych i podać stosowne przykłady.

Temat 11. Omówić technikę programowania dynamicznego; przedstawić stosowne algorytmy. Temat 12

Omówić tematykę reprezentowaną przez problem Hetmanów (aspekt implementacyjny, algorytm). Temat 13

Dowieść, że algorytm sortowania przez proste wstawianie ma czas realizacji zawarty od O(n) do O(n²). Temat 14

Omówić możliwe aspekty poprawiania efektywności sortowania przez wstawianie.

Podać stosowne przykłady i algorytmy.

Temat 15

Porównać sortowanie bąbelkowe(BubbleSort) i sortowanie przez wytrząsanie (ShakerSort).

Podać w kodzie pseudojęzyka wymienione algorytmy.

Temat 16. Przedstawić i omówić algorytm sortowania Shella. Porównać z BubbleSort.

Temat 17

Omówić strategię szybkiego sortowania (QuickSort). Podać algorytmy realizujące funkcje podziału metodą.

Przedyskutować problem złożoności.

Temat 18

Omówić strategię sortowania przez zliczanie. Podać przykład procesu sortowania.

Temat 19. Porównać metodykę sortowania pozycyjnego i kubełkowego.

Temat 20. Przedstawić i omówić algorytmy sortowania pozycyjnego (rada sort).

Temat 21. Przedstawić i omówić algorytmy sortowania klasy O(n); przykłady sortowania.

Temat 22

Omówić działanie stosu oraz przedstawić algorytmy funkcji niezbędnych do jego funkcjonowania.

Przedstawić metody implementacji stosu i problemy z tego wynikające.

Temat 23 Omówić kolejkę oraz przedstawić algorytmy funkcji niezbędnych do jej funkcjonowania.

Temat 24

Omówić listę jednokierunkową oraz mechanizmy wstawiania i usuwania z niej elementów.

Podać przykłady stosownych algorytmów lub implementacje.

Temat 25 Scharakteryzować pojęcie listy dwukierunkowej.

Omówić algorytmy szukania, wstawiania i usuwania z niej elementów oraz rolę wartownika.

Temat 26

Omówić drzewa poszukiwań binarnych (BST) wraz z problemem ich implementacji. Przykłady drzew BST. Omówić algorytmy i problemy wynikające ze wstawiania i usuwania elementu z drzewa BST.

1

Algorytmy i Struktury Danych -wyłącznie Przykładowe tematy Egzaminu 2

Temat 27

Podać przykłady drzew BST. Omówić algorytmy związane z „przechodzenie drzewa". Przykłady.

Temat 28

Przedstawić na przykładach poznane konstrukcje drzew ( bez B-drzeW) oraz omówić algorytmy usuwania z

nich elementów.

Temat 29

Omówić podobieństwa i różnice między drzewami typu BST a B-drzewami.

Podać stosowne przykłady tych drzew. . Podać algorytmy usuwania elementu z tych drzew.

Temat 30a

Omówić strukturę kopca oraz podać przykłady kopców. Co oznacza pojęcie „przywracanie własności kopca",

przedstaw stosowny algorytm realizujący to pojęcie. Omówić metody implementacji kopca, przykład.

Temat 30b

Czy dla jednego zbioru danych można utworzyć kilka kopców (uzasadnij odpowiedź). Podać przykłady.

Podać i omówić algorytmy wstawiania i usuwania elementu z kopca.

Temat 30c

Omówić zastosowanie kopca jako kolejki priorytetowej, przedstawić szkice algorytmów.

Przestawić i omówić algorytm budowy kopca, przykład.

Temat 31

Omówić strukturę i własności B-drzewa. Podać przykład B-drzewa oraz strukturę jego węzła.

Podać i omówić algorytm wyszukiwania klucza w B-drzewie.

Temat 32

Podać poznane typy B-drzew. Przedstawić i omówić algorytm usuwania klucza z B-drzewa oraz oszacować

jego złożoność. Podać stosowne przykłady .

Temat 33. Omówić pojęcie grafu. Podać przykłady grafów oraz metody ich implementacji.

Podać i omówić algorytm przechodzenia drzewa wszerz.

Temat 34. Zbudować graf nieskierowny 9-cio węzłowy i przedstawić metody jego implementacji.

Omówić pojęcia: „najkrótsza ścieżka" i „minimalne drzewo rozpinające".

Podać i omówić algorytm przechodzenia drzewa w głąb. Temat 35

Przedstaw algorytmy, w których zastosowano implementację rekurencyjną. .

Przeanalizuj ich złożoność obliczeniową.

Temat 36. Omówić algorytm Knutha-Morrisa-Pratta. Podać stosowne przykłady. Temat 37. Omówić algorytm Rabina - Karpa. Podać stosowne przykłady.

Temat 38. Omówić wyszukiwania wzorca na przykładzie algorytmu "Brute Force" - Podać przykłady. Temat 39. Przedstawić problem kompresji. Omówić algorytm Huffmana.

Temat 40. Omówić pojęcie „minimalne drzewo rozpinające" i podać algorytm Kruskala.

Temat 41. Omówić algorytm Dijkstry i problem, który rozwiązuje.

Temat 42.

Omówić metodyki równoważenia drzew BST i omówić dokładnie algorytm DWS, przykłady. Temat 43.

Omówić drzewa AVL i podać przykładowe algorytmy obsługujące te drzewa. Temat 44.

Omówić drzewa samokorygujące się. Przedstawić strategie Allena, Munro i Bitnera lub techniki rozchylania. Temat 45.

Omówić realizacje rotacji w drzewach-przykłady, oraz podać algorytmy wykorzystujące rotacje. Temat 46. Omówić drzewa dwumianowe i podać algorytm ich łączenia. Temat 47.

Omówić kopiec dwumianowy i przedstawić algorytmy dla wskazanych funkcji realizujących operacje na kopcu. Temat 47. Omówić kopiec Fibonacciego i przedstawić algorytmy dla wskazanych funkcji realizujących operacje na kopcu.

---