Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
Fondamenti dell'informatica

Docenti: F. Cardone, C. Zandron, L. Pomello

Crediti: 12 CFU

OBIETTIVI FORMATIVI

Conoscenze:

Concetti fondamentali della logica proposizionale e del prim'ordine.  

Introduzione alle tecniche di descrizione della semantica dei linguaggi di programmazione, con

particolare attenzione alla semantica denotazionale ed operazionale.

Conoscenze fondamentali relative a computabilità, complessità computazionale in termini

di spazio e di tempo, e algoritmi di approssimazione.

Fondamenti della teoria della concorrenza e dei relativi strumenti matematici.

 

Capacità:

Lo studente acquisterà familiarità con le principali tecniche di formalizzazione della deduzione, 

e con alcuni comuni metodi di dimostrazione.

Tecniche di prova di programmi basate sulla semantica, in particolare l'analisi dei cicli while mediante minimo punto fisso.

Acquisterà familiarità con le principali tecniche di riduzione tra problemi, e

con le tecniche utilizzate per determinare la classe di complessità di un problema computazionale.

Sarà in grado di utilizzare metodi e tecniche formali per il disegno e l’analisi  di modelli di sistemi concorrenti

 

Modulo SEMANTICA (4 CFU)

- Sintassi e semantica di linguaggi formalizzati. Correttezza e completezza.

- Sistemi formali. Induzione.

- Logica proposizionale: teoria della dimostrazione e semantica.

- Logica dei predicati: teoria della dimostrazione e semantica.

- Semantica formale dei linguaggi di programmazione (Semantica operazionale;

- Semantica denotazionale; Il teorema del punto fisso di Scott)

- Dimostrazione delle proprietà di un programma: Semantica assiomatica e dimostrazioni di correttezza

 

Testo consigliato: 

Glynn Winskel, The formal semantics of programming languages, MIT Press.

 

Modulo COMPLESSITA' (4 CFU)

- Elementi di computabilità

- Classi di complessità computazionale: P e NP

- Riduzione tra problemi: problemi NP-completi

- Algoritmi di approssimazione

- Classi di complessità nello spazio

- Classi di complessità in spazio sub-lineare

 

Testo consigliato: 

C. Papadimitriou, Computational Complexity, Addison-Wesley

 

 

Modulo PROCESSI CONCORRENTI (4 CFU)

- Teoria generale delle reti di Petri: reti Elementari e altre classi di reti. 

- La struttura di un sistema e il comportamento non sequenziale.

- Sistemi di transizioni, teoria delle regioni. Specifica e sintesi.

- I modelli dei processi comunicanti e le algebre di processi.

- Semantica della concorrenza ed equivalenza all'osservazione.

 

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 28/03/2011