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

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.