.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.

Lezione del 05-05-04

Argomenti trattati nella lezione di oggi:

- Teorema: definizioni equivalenti di insiemi ricorsivamente numerabili
- Teorema: se A è ricorsivo, allora A è ricorsivamente numerabile
- Chiusura della classe Ric (sotto unione, intersezione, complemento)

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

Lezione del 11-05-04

Argomenti trattati nella lezione di oggi:

- Se A e A^c sono ricorsivamente numerabili, A è ricorsivo.
- Insieme che rispetta le funzioni
- Teorema di Rice

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

Lezione del 12-05-04

Durante la lezione di oggi sono stati svolti in aula esercizi sugli SPA e su insiemi ricorsivi/ricorsivamente numerabili.

Ricordo che l'esame finale prevede un orale più, a scelta, uno scritto (contenente esercizi del tipo mostrato oggi) oppure un approfondimento.

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

Lezione del 18-05-04

Argomenti trattati nella lezione di oggi:

- Macchina di Turing: definizione e funzionamento
- Teorema: La classe degli insiemi accettati da una mdT coincide con la classe dei RicNum
- Definizione di algoritmo deterministico
- Teorema: La classe degli insiemi accettati da algoritmi deterministici concide con la classe dei Ric.

Avviso: La lezione di domani, mercoledì 19 maggio, è sospesa causa sciopero dei mezzi pubblici. La lezione sarà recuperata a giugno.

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

Lezione del 25-04-05

Argomenti trattati nella lezione di oggi:

- Funzione calcolata da una macchina di Turing
- Le macchine di Turing sono un s.p.a.
- Tempo di calcolo, complessità in tempo
- Riconoscimento in tempo f(n)
- Notazione O (o-grande)
- Classe DTIME
- La Classe P
- Tesi di Church Estesa


Avviso: La lezione del 2 giugno, che non avrà luogo per via della Festa della Repubblica, verrà recuperata giovedì 3 giugno dalle 12.30 alle 14.30 in auletta 4.

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

Lezione del 26-05-04

Argomenti trattati nella lezione di oggi:

- Spazio di calcolo e complessità in spazio worst-case
- Macchina di Turing a due nastri e due testine
- DSPACE
- Classe L
- DTIME(f(n)) incluso in DSPACE(f(n))
- Teorema: L incluso in P

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

Lezione del 01-06-04

Argomenti trattati nella lezione di oggi:

- Macchina di Turing dotata di nastro di output
- Algoritmi non deterministici
- Macchina di Turing non deterministica
- Classe NP

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

Ciao a tutti,
c'è qualcuno che il 25 giugno ha sostenuto l'esame scritto di questo corso? Mi interesserebbe sapere come avete risolto l'ultimo esercizio...

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

Ciao ragazzi, ieri ho sostenuto l'esame di questo corso. Vi do un piccolo elenco delle domande del mio orale, magari potrebbero esservi utili:

- Definizione di insieme ricorsivo e ricorsivamente numerabile
- Relazione tra la classe Ric e la classe RicNum, esempi di insiemi appartenenti a queste classi
- Teorema di Rice e sua dimostrazione
- Teorema di ricorsione e sua dimostrazione
- Definizione di tempo e spazio su macchina di Turing, classe P e NP
- Dimostrazione del teorema: P=NP se esiste un problema NP-completo appartenente a P
- Riduzione polinomiale
- Dimostrazione di L sottoinsieme di P

Mi pare che questo fosse tutto, cmq credo che renda l'idea.
Perciò, non mi resta che augurarvi buona fortuna! (ma non si diceva "in bocca al lupo"?? )

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