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

• 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

• Wstęp: poprawność i złożoność algorytmu (Ćwiczenia)
• Wstęp: elementarne techniki algorytmiczne i struktury danych (Ćwiczenia)
• Sortowanie przez porównania: BubleSort, SelectionSort i InsertionSort (Ćwiczenia)
• Sortowanie przez porównania: MergeSort, HeapSort i QuickSort (Ćwiczenia)
• Sortowanie: dolna granica, sortowanie pozycyjne (Ćwiczenia)
• Selekcja (Ćwiczenia)
• Wyszukiwanie (Ćwiczenia)
• Słowniki (Ćwiczenia)
• Kolejki priorytetowe (Ćwiczenia)
• Find-Union (Ćwiczenia)
• Algorytmy grafowe - najlżejsze ścieżki (Ćwiczenia)
• Algorytmy grafowe - przeszukiwanie grafów (Ćwiczenia)
• Algorytmy tekstowe I (Ćwiczenia)
• Algorytmy tekstowe II (Ćwiczenia)
• NP-zupełność (Ćwiczenia)

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.