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

Domande Orale Degano

Mi sono presentata con i compitini a cui ha dato solo uno sguardo veloce.

- Descrivere le proprietà di A = { i | φ_i = φ_2i }
- A è un i.i.r.f.? No
- Come trovare un i che dimostri che l'insieme non è vuoto (serve il teorema di ricorsione)
- Enunciato e dimostrazione del teorema di ricorsione
- Enunciato e dimostrazione intuitiva del teorema di accelerazione

L'importante è provare a iniziare a scrivere qualcosa, nel caso vi blocchiate (o sbagliate a scrivere qualcosa) vi dà dei suggerimenti per arrivare alla soluzione. Un'altra cosa importante è non dare l'idea di aver imparato le dimostrazioni dei teoremi a memoria.
Mi sono presentato con i compitini all'appello di luglio 2019, rimbalzato dopo 40 minuti di orale. Mi ha chiesto:

- Dato I = { x | #( dom( φ_x )) = 1 } dire se R o RE. ( È co-RE )
- Enunciare e dimostrare il teorema 1.10.4 (pre-Rice).
- Enunciare e dimostrare (in dettaglio) il teorema 3.5.2 ( riduzioni in LOGSPACE classificano P e NP ).

Ripresentato a settembre con i compitini, orale durato 4 minuti (verbalizzato). Mi ha chiesto:

- Enunciare e dimostrare il teorema di ricorsione (Kleene 2) 1.9.14
- Mi ha chiesto come farei a dimostrare che un MdT non deterministica può calcolare gli stessi problemi di una macchina deterministica e vice-versa. ( Enunciato del teorema 3.3.6)

NOTA: consiglio a chiunque di andare a ricevimento e di chiarivi ogni possibile dubbio (anche banale), apprezza il vostro impegno e interesse in materia.
- dimostrare che [math] è non ricorsivo
- [math] è un [math]? (risposta: si)
- dimostrazione del Teorema di Rice
- [math] come ci si arriva? quindi dimostrare il Teorema 3.3.6.
  • Dimostrazione Circuit-SAT NP-completo e cosa cambia rispetto alla dimostrazione Circuit-Value P-completo;
  • Data Mdt non det. con grado di non determinismo N, come trasformarla in una Mdt non det. con grado di non determinismo 2;
  • In quali casi A si riduce ad A-segnato (più esempi)
  • Teorema di Forma Normale
- proprietà dell'insieme A_n = { i<n | phi_i è totale } è un iirf? descriverne le proprietà (r,re,non-re)
- proprietà dell'insieme infinito rappresentato dall'unione di A_n con n=1,2,3...N è un iirf?
- Definizione di iirf e Lemma (pre-Rice) con dimostrazione

- Dimostrazione completezza di Circuit Value
- Teorema di accelerazione lineare (con collegamenti al teorema di compressione lineare) e differenze rispetto al teorema di accelerazione di blum
- Definizione di funzione di misura appropriata
1) dato A = { i | 3 \in(dom(phi_i))} ragionare sull'insieme (è ricorsivamente enumerabile?)
2) dimostrare che K è RE-completo per ≤rec
3) dimostrare che le funzioni calcolabili totali classificano R ed RE
4) supponiamo che NP = co-NP, cosa possiamo dire su P è incluso in NP? (in pratica voleva fregarmi facendomi dire che P = NP in questo caso, e ci è riuscito, perché in realtà non si può dire nulla)

Orale durato una trentina di minuti, Degano molto tranquillo, alla fine mi ha messo 27.
1) Proprietà dell'insieme { x < f(42) | φ_x(f(42)) = φ_f(42)(x) } con f calcolabile totale.
2) Enunciato e dimostrazione del teorema di ricorsione.
3) Dimostrare che LOGSPACE è chiuso per composizione.
L'esame a distanza è solo orale su Microsoft Teams e dura massimo 30 minuti (meno se si risponde senza esitazioni). La data pubblicata su esami.unipi.it è la data di inizio degli orali, che proseguono per più giorni fino a esaurimento candidati. Per scrivere la maggior parte degli studenti ha usato un foglio da inquadrare con la webcam dopo aver scritto, oppure la chat di Teams; alcuni (pochi) hanno usato la condivisione dello schermo o la lavagna integrata in Teams. Alla fine dell'orale Degano si disconnette brevemente per decidere il voto.

Domande del 25 maggio 2020:
(potrebbero mancare delle domande o esserci errori in come le ho trascritte)

Codice: Seleziona tutto

Esiste una funzione calcolabile totale f tale che per ogni indice i la macchina di indice phi con f con i è totale?
 
Fare un esempio di funzione il cui indice sta dentro TOT
 
Le funzioni costanti sono calcolabili? Sono anche totali?
 
Enunciare e dimostrare il teorema di enumerazione
 
Dimostrare che LOGSPACE sia incluso in P
 
Che cos'è la classe di complessità SPACE?
 
-----------------
 
Esiste una funzione calcolabile totale f che trasforma indici in indici tale che per ogni i indice l'immagine di phi f con i è un indice ricorsivo?
esiste f c.t. tale che per ogni i si ha che imm(\phi_f(i)) e` ricorsivo
 
L'insieme delle funzioni la cui immagine è l'insieme ricorsivo, non è ricorsivo?
{i | imm(\phi_i) e` ricorsivo) non e` ricorsivo?
Dimostrarlo
 
A insieme di indici che rapp funzioni. Se A diverso da vuoto oppure A diverso da N, allora HK <= rec A vel K <= rec A segnato
 
Supponiamo che sia data la riduzione ... tale che CIRCUIT-VALUE è NP-COMPLETO.
Me la sa generalizzare dimostrando che CIRCUIT-SAT è NP-completo?
 
-----------------------
 
Dimostrare che l'insieme degli indici generati dal padding lemma non è un insieme di indici che rappresenta funzioni
 
Rispondere all'ultima domanda dell'orale precedente
 
-----------------------
 
L'unione di due insiemi ricorsivi, è un insieme ricorsivo? Dimostrarlo
 
f calcolabile totale f(i) = A_i
i \in I con I ricorsivo
A_i sottoinsieme di N ricorsivo
Unione per i \in I degli f(i) è sempre ricorsivo? Quando lo è?
 
Dimostrare che se un problema è risolto in tempo non deterministico F, allora è risolto in tempo deterministico 2^F, 3^F, ...
 
-----------
 
Dimostrare che l'unione infinita di insiemi ricorsivi non è ricorsiva
U = Unione per i \in I degli f(i) e` ricorsivo?
f calcolabile totale f(i) = A_i
 
Enunciare e dimostrare il teorema del parametro
 
Teorema di accelerazione lineare
 
--------------
 
Questione dell'insieme risultante dall'unione di infiniti insiemi ricorsivi
 
Enunciare e dimostrare il teorema di ricorsione
 
Definizione di funzione appropriata. Perché abbiamo bisogno di avere funzioni appropriate?
Un orale del 29 maggio 2020:
- def i.i.r.f.
- teo+dim Sia A i.i.r.f. diverso da insieme vuoto e dai numeri naturali allora K <= A oppure K<= A segnato
- K è i.i.r.f. ?
- Dim Circuit-SAT è NP-completo