Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Algorytmy i struktury danych (M)

Nazwa angielska (title in English):
Prowadzący (lecturer): Krzysztof Loryś
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 13
Rodzaj (type): obowiązkowy
Rodzaj od 2007 (type since 2007): obowiązkowy.O2
Liczba godzin (hours in semester):
wykład:60
ćwiczenia:30
pracownia:30
repetytorium:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): letni

Wymagania (prerequisites)

Program (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. Dolne granice: modele i metody. Drzewa decyzyjne, liniowe drzewa decyzyjne, gry z adwersarzem, redukcje. (2 godz.)
  4. Sortowanie: Heapsort , Mergesort i Quicksort. Sortowanie w czasie liniowym: Countsort, Radixsort, Bucketsort. (6 godz.)
  5. Selekcja: algorytmy Hoare'a i "magicznych piątek". (2 godz.)
  6. Kolejki priorytetowe: kopce binarne, dwumianowe i Fibonacciego. Zastosowania w problemie najkrótszych ścieżek i minimalnego drzewa rozpinającego. (4 godz.)
  7. Scalanie. Drzewa turniejowe. Sortowanie zewnętrzne. (2 godz.)
  8. Słowniki. Drzewa BST, zrównoważone drzewa BST (AVL, 2-3-4-drzewa, drzewa czerwono-czarne). Optymalne drzewa wyszukiwań binarnych. Drzewa samoorganizujące się. Haszowanie. Słowniki statyczne. (8 godz.)
  9. Wyszukiwanie zewnętrzne – B-drzewa. (2 godz.)
  10. Problem sumowania zbiorów rozłącznych i jego zastosowania. (4 godz.)
  11. Algorytmy grafowe: DFS i jego zastosowania, przepływy w sieciach, skojarzenia. (4 godz.)
  12. Algorytmy tekstowe: Wyszukiwanie wzorca (algorytm Karpa-Rabina, Algorytm Knutha-Morrisa-Pratta). Drzewa sufiksowe. (4 godz.)
  13. Geometria obliczeniowa. Lokalizacja punktu. Otoczka wypukła. Technika zamiatania. (4 godz.)
  14. Algorytmy algebraiczne i teorioliczbowe. FFT. Szybkie mnożenie liczb i wielomianów. (4 godz.)
  15. NP-zupełność. Algorytmy aproksymacyjne dla problemów obliczeniowo trudnych. Heurystyki dla problemów trudnych (algorytmy genetyczne, simulated annealing). (4 godz.)
  16. Modele obliczeń równoległych: PRAM, tablica procesorów, hiperkostka. Algorytmy równoległe. Klasa NC i problemy P-zupełne. (2 godz.)
  17. Specjalne modele obliczeń: sieci komparatorów, obwody logiczne. (2 godz.)
  18. Algorytmy randomizacyjne. Przykłady zastosowań randomizacji w geometrii obliczeniowej, algorytmach grafowych, algorytmach równoległych, konstrukcji struktur danych. (2 godz.)

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):