Domande Orale Degano

Nymeria
Messaggi: 1
Iscritto il: 12/07/2019, 17:39

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.
Avatar utente
elia.luca
Messaggi: 3
Iscritto il: 21/01/2019, 13:25

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.
Avatar utente
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.
Monica
Messaggi: 1
Iscritto il: 05/04/2020, 15:00

  • 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
jiderba
Messaggi: 1
Iscritto il: 24/03/2019, 23:36

- 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
gotoxy
Messaggi: 1
Iscritto il: 27/05/2020, 10:00

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.
Ultima modifica di gotoxy il 31/05/2020, 12:24, modificato 1 volta in totale.
alessandro.puccia
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.
alessandro.antonelli
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.
alessandro.antonelli
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
Avatar utente
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)
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”