Docenti: Roberto Grossi, Linda Pagli, Nadia Pisanti

Correzione compiti e verbalizzazione venerdì 18 febbraio ore 11:00 e lunedì 28 febbraio ore 11:00 presso lo studio della prof.ssa Pagli.

In questo corso studieremo, progetteremo e analizzeremo soluzioni algoritmiche e strutture di dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato, quali interi, stringhe, punti (geometrici), alberi, grafi.

Questo corso costituisce un naturale approfondimento e ampliamento delle conoscenze di base apprese nel percorso della laurea triennale.

Il suo syllabus è organizzato per ambiti applicativi, al fine di contestualizzare le tecniche studiate nella realizzazione di software efficiente per essi, e così da consentire adattamenti e specializzazioni di anno in anno che si renderanno necessari e/o opportuni.

• Compressione di testi e di interi
• Strutture di dati randomizzate
• Motori di ricerca: liste invertite

• Modelli di computazione
• Permutazioni e ordinamenti
• Dizionari

• Matrice dei suffissi
• Albero dei suffissi
• Algoritmi di pattern matching

• Strutture di dati distribuite
• Analisi competitiva
• Algoritmi on-line

• I problemi NP-hard
• Algoritmi di approssimazione
• Algoritmi randomizzati

• Collegamento a UNIMAP

• PROBLEMI DIFFICILI E APPROSSIMAZIONE
  • dispensa_1.0.pdf: capitolo 9 del testo Crescenzi, Gambosi, Grossi
    • dispensa_1.1.pdf (a cura di P. Crescenzi)
    • appunti_1.2 (a cura di E. Dinelli)
    • Sito dedicato a problemi di ottimizzazione NP-hard
    • Sito dedicato al problema del commesso viaggiatore (TSP)
  • dispensa_2.0.pdf: non-determinismo (a cura di Horowitz-Sahni)
    • L'esempio 12.2 contiene degli errori: individuarli.
    • Teoremi 12.5 e 12.7 senza dimostrazione.
    • Nel Teorema 12.8, k>=(1+e)n deve essere: k>=1+en.
  • dispensa_3.0: capitolo 2 del testo Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi
    • studiare soltanto: pp.39-47, paragrafo 2.2.2
    • dispensa_3.1
    • dispensa_3.2: varianti di max-sat (da consultare)

• STRINGOLOGIA
  • Exact matching (patternmatching1.pdf, patternmatching2.pdf)
  • Aho-Corasickuno.pdf
  • Karp-Rabin due.pdf
  • Suffix tree tre.pdf
  • Suffix array quattro.pdf

• ALGORITMI ON LINE
  • Move to front mtf.pdf
  • Algoritmi per il problema del paging paging.pdf
  • Web Caching: algoritmi Greedy Dual e Greedy Dual Size gds.pdf

• HASHING DISTRIBUITO
  • Consistent Hashing dispensa
  • Dalla tesi di master di Daniel M. Lewinprima parteseconda parte. Studiare fino all'enunciato del teorema 2.2.3. Poi i lemmi 2.2.5 e 2.2.6.

• ALGORITMI RANDOMIZZATI
  • QUICKSORT randomizzato randqs.pdf
  • Test di primalità di Miller&Rabin alg-random.pdf
  • CUCU Hashing cuckoo-undergrad.pdf

• MEMORIE GERARCHICHE
  • Modelli di computazione, permutazioni e ordinamenti: J. S. Vitter. Algorithms and Data Structures for External Memory, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008. Also published as Volume 2, Issue 4 of Foundations and Trends in Theoretical Computer Science VERSIONE ELETTRONICA (introduzione, sezione 2.1, capitolo 3, sezione 5.2, sezione 5.6, sezione 11.1)

• VOTI FINALI PER I COMPITINI (voti dei due compitini, con media approssimata per eccesso e incrementata di tre punti per il punteggio finale):

   BALDINI: 19 , 17 -> 21
   DE SALVE: 17, 25 -> 24
   DINELLI: 20, 14 -> 20 -> 21 (incremento per stesura dispensa)
   DONDIO: 21, 20 -> 24
   GUIDOTTI: 22, 26 -> 27 -> 28 (incremento per commento su esercitazione)
   MEDICI: 19, 22 -> 24
   MILLI: 22, 27 -> 28
   PASTORINI: 17, 17 -> 20
   STRONATI: 17, 24 -> 24
   TAMBUSCIO: 18, 23 -> 24
   VOLPI: 21, 22 -> 25 

  N.B.: per incrementare il voto finale, l'unica possibilità è quella di ripetere la prova nei prossimi appelli

• Compitino del 15.12.2010 testo
• Compitino del 26.01.2011 testo
  • Risultati: BALDINI 17, DE SALVE 25, DINELLI 14, DONDIO 20, GRIOLI 20, GUIDOTTI 26, MEDICI 22, MASCITTI 23, MILLI 27, PASTORINI 17, STRONATI 24, TAMBUSCIO 23, VOLPI 22.

• VOTI FINALI APPELLO DEL 1/2/2011

   ANDOLFI Matteo                  23
   BALDINI Francesco               24
   CARLINI Mattia                  ins.
   CRUPI Andrea                    ins.
   DE SALVE Andrea                 28
   DINELLI Emanuele                25
   GALATOLO Gabriele               24
   GRIOLI Christian                23
   MANZULLI Annalisa               ins.
   MARZINI Emanuel                 ins.
   MASCITTI Davide                 30L
   MEZZANI Miriam                  21
   PAGANO Giancarlo                18
   PASTORINI Marco                 22
   PIERMARTINI Damiano             26
   STRONATI Marco                  27
   TAMBUSCIO Marcella              28
   XHAGJIHA Vamis                  21

• VOTI FINALI APPELLO DEL 16/2/2011

   ANDOLFI Matteo                  26
   CARLINI Mattia                  ins.
   GRIOLI Christian                25
   MANZULLI Annalisa               23
   MARZINI Emanuel                 18
   MAWI Gabriele                   18
   MEZZANI Miriam                  21
   SALINES Alessio                 19
   

• Risultati APPELLO DEL 06/06/2011: AUSILIO Alessio 22; MARZINI Emanuel ins. Correzione e registrazione: 21/06/2011 ore 9.30 aula A.
• Risultati APPELLO DEL 21/06/2011: BACARELLA Daniele ins.; MARZINI Emanuel 23; VAIRA Francesco 19. Correzione e registrazione: 7/7/2011 ore 9.30 aula A.
• Risutati APPELLO DEL 07/07/2011: BACARELLA Daniele ins.; Marcheschi Chiara 19; VAIRA Francesco 21; XHAGGIKA Vamis 19. Correzione e registrazione: 11/07/2011 ore 11 uffico Pagli oppure 13/07/2011 ore 15 ufficio Grossi.

• TESTI DI ALCUNI ESAMI: algo2-01-02-11.pdf, algo2-16-02-11.pdf, algo2-26-01-11.pdf, algo2-30-11-10.pdf