Algorytmy i struktury danych WM-I-ASD
Ćwiczenia (CW) Semestr letni 2022/23

Literatura obowiązkowa, jedna pozycja do wyboru

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.

1. Podstawowe motywacje. Asympotyczna 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żność. 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. Podstawy szybkiej transformaty Fouriera (FFT).