Calcolabilità e complessità 13/14

Il corso affronta il tema della risolubilita' di problemi con metodi meccanici, trattando anzitutto la teoria della computabilita' sia dal punto di vista classico - macchine di Turing, funzioni ricorsive, grammatiche - che da prospettive piu' attuali, come quella dei programmi while, legate ai linguaggi di programmazione. Si discutono poi i vari possibili criteri di misura delle risorse disponibili (tempo, memoria, cpu) e le classi di complessita', affrontando la classica questione P = NP.