Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy dla Problemów NP-zupełnych
Tok studiów:
2017/2018
Kod:
AMA-2-003-MZ-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w zarządzaniu
Kierunek:
Matematyka
Semestr:
0
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr Frydrych Wacław (frydrych@agh.edu.pl)
Osoby prowadzące:
dr Frydrych Wacław (frydrych@agh.edu.pl)
Krótka charakterystyka modułu

Student ma uporządkowaną wiedzę o problemach złożoności algorytmów i zna podstawowe przykłady problemów NP-zupełnych.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Student ma uporządkowaną wiedzę o problemach złożoności algorytmów i zna podstawowe przykłady problemów NP-zupełnych MA2A_W03, MA2A_W08, MA2A_W02 Aktywność na zajęciach
M_W002 Student zna algorytmy dokładne dla rozwiązywania problemów NP-zupełnych oparte na programowaniu dynamicznym i z wykorzystaniem algorytmów z nawrotami MA2A_W11, MA2A_W08 Aktywność na zajęciach,
Kolokwium
M_W003 Student zna algorytmy aproksymacyjne oparte na metodach zachłannych i metodzie lokalnego ulepszania oraz algorytmy heurystyczne oparte na metodzie symulowanego wyżarzania oraz algorytmy genetyczne MA2A_W11, MA2A_W08 Aktywność na zajęciach,
Kolokwium
Umiejętności
M_U001 student umie zaimplementować w wybranym języku programowania podstawowe algorytmy MA2A_U19, MA2A_U20 Aktywność na zajęciach,
Projekt
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Student ma uporządkowaną wiedzę o problemach złożoności algorytmów i zna podstawowe przykłady problemów NP-zupełnych - - - - + - - - - - -
M_W002 Student zna algorytmy dokładne dla rozwiązywania problemów NP-zupełnych oparte na programowaniu dynamicznym i z wykorzystaniem algorytmów z nawrotami - - - - + - - - - - -
M_W003 Student zna algorytmy aproksymacyjne oparte na metodach zachłannych i metodzie lokalnego ulepszania oraz algorytmy heurystyczne oparte na metodzie symulowanego wyżarzania oraz algorytmy genetyczne - - - - + - - - - - -
Umiejętności
M_U001 student umie zaimplementować w wybranym języku programowania podstawowe algorytmy - - - - + - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Konwersatorium:

1. Przypomnienie podstawowych pojęć teorii złożoności algorytmów. Problemy decyzyjne i optymalizacyjne. Problemy NP – zupełne.

2. Przypomnienie podstawowych technik dowodzenia NP – zupełności dla problemów kombinatorycznych i grafowych.

3. Algorytm pseudowielomianowy dla problemu podziału zbioru wykorzystujący technikę programowania dynamicznego. Silna NP – zupełność.

4. Algorytmy dokładne dla rozwiązania problemów NP – zupełnych. Przeszukiwanie wyczerpujące. Algorytm z nawrotami dla problemu plecakowego i cyklu Hamiltona w grafie. Drzewo przeszukiwań algorytmu z nawrotami.

5. Algorytm z nawrotami z odcinaniem gałęzi dla problemu plecakowego i dla problemu komiwojażera.

6. Algorytmy z nawrotami z funkcją ograniczającą dla problemu plecakowego.

7. Metoda podziału i ograniczeń dla problemu komiwojażera z funkcją ograniczającą opartą na wartości zredukowanej macierzy odległości.

8. Algorytmy aproksymacyjne dla problemów NP – zupełnych. Definicja algorytmu k-optymalnego. Zachłanny algorytm aproksymacyjny dla problemu pokrycia wierzchołkowego. Nieaproksymowalność ogólnego problemu komiwojażera TSP.

9. Algorytm aproksymacyjny dla metrycznego problemu drzewa Steinera z wykorzystaniem minimalnego drzewa rozpinającego. Algorytm Christofidesa dla problemu metrycznego TSP.

10. Schematy aproksymacyjne, wielomianowe schematy aproksymacyjne i w pełni wielomianowe schematy aproksymacyjne. W pełni wielomianowy schemat aproksymacyjny dla problemu plecakowego. Związek między silną NP – zupełnością a istnieniem w pełni wielomianowego schematu aproksymacyjnego.

11. Algorytmy aproksymacyjne oparte na metodzie lokalnego ulepszania dla problemu maksymalnego przekroju w grafie i dla problemu komiwojażera.

12. Algorytmy heurystyczne. Algorytmy oparte na metodzie symulowanego wyżarzania.

13. Algorytmy genetyczne. Algorytmy genetyczne dla problemu plecakowego i dla problemu komiwojażera.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 55 godz
Punkty ECTS za moduł 2 ECTS
Udział w konwersatoriach 30 godz
Wykonanie projektu 10 godz
Dodatkowe godziny kontaktowe z nauczycielem 5 godz
Przygotowanie do zajęć 10 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

wynik kolokwium, ocena projektu, frekwencja na zajęciach, aktywność na zajęciach

Wymagania wstępne i dodatkowe:

Znajomość języka C/C++, podstawowe pojęcia kombinatoryki i teorii grafów, podstawowe metody projektowania algorytmów.

Zalecana literatura i pomoce naukowe:

1) S. Dasgupta, Ch. Papadimitriou, U. Vazirani, Algorytmy.
2) J. Hromkovic, Algoritmics for Hard Problems.
3) D. L. Kreher, D. R. Stinson, Combinatorial Algorithms.
4) V. V. Vazirani, Algorytmy aproksymacyjne.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

1. Frydrych, Wacław; Nonhamiltonian 2-connected claw-free graphs with large 4-degree sum;
Discrete Math. 236, No.1-3, 123-130 (2001).

2. Frydrych, Wacław; Skupień, Zdzisław; Non-traceability of large connected claw-free graphs;
J. Graph Theory 27, No.2, 75-86 (1998).

3. Frydrych, W.; All nonhamiltonian tough graphs satisfying a 3-degree sum and Fan-type conditions;
Discrete Math. 121, No.1-3, 93-104 (1993).

Informacje dodatkowe:

Brak