.dsy:it. (http://www.dsy.it/forum/)
- Informatica teorica (http://www.dsy.it/forum/forumdisplay.php?forumid=251)
-- {2003/2004}[Diario del corso]Metodi Per il Trattamento dell'Informazione (http://www.dsy.it/forum/showthread.php?threadid=9184)

[Diario del corso]Metodi Per il Trattamento dell'Informazione

"Metodi per il trattamento dell'informazione" è un corso fondamentale per la Laurea Specialistica in Informatica.
Seguono alcune informazioni generali sul corso.

Docente: C. Mereghetti

Sito Web di Riferimento: http://homes.dsi.unimi.it/~mereghet/mt.html

Orari delle lezioni:
martedì 12.30 - 14.30 (aula alfa)
mercoledì 12.30 - 14.30 (aula beta)

Modalità di Esame: in fase di definizione.

Materiale didattico: per la preparazione sono sufficienti le due dispense presenti sul sito del corso.

Argomenti del corso:

1. Calcolabilità:
- macchina RAM
- modello while
- classe delle funzioni RP
- tesi di Church
- S.p.a. (Sistemi di Programmazione Accettabili)

2. Complessità:
- macchina di Turing
- tempo, spazio
- efficienza = polinomialità
- classe P
- classe NP
- completezza

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 02-03-04

Argomenti trattati nella lezione di oggi:

Cenni a concetti matematici:
- definizione di funzione
- funzioni iniettive, suriettive, biiettive
- inversa di una funzione
- composizione di funzioni
- funzione identità

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 3-3-04

Argomenti trattati nella lezione di oggi:

- Funzioni parziali
- Funzione di valutazione
- Sistema di Calcolo
- Insiemi isomorfi
- Cardinalità finita, cardinalità numerabile

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 9-3-04

Argomenti trattati nella lezione di oggi:

- Funzione calcolabile
- Funzione coppia di Cantor
- Codifica di dati tramite la funzione coppia

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione 10-3-04

Argomenti trattati nella lezione di oggi:

- Codifica di array, matrici, grafi in interi
- Linguaggio RAM:
* Sintassi
* Architettura
* Fasi di esecuzione di un programma
* Semantica Operazionale
* Stato della Macchina
* Stato finale
* Inizializzazione e Stato iniziale
* Funzione di Stato Prossimo

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 16-03-04

Argomenti trattati nella lezione di oggi:

-Sistema RAM (cont.):
* Funzione di stato prossimo
* Computazione di un programma RAM; computazione accettata
* Output
* Classe delle funzioni calcolate da programmi RAM

- Sistema while:
* comandi
* architettura della macchina while
* programma while

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 17-03-04

Argomenti trattati nella lezione di oggi:

- Macchina while (cont.):
* Stato della macchina
* Funzione di stato prossimo
* Stato iniziale
* Funzione calcolata dal programma while

- Traduzione da un linguaggio L1 a un linguaggio L2 (compilazione)
- Traduzione da while a RAM (to be continued)

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 23-03-04

Argomenti trattati nella lezione di oggi:

- Traduzione da RAM a while (cont.)
- F(RAM) <= F(while): passi della successiva dimostrazione:
* Realizzazione di una codifica da PROG a N+ tramite la godelizzazione
* Realizzazione di un interprete while per progammi RAM

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 24-03-04

Argomenti trattati nella lezione di oggi:

- codifica di istruzioni RAM
- Interprete while per programmi RAM

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 30-03-04

Argomenti trattati nella lezione di oggi:

- Programma W interprete per programmi while
- F(RAM) = F(while)
- eliminazione del GOTO
- Interprete Universale

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 31-03-04

Argomenti trattati nella lezione di oggi:

- Intermezzo: calcolo delle funzioni sin e des
- Chiusura di un insieme rispetto ad un'operazione

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 6-4-04

Argomenti trattati nella lezione di oggi:

- Insieme ELEM delle funzioni elementari
- Composizione di funzioni, Ricorsione Primitiva
- Classe delle funzioni Ricorsive Primitive

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 7-4-04

Argomenti trattati nella lezione di oggi:

- RicPrim è inclusa in F(while): dimostrazione
- RicPrim = F(for)
- Operazione di Minimalizzazione
- Classe P delle funzioni Ricorsive Parziali
- P è inclusa in F(while): dimostrazione

__________________
The man in black fled across the desert and the gunslinger followed.

Comunicazione di servizio

Per un paio di settimane non potrò seguire le lezioni. Se qualcuno vuole sostituirmi, sarà ben accetto!!

A presto

__________________
The man in black fled across the desert and the gunslinger followed.

Lezione del 04-05-04

Argomenti trattati nella lezione di oggi:

- Il problema dell'arresto
- Insiemi Ricorsivamente Numerabili (Semi-Decidibili)

__________________
The man in black fled across the desert and the gunslinger followed.