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)