Diariolezioni < Complessita

Tags: view all tags

---++*Sintesi delle lezioni*

   * 2 Ottobre
      * Presentazione del corso.
      * argomenti tipici di un corso di calcolabilità e argomenti tipici di un corso di complessità.
      * numeri transfiniti, cardinalità dei reali, ipotesi del continuo
      * metodo della diagonalizzazione di Cantor, esistenza di funzioni non calcolabili.
      * problemi decidibili e problemi semidecidibili. 
      * ultimo teorema di Fermat, la congettura di Colatz, la congettura di Goldbach
      

   * 5 Ottobre
      * indecidibilità del  problema della fermata. 
      * prove di indecidibilità tramite la tecnica della riduzione: indecidibilità del problema dell'equivalenza e del problema della corrispondenza di Post     
      * Tesi di Church-Turing.
      * Tesi del calcolo sequenziale.

   * 9 Ottobre
      * macchine di Turing a uno o più nastri
      * algoritmi per il riconoscimento di palindromi e lower bound Omega(n^2) nel caso di macchine ad un solo nastro.

   * 12 Ottobre
      * problemi trattabili e problemi intrattabili, la classe P
      * la gerarchia esponenziale di tempo, e la classe ELEMENTARY
      * le gerarchia esponenziale di spazio 
      * relazione tra le classi delle due gerarchie: P \subseteq PSPACE \subseteq EXPTIME \subseteq EXPSPACE ..... 

   * 15 Ottobre
      * il problema della fermata limitata, un risultato di separazione: P \subset EXPTIME
      * padding argument: se P= PSPACE allora EXPTIME=EXPSPACE

   * 19 Ottobre
      * dentro la classe P. Il modello di calcolo per classi sublineari.
      * se un problema risolvibile in spazio  s(n) = \omega (log n) allora risolvibile in tempo 2^O(s(n)).
      * la gerarchia L\subset 2L \subset 3L ..... e L\subseteq P
      * il problema della s,t-connettività. Sua appartenenza alla classe P e alla classe 2L
      * classi di complessità probabilistiche.

   * 23 Ottobre
      * variabili casuali, valore atteso e diseguaglianza di Markov
      * la classe RL
      * passeggiate casuali e s,t-connettività in RL
      * cover time e hitting time di grafi
      * cover time esponenziale per grafi diretti.

   * 26 Ottobre
      * passeggiate casuali e il problema della soddisfacibilità
      * algoritmo probabilistico per 2SAT in tempo O(n^4)

   * 30 Ottobre
      * algoritmo probabilistico per 3SAT in tempo O(n^5(4/3)^n)
      * riduzioni tra problemi e completezza.

   * 2 Novembre  giorno di festa

   * 6 Novembre
      * i verificatori e la classe NP, i confutatori e la classe co-NP
      * P \subseteq NP \subseteq PSPACE
      * il teorema di Ladner e la classe NPI
      * i problemi NP completi e i problemi co-NP completi
      * le classi QP e SUBEXP e l' Exponential-Time  Hypothesis (ETH)
      * il problema della fattorizzazione e il problema dell'isomorfismo tra grafi.

   * 9 Novembre
      * Algoritmi randomizzati e algoritmi probabilistici.
      * algoritmi tipo Montecarlo e tipo Las Vegas
      * la classe PP e la classe BPP
      * il lemma di amplificazione

   * 13 e 16  settimana degli esoneri
 
   * 20 Novembre
      * le classi RP e co-RP
      * il problema di verificare se un polinomio e' identicamente nullo e il problema dell'uguaglianza di polinomi
      * il torema di Schwartz

   * 23 Novembre
      * PP \subseteq PSPACE, 
      * RP\subseteq NP e co-RP\subseteq co-NP
      * la classe ZPP

   * 27 Novembre
      * un problema A appartiene alla classe ZPP se e solo se ha tempo atteso polinomiale
      * la classe #P, FP\subseteq #P, FP=#P se e solo se P=PP.
      * cook riduzioni e problemi #P completi, riduzioni polinomiali parsimoniose
      * il problema di contare i diversi  alberi di copertura di un grafo. Teorema di Kirchhoff e la formula di Cayley.

   * 30 Novembre
      * FESTA

   * 4 Dicembre
      *  il problema di contare il numero di cicli in un grafo. #ciclo è in FP   implica NP=P
      *  il problema di contare gli assegnamenti che soddisfano un certa formula booleana in DNF. #DNF è #P completo

   * 7 Dicembre
      *   il metodo di Monte Carlo per problemi di conteggio.  La classe di complessità probabilistica FPRAS
      *   il problema #DNF  è in FPRAS (applicazione del metodo di Monte Carlo)
      *   metodo della mediana per amplificare la probabilità di successo in un algoritmo di \epsilon-approssimazione 

   * 11 Dicembre
      *  enunciato e prova del Chernoff bound.
      *  Classi di complessità per problemi di ottimizzazione. Le classi NPO e PO.
      *  problemi di ottimizzazione NP-ardui
      *  PO=NPO se e solo se P=NP

   * 14 Dicembre
      *   rapporto d'approssimazione e algoritmi approssimanti per il problema della massima cricca (MAX CLIQUE) e  il problema dela massima soddisfacibilità (MAXSAT)
      *   le classi APX, PTAS e FPTAS
      *   se P diverso da NP allora il problema del commesso viaggiatore è in NPO-APX 

   * 18 Dicembre
      *   se P diverso da NP allora il problema del Bin Packing  è in APX-PTAS 
      *   se P diverso da NP allora i problemi di ottimizzazione polinomialmente limitati con versione decisionale NP-comleta non possono avere uno schema di approssimazione completamente polinomiale.
      *   se P diverso da NP allora il problema dello Zaino   è in FPTAS-PO