Algorytmy i struktury danych

Forma zajęć

Wykład (30 godzin) + laboratorium (30 godzin)

Opis

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych.

Sylabus

Autorzy

• Wojciech Rytter,
• Krzysztof Diks

Wymagania wstępne

• Wstęp do programowania
• Metody programowania
• Matematyka dyskretna
• Logika i teoria mnogości

Zawartość

• Podstawowe zasady analizy algorytmów (1)
  • poprawność,
  • złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany),
  • złożoność problemu algorytmicznego.
• Sortowanie (3)
  • sortowanie przez porównania (InsertionSort, QuickSort, MergeSort),
  • HeapSort i kopce binarne,
  • złożoność problemu sortowania,
  • sortowanie pozycyjne.
• Selekcja (1)
  • algorytm Hoare'a,
  • algorytm magicznych piątek.
• Wyszukiwanie (2)
  • liniowe,
  • binarne,
  • drzewa poszukiwań binarnych,
  • haszowanie.
• Złożone struktury danych (3)
  • słowniki i ich implementacje - zrównoważone drzewa poszukiwań bibarnych, drzewa typu splay, B-drzewa,
  • kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego,
  • sumowanie zbiorów rozłącznych.
• Algorytmy grafowe (2)
  • DFS i jego zastosowania,
  • problemy ścieżkowe -- Algorytm Dijkstry,
  • minimalne drzewo rozpinające.
• Algorytmy tekstowe (2)
  • wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora,
  • kompresja tekstów.
• NP-zupełność (1)
  • Klasa NP
  • Problemy NP-trudne i NP-zupełne

Moduły

• Wykład 1
• Wykład 2

Literatura

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