Studiare

In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.

Piano Didattico

Il piano didattico è l'elenco degli insegnamenti e delle altre attività formative che devono essere sostenute nel corso della propria carriera universitaria.
Selezionare il piano didattico in base all'anno accademico di iscrizione.

CURRICULUM TIPO:

1° Anno 

InsegnamentiCreditiTAFSSD
Insegnamenti offerti ad anni alterni
6
B
MAT/02
6
B
MAT/02
12
B
MAT/05
Insegnamenti offerti ad anni alterni
12
B
MAT/08
12
B
MAT/06
6
B
MAT/05
6
B
MAT/07
12
B
MAT/03

2° Anno   Attivato nell'A.A. 2011/2012

InsegnamentiCreditiTAFSSD
Due tra i seguenti insegnamenti
6
C
MAT/09
6
C
MAT/08
6
C
INF/01
6
C
MAT/06
6
C
MAT/08
6
C
MAT/08
6
C
MAT/09
6
C
INF/01
32
E
-
InsegnamentiCreditiTAFSSD
Insegnamenti offerti ad anni alterni
6
B
MAT/02
6
B
MAT/02
12
B
MAT/05
Insegnamenti offerti ad anni alterni
12
B
MAT/08
12
B
MAT/06
6
B
MAT/05
6
B
MAT/07
12
B
MAT/03
Insegnamenti Crediti TAF SSD
Tra gli anni: 1°- 2°
12
D
-
Tra gli anni: 1°- 2°
Ulteriori competenze
4
F
-

Legenda | Tipo Attività Formativa (TAF)

TAF (Tipologia Attività Formativa) Tutti gli insegnamenti e le attività sono classificate in diversi tipi di attività formativa, indicati da una lettera.

A Attività di base
B Attività caratterizzanti
C Attività formative affini o integrative
D Attività a scelta dello studente
E Prova finale
F Altre attività formative
S Stage e tirocini presso imprese, enti pubblici o privati, ordini professionali

Metodi matematici per l'informatica (2011/2012)

Codice insegnamento

4S02855

Crediti

6

Coordinatore

Ugo Solitro

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

INF/01 - INFORMATICA

Seminari 0

L'insegnamento è organizzato come segue:

Parte 2

Crediti

3

Periodo

I semestre

Docenti

Gianluigi Bellin

Parte 1

Crediti

3

Periodo

I semestre

Docenti

Ugo Solitro

Obiettivi formativi

Un'introduzione alla teoria della computabilità e alla logica computazionale.

Programma

Modulo: Computabilità.
-------
Introduzione.
Automi, Linguaggi e Grammatiche. Risultati prinicipali.

Calcolabilità
Algoritmi. Sistemi di Calcolo Effettivo: Macchine di Turing, Funzioni parziali ricorsive, ...
Risultati fondamentali. Tesi di Church. Aritmetizzazione e Universalità. Problemi insolubili.
Teoria matematica della Ricorsione.

Complessità.
Classi di Complessità. NP-Completezza.
Complementi
------------------------

Modulo: Logica computazionale.

Rappresentazione di prove ed algoritmi.
Calcoli dei sequenti, eliminazione del taglio, semantic tableaux. Deduzione naturale intuizionistica.

Lambda calcolo, proprietà di Church-Rosser. Rappresentabilità delle funzioni parziali ricorsive. Tipi semplici e tipabilità.

Corrispondenza di Curry Howard e teorema di normalizzazione debole del lambda calcolo con tipi semplici. Complementi.

Bibliografia

Testi di riferimento
Attività Autore Titolo Casa editrice Anno ISBN Note
Parte 1 Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821 Testo di consultazione
Parte 1 Garey, M. R. and Johnson, D. S. Computers intractability: a guide to the theory of NP-completeness Freeman 1979 0-7167-1045-5 Testo di consultazione
Parte 1 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages and Computation (Edizione 2) Addison-Wesley 2000 0201441241 Testo di consultazione
Parte 1 H. Rogers Theory of recursive functions and effective computability MIT Press 1988 Testo di consultazione

Modalità d'esame

L'esame prevede una prova di verifica per ciascun modulo e un colloquio orale finale.

Le/gli studentesse/studenti con disabilità o disturbi specifici di apprendimento (DSA), che intendano richiedere l'adattamento della prova d'esame, devono seguire le indicazioni riportate QUI