Algorytmy i struktury danych

Sylabus

Autorzy

• Wojciech Rytter,
• Krzysztof Diks

Zawartość

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