II Esonero di Fondamenti di Informatica II (secondo
modulo)
30-6-1998
Compito B
Esercizio N. 1 Mostrare esempi di problemi NP-completi
e illustrare le loro proprietà.
Esercizio N. 2 Si consideri un grafo non orientato
G = (V, E). Un Insieme Indipendente di vertici (in breve Insieme
Indipendente) per G è un insieme V' C V tale
che, per ogni coppia di nodi u, v e
V, l'arco (u, v) non appartiene ad E. La misura di un Insieme
Indipendente è la cardinalità |V'| dell'insieme V'.
(N.B.: e = ' rovesciato).
Il problema del Massimo Insieme Indipendente per G consiste
nel determinare un Insieme Indipendente V' per G di cardinalità
massima. Tale problema è NP-completo.
Consideriamo il seguente algoritmo:
Sia dato un grafo G = (V, E) e l'Insieme Indipendente V' = 0
(insieme vuoto).
Finchè è possibile trovare un nodo v e
V tale che V' U {v} è un Insieme Indipendente,
inserisci il nodo v nell'insieme V' e ripeti il passo.
Che tecnica algoritmica viene utilizzata?
Mostrare che, l'algoritmo proposto non trova sempre un Insieme Indipendente
di cardinalità massima.
Esercizio N. 3 Descrivere, anche mediante esempi,
la tecnica greedy per la risoluzione di problemi.