Pełny opis: |
Prezentacja, w możliwie pragmatycznym ujęciu, głównych pojęć, metod i wyników analizy złożoności algorytmów obliczeniowych.
Treść wykładu Wprowadzenie do tematyki (2h). Problemy algorytmizowalne, algorytmy i programy, modele obliczeń; klasy złożoności problemów i algorytmów sekwencyjnych; rozmiar problemu, złożoność czasowa i pamięciowa; złożoność pesymistyczna, oczekiwana, zamortyzowana, oszacowania asymptotyczne; redukowalność algorytmów, kres górny złożoności, kres dolny i algorytmy optymalne.
Techniki analizy (4h). Notacja asymptotyczna. Elementarne techniki analizy złożoności pesymistycznej i oczekiwanej; równania rekurencyjne liniowe jednorodne i niejednorodne, twierdzenie o rozwiązaniu równania z niejednorodnością wielomianowo-wykładniczą. Równania dekompozycji, postać kanoniczna Bentleya-Hakena-Saxe`a rozwiązywania równań dekompozycji. Funkcje tworzące.
Przykłady analizy - algorytmy i struktury podstawowe (4h). Algorytmy Karatsuby i Strassena; analiza złożoności operacji dla kopców binarnych (heaps), algorytm selekcji, liniowy algorytm z medianą median, badanie ograniczenia dolnego dla operacji selekcji. Operacje na zbiorach, algorytmy UNION-FIND,zastosowania w problemach równoważności, algorytm Kruskala, dla drzew rozpinających.
Dekompozycja wielowymiarowa (6h). Schemat dekompozycji i omiatania dla problemów geometrycznych, problemy globalne i przepytywania. Dominacja punktów w zbiorach wielowymiarowych; wyznaczanie punktw ekstremalnych. Problemy związane z metrykami (analiza bliskości). Przeszukiwanie zakresowe, drzewa dychotomiczne, k-d drzewa i drzewa zakresowe. Usuwanie degeneracji w problemach geometrycznych.
Problemy optymalizacji (6h). Metody rozwiązywania i złożoność problemów optymalizacji. Metoda odrywania i algorytmy zachłanne. Algorytmy Kruskala, Prima, Dijkstry. Pojecie matroidu. Programowanie dynamiczne w problemach sieciowych i drzewach szukania, algorytm Floyda. Algorytmy szukania z nawrotami, metoda rozgałęzień i ograniczeń, algorytm Little`a dla problemu komiwojażera.
Metoda transformacji dziedziny (2h). Dyskretna transformata Fouriera w dziedzinie zespolonej; FFT w ciałach skończonych i szybkie mnożenie wielomianów; szybkie mnożenie wielkich liczb.
Klasy złożoności (2h). Modele obliczeń; problemy decyzyjne, obliczeniowe i optymalizacyjne. Model niedeterministyczny, klasy P i NP, problemy NP-trudne i NP-zupełne, problemy spełnialności, twierdzenie Cooka, technika dowodzenia przynależności problemów do klasy NPC, przykłady problemów w klasie NP. Klasyfikacja Gareya.
Algorytmy aproksymacyjne (2h). Technologia. Aproksymacje dla problemu minimalnego pokrycia wierzchołkowego grafu. Aproksymacje dla problemu komiwojażera (TSP), algorytm Christofidesa, ulepszanie iteracyjne. Twierdzenie o niemocy. Mataheurystyki, symulowane wyżarzanie, metodyka GRASP, tabu search, algorytmy genetyczne i ewolucyjne, algorytmy mrówkowe.
Zakres projektu W ramach projektu studenci opracowują algorytmy dla zadanych problemów wymagających użycia kilku algorytmów podstawowych i przeprowadzają analizę złożoności pesymistycznej oraz pomiary czasu. Proponowane problemy projektowe dotyczą algorytmów geometrycznych, kombinatorycznych, optymalizacji, przetwarzania tekstów, symulacji sterowanej zdarzeniami, przetwarzania w grafach.
|
Literatura: |
- Cormen T, Leiserson Ch, Rivest R: Wprowadzenie do algorytmów,
WNT, Warszawa 1997, 2001, 2004.
- Aho A.V, Hopcroft J.E, Ullman J.D: Projektowanie i Analiza
Algorytmów, Helion, Gliwice 2003.
- Sedgewick R: Algorytmy w C++ (1999); Algorytmy w C++: grafy
(2003), ReadMe, Warszawa.
- Reingold E.M., Nievergelt J., Deo N. : Algorytmy Kombinatoryczne,
WNT, Warszawa 1985.
Literatura uzupełniająca:
- Skiena S, Revilla M: Wyzwania programistyczne, WSiP, Wwa 2004.
- Lipski W.: Kombinatoryka dla Programistów, WNT, Warszawa 1982;
2004.
- Banachowski L., Kreczmar A., Rytter W.: Analiza Algorytmów i
Struktur Danych, WNT, Warszawa 1987; 1989.
- Sysło M., Deo N., Kowalik J.: Algorytmy Optymalizacji Dyskretnej,
PWN, Warszawa 1993; 1999.
|