Algorytmy i struktury danych (M)
| Język wykładowy |
Polski |
| Semestr |
Letni |
| Status |
W ofercie |
| Opiekun |
Krzysztof Loryś
|
| Liczba godzin |
60 (wyk.)
45 (ćw.)
30 (prac.)
30 (rep.)
|
| Rodzaj |
Obowiązkowy 2 |
| ECTS |
9
|
| Polecany dla I roku |
Nie |
| Egzamin |
Tak |
| Grupy efektów kształcenia |
Podstawy informatyki i programowania
|
Opis przedmiotu:
**Program:**
1. Przegląd metod projektowania efektywnych algorytmow: 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 najkrotszych ś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, zrownoważ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 zbiorow 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 wielomianow. (4 godz.)
14. NP-zupełność. Algorytmy aproksymacyjne dla problemow obliczeniowo trudnych. Heurystyki dla problemow trudnych (algorytmy genetyczne, simulated annealing). (4 godz.)
15. Modele obliczeń rownoległych: PRAM, tablica procesorow, hiperkostka. Algorytmy rownoległe. Klasa NC i problemy P-zupełne. (2 godz.)
16. Specjalne modele obliczeń: sieci komparatorow, obwody logiczne. (2 godz.)
17. Algorytmy randomizacyjne. Przykłady w dziedzinach: struktury danych, geometria obliczeniowa, algorytmy grafowe, algorytmy rownoległe. (2 godz.)
**Wymagania:** Programowanie i Matematyka dyskretna
