====== Nome modulo ======
----
===== News =====
<WRAP center round important 95%>
 </WRAP>

----
===== Informazioni Generali =====
<WRAP box round 95% center>
**Docente**: 
  * [[http://barbarare.wordpress.com|Barbara Re]] 

**Orario delle Lezioni**:
  * Martedì:  15:00 – 17:00 
  * Giovedì: 15:00 – 17:00 


**Ricevimento studenti**:
  * Al termine delle lezioni o previo appuntamento via mail.
</WRAP>
----
===== Obiettivi del Corso =====

<WRAP box round 95% center>
  * Conoscere le motivazioni della nascita dell'Informatica moderna e dell'idea astratta di calcolatore
  * Osservare l'esistenza di problemi che non si possono risolvere, o che si possono risolvere solo a costi inaccessibili
  * Confrontare i vari possibili approcci alla computabilità

</WRAP>

----
===== Contenuti del Corso =====

<WRAP round 95% center box>
  * La computabilità da Leibniz ai giorni nostri. Il concetto di Algoritmo.
  * Macchine di Turing. Alfabeti, stringhe e linguaggi. Funzioni calcolabili e linguaggi decidibili secondo Turing. La tesi di Church. Macchine di Turing non deterministiche. 
  * Problemi senza soluzione.  La macchina Universale. Il problema dell'arresto. Il decimo problema di Hilbert. I teoremi di Rice e di Kleene.
  * Funzioni Ricorsive. Calcolabilità secondo Church. Funzioni parziali ricorsive.
  * Calcolabilità e Grammatiche. Grammatiche e automi. La gerarchia di Chomsky. Linguaggi regolari, liberi da contesto, dipendenti dal contesto. Automi di riconoscimento.
  * Calcolabilità e Linguaggi di Programmazione. Il linguaggio WHILE: sintassi e semantica.

</WRAP>
----
===== Materiale =====
<WRAP box round center 95%>
**Slide del Corso**
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class1%20-%20Syllabus.pdf|Introduzione al corso]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class2%20-%20Introduzione.pdf |Introduzione alla teoria della computabilità ]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class3%20-%20StringheLinguaggi.pdf |Alfabeti, stringhe e linguaggi]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class4%20-%20LinguaggiFormali.pdf |Grammatiche]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class5%20-%20LinguaggiFormali%20%28Esercizi%29.pdf |Esercitazioni]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class6%20-%20Automi.pdf|Automi1]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class7%20-%20LinguaggiRegolari.pdf|Automi2]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class8%20-%20Automi%20%28esercizi%29.pdf|Esercitazioni]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class9%20-%20%20%28esercizi%29.pdf |Esercitazioni]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class10%20-%20ASFD-ASFND.pdf |ASFD e ASFND]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class11%20-%20MacchinediTuring.pdf |Macchine di Turing]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class12%20-%20MacchinediTuring%20esercizi.pdf | Macchine di Turing (esercitazioni)]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class13%20-%20Problemi%20Senza%20Soluzioni.pdf | Problemi senza soluzioni]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class14%20-%20FunzioniRicorsive.pdf | Funzioni Ricorsive]]
  * [[ https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class15%20-%20LinguaggioWhile.pdf| Linguaggio WHILE: Sintassi e Semantica]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/SimulazioneEsame.pdf | Simulazione prova d’esame]]
  * [[https://dl.dropboxusercontent.com/u/1606914/Fondamenti/Class16%20-%20Simulazione.pdf | Soluzioni Simulazione prova d’esame]]

**Testi di Riferimento**
  * F. Corradini, S. Leonesi, S. Mancini, C. Toffalori: Teoria della computabilità e della complessità. McGraw-Hill Italia, 2005. (Capitolo 1 – 6)

</WRAP>
----
===== Esami =====
<WRAP box round center 95%>
**Date Esami A.A. 2014/2015 (https://didattica.unicam.it/Home.do)**
  * 01/02/2016 11:30
  * 01/10/2015 11:30 
  * 15/09/2015 11:30 
  * 01/07/2015 11:30 
  * 16/06/2015 11:30 
  * 31/03/2015 11:30 
  * 23/02/2015 11:30 
  * 03/02/2015 11:30

**Regole di esame**: 

La prova consiste in uno scritto sugli argomenti del syllabus composto da domande a risposta aperta ed esercizi. La durata prevista è di 2 h.

** Risultati Esame **
  * N/A
</WRAP>