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 e alla Computazione
  01.01 Informatica: Scienza, Metodologia, Tecnologia
  01.02 Impatto Socio-Economico e Pensiero Computazionale
  01.03 Problemi Computazionali e Soluzioni Algoritmiche
  01.04 Cenni di Storia dell'Informatica

02. La Visione Operazionale: Macchine di Turing
  02.01 Un Modello Classico di Computazione
  02.02 Dal Logicismo all'Incompletezza e all'Indecidibilità
  02.03 Macchine di Turing e Macchina di Turing Universale
  02.04 Funzioni Calcolate e Linguaggi Riconosciuti

03. La Visione Funzionale: Lambda Calcolo
  03.01 Sintassi del Lambda Calcolo
  03.02 Semantica e Logica Combinatoria
  03.03 Funzioni Ricorsive via Punti Fissi
  03.04 Terminazione e Confluenza
  03.05 Lambda Calcolo con Tipi

04. Calcolabilità di Funzioni, Insiemi, Problemi
  04.01 Tesi di Church-Turing
  04.02 Funzioni Ricorsive Primitive e Generali
  04.03 Insiemi Ricorsivi e Ricorsivamente Enumerabili
  04.04 Problemi Decidibili e Indecidibili
  04.05 Problemi Trattabili e Intrattabili

05. La Visione Modellistica: Algebre di Processi
  05.01 Concorrenza e Comunicazione
  05.02 Sintassi dei Calcoli di Processi
  05.03 Semantica Interfogliante
  05.04 Semantica Concorrente via Reti di Petri
  05.05 Potere Computazionale dei Calcoli di Processi
  05.06 Spettro delle Equivalenze Comportamentali
  05.07 Bisimilarità Forte e Sue Proprietà
  05.08 Bisimilarità Debole e Sue Proprietà

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.

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.