MATEMATICA Ogni problema è risolubile? - Accademia dei Lincei e SNS - 18 gennaio 2018

www.sns.it/eve...
MATEMATICA - LA MATEMATICA NEL MONDO CONTEMPORANEO
Pierpaolo Degano, Università di Pisa, Dip. di Informatica
Coordinatori del corso
Francesco Pegoraro, Università di Pisa
Fulvio Ricci, Scuola Normale Superiore
Destinatari
Docenti di scuola secondaria di secondo grado
Finalità, obiettivi e metodologia di lavoro
Il corso si articola in tre cicli, che possono essere frequentati assieme o singolarmente
www.sns.it/scu...
I MODULO
Ogni problema è risolubile?
Prof. Pierpaolo Degano, Università di Pisa, Dip. di Informatica, 18, 19, 25 gennaio
3 lezioni di 3 ore ciascuna
Al Congresso Internazionale dei Matematici a Parigi nel 1900 Hilbert affermò che «ogni problema matematico deve necessariamente avere una caratterizzazione esatta, sia sotto forma di una soluzione esatta, sia mediante la dimostrazione dell'impossibilità della sua soluzione e di tutti i tentativi per raggiungerla». In seguito riformulò tale iper-ottimistica affermazione nella forma seguente: «L'Entscheidungsproblem è risolto se si conosce una procedura che permette di decidere, con un numero finito di operazioni, la validità o la soddisfacibilità di una data espressione logica».
Presenteremo la formalizzazione del concetto di procedura, o meglio di algoritmo, proposta da Turing in termini delle sue macchine e sul loro rapporto con le funzioni che rappresentano. Esamineremo allora in cosa consista il “calcolare meccanicamente” e i suoi legami con la nozione di dimostrazione in matematica. Scopriremo che, anche in assenza di limiti sulle risorse necessarie al calcolo, per es. sul numero di passi o di fogli di carta usati per i conti intermedi, esistono dei problemi che non possono venir risolti, dando origine a una gerarchia in termini di “difficoltà". Quando poi si impongano dei vincoli sull'uso delle risorse, tipicamente dipendenti dalla dimensione dei dati di ingresso al problema, si scopre una gerarchia analoga, nella quale giocano un ruolo importante le classi dei problemi P ed NP, che sono risolvibili rispettivamente in tempo polinomiale deterministico e non-deterministico.
L'intuizione che sottende la teoria della calcolabilità e di quella della complessità sarà accompagnata da riferimenti puntuali sull'enorme impatto e sull'uso quotidiano che hanno i suoi risultati nel campo dell'Informatica.