| Literatura: |
Literatura obowiązkowa (jedna z pozycji)
1. Cormen T., C. Leiserson, R. Rivest, Wprowadzenie do algorytmów, Wydawnictwa Naukowo - Techniczne 1999.
2. Sedgewick, Wayne, Algorytmy, Helion, 2012.
Literatura uzupełniająca
3. Dasgupta, Papadimitriou, Vazirani, Algorytmy, WN PWN, 2018
4. Knuth D., Sztuka programowania, WNT, tomy I-IV, 2002-2007.
5. Aho A., Hopcroft J., Ullman J., Projektowanie i analiza algorytmów komputerowych, PWN.
6. Banachowski, Diks, Rytter, Algorytmy i struktury danych, PWN 2017.
7. Harel, Feldman, Rzecz o istocie informatyki. Algorytmika, WNT.
|
| Zakres tematów: |
1. Podstawowe motywacje. Asymptotyczna szybkość wzrostu funkcji, duże i małe „o”. Wprowadzenie do analizy złożoności algorytmów, metoda niezmienników.
2. Podstawowe techniki programowania: rekursja, dziel i rządź, programowanie dynamiczne. Twierdzenie o rekursji uniwersalnej.
3. Podstawowe struktury danych i operacje na nich: lista, stos, kolejka.
4. Definicja problemu sortowania. Sortowanie przez scalanie i jego złożoność.
5. Sortowanie szybkie i jego złożoność. Modyfikacje sortowania szybkiego.
6. Implementacja kolejki przy użyciu kopca. Sortowanie przez kopcowanie.
7. Dolne ograniczenie na szybkość sortowania przy pomocy porównań i przestawień. Sortowanie pozycyjne i kubełkowe.
8. Struktury słownikowe. Definicja oraz implementacje drzewa. Problem wyszukiwania. Wyszukiwanie przez połowienie oraz drzewa poszukiwań (BST).
9. Podstawowe operacje na drzewie BST oraz ich złożoność: wstawianie, wyszukiwanie, usuwanie. Metody przeglądania drzewa.
10. Zrównoważone drzewo wyszukiwań binarnych (AVL).
11. Drzewa 2-3. Drzewa czerwono-czarne. B drzewa.
12. Definicja grafu oraz metody jego reprezentacji. Metody przeglądania grafu: w głąb (DFS) i w szerz (BFS).
13. Implementacja DFS i BFS przy użyciu kolejki i stosu. Sortowanie topologiczne grafu.
14. Konstrukcja minimalnego drzewa rozpinającego. Algorytm Prima i jego złożoność. Opis algorytmu Kruskala.
15. Tablice mieszające.
|
