II Esonero di Fondamenti di Informatica II (secondo modulo)
2-7-1998

Esercizio N. 1 Fornire esempi di problemi risolubili in tempo polinomiale (indicando anche mediante quale tecnica algoritmica) ed esempi di problemi di cui siano solo note soluzioni di costo esponenziale (indicando anche in questo caso quali tecniche algoritmiche possono essere usate).

Esercizio N. 2 Fornire esempi di problemi decidibíli e indecidibili relativi al comportamento di un programma.

Esercizio N. 3 Descrivere la tecnica di programmazione dinamica e la tecnica divide et impera. Che cosa hanno in comune ed in cosa differiscono? Mostrare esempi di applicazione delle due tecniche.