mistergks
28-11-2013, 16:49
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
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