Questo insegnamento ha lo scopo di introdurre i fondamenti teorici delle scienze informatiche, con particolare riferimento alla decidibilità di problemi computazionali, alla calcolabilità di funzioni e insiemi e alla modellazione formale di sistemi computazionali, attraverso notazioni di base come macchine di Turing, lambda calcolo e algebre di processi.

01. Introduzione all'Informatica
  01.01 Informatica: Scienza, Metodologia, Tecnologia
  01.02 Impatto Socio-Economico e Pensiero Computazionale
  01.03 Cenni di Storia dell'Informatica
  01.04 Perché la Teoria È Importante: Disastri Informatici

02. Introduzione alla Computazione
  02.01 Problemi Computazionali e Soluzioni Algoritmiche
  02.02 Un Modello Classico di Computazione
  02.03 Dal Logicismo all'Incompletezza e all'Indecidibilità
  02.04 Induzione, Enumerazioni, Codifiche

03. La Visione Operazionale: Macchine di Turing
  03.01 Automi e Macchine di Turing
  03.02 La Macchina di Turing Universale
  03.03 Linguaggi Riconosciuti da Macchine di Turing
  03.04 Funzioni Calcolate da Macchine di Turing

04. La Visione Funzionale: Lambda Calcolo
  04.01 Sintassi del Lambda Calcolo
  04.02 Semantica e Logica Combinatoria
  04.03 Funzioni Ricorsive via Punti Fissi
  04.04 Terminazione e Confluenza
  04.05 Lambda Calcolo con Tipi

05. Calcolabilità per Funzioni, Insiemi, Problemi
  05.01 Tesi di Church-Turing
  05.02 Funzioni Ricorsive Primitive e Generali
  05.03 Insiemi Ricorsivi e Ricorsivamente Enumerabili
  05.04 Problemi Decidibili e Indecidibili
  05.05 Problemi Trattabili e Intrattabili

06. La Visione Modellistica: Algebre di Processi
  06.01 Concorrenza e Comunicazione
  06.02 Sintassi dei Calcoli di Processi
  06.03 Semantica Interfogliante via Sistemi di Transizione Etichettati
  06.04 Potere Computazionale dei Calcoli di Processi
  06.05 Spettro delle Equivalenze Comportamentali
  06.06 Bisimilarità Forte e Sue Proprietà
  06.07 Bisimilarità Deboli e Loro Proprietà
  06.08 Semantica Concorrente via Reti di Petri
  06.09 Semantica Concorrente via Strutture di Eventi
  06.10 Bisimilarità Concorrenti

Non vi sono propedeuticità obbligatorie.

Il materiale didattico predisposto dalla/dal docente in aggiunta ai testi consigliati (come ad esempio diapositive, dispense, esercizi, bibliografia) e le comunicazioni della/del docente specifiche per l'insegnamento sono reperibili all'interno della piattaforma Moodle › blended.uniurb.it

Modalità didattiche

Lezioni teoriche.

Obblighi

La frequenza è fortemente consigliata.

Testi di studio

Hopcroft, Motwani, Ullman, "Automata Theory, Languages, and Computation", Pearson Addison-Wesley, 2006.

Barendregt, "The Lambda Calculus: Its Syntax and Semantics", North Holland, 2014.

Milner, "Communication and Concurrency", Prentice Hall, 1989.

Modalità di
accertamento

Prova orale su un argomento concordato col docente.

Disabilità e DSA

Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.

A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.