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ą

Seminarium: zaawansowane struktury danych

Nazwa angielska (title in English): Seminar on Advanced Data Structures
Prowadzący (lecturer): Paweł Rzechonek
Liczba punktów (ECTS): 4
Liczba punktów 2007 (ECTS since 2007): 3
Rodzaj (type): seminarium
Rodzaj od 2007 (type since 2007): seminarium
Liczba godzin (hours in semester):
seminarium:30
Egzamin (exam): nie
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Celem seminarium jest przegląd aktualnego stanu wiedzy związanej ze strukturami danych. Przedstawimy zarówno struktury danych wykorzystywane praktycznie w systemach informatycznych czy grach komputerowych jak i struktury o znaczeniu teoretycznym o zaskakujących własnościach czasowych i pamięciowych.

Na seminarium zapoznamy się z zaawansowanymi strukturami danych, na które nie ma czasu w trakcie standardowego wykładu z Algorytmów i struktur danych. Skupimy się na rzetelnej analizie złożoności obliczeniowej procedur działających na omawianych strukturach a w szczególności na czasie ich działania (w sensie czasu pesymistycznego, oczekiwanego lub zamortyzowanego dla ciągu operacji na strukturze).

Uwaga! Seminarium jest przeznaczone dla dojrzałych i ambitnych studentów, którzy chcą pogłębić wiedzę zdobytą na wykładzie z algorytmów i struktur danych oraz innych wykładach algorytmicznych.

Program (program)

  1. realizacja słowników w oparciu o tablice z haszowaniem (haszowanie uniwersalne; haszowanie w przetrzeni liniowej i ze stałym czasem zapytań - algorytm Fredmana, Komlosa, Semerediego; haszowanie dynamiczne - cuckoo hashing; filtry Blooma)
  2. realizacja słowników w oparciu o drzewa zbalansowane (splay tres, a-b trees, drzewa Tango)
  3. kolejki priorytetowe z operają łączenia (kopce parujące; kopce miękkie; kolejka Brodala)
  4. struktury danych wykorzystywane w systemach bazodanowych
  5. struktury danych wykorzystywane w grafice komputerowej
  6. struktury danych dla dynamicznych algorytmów grafowych
  7. zarządzanie pamięcią cache i stertą
  8. Sortowanie i wyszukiwanie liczb całkowitych z ograniczonego uniwersum (drzewa van Emde Boas'a; X-szybkie drzewa trie, Y-szybkie drzewa trie, fusion trees; szybkie sortowanie liczb całkowitych w czasie O(n*loglog n); twierdzenie o równoważności problemów sortowania i kolejki priorytetowej)

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):