Informatica teorica: materiale utile

[mistergks]

Ciao a tutti!
Forse sono un po off topic ma sono argomenti che viaggiano insieme alla programmazione.
Qualcuno sa consigliarmi delle dispense o libro o materiale in qualsiasi formato PRECISO e SINTETICO su questi argomenti?:

* Ciò che si può risolvere e ciò che non si può risolvere (Calcolabilità ) Ciò che si può risolvere: a che costo? (Complessità )
* La tecnica della diagonalizzazione. Applicazione al Power Set dei numeri naturali.
* Introduzione ai linguaggi. Linguaggi e problemi di decisione.
* Indecidibilità del problema HELLO-WORLD e riducibilità tra problemi.
* Esercitazione sulle riduzioni tra problemi. Introduzione alla macchina di Turing.
* Esercitazione sulle macchine di Turing (es.: riconoscere i linguaggi ww^r e wcw)
* Macchine di Turing multitraccia e multinastro. Simulazione di una macchina multinastro con una mononastro e costi di esecuzione.
* Introduzione alle macchine di Turing non deterministiche.
* Esercitazione sulle macchine di Turing non deterministiche: data una coppia di stringhe, decidere se la prima è una sottostringa della seconda; colorabilità di un grafo.
* Linguaggi ricorsivamente enumerabili, linguaggi ricorsivi. Teoremi sul complemento dei linguaggi. Il linguaggio Ld ed il linguaggio Lu.
* Ancora sulla indecidibilità: il Teorema di Rice
* Valutazione dei costi di esecuzione in termini di tempo e di spazio. Una gerarchia di classi di complessità.
* Problemi Polinomiali e problemi NP.
* Concetto di riduzione polinomiale tra problemi. Problemi NP-ardui ed NP-completi.
* Esercitazione sulle riduzioni tra problemi.
* Il teorema di Cook.
* Altre classi di complessità. La classe co-NP. Problemi nell’intersezione tra NP e co-NP

[british]

come libro,

Mandrioli, Ghezzi
Informatica Teorica
ed. Città Studi

tosto ma completo. C'è anche un eserciziario

Mandrioli, Lavazza, Morzenti, San Pietro, Spoletini
Esercizi di informatica teorica
ed. Progetto Leonardo

[mistergks]

Qualcosa di piu sintetico?

[british]

Originariamente inviato da mistergks

Qualcosa di piu sintetico?

Non è che il tuo elenco fosse proprio sintetico, per quantità e qualità degli argomenti!

[mistergks]

Originariamente inviato da british

Non è che il tuo elenco fosse proprio sintetico, per quantità e qualità degli argomenti!

Certo:-) ma appunto cerco qualcosa che comprenda tutti gli argomenti ma che sia sintetico ed essenziale!

Inviato dal mio GT-I9003 con Tapatalk 2

[-MiStO-]

la migliore dispensa sull argomento:
http://users.dimi.uniud.it/~agostino...D/dispensa.pdf

usata a suo tempo...che mattone di esame