Search this site
Embedded Files
Skip to main content
Skip to navigation
Automi e Linguaggi
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
Automi e Linguaggi
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
More
Informazioni generali
Organizzazione didattica
Videolezioni
Calendario
Esami
Valutazione
Videolezioni, parte III: teoria della complessità
Lezione 21
Parte 1: Introduzione alla teoria della complessità computazionale [11:
40
]
Parte 2: Limiti superiori asintotici e le classi di complessità TIME(t(n)) [1
3
:
10
]
Parte 3: Esempi di analisi di complessità temporale di algoritmi [19:
46
]
Parte 4: Analisi temporale della emulazione di diverse varianti di macchine di Turing [17:
51
]
Parte 5: La classe P dei problemi computazionali risolvibili in tempo polinomiale [15:
35
]
Parte 6: Esempi di problemi computazionali nella classe P [2
3
:
00
]
Lezione 22
Parte 1: Problemi computazionali polinomialmente verificabili [15:
48
]
Parte 2: La classe NP dei problemi polinomialmente verficabili e sua caratterizzazione tramite NTM [21:13]
Parte 3: Esempi di problemi in NP e coNP [20:
33
]
Parte 4: La classe EXPTIME dei problemi risolvibili in tempo esponenziale e la questione P =? NP =? EXPTIME [13:
38
]
Parte 5: Riduzioni polinomiali ed i problemi di soddisfacibilità di formule booleane [18:
19
]
Lezione 23
Parte 1: Esempio di riduzione polinomiale da 3SAT a CLIQUE [25:
54
]
Parte 2: Linguaggi NP-completi e linguaggi NP-hard [
7
:
02
]
Parte 3: NP-completezza di SAT (teorema di Cook-Levin): idea generale della dimostrazione [12:
54
]
Parte 4: NP-completezza di SAT (teorema di Cook-Levin): struttura della formula Booleana [24:
21
]
Parte 5: NP-completezza di SAT (teorema di Cook-Levin): limiti polinomiali ed estensione a 3SAT [
26
:
12
]
Lezione 24
Parte 1: NP-completezza del problema VERTEX COVER [25:
56
]
Parte 2: NP-completezza del problema HAMILTONIAN PATH [2
9
:
04
]
Parte 3: NP-completezza del problema UNDIRECTED HAMILTONIAN PATH [9:
48
]
Parte 4: NP-completezza del problema SUBSET SUM [19:
43
]
Parte 5: NP-completezza del problema INDEPENDENT SET e relazioni con VERTEX COVER e CLIQUE [8:
25
]
Lezione 25
Parte 1: La complessità spaziale dei problemi computazionali [26:07]
Parte 2: Il teorema di Savitch [13:42]
Parte 3: Dimostrazione del teorema di Savitch [17:
29
]
Parte 4: La classe PSPACE e la definizione di PSPACE-completezza [12:
28
]
Parte 5: Il problema TQBF è in PSPACE [11:
27
]
Parte 6: Il problema TQBF è PSPACE-completo [20:
48
]
Lezione 26
Parte 1: Il problema FORMULA GAME equivalente a TQBF [
12
:
00
]
Parte 2: Il problema GENERALIZED GEOGRAPHY è in PSPACE [14:
18
]
Parte 3: Il problema GENERALIZED GEOGRAPHY è PSPACE-completo [18:
40
]
Parte 4: Le classi di complessità spaziale logaritmiche L e NL [20:
36
]
Parte 5: Riduzioni in spazio logaritmico e NL-completezza [15:
29
]
Parte 6: Il problema PATH è NL-completo [13:
39
]
Google Sites
Report abuse
Page details
Page updated
Google Sites
Report abuse