Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy dla Problemów NP-zupełnych
Tok studiów:
2019/2020
Kod:
AMAT-2-105-MI-s
Wydział:
Matematyki Stosowanej
Poziom studiów:
Studia II stopnia
Specjalność:
Matematyka w informatyce
Kierunek:
Matematyka
Semestr:
1
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Stacjonarne
Strona www:
 
Prowadzący moduł:
dr Frydrych Wacław (frydrych@agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

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 uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 Student zna algorytmy dokładne dla rozwiązywania problemów NP-zupełnych oparte na programowaniu dynamicznym i z wykorzystaniem algorytmów z nawrotami MAT2A_W11, MAT2A_W08 Odpowiedź ustna,
Esej,
Egzamin,
Aktywność na zajęciach,
Kolokwium
M_W002 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 MAT2A_W11, MAT2A_W08 Odpowiedź ustna,
Esej,
Egzamin,
Aktywność na zajęciach,
Kolokwium
M_W003 Student ma uporządkowaną wiedzę o problemach złożoności algorytmów i zna podstawowe przykłady problemów NP-zupełnych MAT2A_W03, MAT2A_W08, MAT2A_W02 Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
Umiejętności: potrafi
M_U001 student umie zaimplementować w wybranym języku programowania podstawowe algorytmy MAT2A_U20, MAT2A_U19, MAT2A_U21 Odpowiedź ustna,
Kolokwium,
Esej,
Egzamin,
Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
60 30 15 15 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 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_W002 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 + + + - - - - - - - -
M_W003 Student ma uporządkowaną wiedzę o problemach złożoności algorytmów i zna podstawowe przykłady problemów NP-zupełnych + + + - - - - - - - -
Umiejętności
M_U001 student umie zaimplementować w wybranym języku programowania podstawowe algorytmy + + + - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 152 godz
Punkty ECTS za moduł 6 ECTS
Udział w zajęciach dydaktycznych/praktyka 60 godz
Przygotowanie do zajęć 60 godz
przygotowanie projektu, prezentacji, pracy pisemnej, sprawozdania 10 godz
Samodzielne studiowanie tematyki zajęć 20 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (30h):

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. Algorytm aproksymacyjny dla problemu minimalnego ważonego pokrycia wierzchołkowego oparty na metodzie zaokrąglania wykorzystującej programowanie liniowe.

11. 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.

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

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

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

Ćwiczenia audytoryjne (15h):
Program ćwiczeń pokrywa się z programem wykładów.

Rozwiązywanie zadań dotyczących treści przekazywanych na kolejnych wykładach.

Ćwiczenia laboratoryjne (15h):

Implementacja algorytmów dokładnych i aproksymacyjnych przedstawionych na wykładach. Podstawowym celem jest napisanie projektu wykorzystującego jedną z podanych na wykładzie metod do rozwiązania wybranego problemu NP-zupełnego.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
  • Ćwiczenia laboratoryjne: W trakcie zajęć laboratoryjnych studenci samodzielnie rozwiązują zadany problem praktyczny, dobierając odpowiednie narzędzia. Prowadzący stymuluje grupę do refleksji nad problemem, tak by otrzymane wyniki miały wysoką wartość merytoryczną.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Warunkiem dopuszczenia do egzaminu jest uzyskanie zaliczenia ćwiczeń i zaliczenia laboratorium.

Warunkiem zaliczenia ćwiczeń jest uzyskanie pozytywnej oceny z kolokwium zaliczeniowego a warunkiem zaliczenia laboratorium jest uzyskanie pozytywnej oceny z wykonanego projektu. Na ocenę z ćwiczeń i laboratorium wpływ mają również frekwencja i aktywność na zajęciach.

Student ma prawo do dwukrotnego udziału w kolokwium zaliczeniowym poprawkowym.

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
  • Ćwiczenia laboratoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci wykonują ćwiczenia laboratoryjne zgodnie z materiałami udostępnionymi przez prowadzącego. Student jest zobowiązany do przygotowania się w przedmiocie wykonywanego ćwiczenia, co może zostać zweryfikowane kolokwium w formie ustnej lub pisemnej. Zaliczenie zajęć odbywa się na podstawie zaprezentowania rozwiązania postawionego problemu. Zaliczenie modułu jest możliwe po zaliczeniu wszystkich zajęć laboratoryjnych.
Sposób obliczania oceny końcowej:

Ocena końcowa (OK) jest średnią ważoną ocen z egzaminu (E), zaliczenia ćwiczeń audytoryjnych (A) i laboratorium (L):
OK=1/2 x E + 1/4 A + 1/4 L.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

W przypadku nieobecności na zajęciach studenci są zobowiązani opanować materiał ćwiczeń czy laboratorium we własnym zakresie.

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

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