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

Domande Orale Degano

Orali gennaio 2015

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!

Orale gennaio 2015
- dati due linguaggi regolari, dimostrare che l'unione è regolare (banale con le grammatiche)
- cosa possiamo dire invece per l'unione infinita? (non vale, va dimostrato)
- dimostrare che LOGSPACE incluso in P
- cosa succede se coNP = NP ? (in particolare cosa possiamo dire di P=NP)
- sappiamo dal padding lemma che esiste una funzione che restituisce indici di macchine equivalenti. Ne può esistere una che li restituisce tutti?

Orale gennaio 2015
- Discutere l'esistenza di una f calcolabile totale tale che
dominio di phi_x = complemento di phi_f(x)

- Dimostrazione teorema del punto fisso
- Dimostrazione teorema di enumerazione
- Dimostrare che l'unione di due linguaggi regolari è regolare, costruendo l'automa
- Dimostrare che NP è incluso in EXP

Sinceramente visti i commenti di chi ci ha preceduto mi sarei aspettato più discussioni e meno dimostrazioni a memoria, il che mi ha un po' spiazzato per come mi ero preparato l'esame... Paradossalmente avrei fatto meglio semplicemente imparandomi quelle poche dimostrazioni che cercando di capire davvero la materia

Orale dicembre 2014
Queste sono le domande (meno qualcuna che non ho ascoltato bene) fatte a me e altri due ragazzi al preappello di dicembre2014. Niente scritto. Dei compitini quest'anno ha fatto solo il primo ,che non ha considerato (io manco l'avevo fatto).

1.L'unione finita di insiemi ricorsivi è ricorsiva?
2.L'unione infinita di insiemi ricorsivi è ricorsiva?
3.L'unione infinita di insiemi ricorsivi può essere non ricorsivamente enumerabile?
4.Dimostrare che TOT è non ricorsivamente enumerabile riducendo ¬K a TOT.
5.L'intersezione di linguaggi regolari è regolare? Come si dimostra?
6.Qual'è la differenza tra il teorema di accelerazione lineare e quello di accelerazione di Blum? 7.Definizione di funzione appropriata e come mai è importante che sia monotona crescente e non strettamente crescente

8. ? (Esercizio la cui soluzione richiamava il teorema del parametro)
9.Dimostrare il teorema del parametro.
10.Dimostrare che la gerarchia di Chomsky è una gerarchia "propria" (ha le inclusioni strette)
11.Perchè il linguaggio [math] non è libero? Dimostrare il pumping lemma per linguaggi liberi.
12.Dimostrare che le funzioni in LOGSPACE classificano P ed NP.

13 ?
14.Dimostrare che [math] (che ha spiegato essere il problema di decidere se in un grafo esiste una cricca di esattamente N/2 nodi dove N è il numero (pari) dei nodi del grafo).
15.Discutere la decidibilità di [math] e [math] ( o na cosa simile )
16.Enunciato e dimostrazione del teorema di enumerazione e come mai diciamo che [math] ha due soli parametri (i,x) e non tre parametri (i,x,y).
17.Dimostrare che dato un ASFND esiste un ASFD equivalente in maniera formale ( o meglio: impostare formalmente cosa si deve andare a dimostrare e dare un'idea di come si potrebbe fare)

Orale ??
Il mezzacricca è un evergreen di Degano. :D

Aggiungo anche una domanda che fece a me: dimostrare che LOGSPACE è chiuso per composizione.
Questo fatto, sepolto nelle dispense all'interno della dimostrazione del Teorema 3.5.2 e bollato come "banale", è invece abbastanza delicato. La dimostrazione che ne dà la dispensa è solo accennata, ma è sostanzialmente giusta. Certo però che meriterebbe più risalto.

Orale febbraio 2015
Venivo dai compitini e da un mezzo orale terminato "male" perchè mi sono bloccato.
Innanzitutto il prof si è reso conto della situazione, al primo orale, e mi ha offerto di tornare un'altra volta, senza bocciarmi.
In ogni caso è in grado di metterti a tuo agio e, a me, ha tenuto buone le domande alle quali avevo risposto correttamente la prima volta (che però non ricordo :( ).
Oggi mi ha quindi chiesto:

* Dimostrare che [math]
* Mostrare che una MdT non deterministica può essere simulata da una MdT deterministica con perdita in tempo esponenziale
* Classificare il linguaggio [math]
* Dimostrare che [math] non è un i.i.r.f.


Orale dicembre 2015
1. L'insieme delle funzioni estendibili a totali {EXT} è ricorsivo, è ricorsivamente enumerabile?
2. L'ASFD minimo che riconosce un linguaggio regolare è unico?
3. L'unione di due linguaggi regolari è regolare? l'unione infinita di linguaggi regolari?
4. NP e CO-NP possono essere uguali? Come verrebbe influenzata questa gerarchia se questo accadesse?

Non ricordo altre domande, nel caso le aggiungo, comunque queste sono state abbastanza lunghe poichè ho dovuto dimostrare ogni singolo punto, anche se alcuni solo intuitivamente

Orale febbraio 2016
1. (non avevo fatto lo scritto) dimostrare che INF (l'insieme degli algoritmi con dominio infinito) si riduce a COST (l'insieme degli algoritmi che ritornano una costante) [un modo è questo:
dato un programma A, costruisci un programma B che, su input n, simula A a coda di rondine su ogni input, e termina restituendo 0 la n-esima volta che A termina su qualche input. Allora B calcola la costante 0 se e solo se A ha dominio infinito (altrimenti B non termina su qualche input).]

2. il linguaggio nel quale la b compare solo in posizioni dispari è regolare? E il linguaggio composto da a^(3n) con n>0 lo è?
3. la concatenazione dei due linguaggi di cui sopra è regolare? E in generale la concatenazione di due linguaggi regolari? Come si dimostra con le grammatiche? (occhio c'è un trabocchetto)
4. Enunciazione e dimostrazione del teorema di forma normale
5. Dimostrare che P = co-P. Costruire la funzione che manda elementi di P in elementi di co-P mediante una Macchina di Turing.

Orale gennaio 2017
- Dire se l'insieme [math] è non-R.E. e dimostrarlo
- Enunciare il teorema di enumerazione e dimostrarlo ( e quindi enunciare anche il teorema di formale normale )
- Dimostrare che [math]
- Trovare un algoritmo e la relativà complessità che risolve la soddisfacibilità di una espressione in forma normale disgiuntiva ( quindi [math] )
- Che relazione ha il precedente problema con SAT ?

Risposte per i curiosi:
- Si e per dimostrarlo si riduce a [math] con la funzione:

[math]

- vedi dispense
- vedi dispense ( numero di passi massimo con [math] celle )
- Vediamo che per essere soddisfacibile basta che una delle clausole sia soddisfacibile, visto che ogni clausola è composta da solo AND tra letterali è soddisfacibile solo se al suo interno non c'è un "ff" oppure contemporaneamente un letterale e la sua negazione. L'algoritmo scorre da sinistra verso destra le clausole e controlla quanto detto prima, ovviamente è lineare nell'input e quindi polinomiale.
- Possiamo controllare una espressione in forma normale disgiuntiva in tempo polinomiale, mentre SAT controlla una espressione in forma normale congiuntiva in tempo polinomiale non-deterministico. Se si trasforma una espressione in forma disgiuntiva in una congiuntiva il numero delle clausola cresce esponenzialmente.

Per il resto orale molto tranquillo, ti lascia il tempo di ragionare e ti aiuta se sei in difficoltà, conta molto la forma con la quale si espongono i teoremi (quantificatori, premesse ecc..).


Orale gennaio 2017
- dimostrare che con le funzioni u-ricorsive si possono calcolare i cicli for
[ risposta: Il Corollario 1.9.4 è una risposta indiretta.
In realtà non serve nemmeno l'operatore di minimizzazione, ma bastano le funzioni ricorsive primitive per calcolare i cicli FOR. La costruzione si fa a colpi di ricorsione primitiva, similmente all'Esempio 1.6.2. ]
- dimostrare che Sat è np-completo
- com'è fatta la funzione di transizione della macchina non deterministica in Sat
- come funziona la MdT che dice se l'assegnamento di Sat è giusto o no
- insieme di indici che rispettano le funzioni
- tesi di Church-Turing
- dimostrare che FIN non è ricorsivamente enumerabile

Orale febbraio 2017
- dimostrare che [math] non è ricorsivo
- dimostrare che [math] è ricorsivamente enumerabile
- definizione di insieme ricorsivamente enumerabile
- lemma dopo la definizione
- dimostrare il lemma
- definizione di funzione appropriata
- teorema di Borodin

Orale aprile 2017
Domande orale appello straordinario Aprile 2017, senza scritto, programma di CC (quindi anche i linguaggi):

- trovare un insieme A contenuto in N , A completo per riduzioni secondo la classe delle funzioni calcolabili totali (rec) (la risposta e' che tanti sottoinsiemi di N sono completi, ma non N intero, non K (che e' contenuto in N) e non tutti i sottoinsiemi ricorsivamente enumerabili [n.d.r. Pare sia sbagliata])

- RE-completezza di K (e' sulle dispense)

- linguaggi liberi, pumping lemma per linguaggi liberi con dimostrazione che a^n b^n c^n non e' libero (con il pumping lemma per linguaggi liberi), dimostrare che i linguaggi liberi non sono chiusi per intersezione (fornendo un esempio che lo dimostri, l'esempio e' simile a quello da fornire per dimostrare che l'unione infinita di linguaggi regolari non e' detto che sia regolare, pero' da fare con a^n b^n c^n)

- dimostrare se 3-SAT e' completo per NP, dove 3-SAT e' il problema SAT in cui ogni congiunto e' composto esattamente da 3 elementi e da qui avendo problemi mi ha chiesto la riduzione da circuit-sat a sat.

Orale maggio 2017
- Data la funzione phi(x) dire se è calcolabile:

phi(x) = { k se phi_x = phi_k con x < k AND per ogni i,j . i < x,k AND phi_ j diverso da phi_i
3 altrimenti
}
Lo ha inventato sul momento, per cui preparatevi anche a questi tipi di esercizi "diversi" da quelli che avete sempre visto qua sul forum (di riduzioni varie).
Non so neanche io come ne sono uscito.. sono sincero :')
- Dimostrare che un insieme qualunque chiamato K3, è R-Completo. (e fare esempio)
- Teorema di enumerazione, dimostrazione intuitiva (spiegare cosa si intende con macchina universale, poche righe sotto la dimostrazione formale nelle dispense) e dimostrazione formale (quella delle dispense)
- La soddisfacibilità di un'espressione booleana in forma disgiuntiva quanto costa? (tempo polinomiale, a volte lineare) E di una in forma congiuntiva? (tempo esponenziale)
Il problema SAT com'è? (NP-Completo)
Quindi se esprimessimo SAT in forma disgiuntiva,avremmo trovato un modo per dire che SAT non è più NP, perchè verrebbe a costare tempo polinomiale, quindi apparterrebbe a P... E' vero o non è vero? (No perchè per passare da forma congiuntiva a disgiuntiva impiego tempo esponenziale)
- Dimostrare che SAT è NP-completo.

Orale ottobre 2017
Un po' di domande a caso da orali che ho visto:

- Dato un problema A, NP completo per riduzioni polinomiali o logaritmiche in spazio
· Trovare un problema che non si riduce ad A
· Trovare un problema a cui A non si riduce
- Teorema di gerarchia
- Teorema di enumerazione
- Esempi di insiemi non ricorsivamente enumerabili
- Definire l'insieme degli indici delle funzioni estendibili, e dimostrare non sia ricorsivo
- Teorema di Rice (dimostrazione)
- Funzione non estendibile
- Teorema di accelerazione lineare e teorema di accelerazione di Blum
- Definizione di funzione appropriata
- Dati gli insiemi I_n: {x tale che x è maggiore di n e minore di 2n e phi_x = phi_n}
- Sono ricorsivi? Ricorsivamente enumerabili?
- La loro unione è ricorsiva? Ricorsivamente enumerabile?
- Teorema di enumerazione (di nuovo, lo chiede spesso)
- Teorema di forma normale
- Legami tra vincoli di tempo e vincoli di spazio, dimostrazione logspace <= P
- Definizione di insieme di indici che rispettano funzioni
- co-NP (insieme dei problemi il cui complemento è in P) è uguale a P? Dimostrarlo
- co-NP è uguale a NP? Se lo fosse si potrebbe dire qualcosa su P = NP?
- Dimostrare che K non è un insieme di indici che rispettano delle funzioni (Credo che la dimostrazione che preferisce parte dal definire una funzione che vale 1 sul proprio indice e non sia definita in nessun altro punto, e poi in qualche modo usare il teorema del parametro e del punto fisso per dimostrare che è calcolabile)
- Enunciare e dimostrare il teorema del punto fisso (NB, per l'ultimo passaggio della dimostrazione nelle dispense è importante dire che la funzione usata grazie al teorema del parametro è iniettiva)

Orale Dicembre 2017
Dimostrare che K < FIN
Dimostrare K< INF
Teorema di Rice + dimostrazione
dimostrazione che CValue è P-Completo
Teorema di ricorsione + dimostrazione
Teorema accelerazione lineare + dimostrazione
dimostrare LOGSPACE < P

Orale Febbraio 2018
Nota: stamani c'era lo scritto e la candidata non aveva visto il testo
Esercizio 1 compito: lui la lascia parlare e poi la aiuta. Lei si infogna sulla direzione dell'implicazione e lui le chiede di scrivere una funzione parziale. Alla fine ce la fa arrivare.
Esercizio 2: non sa dire un modo alternativo per la soddisfacibilità di un problema in forma normale disgiuntiva che non sia polinomiale. Alla fine la fa arrivare alla soluzione lineare. Domanda: come si dimostra che SAT disgiuntivo è np? Ce la fa arrivare (soluzione: con uno spazio esponenziale).
Domanda di teoria: enuncia e dimostra il teorema di enumerazione. Lo fa bene
Domanda di teoria: dimostra l'inclusione logspace C ptime. Lo fa bene.

Voto 23, ma non so da quanto partisse
Compito ECC 2018.jpg
Compito ECC 2018.jpg (98.02 KiB) Visto 307 volte
[n.d.r. non so se le cose scritte a penna sono giuste]

Orale aprile 2018
- Dimostrazione che Circuit-SAT è NP-completo
- Svolgimento di un esercizio proposto da lui ( non ci sono riuscito molto bene, Degano mi ha guidato un po' )
- In che relazione sono P e co-P
- Enunciato e dimostrazione del Teorema di Ricorsione

Orale luglio 2018
- Data una funzione f calcolabile totale e strettamente crescente, l'insieme A = Imm(f) è ricorsivo? E' r.e.? (risposta: E' r.e. e anche ricorsivo, per var vedere che è ricorsivo si doveva far vedere che se ho una x e voglio vedere se sta in A o no posso calcolare la f(0) e le successive fino a che non trovo un valore che è maggiore della x che cerco, in quel caso x non sta in A)
- Definire una f calcolabile totale e strettamente crescente tale che A = Imm(f)
- Teorema di enumerazione e dimostrazione
- Dimostrare che [math]

Altre domande che ha fatto:

- Dimostrare che k non è vuoto
- Dimostrare che k non è un i.i.r.f.
- Se nel teorema di Rice metto che la f deve essere anche strettamente crescente cambia qualcosa
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
Partivo da uno scritto dove nei due esercizi ha dato 2/3 ad entrambi, complessivamente valutato come "Buono". Le parti tra parentesi quadre sono suggerimenti per costruire le risposte.

L'orale inizia con il professore che riguarda lo scritto, ma fondamentalmente non si è ricollegato molto allo stesso, né in termini di cose corrette o cose sbagliate.

Inizialmente mi chiede di trovare le proprietà del seguente insieme: I = { x | ∃! y . φ_x (y) = 0 } , ovvero delle funzioni che hanno un unico punto dove tale funzione è 0. La domanda iniziale era generale, ha lasciato intendere che ero libero di dimostrare quel che volevo e mi soffermo sul fatto che fosse un I.I.R.F.
[ Su suo suggerimento, ho disegnato un'ipotetica funzione dell'insieme, in particolare una che f(0) = 0, f(n+1) = 1, poi un'altra f(0) = 1, f(1) = 0, f(n+1) = 1, creando quindi delle funzioni che da un punto in poi fossero costanti per semplicità. Infine una funzione g(0) = 0 e g(n+1) che non converge: quindi troviamo che le condizioni per I.I.R.F. sono soddisfatte ]

Dopo di ciò, ci ricolleghiamo al teorema di Rice di cui do la definizione del teorema e la dimostrazione, che usa una proprietà per dimostrare i casi non banali (K si riduce ad A o ad A-segnato), di cui mi ha fatto a sua volta fare la dimostrazione.

Infine ha ripreso il secondo esercizio del compito (di cui non posseggo una copia attualmente) e mi ha richiesto se, sapendo che p ∈ P si riduce effettivamente secondo LOGSPACE a Q (di default dal testo dell'esercizio), aggiungendoci che p si riduceva effettivamente anche a Q-segnato, cosa cambiava per Q.
[ Q è almeno P, come prima ]

Il professore è stato veramente cordiale e disponibile, mi ha aiutato ogni volta ne avessi bisogno e mi ha concesso tutto il tempo di cui necessitavo.
1. Discutere le proprietà dell'insieme I = { x | ∃y . φ_x (y) = φ_x (x) }.
2. Dimostrare il teorema "I è ricorsivamente enumerabile se e solo se è vuoto oppure è l'immagine di una funzione calcolabile totale".
3. Dimostrare che CIRCUIT-SAT è NP-completo.

Risposta alla 1:
I è un insieme ricorsivo. Infatti ponendo y = x, si ottiene l'insieme { x | φ_x (x) = φ_x (x) } = N che è ricorsivo.
Definito l'insieme A = { i φ_i φ_i+1} mi ha fatto discutere sulle proprietà di questo insieme ( NON È UN INSIEME DI INDICI CHE CALCOLANO FUNZIONI E NON È RICORSIVO)
Dimostrare teorema del punto fisso collegato all'esercizio precedente; cos'è una funzione appropriata e a cosa servono. Cosa succede se non prendo funzioni appropriate ( teorema di accelerazione lineare di Blum che a dirla tutta mi ha detto lineare non è)
- Definizione di i.i.r.f
- Dire (e dimostrare) se una classe che contiene tutti gli i.i.r.f è un' algebra booleana (cioè se negando o facendo la congiunzione su elementi di tale classe il risultato appartiene ancora ad essa)
- dimostrare che K si riduce a TOT-SEGNATO
- dimostrare che NP è incluso-stretto in EXP. Su questa domanda è andato molto nel dettaglio chiedendo come potrei passare da un ipotetico albero delle scelte di una MdT non-deterministica non bilanciato ad uno bilanciato (per porsi nel caso della dimostrazione per cui NTIME(f(n)) è incluso-stretto a TIME(c^(f(n))) ), e come implementerei tale trasformazione con una mdt deterministica impiegando tempo polinomiale.

Il consiglio che posso dare è quello di scrivere e provare a dare soluzione anche sbagliate piuttosto che stare in silenzio (se rimanete zitti non fa molto per aiutarvi; viceversa può indirizzarvi un minimo).
Orale dell'11 luglio, mi presento con i compitini (gli viene data solo un'occhiata veloce).

Quasi tutti gli orali seguono lo schema di un esercizio e due teoremi.

Il mio:
- Dato l'insieme A = { x | dom(phi x) = {3} }, dire quali sono le sue proprietà
- Enunciato e dimostrazione del teorema di forma normale
- Enunciato e dimostrazione intuitiva del teorema della riduzione del numero di nastri

Il professore è molto tranquillo e dà tutto il tempo che serve per pensare.
Orale del 11/07/2019

è partito chiedendomi di "tratteggiare" una funzione che data una φ ricorsiva primitiva mi generava un programma for
  • λx.0 è l'azzeramento della variabile
    λx.x+1 assegna alla variabile x il suo successore
    λx1....xn.xi 1<=i<=n è la selezione di una variabile xi
    h in n+1 var e g1...gn in m var h(g1(x1..xm)...gn(x1..xm)) è il ";"
    h in n+1 var g in n-1 var allora f in n var = { f(0,x2..xn) = g(x2..xn); f(x1 + 1, x2..xn) = h(x1, f(x1..xn), x2..xn) è il costrutto for. su questo punto ci abbiamo chiaccherato un poco.
teorema del parametro
  • quella che descrive è una procedura effettiva, ha provato a fregarmi chiedendomi come fossi sicuro che la ricerca della MdT terminasse (codifica => termina)
se NP = co-NP cosa possiamo dire su P = NP?
  • co-NP={I | T ∈ NP}, non cambia nulla.
A grandi linee i passi fondamentali di CircuitSAT è NP-Completo
Come il blocco T(i,j) dipende solo dai 3 sopra?

in bocca al lupo.