Probleme NP

INTRODUCERE
CAPITOLUL 1: PROBLEME ŞI ALGORITMI NP
1.1. Noţiuni introductive. .5
1.2. Structura unui algoritm NP. 6
CAPITOLUL 2: PROBLEME NP-DIFICILE ŞI PROBLEME
NP-COMPLETE. 10
CAPITOLUL 3: TEOREMA LUI COOK
3.1 Problema satisfacerii. 13
3.2 Enunţul teoremei lui Cook. 13
3.3 Modelul de maşină şi forma algoritmului folosite în demonstraţie. 14
3.4 Forma constructivă C corespunzătoare unui algoritm. 16
IV. CÂTEVA PROBLEME NP-COMPLETE
IV.1 Problema 3-satisfacerii. 25
IV.2 Problema 3-cuplării. 27 4.3 Problema K-acoperirii cu vârfuri a unui graf. 32
IV.4 Problemele clicii şi mulţimii independente. 35
IV.5 Problema ciclului hamiltonian. 36
IV.6 Problema partiţiei. 40
BIBLIOGRAFIE. 43