Algorytmy i struktury danych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Sylabus

Autor sylabusa prof. dr hab. Wojciech Rytter prof. dr hab. Krzysztof Diks dr Piotr Sankowski

  • Podstawowe zasady analizy algorytmów:
    • poprawność,
    • złożoność obliczeniowa (pesymistyczna, oczekiwana),
    • złożoność problemu algorytmicznego.
  • Sortowanie:
    • sortowanie przez porównania (InsertionSort, QuickSort, MergeSort),
    • HeapSort i kopce binarne,
    • złożoność problemu sortowania.
  • Selekcja:
    • minimum i maximum,
    • algorytm Hoare'a,
    • algorytm magicznych piątek.
  • Wyszukiwanie:
    • liniowe,
    • binarne,
    • drzewa wyszukiwań binarnych,
    • zrównoważone drzewa wyszukiwań binarnych,
    • B-drzewa,
    • haszowanie.
  • Złożone struktury danych:
    • kolejki priorytetowe,
    • struktury danych dla zbiorów rozłącznych.
  • Algorytmy grafowe:
    • DFS i jego zastosowania,
    • problemy ścieżkowe -- Algorytm Dijkstry,
    • najmniejsze drzewo rozpinające.