Algorytmy i struktury danych

Treści programowe:

• Podstawowe zasady analizy algorytmów:
  • poprawność
  • złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana)
  • koszt zamortyzowany: metoda potencjału
• Podstawowe techniki i struktury:
  • metoda dziel i zwyciężaj
  • metoda zachłanna
  • pogramowanie dynamiczne
  • transformacyjna konstrukcja algorytmu
  • elementarne struktury danych: stosy, kolejki, listy
• Sortowanie:
  • sortowanie przez porównania (InsertionSort, QuickSort, MergeSort)
  • proste kolejki priorytetowe: kopce binarne
  • HeapSort
  • sortowanie pozycyjne
  • złożoność problemu sortowania
• Selekcja:
  • algorytm Hoare'a
  • algorytm magicznych piątek
• Wyszukiwanie i proste słowniki:
  • wyszukiwanie liniowe i binarne
  • prosty słownik: drzewa poszukiwań binarnych
  • haszowanie
• Efektywne implementacje słownika:
  • drzewa AVL
  • drzewa typu splay
  • B-drzewa
• Złożone struktury danych:
  • wzmocnione kolejki priorytetowe: kolejki dwumianowe, kopce Fibonacciego
  • efektywne sumowanie zbiorów rozłącznych
• Algorytmy grafowe:
  • DFS i jego zastosowania
  • problemy ścieżkowe -- Algorytm Dijkstry
  • minimalne drzewo rozpinające
• Wyszukiwanie wzorca w tekstach:
  • prefikso-sufiksy
  • algorytm Knutha-Morisa-Pratta
• Tekstowe struktury danych:
  • tablice sufiksowe
  • drzewa sufiksowe
• NP-zupełność:
  • klasa NP
  • problemy NP-trudne i NP-zupełne

Literatura:

• Algorytmy i struktury danych, L. Banachowski, K. Diks, W. Rytter, Wydawnictwa Naukowo - Techniczne, 2006.
• Wprowadzenie do algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwa Naukowo - Techniczne, 2004.