Kontakt:

pokój: 339
telefon: +48 71 3757836
mail:
www: http://www.ii.uni.wroc.pl/~prz/

Konsultacje:

poniedziałek 12-14
pokój 339
proszę wcześniej uzgodnić dokładny termin konsultacji drogą mailową

Semestr zimowy w roku akademickim 2010/11

Adres:

Instytut Informatyki
Uniwersytetu Wrocławskiego
ul. Joliot-Curie 15
50-383 Wrocław
OGŁOSZENIA

17 stycznia 2011 r.

Następne zajęcia:

Następne spotkanie seminaryjne z jednym wystąpieniem, zaplanowane na 24 stycznia 2011 r, rozpocznie się wyjątkowo o godzinie 17:15.

17 stycznia 2011 r.

Dodatkowe zajęcia:

Trzeba będzie zorganizować dodatkowe spotanie na referaty, które wypadły w trakcie semestru. Na dzisiejszych zajęciach ustaliliśmy, że dodatkowe seminarium z 3 referatami odbędzie się w poniedziałek 7 lutego i zaczniemy o godzinie 14:15.

29 listopada 2010 r.

Odwołane zajęcia:

Dzisiejsze zajęcia (29 listopada) nie odbędą się z powodu nieobecności prelegenta.

25 listopada 2010 r.

Zmiany w terminarzu:

Nastąpiła kolejna zmiana w terminarzu. W najbliższy poniedziałek 29 listopada wystąpi Piotr Walkowski i opowie o B-drzewach.

25 października 2010 r.

Odwołane zajęcia:

Dzisiejsze zajęcia (25 października) nie odbędą się z powodu nieobecności prelegenta.

4 października 2010 r.

Pierwsze spotkanie:

Na pierwszym spotkaniu 4 października omówię tematykę seminarium i przedstawię materiały do opracowania.

3 października 2010 r.

Punkt informacyjny:

To właśnie w tym miejscu będą się pojawiać ważne ogłoszenia dotyczące organizacji zajęć związanych z tym przedmiotem. Proszę zaglądać do tych ogłoszń, szczególnie przed kolejnym spotkaniem.

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:

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