Algorytmy i struktury danych (M)
lato 2015/16
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 dyskretna
Wykłady
Lista
Prowadzący |
Termin zajęć |
Limit |
Zapisani |
Kolejka |
Krzysztof Loryś
|
pn 14:00-16:00 (s. 25)
wt 14:00-16:00 (s. 25)
|
300
|
121 |
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 |
Adam Kunysz
|
śr 10:00-12:00 (s. 105)
|
22
|
9 |
0 |
Łukasz Jeż
|
śr 10:00-12:00 (s. 103)
|
22
|
20 |
0 |
Paweł Rzechonek
|
śr 10:00-12:00 (s. 141)
|
22
|
22 |
0 |
Krzysztof Piecuch
|
śr 10:00-12:00 (s. 5)
|
22
|
23 |
0 |
Krzysztof Loryś
zaaw
|
śr 10:00-12:00 (s. 139)
|
22
|
22 |
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
|
pt 08:00-10:00 (s. )
|
300
|
88 |
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 |
Łukasz Jeż
|
cz 08:00-10:00 (s. 25)
|
300
|
84 |
0 |
Rafał Nowak
|
cz 08:00-10:00 (s. 25)
|
0
|
0 |
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 |
pn 15:15-16:00 |
Adam Kunysz |
342 |
Proszę umawiać się na konsultacje przez email. |
Paweł Rzechonek |
308 |
Email lub MS Teams |
Krzysztof Piecuch |
325 |
Ustalimy na zajęciach |
Marcin Bieńkowski |
343 |
Środy zaraz po wykładzie z Sieci komputerowych (ok. 14:00 w sali 119). Inne terminy też możliwe: proszę o kontakt mailowy. |
Krzysztof Loryś |
346 |
Wt 16-17
Pt 12-13 |