Pages: [1]   Go Down
Print
Author Topic: Testo esame 13/7  (Read 2739 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
marvin
Matricola
*
Offline Offline

Posts: 23


« on: 11-09-2009, 12:14:46 »

Qualcuno potrebbe gentilmente trascrivere,anche in maniera approssimativa, il testo dell'ultimo esame? Ne sarei grato. Ho già contattato il prof ma non ho ricevuto risposta.
Logged
unaviandante
Matricola
*
Offline Offline

Posts: 73



« Reply #1 on: 11-09-2009, 18:09:32 »

ecco il testo dell'ultimo compito:

1. Definire le Classi di Complessità Deterministiche e Non-Deterministiche, e le
relative Proprietà.
2. Dimostrare la seguente Proprietà: Se L é riconosciuto da una DTM in spazio S(n)
con k > 1 nastri, allora L é riconosciuto da una DTM in spazio S(n) con 1 solo
nastro.
3. Descrivere le classi P, NP, e i problemi NP-completi.
4. Definire una Misura della Complessità e descrivere un esempio di Misura di
Complessità.
5. Dare la Definizione di Classe di Complessità e costruire una sequenza gerarchica
di Classi di Complessità.


Ciao
Rita
Logged
marvin
Matricola
*
Offline Offline

Posts: 23


« Reply #2 on: 11-09-2009, 20:31:53 »

Grazie mille!
Logged
Pages: [1]   Go Up
Print
Jump to: