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 (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.
• Algorytmy tekstowe:
  • algorytm Knutha-Morisa-Pratta,
  • drzewa sufiksowe.

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.