.dsy:it. - {2003/2004}[Diario del corso]Metodi Per il Trattamento dell'Informazione

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi G - M > Informatica teorica > {2003/2004}[Diario del corso]Metodi Per il Trattamento dell'Informazione

Pages (2): « 1 [2]

Last Thread Next Thread

Author

Thread Expand all | Contract all

Bulma

.grande:maestro.

User info:

Registered: Jun 2002
Posts: 1706 (0.21 al dì)
Location: Rondinera City
Corso: Specialistica in Informatica
Anno: Dott. Mag.
Time Online: 72 Days, 20:00:05: [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

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.

05-05-2004 13:39

Click here to Send Bulma a Private Message

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

11-05-2004 13:45

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

12-05-2004 13:58

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

18-05-2004 14:09

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

Last edited by Bulma on 26-05-2004 at 13:53

25-05-2004 14:08

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

26-05-2004 13:53

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

03-06-2004 11:00

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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.

03-07-2004 15:05

Bulma

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

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: )
:ciao: