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:
  • poprawność,
  • złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, koszt zamortyzowany),
  • 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 poszukiwań binarnych,
  • zrównoważone drzewa poszukiwań 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 i jego implementacje,
  • minimalne drzewo rozpinające.
• Algorytmy tekstowe:
  • wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora,
  • struktury danych dla tekstów - drzewa sufiksowe.
• NP-zupełność i algorytmy aproksymacyjne
  • Klasa NP i problemy NP-zupełne
  • dowodzenie NP-zupełności
  • algorytmy aproksymacyjne, schematy aproksymacyjne, nieaproksymowalność

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.