Algorytmy i struktury danych (M) lato 2018/19
| Język wykładowy | Polski |
|---|---|
| Opiekun | Krzysztof Loryś |
| Liczba godzin | 60 (wyk.) 30 (ć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 dyskretnaWykłady
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Krzysztof Loryś
|
wt 16:00-18:00 (s. 25) śr 16:00-18:00 (s. 25) | 300 | 187 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Ćwiczenia
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Szymon Dudycz
|
pt 10:00-12:00 (s. 141) | 21 | 20 | 0 |
|
Paweł Gawrychowski
ISIM |
pt 10:00-12:00 (s. 4) | 20 | 20 | 0 |
|
Łukasz Jeż
|
pt 10:00-12:00 (s. 103) | 21 | 20 | 0 |
|
Adam Kunysz
|
pt 10:00-12:00 (s. 5) | 21 | 16 | 0 |
|
Krzysztof Loryś
zaaw |
pt 10:00-12:00 (s. 310) | 12 | 10 | 0 |
|
Krzysztof Piecuch
|
pt 10:00-12:00 (s. 139) | 21 | 21 | 0 |
|
Paweł Rzechonek
|
pt 10:00-12:00 (s. 105) | 21 | 21 | 0 |
|
Mateusz Wasylkiewicz
|
pt 10:00-12:00 (s. 104) | 21 | 18 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Pracownie
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Marcin Bieńkowski
|
cz 14:00-16:00 (s. wirtualna3) | 300 | 140 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Repetytoria
Lista| Prowadzący | Termin zajęć | Limit | Zapisani | Kolejka |
|---|---|---|---|---|
|
Rafał Nowak
|
cz 08:00-10:00 (s. 25) | 300 | 120 | 0 |
UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.
Konsultacje prowadzących:
| Imię i nazwisko | Pokój | Konsultacje |
|---|---|---|
| Rafał Nowak | 240 | Office hours: every Tuesday, 9:15-10:00 or 13:15-14:00 See this calendar for appointment slots https://bit.ly/2mNkMYB |
| Łukasz Jeż | 323 | Tue 15:15-16:00, Wed 16:15-17:00; if neither time suits you, email me. |
| Adam Kunysz | 342 | Proszę umawiać się na konsultacje przez email. |
| Paweł Gawrychowski | 343 | Thursday 14:15-16:00 on MS Teams, please send me an email. |
| Marcin Bieńkowski | 343 | Środy zaraz po wykładzie z Sieci komputerowych (ok. 12:00 w sali 119). Inne terminy też możliwe: proszę o kontakt mailowy. |
| Krzysztof Piecuch | 325 | Ustalimy na zajęciach |
| Paweł Rzechonek | 308 | Email lub MS Teams |
| Mateusz Wasylkiewicz | 340 | - |
| Szymon Dudycz | 326 | Czwartki o 12, poprzez Teams. |
| Krzysztof Loryś | 346 | Wt 19-20 Pt 12-13 |