Il corso si propone di fornire le conoscenze di base della teoria della calcolabilità e della complessità. Al termine del corso gli studenti saranno in grado di capire cos’è un problema indecidibile o intrinsecamente difficile ed eventualmente dimostrarne tali proprietà mediante l’applicazione dei teoremi studiati durante il corso o mediante l’uso di tecniche basate sulla riduzione tra problemi.
4. Macchine di Turing multinastro
5. Macchine di Turing non-deterministiche
6. Macchina di Turing universale e problema della fermata
7. Problemi decidibili e non decidibili
8. Problemi non decidibili e riducibilità - prima parte
9. Problemi non decidibili e riducibilità - seconda parte
11. Decidibilità delle teorie logiche
12. Misurazione della Complessità e introduzione alla classe P
14. NP-Completezza - prima parte
15. NP-Completezza - seconda parte
16. Altri problemi NP-Completi
17. Esercitazione su problemi NP-Completi
18. Space Complexity
19. Savitch Theorem
E’ ricercatore universitario in Informatica dal 2005 presso la Sezione di Informatica del Dipartimento di Scienze Fisiche dell’Università “Federico II”. L’attività di ricerca riguarda i linguaggi formali, gli aspetti formali di specifica e verifica di sistemi hardware e software, il model checking, la verifica di sistemi aperti, la teoria dei giochi, la teoria degli automi, le logiche temporali sia discrete che in tempo denso. Consegue la laurea in Scienze dell’Informazione con voto di 110/110 con lode nel 1997, presso l’Univ. di Salerno. Presso la stessa università consegue, nel Maggio 1999, il Master in Metodologie Telematico-Multimediali con il voto di 100/100 e, nel Febbraio 2003, il dottorato di Ricerca in Informatica, discutendo una tesi sulla teoria dei giochi. Durante il dottorato, Aniello Murano è Visiting Scholar presso la Rice University di Houston (TX-USA) per un anno, sotto la supervisione della Prof. M. Y. Vardi. Dal 2003 al 2004 è post-doc presso la Hebrew University di Gerusalemme sotto la supervisione della Prof. O. Kupferman. È supervisore scientifico di studenti di dottorato e di master. È autore di circa 40 lavori scientifici.
Curriculum completo