MIMINF:Języki, automaty i obliczenia

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Podstawowe modele obliczeń (automaty, gramatyki, maszyna Turinga), związki między trudnoœścią problemów obliczeniowych a strukturalną złożonoœcią modeli obliczeń. Hierarchia Chomsky'ego. Matematyczny sens pojęcia obliczalnośœci oraz jego ograniczenia, a także - w zarysie - podstawowe zagadnienia złożonośœci obliczeniowej.

Sylabus

Autorzy

• Damian Niwiński — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

Wymagania wstępne

• Wstęp do programowania
• Matematyka dyskretna
• Podstawy matematyki
• Analiza matematyczna 1
• Geometria z algebrą liniową

Zawartość

• Podstawowe zasady analizy algorytmów:
  • poprawność
  • złożoność obliczeniowa algorytmu (czasowa i pamieciowa, pesymistyczna i oczekiwana, koszt zamortyzowany)
  • złożoność problemu algorytmicznego a złożoność algorytmu - dolne granice, metody analizy złożoności
• Metody projektowania wydajnych algorytmów:
  • metoda dziel i zwyciężaj
  • algorytmy zachłanne
  • pogramowanie dynamiczne
  • przeszukiwanie z nawrotami i metoda podziału i ograniczeń
  • transformacyjna konstrukcja algorytmu
• Sortowanie:
  • sortowanie przez porównania (sortowanie przez wstawianie - InsertionSort, sortowanie szybkie - QuickSort, sortowanie przez scalanie - MergeSort)
  • proste kolejki priorytetowe: kopce binarne
  • sortowanie kopcowe - HeapSort
  • sortowanie pozycyjne
  • złożoność problemu sortowania
• Selekcja:
  • algorytm Hoare'a
  • algorytm magicznych piątek
• Wyszukiwanie i słowniki:
  • wyszukiwanie liniowe i binarne
  • drzewa wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych (AVL, drzewa czerwono-czarne, drzewa typu splay)
  • haszowanie (funkcje haszujące, haszowanie uniwersalne, metody rozwiązywania kolizji, haszowanie doskonałe)
  • B-drzewa
• Kolejki priorytetowe:
  • złączalne kolejki priorytetowe (kopce dwumianowe i Fibonacciego)
  • algorytm Dijkstry
• Problem "Find-Union" i jego zastosowania
• Algorytmy grafowe:
  • komputerowe reprezentacje grafów
  • metody przeszukiwania grafów i ich zastosowania - najkrótsze ścieżki, spójność, dwuspójność, silna spójność, sortowanie topologiczne
  • problemy ścieżkowe
  • minimalne drzewo rozpinające
  • najliczniejsze skojarzenia w grafach dwudzielnych
• Wyszukiwanie wzorca w tekstach:
  • prefikso-sufiksy
  • algorytm Knutha-Morisa-Pratta
• Tekstowe struktury danych:
  • tablice sufiksowe
  • drzewa sufiksowe

Literatura

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