49778 - LINGUAGGI E MODELLI COMPUTAZIONALI LM

Scheda insegnamento

  • Docente Mirko Viroli

  • Moduli Mirko Viroli (Modulo 1)
    Matteo Casadei (Modulo 2)

  • Crediti formativi 9

  • SSD ING-INF/05

  • Lingua di insegnamento Italiano

  • Campus di Cesena

  • Corso Laurea Magistrale in Ingegneria informatica (cod. 8200)

Anno Accademico 2010/2011

Conoscenze e abilità da conseguire

Al termine del corso, lo studente possiede le conoscenze di base per l'analisi e la progettazione di linguaggi di programmazione, la specifica di sistemi computazionali, e per la comprensione e l'uso dei principali modelli computazionali usati nell'ingegneria dei sistemi software. In particolare, lo studente è in grado di: - progettare software che sfrutti il paradigma della programmazione logica ed il linguaggio Prolog; - progettare un linguaggio di programmazione e costruirne un interprete o traduttore; - specificare aspetti sintattici e semantici di un sistema computazionale; - comprendere i principali modelli computazionali proposti in letteratura, ed utilizzarli per l'analisi di sistemi computazionali complessi.

Contenuti

  • Riassunto sui principali aspetti della teoria della computazione. Computazione ed Interazione. Automi e scale d'espressività: la macchina di Turing. Incompletezza di Goedel. Algoritmi. Tipi di dato astratti. Utilizzo del linguaggio MAUDE per la specifica di tipi di dato astratti e algoritmi.
  • Il linguaggio Prolog. Interpretazione relazione del Prolog, sintassi del Prolog, albero SLD, operatore di cut "!", esempi di programmazione, interpretazione procedurale. Metaprogrammazione e metainterpretazione. La tecnologia tuProlog: integrazione di Java e Prolog.
  • Logica. Logica propositionale. Logica del primo ordine. Interpretazione logica del Prolog. Accenni ad altre logiche.
  • Sintassi, grammatiche, e interpretazione. Le grammatiche formali. Derivazione di una frase. Classificazione di Chomsky. Riconoscibilità. Grammatiche BNF ed Extended BNF. Ambiguità. Trasformazioni di grammatiche. Espressioni regolari. Riconoscitori a stati finiti. Riconoscimento con linguaggi imperativi e logici. Generatori di frasi. Riconoscitori per grammatiche di tipo 2. Grammatiche LL. Esercizi in Java e Prolog. Il tool JavaCC. Esercizi nella definizione di linguaggi.
  • La semantica operazionale dei linguaggi. Semplici esempi. Formalismi. Reti di Petri. L'uso di MAUDE per le semantiche operazionali e il model-checking.
  • Modelli avanzati. Algebre di Processo, Sistemi stocastici (SPIM, PRISM). Panoramica su alcuni modelli e tool proposti in letteratura.

Testi/Bibliografia

Slide proiettate dal docente
Riferimenti bibliografici forniti durante il corso

Metodi didattici

Lezioni in aula

Esercitazioni in laboratorio

Modalità di verifica e valutazione dell'apprendimento

Esame scritto con esercizi

Esame pratico articolato articolato in:

  • discussione di un progetto
  • colloquio col docente

Strumenti a supporto della didattica

Slides proiettate a lezione

Software:

  • JDK 5.0 (o successivi)
  • tuProlog (http://tuprolog.sourceforge.net/)
  • MAUDE (http://maude.cs.uiuc.edu/)
  • SPIM (http://research.microsoft.com/en-us/projects/spim/)
  • PRISM (http://www.prismmodelchecker.org/)

Link ad altre eventuali informazioni

http://apice.unibo.it/xwiki/bin/view/MirkoViroli/Courses

Orario di ricevimento

Consulta il sito web di Mirko Viroli

Consulta il sito web di Matteo Casadei