II Esonero di Fondamenti di Informatica II (secondo modulo)
30-6-1998
Compito A
Esercizio N. 1 Mostrare esempi di funzioni non calcolabili e spiegare da cosa deriva la loro non calcolabilità.

Esercizio N. 2 Si consideri un grafo non orientato G = (V, E). Un Insieme Dominante di vertici (in breve Insieme Dominante) per G è un insieme V' C V tale che per ogni vertice u e V - V' esiste un nodo v e V' adiacente ad u (ovvero per cui (u, v) e E). La misura di un Insieme Dominante è la cardinalità |V'| dell'insieme V'.
(N.B.: e = ' rovesciato).
Il problema del Minimo Insieme Dominante per G consiste nel determinare un Insieme Dominante V' per G di cardinalità minima. Tale problema è NP-completo.

Consideriamo il seguente algoritmo:

· Sia dato un grafo G = (V, E).

· Inizializza V' = 0 (insieme vuoto) e ripeti il passo seguente finchè ci sono nodi non dominati in G (un nodo u e V è non dominato se u e V - V' e nessun nodo v e V' è adiacente ad u):
Inserisci in V' il nodo v e V - V' che domina il massimo numero di nodi in V - V' che non sono dominati da nodi in V'.

   - Che tecnica algoritmica viene utilizzata?

- Mostrare che l'algoritmo proposto non trova sempre un Insieme Dominante di cardinalità minima.

 Esercizio N. 3 Descrivere, anche mediante esempi, la tecnica della ricerca locale.