Zagadnienia do egzaminu z przedmiotu

„Algorytmy i struktury danych”

(studia stacjonarne)

1.

Elementy analizy algorytmów.

2.

Złożoność obliczeniowa algorytmów: czasowa, pamięciowa, pesymistyczna, optymistyczna, przeciętna.

3.

Asymptotyczna złożoność obliczeniowa.

4.

Standardowe notacje złożoności, definicje i własności.

5.

Poprawność semantyczna, metoda niezmienników pętli, dowodzenie poprawności.

6.

Elementarne algorytmy sortowania: Select_Sort, Insert_Sort, Bubble_Sort.

7.

Stabilność algorytmów.

8.

Rekurencja. Definicje rekurencyjne i funkcje rekurencyjne.

9.

Równania rekurencyjne, metody rozwiązywania.

10. Dowodzenie własności algorytmów rekurencyjnych, dowody indukcyjne.
11. Techniki projektowania algorytmów. Schemat "dziel i zwyciężaj”.
12. Metoda programowania dynamicznego.
13. Sortowanie szybkie (Quick_Sort). Struktura algorytmu i złożoność obliczeniowa.
14. Schematy sortowania szybkiego.
15. Scalanie i sortowanie przez scalanie (Merge_Sort). Złożoność czasowa i pamięciowa.
16. Sortowanie Shella.
17. Kopiec. Budowanie i przywracanie własności kopca. Elementarne implementacje.
18. Sortowanie kopcowe (Heap_Sort), złożoność obliczeniowa algorytmu.
19. Analiza porównawcza algorytmów sortowania.
20. Abstrakcyjne typy danych (ADT).
21. Dynamiczne struktury danych.
22. Reprezentacja struktur dowiązaniowych za pomocą tablic.
23. Listy jednokierunkowe, dwukierunkowe i cykliczne. Interfejs listy.
24. Tablicowa reprezentacja list. Ilustracja reprezentacji.
25. Stos. Reprezentacja dowiązaniowa. Interfejs stosu.
26. Tablicowa reprezentacja stosu. Algorytmy realizacji tablicowej, ilustracja.
27. Kolejka. Reprezentacja dowiązaniowa, podstawowe operacje.
28. Tablicowa realizacja kolejki. Algorytmy implementacji tablicowej.
29. Kolejki priorytetowe. Struktura danych kolejki.
30. Grafy. Zastosowania w teorii algorytmów.
31. Implementacje tablicowe i dowiązaniowe grafów.
32. Trawersowanie grafu. Strategia BFS i DFS.
33. Drzewa, definicje, własności i klasyfikacja.
34. Drzewa binarne. Algorytmy działające na drzewach binarnych.
35. Drzewa przeszukiwań binarnych (BST).
36. Trawersowanie drzew BST.
37. Operacje wstawiania i usuwania dla drzew BST.
38. Efektywność operacji dla drzew BST, złożoność obliczeniowa.
39. Równoważenie drzew BST. Algorytm DSW.
40. Drzewa AVL.
41. Algorytmy równoważenia drzew AVL.
42. Drzewa czerwono-czarne RB, własności.
43. Operacje rotacji na drzewach RB.
44. Operacje usuwania i wstawiania do drzew RB.
45. Słowniki. Interfejs ADT.
46. Tablice haszowane. Zastosowania haszowania.
47. Funkcje haszujące.
48. Metody rozwiązywanie konfliktów.
49. Wyszukiwanie wzorca w tekście. Algorytmy Tekstowe.
50. Złożoność obliczeniowa i porównanie algorytmów tekstowych.