Algorytmy i struktury danych

Sylabus

Autor sylabusa prof. dr hab. Wojciech Rytter, prof. dr hab. Krzysztof Diks

• 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.