Algorytmy i struktury danych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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
    • sortowanie pozycyjne
  • Selekcja
    • algorytm Hoare'a
    • algorytm magicznych piątek
  • Wyszukiwanie
    • liniowe
    • binarne
    • drzewa poszukiwań binarnych
    • haszowanie
  • Złożone struktury danych
    • słowniki i ich implementacje - zrównoważone drzewa poszukiwań binarnych, drzewa typu splay, B-drzewa
    • kolejki priorytetowe - kolejki dwumianowe i kopce Fibonacciego
    • sumowanie zbiorów rozłącznych
  • Algorytmy grafowe
    • DFS i jego zastosowania
    • problemy ścieżkowe -- Algorytm Dijkstry
    • minimalne drzewo rozpinające
  • Algorytmy tekstowe
    • wyszukiwanie wzorca w tekście - algorytmy Knutha-Morisa-Pratta i Boyera-Moora
    • kompresja tekstów
  • NP-zupełność
    • klasa NP
    • problemy NP-trudne i NP-zupełne

Moduły

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.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych&oldid=3418”