Algorytmy i struktury danych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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

  • Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
  • Tomasz Waleń — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

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: 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

Moduły

Literatura

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