Egzamin bedzie dotyczyl drugiej czesci kursu NAI.

Glowne tematy:

1) NP-zupelnosc
2) heurystyki:
 a) przeszukiwanie lokalne 
 b) podejscie zachlanne
 c) algorytmy genetyczne

ad 1) Zakres jest pokryty przez rozdzial "NP-zupelnosc" w podreczniku "Wprowadzenie do Algorytmow" Cormena, etc.

Prosze przeczytac ten rozdzial aby przygotowac sie do egzaminu.

Przykladowe zadania:
- podaj definicje i wyjasnienie danego pojecia (np. P, NP, NP-zupelne, NP-trudne, redukcja, etc.)
- podaj i wyjasnij bardzo precyzyjna specyfikacje danego problemu optymalizacyjnego albo jego wersji decyzyjnej (np. TSP, plecakowy, HAMILTON, CLIQUE, Independent Set, Vertex Cover, (CIRCUIT-)SAT, 3-CNF)
- udowodnij, ze podany problem jest NP-zupelny za pomoca (prostej) redukcji albo wyjasnij dlaczego jest w klasie P

ad 2:
Majac podana specyfikacje problemu optymalizacyjnego lub decyzyjnego, zaproponuje metode rozwiazania go:
a) za pomoca przeszukiwania lokalnego (wtedy zaproponuj sensowna relacje sasiedztwa i udowodnij, ze spelnia 4 wymagane cechy)
b) za pomoca algorytmu zachlannego (w tym, udowodnij, za pomoca matroidu i twierdzenia Rado-Edmondsa, ze jest optymalny lub podaj przyklad, ze nie jest)