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.