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.
Domande Orale Degano
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.
- 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.
- andrea.tosti
- Messaggi: 15
- Iscritto il: 02/10/2018, 9:20
- 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.
- [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
- 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.
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.
Ultima modifica di gotoxy il 31/05/2020, 12:24, modificato 1 volta in totale.
-
- Messaggi: 1
- Iscritto il: 27/05/2020, 10: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.
2) Enunciato e dimostrazione del teorema di ricorsione.
3) Dimostrare che LOGSPACE è chiuso per composizione.
-
- Messaggi: 21
- Iscritto il: 02/10/2018, 15:25
L'esame a distanza è solo orale su Microsoft Teams e dura massimo 30 minuti (meno se si risponde senza esitazioni).
Ultima modifica di alessandro.antonelli il 12/09/2021, 10:32, modificato 1 volta in totale.
-
- Messaggi: 21
- Iscritto il: 02/10/2018, 15:25
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
- alessandrotindiglia
- Messaggi: 1
- Iscritto il: 15/06/2020, 12:47
Teorema di Rice (pag 70)
P incluso ed è proprio in EXP: corollario 3.4.3 (pag 163)
Teorema forma Normale (pag 46)
NP incluso EXP Teorema 3.3.6 (pag 156) + corollario 3.4.3 (pag 163)
Teorema 3.3.6(pag 156)
Teorema di Enumerazione (pag 47)
Teorema di Accelerazione lineare (pag 141)
P incluso ed è proprio in EXP: corollario 3.4.3 (pag 163)
Teorema forma Normale (pag 46)
NP incluso EXP Teorema 3.3.6 (pag 156) + corollario 3.4.3 (pag 163)
Teorema 3.3.6(pag 156)
Teorema di Enumerazione (pag 47)
Teorema di Accelerazione lineare (pag 141)