Domande Orale Degano

NiccoZ
Messaggi: 2
Iscritto il: 05/11/2020, 15:55

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.
Avatar utente
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
loreangeli
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.
marina.pierotti
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%
Allegati
Esercizi orale ECC.pdf
(254.14 KiB) Scaricato 1097 volte
Jacopo
Messaggi: 4
Iscritto il: 16/06/2021, 14:21

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à.
g.maoro
Messaggi: 2
Iscritto il: 28/09/2019, 0:52

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)
GiuseppeGR
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
Lui è molto paziente e ti lascia ragionare dando anche alcuni aiuti ma richiede molta precisione. Nelle dimostrazioni delle dispense alcune cose vengono tralasciate per cui consiglio una visione veloce delle lezioni.
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”