Algorytmy i struktury danych (M)
lato 2011/12
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 algorytmów: 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 najkrótszych ś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, zrównoważ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 zbiorów 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 wielomianów. (4 godz.)
14. NP-zupełność. Algorytmy aproksymacyjne dla problemów obliczeniowo trudnych. Heurystyki dla problemów trudnych (algorytmy genetyczne, simulated annealing). (4 godz.)
15. Modele obliczeń równoległych: PRAM, tablica procesorów, hiperkostka. Algorytmy równoległe. Klasa NC i problemy P-zupełne. (2 godz.)
16. Specjalne modele obliczeń: sieci komparatorów, obwody logiczne. (2 godz.)
17. Algorytmy randomizacyjne. Przykłady w dziedzinach: struktury danych, geometria obliczeniowa, algorytmy grafowe, algorytmy równoległe. (2 godz.)
**Wymagania:** Programowanie i Matematyka dyskretna
Wykłady
Lista
Prowadzący
Termin zajęć
Limit
Zapisani
Kolejka
Krzysztof Loryś
300
167
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
300
123
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
Jarosław Byrka
300
155
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
Jarosław Byrka 244
Czwartek od 10 do 12
(prosze o kontakt przez e-mail dzien wczesniej)
Jakub Łopuszański
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.
Paweł Rzechonek 308
Email lub MS Teams
Przemysława Kanarek 305
w semestrze zimowym 2015/16 konsultacje mam w terminach: wt. 11-12, cz. 11-12; w razie potrzeby można umówić się też na inny termin przez e-mail (generalnie preferuję wtorki i czwartki)
Marek Szykuła 312
E-mail, Discord lub Teams.
Krzysztof Loryś 346
Wt 16-17
Pt 12-13
Tomasz Gogacz 336
środa 12-13
