Drzewa Jako Struktury Danych

Opis zajęć

Prowadzący: Karol Pokorski

Wyjaśnione zostanie pokrótce co to jest drzewo oraz jakie ma znaczenie w teorii grafów. Zostanie pokazane kilka podstawowych własności i specyficzne drzewa: np. binarne. Główną częścią wykładu będzie prezentacja struktur danych: kopca, drzewa potęgowego, drzewa licznikowego, drzewa przedziałowego i drzewa pokryciowego. Zaprezentowane zostaną dowody poprawności działania i efektywności tych struktur. Oczywiście będziemy implementować te drzewa. :)

Wymagania

  • znajomość pojęcia złożoności obliczeniowej, umiejętność jej szacowania i zrozumienie jak kluczowym jest czynnikiem podczas analizy algorytmów
  • podstawy matematyki (naprawdę, wystarczą podstawy wręcz z gimnazjum)
  • wypadałoby wiedzieć w jaki sposób w pamięci komputera mogą być reprezentowane drzewa
  • znajomość jakiegoś "nowożytnego" języka programowania (C/C++/Pascal)
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License