Algorytmy i struktury danych

Program:

1. Przegląd metod projektowania efektywnych algorytmów: dziel i zwyciężaj, programowanie dynamiczne, metoda zachłanna. (4 godz.)
2. Złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, zamortyzowana). Przykłady analizy kosztu. (2 godz.)
3. Sortowanie: Heapsort i Quicksort. Model drzew decyzyjnych i dolne ograniczenie na problem sortowania. Sortowanie w czasie liniowym: Countsort, Radixsort, Bucketsort. (6 godz.)
4. Selekcja: algorytmy Hoarea i magicznych piątek. (2 godz.)
5. Kolejki priorytetowe: kopce binarne, dwumianowe i Fibonacciego. Zastosowania w problemie najkrótszych ścieżek i minimalnego drzewa rozpinającego. (4 godz.)
6. Scalanie. Drzewa turniejowe. Sortowanie zewnętrzne. (2 godz.)
7. Wyszukiwanie i problem słownika. Drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, 2-3-4-drzewa, drzewa czerwono-czarne). Optymalne drzewa wyszukiwań binarnych. Haszowanie. Wyszukiwanie pozycyjne. (8 godz.)
8. Wyszukiwanie zewnętrzne - B-drzewa. (2 godz.)
9. Problem sumowania zbiorów rozłącznych i jego zastosowania. (4 godz.)
10. Algorytmy grafowe: przepływy w sieciach, skojarzenia. (4 godz.)
11. Algorytmy na tekstach. Wyszukiwanie wzorca. Drzewa sufiksowe. (4 godz.)
12. Geometria obliczeniowa. Lokalizacja punktu. Otoczka wypukła. Technika zamiatania. (4 godz.)
13. Algorytmy algebraiczne i teorioliczbowe. FFT. Szybkie mnożenie liczb i wielomianów. (4 godz.)
14. NP-zupełność. Algorytmy aproksymacyjne dla problemów obliczeniowo trudnych. Heurystyki dla problemów trudnych (algorytmy genetyczne, simulated annealing). (4 godz.)
15. Modele obliczeń równoległych: PRAM, tablica procesorów, hiperkostka. Algorytmy równoległe. Klasa NC i problemy P-zupełne. (2 godz.)
16. Specjalne modele obliczeń: sieci komparatorów, obwody logiczne. (2 godz.)
17. Algorytmy randomizacyjne. Przykłady w dziedzinach: struktury danych, geometria obliczeniowa, algorytmy grafowe, algorytmy równoległe. (2 godz.)

Wymagania: Programowanie i Matematyka dyskretna