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.
Domande Orale Degano
- ANDREAGIUSTI
- Messaggi: 1
- Iscritto il: 06/07/2021, 18:16
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
- 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
-
- Messaggi: 1
- Iscritto il: 13/01/2022, 11:30
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.
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.
-
- Messaggi: 2
- Iscritto il: 02/01/2019, 18:31
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%
- 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
-
- Esercizi orale ECC.pdf
- (254.14 KiB) Scaricato 1078 volte
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à.
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à.
Domande orale 16 dicembre 2022
Io ho fatto l'orale con l'assistente, ho notato che in genere fa due domande sulla complessità e due sulla calcolablità.
1. dimostrare che K non è ricorsivo (dimostrazione per assurdo)
2. mi ha fatto fare un esercizio di calcolabilità che non ricordo
3. dimostrare che circuit-value è P-completo
4. enunciato e dimostrazione del passaggio da una macchina non deterministica a una deterministica (perdita esponenziale)
Io ho fatto l'orale con l'assistente, ho notato che in genere fa due domande sulla complessità e due sulla calcolablità.
1. dimostrare che K non è ricorsivo (dimostrazione per assurdo)
2. mi ha fatto fare un esercizio di calcolabilità che non ricordo
3. dimostrare che circuit-value è P-completo
4. enunciato e dimostrazione del passaggio da una macchina non deterministica a una deterministica (perdita esponenziale)
-
- Messaggi: 1
- Iscritto il: 02/07/2023, 12:15
Queste sono le domande del mio orale di Giugno 2023. In generale chiede un esercizio sugli i.i.rf, una dimostrazione della prima parte del corso e una sulla seconda.
- Caratterizzare l'insieme I={ i | Imm(phi_i)=insieme vuoto}
- Dare due caratterizzazioni di RE e dimostrare una delle due
- logSpace è incluso in P ? Dimostrazione