myAriel

Il corso è dedicato a due argomenti principali: la calcolabilità e la complessità computazionale. Nella prima parte la nozione di calcolabilità viene introdotta usando semplici linguaggi di programmazione. In particolare si illustra e si giustifica la tesi di Church, si presentano i problemi indecidibili fondamentali e i risultati principali di teoria della ricorsività. La seconda parte è dedicata alla complessità computazionale dei problemi decidibili, ovvero all'analisi della quantità di risorse (tempo di calcolo e spazio di memoria) richiesta dai corrispondenti algoritmi. In particolare vengono studiate le principali classi di complessità in tempo e spazio e le proprietà dei problemi NP-completi.