Kontakt:

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

Konsultacje (pokój 339):

  • poniedziałek 18-19
  • środa 12-13
Proszę wcześniej uzgodnić dokładny termin konsultacji drogą mailową.

zaawansowane struktury danych (semestr zimowy 2012/13)

Adres:

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

7 lutego 2013 r.

Oceny zaliczeniowe:

Chciałbym Państwu powpisywać już oceny do indeksów z tego seminarium. Proszę się ze mną kontaktować indywidualnie w celu omówienia opracowania. Moga to być godziny konsultacji albo umówione spotkanie w innym terminie.

1 października 2012 r.

Pierwsze spotkanie:

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

27 września 2012 r.

Punkt informacyjny:

W tym miejscu będą się pojawiać ważne ogłoszenia dotyczące organizacji zajęć związanych z tym seminarium. Proszę sprawdzać ogłosznia, 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 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:

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