AiS tematy

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

Temat 1

(0(1)    dla n < a

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

\2-T(nf2) + 0(n) dla n>a

Omówić poszczególne składniki tej funkcji.

Omówić 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, O oraz A 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ć problem złożoności obliczeniowej i przedstawić sposoby jej obliczania.

Temat 6

Omówić wszechstronnie problem 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

Na przykładzie problemu Misjonarz i Ludożerca omówić problematykę tej klasy algorytmów.

Temat 13

Omówić problem Hetmanów oraz jego aspekt implementacyjny.

Przedstawić stosowne algorytmy.

Temat 14

Dowieść, że algorytm sortowania przez proste wstawianie może mieć czas realizacji zawarty od O(n) do 0(n²).

Temat 15

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

Podać stosowne przykłady i algorytmy.

Temat 16

Dokonać analizy porównawczej sortowania bąbelkowego(BubbleSort) i sortowania przez wytrząsanie (ShakerSort).

Temat 17

Podać w kodzie pseudojęzyka algorytmy: sortowania b ąbel k o weg o (Bub ble S or t) oraz sortowania przez wytrząsanie (ShakerSort). Omówić przyczyny powstania algorytmu sortowania przez wytrząsanie (ShakerSort). Temat 18

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

Temat 19a

Omówić dokładnie metodę szybkiego sortowania (OuickSort). Przedyskutować problem złożoności. Temat 19b

Podać istotne elementy strategii szybkiego sortowania (OuickSort). Omówić technikę realizacji funkcji podziału metodą przeglądu dwustronnego oraz przeglądu jednostronnego.

Temat 20

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

Temat 21

Omówić działanie stosu oraz przedstawić komplet funkcji niezbędnych do jego funkcjonowania. Przedstawić metody implementacji stosu i problemy z tego wynikające.

Temat 22

Omówić kolejkę oraz przedstawić stosowne funkcje niezbędnych do jej funkcjonowania.

Temat 23

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

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

Temat 24

Scharakteryzować pojęcie listy dwukierunkowej.

Przedstawić i omówić algorytmy szukania, wstawiania i usuwania z niej elementów.

Temat 25

Omówić drzewa poszukiwań binarnych (BST) wraz z problemem ich implementacji.

Podać przykłady drzew BST. Przedstawić i przedyskutować algorytmy wyszukiwania kluczy.

Temat 26

Podać przykłady drzew BST. Omówić pojęcie „przechodzenie drzewa”.

Omówić algorytmy i problemy wynikające ze wstawiania i usuwania elementu z drzewa BST.

Temat 27

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

Temat 28

Należy 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 29a

Omówić dokładnie 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.

Temat 29b

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

Podać przykłady kopców. Podać i omówić algorytmy wstawiania i usuwania elementu z kopca. Temat 29c

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

Przestawić i omówić algorytm budowy kopca.

Temat 29d. Omówić metody implementacji kopca.

Przestawić algorytm sortowania przez kopcowanie; omówić jego działanie na przykładzie.

Temat 30

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 31

Podać charakterystykę B-drzewa. Podać i omówić algorytmy usuwania kluczy z B-drzewa.

Temat 32

Scharakteryzować B-drzewa i kopiec (różnice lub podobieństwa). 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. Porównać metodykę sortowania pozycyjnego i kubełkowego.

Temat 41. Przedstawić i omówić algorytmy sortowania pozycyjnego (radix soi1).

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