temat I
|
Algorytmy sortowania
- Naiwne algorytmy sortowania:
- Sortowanie przez proste wybieranie (Selection Sort)
- Sortowanie przez proste wstawianie (Insertion Sort)
- Sortowanie przez prostą zamianę (Bubble Sort)
- Złożoność pamięciowa algorytmów sortowania
- Podstawowe operacje w sortowaniu
- Złożoność obliczeniowa algorytmów sortowania
- Analiza złożoności obliczeniowej dla różnych rozkładów danych wejściowych
- Algorytmy sortowania oparte na podejściu „dziel i zwyciężaj”
- Sortowanie szybkie (Quick sort)
- Sortowanie stogowe (Heap Sort)
- Sortowanie przez scalanie (Merge Sort)
- Co oznacza stabilność sortowania
- Właściwość sortowania w miejscu
- Inne przykłady algorytmów sortowania
- Sortowanie za pomocą malejących przyrostów (Shell Sort)
- Sortowanie przez zliczanie (Counting sort)
|
temat II
|
Złożone struktury danych
- Struktura listy jedno- i dwukierunkowej
- Struktura drzewa poszukiwań binarnych (BST)
- Drzewo zrównoważone (AVL), drzewo dokładnie wyważone (DDW), drzewo zdegenerowane (winorośl)
- Własności różnych drzew BST
- Tworzenie i usuwanie listy/drzewa
- Metoda przeszukiwania binarnego w tworzeniu drzewa AVL
- Wyszukiwanie elementu na liście/w drzewie
- Usuwanie pojedynczych elementów listy/drzewa
- Przeglądanie drzewa w porządku wzdłużnym (preorder), poprzecznym (inorder) i wstecznym (postorder)
- Rotacje w drzewie binarnym
- Równoważenie drzewa metodą DSW (Day-Stout-Warren)
- Równoważenie drzewa metodą z usuwaniem korzeni niezbalansowanych poddrzew
|
| temat III |
Algorytmy grafowe
- Wybrane pojęcia z teorii grafów
- Reprezentacje maszynowe grafu: lista krawędzi, macierz sąsiedztwa, macierz incydencji, lista sąsiedztwa, lista następników, lista poprzedników, macierz grafu
- Własności różnych reprezentacji maszynowych grafu
- Złożoność pamięciowa i złożoność pozyskiwania informacji o grafie dla różnych reprezentacji maszynowych
- Algorytmy przeszukiwania grafu w głąb (Depth First Search = DFS) i wszerz (Breadth First Search = BFS)
- Algorytm sortowania topologicznego metodą Kahna
- Algorytm sortowania topologicznego z wykorzystaniem przechodzenia w głąb
|
| temat IV |
Algorytmy z powracaniem
- Idea działania algorytmów z powracaniem
- Problem znajdowania ścieżki i cyklu Hamiltona w grafie
- Problem znajdowania ścieżki i cyklu Eulera w grafie
- Wersja przeszukiwania i wersja decyzyjna problemu ścieżki Hamiltona i ścieżki Eulera
- Algorytm z powracaniem dla problemu poszukiwania cyklu Hamiltona
- Algorytm z powracaniem dla problemu poszukiwania cyklu Eulera
- Przynależność obydwu problemów do klas złożoności
- Złożoność obliczeniowa algorytmów poszukiwania cyklu Hamiltona i cyklu Eulera
|
| temat V |
Programowanie dynamiczne
- Problem plecakowy i jego różne wersje
- Sformułowanie 0-1 problemu plecakowego
- Algorytm wyczerpujący dla 0-1 problemu plecakowego
- Algorytm zachłanny dla 0-1 problemu plecakowego
- Metodyka programowania dynamicznego
- Algorytm programowania dynamicznego dla 0-1 problemu plecakowego
- Klasa złożoności problemu plecakowego
- Złożoność obliczeniowa algorytmów wyczerpującego, zachłannego i programowania dynamicznego dla 0-1 problemu plecakowego
|
