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

Domande Orale Degano

Velocemente le impressioni di questa giornata di orali per coloro che verranno:

- I compitini servono a voi, non a Degano
- Lo scritto che fa è pro forma
- Sono andato nel pallone sulla prima definizione, mi ha messo assolutamente subito a mio agio
- In genere ha chiesto un esercizio o due che richiedesse ragionamento, poi o definizioni o teoremi
- E' magnanimo con i voti ( "sarà che il vino è più cattivo quest'anno ma mi sembrate più bravi del solito")
- Continua a criticare i voti del Vanneschi ("chi le ha dato questo voto??")

Consiglio: Studiate e capite i Teoremi, ci tiene molto, e con quelli fate il resto.

Per il resto, le domande che mi ha posto sono più o meno le seguenti:

- Def di fun. appropriata
- Teo di Gerarchia
- Teo Lacuna di Borodin
- Teo Accelerazione di Blum
- Teo Accelerazione Lineare ( a grandi linee, i passi cruciali)
- Teo Forma Normale
- Myhill-Nerode (accennato)
- Teo Automa Minimo
- Teo Ricorsione (solo accennato)
- Un esercizio che non sto a riportare perché è stato abbastanza confuso. Si trattava di usare il teorema di ricorsione e sue conseguenze sul numero di punti fissi. Quindi sappiateli
- Dire se { x | FIx = FIx+1 } (con x e x+1 indici) è Ricorsivo. Risposta : no.

In bocca al lupo!
Domande orale preappello 7/06/19 (Ero il primo, dunque riporto solo le mie)

f,d funzioni calcolabili. f composto d è calcolabile?
I = {x | Imm(f) ^ Dom(g)} con ^ = intersezione
Definizione e dimostrazione teorema di enumerazione
Dire che classe è Co-L o, per meglio dire, in che relazione è con le altre classi di complessità e la dimostrazione di ciò
Dimostrazione NP-Completezza di Circuit-Sat

Ovviamente per ogni punto chiedeva non solo la risposta, ma anche una dimostrazione.
Ho notato che, in generale, le domande che fa non sono difficili. Lo diventano con l'ansia da prestazione, ma ti da il tempo e il modo di riflettere.
Gli orali sono abbastanza tranquilli, solitamente chiede un esercizio e un paio di teoremi con dimostrazione se rispondi bene finisce subito. Ti aiuta molto nel ragionamento e direi che l'esame non è stato come viene descritto abitualmente.

DOMANDE:
- Come può essere l'unione finita e infinita di insiemi ricorsivi?
- Teorema di forma normale con dimostrazione
- Teorema e dimostrazione LOGSPACE incluso in P
Domande che ha fatto a me:
- Dimostrare che INF si riduce a TOT (mi ha dato una mano con la riduzione)
- Enunciare e dimostrare (intuitivamente, come l'ha spiegato lui) il teorema del parametro
- Mostrare i passaggi chiave della dimostrazione di P-completezza di CircuitValue

Altre domande che ho sentito dagli orali precedenti e che mi ricordo:
- Dimostrare che [math] non è un i.i.r.f.
- Dire se l'insieme costruito nel padding lemma è un i.i.r.f.
- Dimostrare il teorema di enumerazione
- Dimostrare il teorema del punto fisso
- Dimostrare il teorema di forma normale