The forum of the Computer Science students of the University of Pisa

Domande Orale Degano

Domande orale Masetti:
- Dim. che I={1} è completo per R
- Teorema del passaggio da una MdT non det. ad una MdT det
- Che cos'è NP? Ed un esempio
- Come si classificano due classi? (le 4 proprietà)
- Qual è la F nella riduzione <=F checlassifica P ed NP ? (logspace)
- Dim. le 4 proprietà sopra nel caso <=LOGSPACE tra P ed NP
- Dim. che K è RE e non R
- Definizione insieme R ed RE
- Perché K not<= K segnato e K segnato not<= K ?
- INF <= CONST
- CONST è R ? (no)
- Dim. che CONST non è R
- K <= CONST

Devo dire che personalmente Masetti mette a proprio agio e ti fa aiuta sempre quando può, a differenza del Degano che non sempre lo fa.
Orale con degano
- sia f calcolabile totale, dire se A_f={i| per ogni x phi_i(x) = f(x)} e' R, R.E, i.i.r.f e darne una motivazione
- enunciare e dimostrare teorema di rice
- enunciare e dimostrare teorema pre-rice (1.10.19 delle dispense)
- dimostrare che le riduzioni tramite P classificano sia P che NP, si dimostra sulla falsa riga del teorema 3.5.2
Lista domande del mio orale:
1. Ai = {x tale che la cardinalità del dom(phi_x)=i con i>0}: dire se è R,RE e iirf.
2. Dimostrare che P è incluso in EXP
3. Dimostrare che SAT si riduce secondo logspace a CRICCA
4. Dimostrare che SAT appartiene a NP.
Orale 18 gennaio 2022
- caratterizzare l'insieme I = {i | se x!=5 phi_i(x) converge} (risposta: non è RE, si dimostra riducendo prima a K, poi al complemento di K)
- teorema del parametro (s-1-1) e dimostrazione
- dimostrare che Logspace è incluso in P
(voto finale 27)

Lascio in allegato una raccolta di domande di esame di appelli precedenti che ho risolto per prepararmi all'esame, potrebbero esserci errori (in particolare il testo in rosso potrebbe essere inesatto) quindi non fidatevi al 100%

Allegati

Domande orale Masetti:

1- Dato A = {x | phi_x è sempre indefinita}, dire se A è R, RE, non-RE. (Rispota: è non-RE)
2- Dire perchè SAT appartiene a NP
3- Dire il tempo necessario per passare da forma normale congiuntiva a forma normale disgiuntiva(Risposta: O(2^n) con n = numero di congiunti).

Mentre aspettavo un amico ho seguito alcune domande del Degano:
1- Dire se esistono funzioni non calcolabili;
2- Dire quando una famiglia di funzioni classifica due problemi;
3- Definizione di problema arduo e problema completo;
4- Far vedere che K è RE-completo per rec;
5- DImostrare che K non è un insieme di indici che rappresenta funzioni;
6- Dimostrare che NTIME(f(n)) contenuto in TIME(c^f(n)), simulazione di una macchina non deterministica con perdita esponenziale;
7- Dato I = {x | dom(phi_x) è ricorsivo}, dimostrare che I si riduce a INF.

Dagli orali che ho visto il Degano ti lascia molto tempo per pensare e ti aiuta molto. L'importante è non fare scena muta e far vedere che si ragiona dicendo cose sensate.
Masetti pure molto tranquillo ti lascia pensare molto e ti aiuta in caso di difficoltà.