Corso 2018 – 2019

vedete anche il materiale sotto.

Fino a poco tempo fa, i matematici teorici consideravano un problema risolto se esisteva un metodo conosciuto, o algoritmo, per risolverlo; il procedimento di esecuzione dell’algoritmo era di importanza secondaria. Tuttavia, c’è una grande differenza tra il sapere che è possibile fare qualcosa e il farlo. Questo atteggiamento di indifferenza sta cambiando rapidamente, grazie ai progressi della tecnologia del computer. Adesso, è importantissimo trovare metodi di soluzione che siano pratici per il calcolo. La teoria della complessità studia i vari algoritmi e la loro relativa efficienza computazionale. Si tratta di una teoria giovane e in pieno sviluppo, che sta motivando nuove direzioni nella matematica e nello stesso tempo trova applicazioni concrete quali quello fondamentale della sicurezza e identificazione dei dati.

– E. Bombieri, Medaglia Fields, in La matematica nella società di oggi, Bollettino UMI, Aprile 2001

Corso 2017-2018

  1. 4/10 – Introduzione, Funzioni Parziali Ricorsive, Funzioni Totali. Cenni di Lambda Calcolo e linguaggi Funzionali.
  2. 5/10 – Enumerazione PR, Diagonalizzazione, Ackerman, operatore di minimizzazione e funzioni Ricorsive (generali). Universalità e Interprete.
  3. 11/10 – Macchine di Turing, Tesi di Church-Turing. Linguaggi Decidibi (Ricorsivi) o Semi-Decidibili (Riconoscibili, Ricorsivamente Enumerabili).
  4. 12/10 – Teoremi su Linguaggi Ricorsivi e R.E., Linguaggio HALT, Dimostrazione che HALT è R.E. ma non Ricorsivo.
  5. 19/10 – Teorema di Rice,Teorema s-m-n, cenni introduttivi alle riduzioni many-to-one.
  6. 25/10 – Esercizi, Dimostrazione del Teorema di Rice, Riduzioni, Proprietà delle Riduzioni, Utilizzo per Dimostrazioni di non Ricorsività. Lattice delle Riduzioni, Linguaggi r.e. completi.
  7. 30/10 – Inizio Complessità Computazionale, definizione di DTIME, richiami di Algoritmi.
  8. 2/11 – Problema dell’Insieme Indipendente (INDSET), definizione di P, EXPTIME. Problemi di Ottimizzazione: Versioni Decisionali.
  9. 6/11 – Richiami di Valutazioni di Complessità, esempi di problemi con complessità lineare, nlogn, quadratica, Problema del Commesso Viaggiatore, Teorema SpeedUp, Valutazione Complessità di INDSET.
  10. 8/11 – NP, NP completezza. INDSET soluzione esponenziale, relazione tra P, NP, EXTIME. Definizione di certificato, verificatore, macchine non-deterministiche, le due definizioni di NP e relazioni.
  11. 9/11 – NP-Completezza, SAT, 3-SAT, Vertex Cover, Set-Cover, Hamiltonian Cycle, TSP. Teorema di Cook-Levin (SAT è NP-Completo) dimostrazione informale.
  12. 13/11 – Panorama oltre NP, PSPACE, Algoritmi di Approssimazione, Algoritmi Randomizzati, Crittografia.
  13. 15/11: Approssimazione: Vertex Cover, Load Balancing, Metodo del Rounding.
  14. 16/11 – Approssimazione: TSP Christofides. Cenni a IP,  AM e Zero-Knowledge Proof Systems, Teorema PCP: enunciato.
  15. 20/11 – Crittografia, Sicurezza Perfetta, Cifrario one-time-pad. Cifrari simmetrici cenni, Cifrari a chiave pubblica cenni. Hash Functions, Funzioni One-Way.
  16. 22/11 – Cenni su Reti in Generale, Reti di Sensori, Modello, Grafi Temporali
  17. 23/11 – Problema di Connettività tra reti di nodi Argos
  18. 27/11 – Diagnosi di Sistemi, modello PMC, t-diagnosticabilità.
  19. 28/11 – Problemi di Diagnosi e di stima della soglia di Diagnosticabilità in strutture regolari, riduzione al problema del vertex-cover. Algoritmo di Diagnosi. Relazioni con il framework dell’argumentation.
  20. 30/11 – coNP,  P e NP
    co-NP, problemi ben caratterizzati, problemi completi in Co-NP, gerarchia polinomiale. PSPACE.

Esercizi:

  • Installare Python 3, Installare ipython e Jupiter, Installare numpy, scipy, networkx, matplotlib. Usare questa Guida
  • Provare questo codice: Indipendent Set with Networkx
  • Ripassare o studiare con attenzione il problema del Minimum Spanning Tree (Minimo Albero Ricoprente).
  • Problema per Esame: Steiner Tree

Articoli:

Materiale Didattico:
Template Latex: Scarica il file arsclassica zip dal sito latextemplate.
Italiano:

Inglese:

Letture Raccomandate:

Per la preparazione si consiglia di leggere la parte introduzione e Cap.2 di Dovier, Giacobazzi, non sottovalutare il richiamo sui fondamenti matematici, che spesso sono stati studiati ad un livello meno formale, si studi con attenzione il richiamo sui linguaggi del primo ordine nel Cap2/Sez 4.
Per la parte di Calcolabilità usare Dovier, Giacobazzi (Parte 2), leggere (almeno una volta) le dimostrazioni di equivalenza tra modelli. Studiare bene le dimostrazioni basate su Diagonalizzazione. Saltare il capitolo sul WHILE.

Corso (2016-2017)

(28-29 /09 da recuperare)

  1. 5/10 – Introduzione. Funzioni Ricorsive Primitive. Funzoni Totali vs Parziali. Enumerazione delle FRP, Diagonalizzazione.
  2. 6/10 – Funzione di Ackerman, richiami su diagonalizzazione, funzioni
    mumu


    -ricorsive. Universalità e Interpreti. Tesi di Church-Turing (usata senza citarla) ampia trattazione nel primo volume di Odifreddi.
    Formalizzazioni alternative:

    λλ


    -calcolo, Macchine di Turing: Definizione, Alfabeti e Linguaggi.

  3. 12/10 – Linguaggi Decidibili (Ricorsivi) vs Riconoscibili (Ricorsivamente Enumerabili, Accettati). Proprietà rispetto al complemento. Halting-Problem dimostrazione diagonale.Teorema s-m-n, Teorema del Punto Fisso (Quine).
  4. 13/10 – Riduzioni many-to-one. Teorema di Rice.
    Testi (Note di Asperti, note), testi graduate: Rogers92, Odifreddi.
    ————————————————-
  5. 19/10 – Introduzione alla Complessità Computazionale, problemi decidibili vs di ricerca vs di ottimizzazione. Definizione di classi di Complessità.
  6. 20/10 – Introduzione alla Complessità Computazionale: classi TIME(f(n)), SPACE(f(n)), definizione di P, problemi facili (polinomiali), definizione di NP come problemi facilmente verificabili, nozione di certificato.
  7. 26/10 Seminario Studenti Esame su SAT e metodi di risoluzione con backtracking.
  8. 27/10 – Macchine non deterministiche, NP come problemi decisionali in NTIME(p(n)) con p(n) un polinomio. Relazione tra le due definizioni, Simulazione del non determinismo.
  9. 2/11 – Riduzioni Polinomiali: Karp e Turing reductions. Definizione di Np-Completezza, esempi. Definizione di SAT e Teorema di Cook (cenni sulla dimostrazione)
  10. 16/11 – Riduzioni Polinomiali: da SAT a INDSET, VERTEX COVER.
  11. 17/11 – Riduzioni2: SAT HamPath. SAT Clique – Knapsack.
  12. 21/11 – Parallel Architecture: Classificazione di Flynn, SIMD,MIMD. Modelli Shared Memory vs Distributed. Esempi di Algoritmi su Shared Memory (somma: albero di riduzione per operatori commutativi).
  13. 22/11 Programmazione Concorrente. PRAM
  14. 23/11 Pthreads. OpenMP, MPI. Esempi. Introduzione algoritmi Randomizzati (articolo di Karp)
  15. Randomizzazione, classi di complessità e inizio sicurezza e crittografia.

Fine parte Calcolabilità: Gli studenti dovrebbero selezionare un argomento presente nei pdf sotto e preparare una piccola tesina su di esso:

** Just for Fun **
The Busy Beaver Competition.
How Real are Real Numbers?
Computable Analysis

Antonio Caruso (2015-16)

Calcolabilità

  1. 30/09/2015:   Funzioni Ricorsive Primitive.
  2. 7/10/2015:  Macchine di Turing, definizione, configurazioni istantanee, macchine che decidono linguaggi vs accettano linguaggi. Macchine che calcolano funzioni. Enumerazione delle MdT. Relazione tra macchine e funzioni parziali da N in N. Teoremi da I a IV (da Rogers) pag. 20-24 da Rogers, e cap. 5 in Asperti. Esistenza di funzioni non parziali ricorsive, esistenza della funzione universale i.e.
  3. 8/10/2015: Halting Problem (interessante la sezione History). Insiemi Ricorsivi vs Ricorsivamente Enumerabili.  Teorema di Rice (Enunciato). Riduzioni tra Linguaggi (1to1, many-to-one) come strumento per dimostrare la non calcolabilità di una funzione. Chiusura dei linguaggi ricorsivi, linguaggi NON r.e.

Complessità Computazionale

  1. 12/10/2015 – Misure di Complessità in Tempo e Spazio, definizione di classe TIME(f(n)), SPACE(f(n)), costruttività di f. Problemi di Decisione, di Ricerca, di Enumerazione e di Ottimizzazione. Classi di Complessità come insiemi di linguaggi o problemi decisionali. Definizione di P, e di EXP. Speed-Up Theorem.
    Studiare intro di Garey and Johnson. e Introduzione e Capitolo 1 di Arora-Barak. Esercizio: 2-SAT, definizione di formula CNF, algoritmo di soddisfacibilità per 2-SAT.
  2. 14/10/2015 – Teorema di Gerarchia Temporale, P
    ⊂⊂


    EXP, definizione della classe NP:   come linguaggi verificabili in tempo polinomiale, concetto di certificato; come classe di linguaggi decidibili in tempo polinomiale da macchine non-deterministiche. Relazione tra le due definizioni. Simulazione (in tempo esponenziale) di una NMDT da parte di una MDT. (Studiare Cap 1,2,3 di Arora).
    Riduzioni Polinomiali tra linguaggi, problemi NP-Hard, definizione di problemi NP-Completi.
    Problema del Massimo Insieme Indipendente, dimostrazione (informale) che INDSET  (la versione decisionale) è in NP.

  3. 26/10/2015:   Richiami Definizioni precedenti. Np-Completezza, Teorema di Cook-Levin -> SAT è NP-Completo (versione con SAT e/o con Circuit-SAT) Cenni. Riduzioni per dimostrazioni di Np-Completezza:
    • SAT < IND_SET < VERTEX_COVER.  IND_SET < CLIQUE
    • SAT < 3SAT
    • Materiale Divulgativo su: TSP, leggete sotto la sperimentazione con ipython, e provatela.
  4. 3SAT < Hamiltonian-Path (cenni). Classe co-NP, problemi co-NP-Completi (TAUTOLOGY), definizione formale e relazioni tra co-NP, NP, P, e PSPACE. Gerarchia Polinomiale. PSPACE, relazioni tra le classi, problemi PSPACE-completi (QSAT). Macchine Probabilistiche BPP, Polynomial Identity Testing.
  5. Cifrari Simmetrici. One-Time Pad. Funzioni One-Way Definizione, candidati possibili: RSA. Generatori Pseudo-Polinomiali. Natural Proofs e P!=NP. Primality Test. Crypto-Hash Functions.
  6. Approssimazione. Classe PTAS, e FPTAS – Schemi di Approssimazione Polinomiale e Pienamente Polinomiale, Problemi Fortemente Np-Completi. Knapsak. APX, fattore di approssimazione costante: Vertex Cover. Cenni sull’algoritmo di Christofide per TSP. Cenni su non approssimabilità: problema aperto unique game conjecture.
  7. One-way function: distinzione tra problemi difficili in worst-case e problemi difficili in media. Parametrized Complexity. Esempio per Vertex Cover. Rounding Linear Programming Relaxation: Applicazione al Vertex Cover Pesato (note). Load Balancing: 2-approssimazione. (slides)

Video: Nice Video su P vs NP
Articoli per Esame: (in fase di compilazione)
Per gli audaci, con un buon background in Teoria dei Gruppi:
http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

  1.  Improving Christofides’ Algorithm for the s-t Path TSP, Hyung-Chan An, Robert Kleinberg, David B. Shmoys,  doi>10.1145/2818310.Journal of the ACM, Vol. 62, No. 5, Article 34, Publication date: October 2015.
  2. Subexponential Algorithms for Unique Games and Related Problems,  Sanjeev Arora, Boaz Barak, David Steurer, Journal of the ACM, Vol. 62, No. 5, Article 34, Publication date: October 2015. DOI: http://dx.doi.org/10.1145/277510
  3. Knuth, final draft of pre-fascicle 6 (318 pages).  The Art of Computer Programming, Fascicolo 6, SAT.
    (ovviamente non tutte le 318 pagine, magari selezionate un argomento, se vi sono più persone interessate a Algoritmi per SAT, sarebbe utile se lavoraste insieme, per preparare una serie di seminari sull’argomento).
  4. Reduction of the graph isomorphism problem to equality checking of nn

    -variables polynomials and the algorithms that use the reduction, [pdf].Alexander Prolubnikov

Libri Online:

Note:

Sperimentazione TSP con ipython:

Installate una distribuzione di Python completa di librerie scientifiche da questo sito. Installate la versione a 32 o 64 bit a seconda della vostra versione di Windows. Python è un linguaggio interpretato ad alto livello, con un set di librerie scientifiche molto sofisticato (alla matlab). L’interfaccia migliore per usarlo è ipython che trovate già nella distribuzione, dopo aver scompattato l’archivio, seguite le info sul sito, per “registrare” nel menu avvio i programmi, oppure semplicemente lanciate i programmi andando nella cartella dove avete scompattato e eseguendo il link relativo.
Usate IPython Notebook, scaricate questo notebook (davvero molto bello).

  • TSP con ipython notebook. Mettetelo nella cartella Notebook, a questo punto quando fate partire IPython Notebook dalla relativa icona (o menu), dovreste trovare il file nell’elenco dei notebook. Apritelo, le celle con il codice si valutano (eseguono) con il pulsante play, o con SHIFT+ENTER.

Articoli per Esame (2015): (in definizione)

Topic:  Unique Game Conjecture. Partite da questo blog . L’argomento è molto vasto, quindi dovrete concentrarvi sulla formulazione della congettura, sul suo utilizzo (prima per i lower bound ad approssimazioni) poi in altri settori. Il riferimento sotto è una survey recente, ma se troppo complessa cercate materiale più specifico sulla UCG, che potete probabilmente trovare tra gli articoli citati, infine l’articolo di Arora, mostra che il problema può essere risolto con complessita sub-exp. Su questo argomento possono lavorare anche più gruppi, basta che magari si concentrino su parti diverse, in ogni caso mandatemi un email.

News -> Video su Unique Game Conjecture (di Khot) (link) raccomandato per chi lavora su questo argomento.

La congettura è davvero aperta, la comunità è divisa tra sostenitori della polinomialità vs difficoltà.

  1. Khot, Subhash (2010), “On the Unique Games Conjecture”, Proc. 25th IEEE Conference on Computational Complexity, pp. 99–121, doi:10.1109/CCC.2010.19
  2. Arora, Sanjeev, Boaz Barak, and David Steurer. “Subexponential algorithms for unique games and related problems.” Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.

Route Planning:

Hannah Bast , Daniel Delling , Andrew Goldberg , Matthias Müller-Hannemann, Thomas Pajor , Peter Sanders, Dorothea Wagner and Renato F. Werneck. Route Planning in Transportation Networks, 2015, Microsoft Research.

        

Teoria dei Giochi  (Vittorio Bilò)

Programma:
– Introduzione alla teoria dei giochi: giochi non cooperativi, il dilemma del prigioniero, giochi di congestione, giochi di condivisione dei costi su reti, strategie dominanti, mosse migliorative, equilibrio di Nash puro, grafo della dinamica di Nash, esistenza e unicità degli equilibri di Nash puri, i giochi Matching Pennies e Battle of Sexes, contromosse migliori e grafo delle contromosse migliori, proprietà del cammino di miglioramento finito e funzioni potenziali, equivalenza tra i giochi di congestione e i giochi con potenziale esatto, gioco di bilanciamento del carico, strategie miste, equilibrio di Nash misto e Teorema di Nash, calcolo degli equilibri di Nash usando la definizione.
– Introduzione alla Teoria Algoritmica dei Giochi: inefficienza degli equilibri di Nash, prezzo dell’anarchia e prezzo della stabilità.
– Giochi di condivisione dei costi su reti: il prezzo dell’anarchia per le funzioni sociali somma dei costi dei giocatori e massimo costo di un giocatore, il prezzo della stabilità per la funzione sociale somma dei costi dei giocatori, limitazioni inferiori al prezzo della stabilità nel caso di reti broadcast e multicast non dirette, i casi particolari di 2 e 3 giocatori.
– Giochi di congestione lineari: il metodo primale-duale, il prezzo dell’anarchia e il prezzo della stabilità per la funzione sociale somma dei costi dei giocatori, definizione di 1-round walk e caratterizzazione del rapporto di approssimazione delle soluzioni raggiunte dopo un 1-round walk che parte da uno stato generico e dallo stato vuoto.
– Cut Games: definizione, esistenza di un potenziale esatto, prezzo dell’anarchia e prezzo della stabilità per la funzione sociale peso del taglio, giocatori moderatamente avidi, prezzo dell’anarchia degli equilibri di Nash approssimati per la funzione sociale peso del taglio, caratterizzazione del rapporto di approssimazione delle soluzioni raggiunte dopo un 1-round walk che parte da uno stato generico.
Materiale didattico: dispensa realizzata dal docente relativa agli argomenti trattati nel corso.
Articoli consigliati per la realizzazione del seminario d’esame:
4) Yann Disser, Andreas Emil Feldmann, Max Klimm, Matús Mihalák: Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games. CoRR abs/1211.2090 (2012).
5) Leah Epstein, Elena Kleiman: Selfish Bin Packing. Algorithmica 60(2): 368-394 (2011).
6) Konstantinos Kollias, Tim Roughgarden: Restoring Pure Equilibria to Weighted Congestion Games. ICALP (2) 2011: 539-551.
7) Ho-Lin Chen, Tim Roughgarden: Network Design with Weighted Players. Theory of Computing Systems 45(2): 302-324 (2009).
8) Tim Roughgarden, Éva Tardos: How bad is selfish routing? Journal of ACM 49(2): 236-259 (2002).
10) Hartwig Bosse, Jaroslaw Byrka, Evangelos Markakis: New algorithms for approximate Nash equilibria in bimatrix games. Theoretical Computer Science 411(1): 164-173 (2010).
11) Constantinos Daskalakis, Aranyak Mehta, Christos H. Papadimitriou: A note on approximate Nash equilibria. Theoretical Computer Science 410(17): 1581-1588 (2009).
12) Tomás Feder, Hamid Nazerzadeh, Amin Saberi: Approximating nash equilibria using small-support strategies. ACM Conference on Electronic Commerce 2007: 352-354.
Le versioni complete di quasi tutti questi articoli possono essere reperite sul web. Chi non ci riuscisse può contattarmi per averne una copia. Si ricorda che ogni gruppo di studenti deve segnalare preventivamente al docente quale articolo ha intenzione di scegliere per il seminario e che, soltanto dopo che il docente ha confermato l’assegnamento dell’articolo al gruppo, si può procedere a iniziare del lavoro. E’ data possibilità a un gruppo di studenti di proporre articoli non appartenenti alla lista proposta dal docente.