Informateci

- dimostrare che [math]EXT è non ricorsivo
- [math]EXT è un [math]I.I.R.F.? (risposta: si)
- dimostrazione del Teorema di Rice
- [math]NP \subseteq EXP come ci si arriva? quindi dimostrare il Teorema 3.3.6.

Testo dell'esercizio: Si determini una funzione <math><mi>f</mi></math> calcolabile totale tale che <math> <mrow> <mi>I</mi> <mo>=</mo> <mrow> <mo form="prefix">{</mo> <mi>i</mi> <mo>|</mo> <msub> <mi>&phi;</mi> <mi>i</mi> </msub> <mo>=</mo> <msub> <mi>&phi;</mi> <mrow> <mi>f</mi>...

Sto provando a fare l'esercizio presente a pagina 2 : dimostrare che I = \{\,x \mid \varphi_x(x) = \varphi_x(x+30) \,\} non è un I.I.R.F. Per definizione, I \mbox{ è un I.I.R.F. se e solo se } \forall_{x,y}\mbox{. se } x\in I \mbox{ e } \varphi_x=\varphi_y \mbox{ allora } y\in I L'idea a questo punt...

Joker Sappiamo che R U R = R perchè entrambi si possono decidere in tempo finito. Cosa succede però con l'unione infinita di insiemi ricorsivi? MindFlyer Può essere sia ricorsiva che non ricorsiva. Esempio: l'unione di {n} per ogni n naturale è ovviamente tutto \mathbb N , e quindi ricorsivo. D'alt...

Joker Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive: Poichè CIRCUIT SAT \leqslant SAT, ci basta dimostrare che CIRCUIT SAT è NP-completo, Perchè ci basta dimostrare questo? Io sapevo che un problema A, completo per una certa classe S, non dice nulla su un altro problema B s...

Probabilmente ti riferisci al compitino della Paganelli, sul gruppo telegram qualcuno ha messo il testo, contattami su telegram @Hungerys

Questo è il post originale https://old.informateci.it/discussion/9 ... -operativa

Venduto.

Dato che negli ultimi anni è cambiato qualcosa sugli argomenti affrontati nello scritto e nell'orale ho creato questo thread a parte. Prima del 2016 c'erano Bevilacqua-Del Corso-Menchi, quindi quelle domande non sono state riportate. Domande di Giugno/Luglio 2016: - Dimostrazione teorema del punto f...

EDIT: VENDUTO Vendo libro usato Reti di calcolatori. Un approccio top-down 1 mar 2013 di Behrouz A. Forouzan (Autore), Firoeuz Mosharraf (Autore), G. D'Angelo (Traduttore), G. Maselli (Traduttore) Prezzo: 25 euro Per altre informazioni contattatemi su Telegram (Username: Hungerys) o qui sul thread.