Algorytmy i struktury danych (M) lato 2017/18

Lista

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ś	śr 10:00-12:00 (s. 25) cz 10:00-12:00 (s. 25)	300	126	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
Paweł Rzechonek	cz 14:00-16:00 (s. 4)	21	20
Łukasz Jeż	cz 14:00-16:00 (s. 105)	21	20
Krzysztof Piecuch	cz 14:00-16:00 (s. 5)	21	20
Krzysztof Loryś zaaw	cz 14:00-16:00 (s. 139)	21	20
Paweł Gawrychowski	cz 14:00-16:00 (s. 104)	21	19

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 10:00-12:00 (s. wirtualna1)	300	93	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	wt 08:00-10:00 (s. 119)	300	72	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
Paweł Gawrychowski	343	Thursday 14:15-16:00 on MS Teams, please send me an 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