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