Semestr zimowy w roku akademickim 2010/11

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, będziemy przedstawiać ogólną ideę ich działania, analizować złożoność obliczeniową poszczególnych operacji wykonywanych na strukturach oraz zajmować się wybranymi detalami implementacyjnymi tych operacji.

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 2010)
• Advanced Data Structures (Spring 2007)
• Advanced Data Structures (Spring 2005)
• Advanced Data Structures (Spring 2003)

Istnieje też kilka książek 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.

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)

Terminarz

• seminarium: poniedziałek 16-18 s.104
• referaty:
  • 18 października 2010 (2 godziny): Aleksander Balicki, Łukasz Zapart
    Van Emde Boas trees, X-fast trees, Y-fast trees.
  • 8 listopada 2010 (1 godzina): Bartosz Rybicki
    Range trees (drzewa obszarów).
  • 22 listopada 2010 (1 godzina): Marcin Panasiuk
    Segment trees (drzewa odcinków).
  • 22 listopada 2010 (1 godzina): Mikołaj Kalinowski
    Cuckoo hashing, Bloom filters.
  • 6 grudnia 2010 (2 godziny): Paweł Kacprzak, Dawid Ryznar
    Dynamic graphs.
  • 13 grudnia 2010 (1 godzina): Jarosław Gomułka
    Range queries - LCA problem, RMQ problem.
  • 13 grudnia 2010 (1 godzina): Marcin Dublański
    Link-cut trees.
  • 20 grudnia 2010 (1 godzina): Łukasz Zatorski
    Tango trees, Wilber bounds.
  • 20 grudnia 2010 (1 godzina): Marta Ziobro
    Fusion trees.
  • 3 stycznia 2011 (2 godziny): Krzysztof Piecuch
    Finger search trees.
  • 10 stycznia 2011 (1 godzina): Tomasz Dudziak
    Cache-oblivious dictionary.
  • 17 stycznia 2011 (1 godzina): Paweł Ledwoń
    Cache-oblivious priority queue.
  • 17 stycznia 2011 (1 godzina): Szymon Laszczyński
    Kd-trees.
  referaty, które wypadły z harmonogramu:
  • 24 stycznia 2011 (1 godzina): Piotr Walkowski
    (a,b)-trees, B-trees, B+trees, B*trees.
  • 31 stycznia 2011 (2 godziny): Jakub Banaszewski, Krzysztof Sornat
    Brodal's meldable priority queues.
  • 7 lutego 2011 (1 godzina): Grzegorz Myszkier
    Drzewa i tablice sufiksowe.
  referaty, które nie zostały zygłoszone:
  • 7 lutego 2011 (1 godzina): Mariusz Koniec
    R-trees.
  • 7 lutego 2011 (1 godzina): Jan Filipowski
    Temporal data structures.

Seminariumum

Organizacja zajęć

Przydział tematów:

Na pierwszych zajęciach studenci wybierają tematy do opracowania. Student powinien zapoznać się z tematami po pierwszych zajęciach (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 wyznaczonym 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 oraz datę wystąpienia;
2. temat wystąpienia;
3. ogólny opis prezentowanej struktury danych, operacje na niej wykonywane i jej zastosowania w algorytmice;
4. rys historyczny badań związanych z omawianym tematem;
5. 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;
6. bibliografię.

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

Oceny:

Ocenie będzie podlegać:

1. wystąpienie przed słuchaczami,
2. pisemne opracowanie zagadnienia,
3. 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 66% zajęć z wystąpieniami oraz starannie zrobione opracowanie pisemne zagadnienia.

Opracowania

• Aleksander Balicki, Łukasz Zapart: Drzewa vEB (van Emde Boas trees, X-fast trees, Y-fast trees). (tex/pdf/zip)
• Bartosz Rybicki: Drzewa obszarów (range trees). (tex/pdf/zip)
• Marcin Panasiuk: Drzewa odcinków (segment trees). (tex/pdf/zip)
• Mikołaj Kalinowski: ...
• Paweł Kacprzak, Dawid Ryznar: Grafy dynamiczne (dynamic graphs). (tex/pdf/zip)
• Jarosław Gomułka: Zapytania przedziałowe (range queries - LCA problem, RMQ problem). (tex/pdf/zip)
• Marcin Dublański: Drzewa LC (link-cut trees). (tex/pdf/zip)
• Łukasz Zatorski: Drzewa tango, granice Wilbera (tango trees, Wilber bounds). (tex/pdf/zip)
• Marta Ziobro: Drzewa fusion (fusion trees). (tex/pdf/zip)
Krzysztof Piecuch: Drzewa FST (finger search trees). (tex/pdf/zip)
• Tomasz Dudziak: <Słowniki w modelu C-O (cache-oblivious dictionary). (tex/pdf/zip)
• Paweł Ledwoń: Kolejki priorytetowe w modelu C-O (cache-oblivious priority queue). (tex/pdf/zip)
• Szymon Laszczyński: Kd-drzewa (Kd-trees). (tex/pdf/zip)
• Piotr Walkowski B-drzewa (B-trees, B+trees, B*trees, (a,b)-trees). (tex/pdf/zip)
• Jakub Banaszewski, Krzysztof Sornat Złączalne kolejki priorytetowe Brodala (Brodal's meldable priority queues). (tex/pdf/zip)
• Grzegorz Myszkier Drzewa i tablice sufiksowe (suffix array and trees). (tex/pdf/zip)

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

Udostępniam też plik z punktacją (hasło: stat).

Instytut Informatyki