Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy dla problemów trudnych obliczeniowo
Tok studiów:
2014/2015
Kod:
IIN-1-681-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
6
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
Faliszewski Piotr (faliszew@agh.edu.pl)
Osoby prowadzące:
dr inż. Gajęcki Marek (mag@agh.edu.pl)
Faliszewski Piotr (faliszew@agh.edu.pl)
Kurdziel Marcin (kurdziel@agh.edu.pl)
Krótka charakterystyka modułu

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 zna i rozumie pojęcia algorytmów aproksymacyjnych i randomizowanych. IN1A_W03 Aktywność na zajęciach
M_W002 Student zna i rozumie podstawowe pojęcia parametrycznej teorii złożoności obliczeniowej. IN1A_W03 Aktywność na zajęciach
Umiejętności
M_U001 Student potrafi stworzyć program komputerowy rozwiązujący problem o wysokiej złożoności obliczeniowej. IN1A_U07, IN1A_U08 Zaliczenie laboratorium
Kompetencje społeczne
M_K001 Student potrafi zaplanować realizację programu komputerowego w sytuacji niepewności co do optymalnego rozwiązania. IN1A_K04 Zaliczenie laboratorium
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 zna i rozumie pojęcia algorytmów aproksymacyjnych i randomizowanych. + - - - - - - - - - -
M_W002 Student zna i rozumie podstawowe pojęcia parametrycznej teorii złożoności obliczeniowej. + - - - - - - - - - -
Umiejętności
M_U001 Student potrafi stworzyć program komputerowy rozwiązujący problem o wysokiej złożoności obliczeniowej. - - + - - - - - - - -
Kompetencje społeczne
M_K001 Student potrafi zaplanować realizację programu komputerowego w sytuacji niepewności co do optymalnego rozwiązania. - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Wykładnicze algorytmy dla problemów NP-zupełnych (4 godz.)
Metody pełnego przeglądu przestrzeni rozwiązań. Optymalizacja metod pełnego przeglądu. Algorytmy randomizowane. Przykłady algorytmów dla problemu spełnialności formuł logicznych.

2. Algorytmy aproksymacyjne dla problemów NP-zupełnych (8 godz.)
Pojęcie algorytmu aproksymacyjnego. Przykłady algorytmów o stałym współczynniku aproksymacji oraz o współczynniku aproksymacji zależnym od rozmiaru problemu. Pojęcie w pełni wielomianowego schematu aproksymacji.

3. Twierdzenie o probabilistycznie weryfikowanych dowodach (2 godz.)
Twierdzenie PCP. Równoważność probabilistycznie weryfikowanych dowodów i klasy NP. Znaczenie twierdzenia PCP dla wyznaczania granic aproksymacji problemów NP-zupełnych.

4. Parametryczna teoria złożoności obliczeniowej (8 godz.)
Klasy parametrycznej złożoności obliczeniowej (FPT, hierarchiwa W1, W2, …). Metody konstrukcji algorytmów FPT (przegląd przestrzeni rozwiązań, programowanie cąłkowitoliczbowe, kodowanie kolorami, kernelizacja). Przykłady problemów W1 i W2 trudnych.

5. Algorytmy randomizowane (8 godz.)
Pojęcie algorytmu randomizowanego. Podstawy matematyczne. Przykłady algorytmów.

Ćwiczenia laboratoryjne:

1. Implementacja programu rozwiązującego trudny problem obliczeniowy (15 godz.)

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 75 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 14 godz
Samodzielne studiowanie tematyki zajęć 32 godz
Udział w ćwiczeniach laboratoryjnych 14 godz
Przygotowanie do zajęć 15 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa, zaliczenia ćwiczeń laboratoryjnych w pierwszym terminie jest oceną z ćwiczeń laboratoryjnych, ale nie niższą niż 3.5. W przypadku zaliczenia ćwiczeń laboratoryjnych w terminie późniejszym niż pierwszy, ocena końcowa nie może być wyższa niż 3.0.

Wymagania wstępne i dodatkowe:

Ogólna znajomość matematyki z naciskiem na matematykę dyskretną. Podstawowa wiedza dotycząca: logiki, teorii grafów, metod konstruowania algorytmów. Znajomość materiału przedmiotu Teoria Obliczeń i Złożoności Obliczeniowej.

Zalecana literatura i pomoce naukowe:

1. Sipser M.: Wprowadzenie do teorii obliczeń. WNT 2009
2. Papadimitriou C.H.: Złożoność obliczeniowa. Helion 2012
3. Bovet D.P, Crescenzi P.: Introduction to the theory of complexity. Prentice Hall, 1994
4. Wegener I.: Complexity Theory, Springer, 2005
5. Michalewicz Z., Fogel D.: Jak to rozwiązać czyli nowoczesna heurystyka. WNT 2006
6. Motwani R., Raghavam P.: Randomized Algorithms, Cambridge University Press 1995

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

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak