Tags:
create new tag
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
Edit | Attach | Watch | Print version | History: r10 < r9 < r8 < r7 < r6 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r10 - 2012-12-20 - AngeloMonti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback