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

Domande Orale Degano

-Riduzione K<= CONST
-Riduzione K segnato <= CONST( mi ha aiutato a definire quando x _in K segnato nella psi)
-Teorema di enumerazione
-Dimostrare che NP incluso in P(Teorema 3.3.6)
-Definizione di NPSACE
- th. del parametro
- EXT è i.i.r.f? Dimostrare che è non-RE
- dimostrare che CIRCUIT-VALUE è P-completo

altre domande che ha fatto in altri orali sono:
- funzioni appropriate
- quando un insieme è re
- dimostrare che se I è r allora è re
- esiste un I re che non è r? Si, K.
- dimostrare che K non è r
- halting problem
- dimostrare che esiste un I che è non-RE
- l'unione di I re è re? No, ad esempio l'insieme di indici tc l'unione da K segnato
- th. di enumerazione
- dimostrare che CIRCUIT-SAT è NP-COMPLETO
- th. del parametro
- dimostrare che LOGSPACE è contenuto in P
- th di Kleene II + dimostrazione
- NTIME(f(n))
- th della forma normale
- th. 3.3.6
- th di accelerazione lineare
- Perché la dimostrazione per diagonalizzazione non funziona per le funzioni parziali? Perché non potrei estendere le definizioni includendo TOT o EXT?
- Dimostrazione che EXT non è ricorsivo.
- Dimostrazione che se A è un iirf diverso da vuoto e N, allora K si riduce ad A oppure K si riduce ad A segnato.
- Dimostrazione di LOGSPACE incluso in P.
- Dimostrare se esiste f calcolabile totale t.c. per ogni x, phi_x(x) converge sse phi_f(x)(f(x)) diverge (f non esiste poichè x sta in K, f(x) sta in K segnato, e non si può ridurre K a K segnato tramite rec e viceversa)
- Cosa possiamo dire su P = co-P
- Teorema di forma normale e dimostrazione
- Dimostrare che le riduzioni in logspace classificano P e NP
Appello Luglio 2020 (solo orale, via Teams)

Primo orale:
- Dato K, esistono sottoinsiemi di K che sono ricorsivi e infiniti?
- Ce ne sono invece di finiti?
- K è RE-Completo (enunciato e dimostrazione)
- Teorema di accelerazione lineare (enunciato e dimostrazione)
- Cosa cambia rispetto al teorema di accelerazione di Blum? Come deve essere la f?
- Teorema di accelerazione di Blum (enunciato)

Secondo orale:
- Presentare un insieme infinito ricorsivo sottoinsieme di K segnato

Terzo orale:
- Quant'è la cardinalità di K segnato? (#N, poichè prendo l'indice della funzione ovunque indefinita e uso il padding lemma su quell'indice per crearne infinite)
- Ax (l'insieme degli indici generato dal padding lemma) è un i.i.r.f.?
- Perchè TOT non è RE? (perchè K si riduce secondo rec a TOT e K si riduce secondo rec a TOT segnato)
- K si riduce secondo rec a TOT segnato (dimostrazione)

Quarto orale:
- Presentare un insieme completo (con riduzioni calcolabili totali) per R. TOT rispetta questa condizione?
- Completezza di un insieme secondo una relazione di riduzioni (definizione)
- Teorema di enumerazione (enunciato e dimostrazione)
- Quando una f è appropriata?
- Perchè prendiamo f appropriate? Non basta che siano solo monotòne?

Quinto orale:
- L'insieme {i | esiste n tale che phi_i(n) = phi_n(i)} è ricorsivo?
- Famiglia di riduzioni che classifica due insiemi di problemi (definizione)
- Le riduzioni rec soddisfano le proprietà? (dimostrazione)
- NP contenuto in EXP (dimostrazione)

Sesto orale:
- L'insieme {x | esiste y tale che phi_x(y) converge in un n° di passi minore o uguale a quelli necessari a phi_y(x) per convergere} è ricorsivo? E' ricorsivamente enumerabile?
- Teorema di enumerazione (enunciato e dimostrazione)
- NP contenuto in EXP (dimostrazione)
- MdT non deterministica decide un problema I (definizione)
- Se NP = Co-NP cosa possiamo dire su P = NP?

Settimo orale:
- L'insieme {x | esiste y tale che phi_x(y) converge sse phi_x+2(y) converge} è ricorsivo?
- Teorema di Rice (enunciato)
- Teorema di pre-Rice (enunciato)
- Teorema di riduzione del numero di nastri (enunciato e dimostrazione)
ORALE 2020 LUGLIO
- esercizio: è decidibile se phi_i = phi_j ?
- teorema del parametro e dimostrazione
- teorema dell'accelerazione lineare e dimostrazione
- funzioni di misura
Ho esguito gli orali dal 9 all 11 settembre, queste le domande (potrebbero volermici più post) [Tra parentesi quadre ci sono alcuni procedimenti]

Perché le funzioni calcolabili non sono tutte le funzioni immaginabili? [Esistono fun non calcolabili - dimostrazione con procedimento di Cantor]
La MdT rappresenta una funzione?
Definizione di funzione calcolabile
Quando la MdT calcola qualcosa?
Quando una funzione è calcolabile? [Quando è T-Calcolabile – tesi di Church-Turing]
Quante macchine esistono che calcolano una funzione costante? [#N – padding lemma]

Quando due insiemi hanno la stessa cardinalità?
Quanti sono i numeri primi? [#N – si codificano i numeri primi con i naturali]
Perché si usa #N e perché i numeri pari sono #N?
Quando un insieme è ricorsivamente enumerabile?
Dato un insieme ricorsivamente enumerabile costruire un sottoinsieme infinito e ricorsivo [sul pdf degli esercizi]
Come si dimostra che un insieme è infinito?
Teorema di Enumerazione

Esiste una funzione calcolabile totale f che trasforma indici in indici?
Teorema del parametro (enunciato semplice s-1-1 e dimostrazione)

Esiste una funzione calcolabile totale f tale che per ogni indice i dominio(phi_f(i)) è l’insieme dei numeri pari?
Il dominio di questa funzione phi_f(i) è ricorsivo?
Definizione di insieme ricorsvio
Definizione di iirf

Esiste una funzione calcolabile totale f tale che per ogni indice i dominio(phi_f(i)) è l’insieme dei numeri pari?
Teorema del parametro (enunciato semplice s-1-1 e dimostrazione)
I problemi in P formano un’algebra booleana?

Dato l’insieme A {i | dom(phi_i) è ricorsivo} descrivere la natura dell insieme (Se è ricorsivo, ricorsivamente enumerabile, etc)
Teorema K<A con funzione ricorsivamente enumerabile
Insieme vuoto € NP?
Se I € NP allora I complementato € NP?
Se I,J € NP allora I intersecato J € NP?
Esiste un algoritmo che decide se un elemento € all’insieme vuoto?
Quale è la funzione caratteristca dell insieme vuoto?
Quando una funzione di misura è appropriata?

Dato K complementato è un iirf?
Dimostrare che l’insieme degli insiemi ricorsivamente enumerabili include la classe degli insiemi ricorsivi

Mostrare che gli insiemi che si costruiscono con il padding lemma non sono gli indici di tutte le funzioni
Dimostrare che un insieme è ricorsivamente enumerabile se e solo se è vuoto o immagine di una funzione calcolabile totale

Dimostrare che l’unione di insiemi ricorsivamente enumerabile è ricorsivamente enumerabile
Teorema di ricorsione
Dimostrare che CONST (insieme funzioni costanti) si riduce a INF (insieme funzioni con dominio infinito)
Dimostrare che Circuit Value è P-Completo [cioè si può ridurre qualsiasi problema € P a Circuit Value]

Dimostare che l’unione infinita di infiniti insiemi ricorsivi è ricorsiva
E se gli insiemi non fossero infiniti?
Dato un insieme ricorsivamente enumerabile ma non ricorsivo [K] mostrare che ha sottoinsiemi ricorsivi infiniti
Teorema di accelerazione lineare
La funzione di misura deve essere appropriata?

Dato un insieme che si riduce al suo complementare con una funzione calcolabile totale quali sono le sue proprietà?
Dato INF (insieme delle MdT con dominio infinito), è vero che questo insieme non è ricorsivo?
Sapendo che Circuit Value è P-Completo, come va modificato l’approccio per la dimostrazione di Circuit SAT NP-Completo? (Il professore chiede anche come ridurre l’albero da n-ario a binario)

Nella definizione dello schema di ricorsione generale c’è che la funzione ausiliaria deve valere zero e terminare. Perché?
Teorema di forma normale
Le riduzioni in tempo polinomiale classificano P ed NP?

Dato un insieme di coppie i,j esistono due numeri m,n tali che phi_i(n)=m e phi_j(n)=m? (cioè convergono allo stesso valore)?
L’insieme è ricorsivo?
Definizione di insieme ricorsivamente enumerabile (definizione alternativa)
Dimostrare le proprietà dell insieme ricorsivamente enumerabile

Dato un insieme ricorsivamente enumerabile A esiste una funzione calcolabile totale f tale che imm(phi_f(x)) è N se x € A e indefinito altrimenti?
Dimostrare che un iirf è ricorsivo se e solo se è vuoto oppure contiene tutti gli indici
Data una MdT a k nastri se la si riduce ad un nastro quale è la perdita in tempo e come la si modella? [Teorema di moltiplicazione dei nastri]

La dunzione ausiliaria mu dello schema di ricorsione richiede anche condizione di convergenza e la definizione alternativa richiede che la funzione sia ricorsiva primitiva. Dimostrare che tra le due enunciazioni non c’è differenza
Teorema del parametro
Discutere la relazione tra tempo e spazio negli algoritmi

Si possono scrivere programmi che non terminano utilizzando un linguaggio FOR? (Nota: il FOR deve rispettare la sintassi mostrata a lezione, non è ammesso il FOR(;;))
Dimostrare la terminazione del FOR [Dimostrazione per induzione]
Si possono esprimere tutte le funzioni totali o solo alcune?

Esiste un formalismo che esprime tutte le funzioni totali?
Delinare la dimostrazione dell’equivalenza tra il formalismo che esprime le funzioni primitive ricorsive e i programmi FOR, o viceversa
Dimostrare che la riduzione in REC classifica R ed RE
Definizione insieme ricorsivamente enumerabile e dimostrare che ogni insieme ricorsivo è anche ricorsivamente enumerabile
Rispetto alla dimostrazione di P-completezza di SAT cosa cambia nella dimostrazione della NP-completezza di Circuit SAT?
Dimostrazione della P-completezza di SAT

Data la forma di eguaglianza debole tra due funzioni che convergono sullo stesso risultato, questa eguaglianza è decidibile? Quale è un algoritmo intuitivo per deciderla?
E’vero che K è completo per RE? Dimostrazione I € RE si riduce a K
Dimostrazione NP-completezza di SAT

Dimostrare che non tutte le funzioni calcolabili parziali si possono estendere a totali
Quando un insieme di indici è un iirf?
Dimostrazione del lemma di riduzione
Quando una funzione si dice appropriata?

Dimostrare che se un iirf non è vuoto e non è N allora k si riduce ad A oppure ad A complementato
Data una espressione booleana in forma disgiuntiva come si verifica che la formula è soddisfacibile?

Dimostrare che le riduzioni in logspace classificano P e NP
Perché è opportuno usare funzioni di misura appropriate?
Dare un esempio di insieme tale che K si riduce ad A ed A complementato
Teorema di enumerazione

Dimostrare P incluso in EXP [conseguenza del teorema di gerarchia]
Quando una MdT non deterministica accetta un dato?
Teorema di ricorsione

Dato TOT (insieme degli indici delle funzioni calcolabili totali) e CONST (insieme degli indici funzioni calcolabili costanti) dimostrare che TOT si riduce a CONST
Teorema di forma normale

Dato un problema NP-completo quale è un problema che non si riduce ad esso in tempo polinomiale o logspace?
Dimostrazione LOGSPACE sottoinsieme di P

Dato un insieme ricorsivo, questo contiene un sottoinsieme ricorsivamente enumerabile?
Perché K non è ricorsivo?
In quali casi A si riduce ad A complementato?
Teorema di accelerazione lineare
La funzione di misura deve essere appropriata per questo problema?

Dati due insiemi ricorsivamente enumerabili e ne prendiamo una intersezione cosa può succedere?

L’intersezione di due insiemi ricorsivamente enumerabili è ricorsivamente enumerabile, e l’insieme vuoto è ricorsivamente enumerabile. Perché compongano un algebra di Boole devono essere chiusi per complemento (cioè il complemento deve essere ricorsivamente enumerabile). Questi due insiemi sono chiusi per complemento? (Cioè A complementato è ricorsivamente enumerabile se A è ricorsivamente enumerabile)
Come è l’intersezione tra un insieme ricorsivo e uno ricorsivamente enumerabile?
Teorema di enumerazione
Dimostrare che le riduzioni in tempo polinomiale classificano P ed NP

Esiste una funzione f calcolabile totale tale che per ogni funzione g calcolabile totale si ha imm(g)=complemento(imm(f composto g))?
Teorema del parametro
Padding Lemma
Perché Monotone Circuit Value è P-completo?
Dimostrazione P-completezza Circuit Value

Dato A ricorsivamente enumerabile quali caratteristiche ha f(A)?
Teorema di Ricorsione
Dato CO-P l’insieme dei problemi I tali che I complementato € P, che rapporto c’è tra P e CO-P?
Perché dobbiamo usare funzioni di misura appropriate?

Quale è il rapporto tra NP e CO-NP?
Teorema di gerarchia
Data una funzione calcolabile parziale f posso costruire una funzione calcolabile totale il cui dominio è immagine di f?

Padding Lemma
Quello che si ottiene dal Padding Lemma è un iirf?
Dato I che si riduce in LOGSPACE a I complementato quali sono le caratteristiche di I?
Dimostrare LOGSPACE incluso in P

Dato un insieme ricorsivo infinito A diverso da N costruire un insieme ricorsivamente enumerabile incluso in A non infinito e non ricorsivo
Alla domanda "Esiste una funzione calcolabile totale f tale che per ogni indice i dominio(phi_f(i)) è l’insieme dei numeri pari?"
Hanno risposto in questo modo (la foto è stata messa sul telegram del corso, la allego qui)
photo5965257804170245515.jpg
photo5965257804170245515.jpg (207.82 KiB) Visto 725 volte
Orale con Giulio Masetti (lui solo, non in coppia con il Degano) del 16 dicembre 2020:
IMG_20201221_175249_326.jpg
IMG_20201221_175249_326.jpg (108.21 KiB) Visto 129 volte
Ciao a tutti, ma ci sono entrambi (sia il Degano che Masetti) durante l'esame?? Posso contattare il Masetti per delle info? Avevo scritto una mail per delle info sul materiale al Degano tempo fa ma non rispose.