{2003/2004}[Diario del corso]Metodi Per il Trattamento dell'Informazione
Clicca QUI per vedere il messaggio nel forum |
| Bulma |
"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 |
| Bulma |
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à |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Funzioni parziali
- Funzione di valutazione
- Sistema di Calcolo
- Insiemi isomorfi
- Cardinalità finita, cardinalità numerabile |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Funzione calcolabile
- Funzione coppia di Cantor
- Codifica di dati tramite la funzione coppia |
| Bulma |
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 |
| Bulma |
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 |
| Bulma |
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) |
| Bulma |
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 |
| Bulma |
Argomenti trattati nella lezione di oggi:
- codifica di istruzioni RAM
- Interprete while per programmi RAM |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Programma W interprete per programmi while
- F(RAM) = F(while)
- eliminazione del GOTO
- Interprete Universale |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Intermezzo: calcolo delle funzioni sin e des
- Chiusura di un insieme rispetto ad un'operazione |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Insieme ELEM delle funzioni elementari
- Composizione di funzioni, Ricorsione Primitiva
- Classe delle funzioni Ricorsive Primitive |
| Bulma |
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 |
| Bulma |
Per un paio di settimane non potrò seguire le lezioni. Se qualcuno vuole sostituirmi, sarà ben accetto!! :D
A presto :ciao: |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Il problema dell'arresto
- Insiemi Ricorsivamente Numerabili (Semi-Decidibili) |
| Bulma |
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) |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Se A e A^c sono ricorsivamente numerabili, A è ricorsivo.
- Insieme che rispetta le funzioni
- Teorema di Rice |
| Bulma |
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. |
| Bulma |
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. |
| Bulma |
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. |
| Bulma |
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 |
| Bulma |
Argomenti trattati nella lezione di oggi:
- Macchina di Turing dotata di nastro di output
- Algoritmi non deterministici
- Macchina di Turing non deterministica
- Classe NP |
| Bulma |
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... :D |
| Bulma |
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"?? :pensa: ) :D
:ciao: |
|
|
|
