Materiale di studio per il corso di Algortimi Avanzati del Corso di Laurea Magistrale in Informatica presso l'Università di Modena e Reggio Emilia, A.A. 2017/18.

1. T.H. Cormen, C.E. Leoserson, R.L. Rivest, C. Stein, Introduction to Algorithms , Mc-Graw Hill, II o III Edizione
2. S. DAsgupta, C.H. Papadimitriu, U.V. Vazirani, Algorithms, Science Engineering & Math, 2011.
3. J. Kleinberg and E. Tardos, Algorithm Design, PEARSON Addison-Wesley, 2006
4. Nancy A. Lynch, Distributed Systems Morgan Kaufmann Publishers, Inc.

• Teoria della Complessità :
  • "Introduction to Algorithms" Cap 34: Intorduzione + Sezioni: 34.1, 34.2, 34.3 (fino a "Circuit satisfability" ESCLUSO), 34.4 (fino a "Teorema 34.9" ESCLUSO).
  • Nozioni introduttive di complessità computazionale (lucidi in formato pdf, 414K).
• Algoritmi di Approssimazione:
  • Vertex Cover: note lezione Prof. Chakrabarti, Dartmouth College ( pdf ).
  • Vertex Cover Pesato in Lecture Notes on Approximation Algorithms del Prof. R. Motwani in sezione 4.2.3.
  • Set Cover: Cap 11.3 in "Algorithm Design".
  • Vertex Cover e Set Cover: note lezione Prof. Suri, Università della California ( txt )
  • Steiner Tree in pdf sezione 2.1.
  • Problema del Commesso Viaggiatore (TSP):
    • note lezione Prof. Chekuri, Università dell'Illinois ( pdf ): SEZIONE 1.1.
    • Cap 2 in "Plotkin, Optimization Paradigms" ( pdf ).
  • Problema dello zaino (Knapsack problem): note lezione Prof. Lap Chi Lau della Chinese University ad Hong Kong ( pdf ).
  • Bin Packing:
    • note lezione Prof. Albers e Dr. Souza della Humboldt Univesitat a Berlino ( pdf ) - SEZIONE 10.3 esclusa.
    (rimosso dal sito - è il file (**))
    • note lezione Prof. Subhash Suri dell'Università di California ( txt ): SEZIONE 11 SOLO per studenti di INFORMATCA che hanno seguito il corso di "Algortimi di Approssimazione" come libera scelta durtante la triennale.
  • Load Balancing e Bin Packing: note lezione Prof. Chekuri Università dell'Illinois ( pdf ): SEZIONI 1.1 - 1.2 - 2.1 - 2.1
• Algoritmi di approssimazione utilizzando la tecnica del rilassamento della formulazione ILP (Integer Linear Programming) del problema:
  • Vertex Cover Pesato e Load Balancing con vincoli sull'assegnamento dei job alle macchine: SEZIONI 11.6 e 11.7 di "Algorithm Design".
  • Vertex Cover Pesato (alternativa) e Set Cover deterministico e randomizzato in Cap 8 di pdf.
• Algoritmi on-line:
  • List update in sezione 5
  • Paging in pdf
  • Compressione basata su liste lineari in sezione 6
• Branch and bound: Fra il materiale disponibile in rete, una buona introduzione generale in italiano è disponibile nelle dispense del prof. De Giovanni in pdf. Per l'applicazione al TSP, sempre in italiano, si può consultare doc
• Approccio primale-duale: Richiami sulla dualità, scarti complementari. Algoritmo primale-duale per il problema del Vertex-Cover in pdf
• Ricerca Locale: Algorithm Design, 12.1,12.2 2 12.4
• Algoritmi probabilistici:
  • Brevi richiami di probabilità. Generazione di numeri casuali. Utilizzo di /dev/(u)random in ambiente Linux. Generazione di variabili con distribuzione assegnata: uniforme, 0/1, binomiale in pdf e pdf (sezioni 3.1 e 3.2)
  • Algoritmi Monte-Carlo one-sided error: verifica di identità polinomiali in pdf , problema del minimum cut edge set in un grafo in Algorithm Design, sez. 13.2.
  • Analisi del caso medio per Quicksort: si veda, ad esempio in pdf .
• Interactive Proofs:
  • Graph non Isomorfism in pdf SEZIONE 1
  • Zero-knowledge Proofs e Graph Isomorfism in pdf SEZIONE 2 e in pdf SEZIONE 1.
    Spiegazione informale del concetto di prova zero-knowledge si puo' trovare in pdf .
  • Problema dell'identificazione: schema con firma digitale in pdf; protocollo FIat-Shamir pdf SEZIONE 2.
• Sistemi Distribuiti
  • Introduzione e modelli in "Distributed Systems": Sezioni 1.1 - 1.2 - 2.1 - 2.2 - 2.3 - 2.6.
  • Problema della Leader Election:
    • Algoritmi LCR e HS per ring e impossibiltà di elezione in ring anonimi in pdf , anche in ps , anche in "Distributed Systems" sezioni 3.1 - 3.2 - 3.3 - 3.4 - 3.5 (trascurando la formalizzazione degli algortimi).
    • Itai-Rodeh algoritmo randomizzato per ring in pdf slide 29-32 e ps
    • Leader Election in general network, algortimo FloodMax in "Distributed Systems" sezione 4.1 (trascurando la formalizzazione degli algortimi).
  • Byzantine agreement in rete asincrona in pdf sezione 17.5