Formalizzazione di problemi
Istanze e soluzioni
Ad ogni problema Π possiamo associare una funzione
dove:
- DΠ = insieme delle istanze di Π
- SΠ = insieme delle risposte di Π
- ∀x ∈ DΠ fΠ(x) = soluzione del problema Π relativa a x
Esempio:
Correttezza e algoritmi
Ad ogni algoritmo ALG associamo una funzione (parziale)
dove:
- InALG = insieme degli ingressi di ALG
- OutALG = insieme delle uscite di ALG
ALG risolve Π se e solo se: