zaawansowane struktury danych (semestr zimowy 2012/13)

Struktury danych służą do przechowywania w pewien uporządkowany sposób informacji w komputerze. We współczesnej informatyce efektywne struktury danych odgrywają często kluczową rolę. Są one wysokopoziomowym narzędziem wykorzystywanym przez algorytmy. Dobrze dobrana struktura danych potrafi znacząco poprawić złożoność obliczeniową algorytmu.

Na seminarium będziemy prezentować zaawansowane struktury danych związane z różnymi działami informatyki, będziemy przedstawiać ogólną ideę ich działania, analizować złożoność obliczeniową poszczególnych operacji wykonywanych na tych strukturach oraz zajmować się detalami implementacyjnymi wybranych operacji.

Tematyka

• dictionaries on hash tables (słowniki zrealizowane na tablicach z haszowaniem)
• dictionaries on trees (słowniki zrealizowane na drzewach)
• priority queues (struktury danych dla kolejek priorytetowych)
• temporal data structures (pomocnicze struktury danych)
• self-adjusting data structures (samoorganizujące się struktury danych)
• dynamic optimality (zachowanie optymalności struktur danych)
• integers (struktury danych dla liczb całkowitych)
• range queries and trees (zapytania przedziałowe)
• dynamic graphs (struktury danych dla grafów dynamicznych)
• external memory and cache-oblivious (zewnętrzne struktury danych)
• succinct data structures (zwięzłe struktury danych)
• geometry (struktury danych wykorzystywane w geometrii)
• databases (struktury danych dla baz danych)
• strings (struktury danych dla algorytmów tekstowych)

Wymagane przygotowanie

• Zaliczony przedmiot algorytmy i struktury danych.
• Zaliczony przedmiot matematyka dyskretna.

Literatura

Materiały do seminarium można znaleść na stonie prof. Erika Demaine'a z Massachusetts Institute of Technology:

• Advanced Data Structures (Spring 2012)
• Advanced Data Structures (Spring 2010)
• Advanced Data Structures (Spring 2007)
• Advanced Data Structures (Spring 2005)
• Advanced Data Structures (Spring 2003)

Istnieje też kilka książek (hasło: books) poświęconych w całości lub części zaawansowanym strukturom danych:

• Peter Brass: Advanced Data Structures. Cambridge University Press, 2008.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. Third Edition. The MIT Press, 2009.

Terminarz

• seminarium: wtorek 14-16 s.139
• referaty:
  • 23 października 2012: Jan Sochiera
    kolejki priorytetowe i sortowanie liczb całkowitych.
  • 30 października 2012: Krzysztof Nowicki
    binarne podziały przestrzeni.
  • 6 listopada 2012: Maciej Graboń
    drzewa vEB.
  • 20 listopada 2012: Seweryn Załupka
    cuckoo hashing.
  • 27 listopada 2012: Przemysław Turczyński
    fusion tree.
  • 4 grudnia 2012: Natalia Levkuv
    zapytania przedziałowe - RMQ i LCA.
  • 11 grudnia 2012: Rafał Sławik
    finger search tree.
  • 18 grudnia 2012: Borys Dyczko
    drzewa sufiksowe.
  • 8, 15 stycznia 2013: Mateusz Lewandowski
    kolejki priorytetowe Brodala.
  • 22 stycznia 2013: Marek Zwonik
    k-d tree.

Seminariumum

Organizacja zajęć

Przydział tematów:

Na pierwszych zajęciach opowiem Wam o czym to seminarium będzie i wskażę linki z materiałami do opracowania. Przez tydzień możecie rozważać te zagadnienia, decydować na wybór jakiegoś tematu albo podjąć decyzję o rezygnacji z zajęć. Lista tematów jest dostępna na stronie znaleść na stonie prof. Erika Demaine'a. Do niektórych tematów mogą się zgłosić po dwie osoby (wystąpienie dwugodzinne) a do pozostałych po jednej osobie (wystąpienie godzinne).

Prezentacja:

W umówionym terminie student powinien dać wykład na wybrany przez siebie temat. Tydzień przed wykładem należy ze mną skonsultować treść prezentowanego materiału.

Opracowanie:

Wybrany temat student ma opracować pisemnie i dostarczyć mi to opracowanie w formie elektronicznej (należy go przygotować w LaTeX'u i dostarczyć mi plik źródłowy z rysunkami oraz pdf'a). Opracowanie powinno zawierać następujące elementy:

1. imię i nazwisko prelegenta, numer indeksu, datę i temat wystąpienia;
2. ogólny opis prezentowanej struktury danych, operacje na niej wykonywane i jej zastosowania w algorytmice;
3. rys historyczny badań związanych z omawianym tematem;
4. prezentację struktury danych, szczegółowy opis operacji wynonywanych na tej strukturze oraz analizę złożoności pamięciowej dla struktury i czasowej dla operacji;
5. bibliografię.

Gotowe opracowanie należy przesłać mi mailem (pliki tex, fig (lub inne formaty rysunków) i pdf) nie później niż dwa tygodnie po wygłoszonym wykładzie. Opracowania te będę udostępniać w sieci (na tej stronie).

Oceny:

Ocenie będzie podlegać:

1. zrozumienie zagadnienia (precyzyjne i trafne sformułowania),
2. wystąpienie przed słuchaczami (jasność przekazu),
3. pisemne opracowanie zagadnienia,
4. obecność i aktywność na zajęciach.

Warunkiem koniecznym uzyskania zaliczenia jest oczywiście rzetelne zapoznanie się z wybranym tematem i przystępne opowiedzenie go na forum grupy, ale także obecność na 2/3 zajęć z wystąpieniami oraz starannie zrobione opracowanie pisemne zagadnienia.

Opracowania

• Borys Dyczko: drzewa sufiksowe (suffix tree). (pdf/zip)
• Rafał Sławik: palczaste drzewo poszukiwań (finger search tree). (pdf/zip)
• Jan Sochiera: sortowanie liczb całkowitych (signature sort). (pdf/zip)
• Przemysław Turczyński: drzewa fusion (fusion tree). (pdf/zip)
• Seweryn Załupka: haszowanie kukułkowe (cuckoo hashing). (pdf/zip)

Udostępniam katalog z oryginalnymi pracami naukowymi (hasło: articles) związanymi z tematami omawianymi na seminarium o zaawansowanych strukturch danych.

Instytut Informatyki