Anno 2010-2011

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):

OMISSIS

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:

OMISSIS

• VOTI FINALI APPELLO DEL 1/2/2011

OMISSIS

• VOTI FINALI APPELLO DEL 16/2/2011

OMISSIS

• Risultati APPELLO DEL 06/06/2011: OMISSIS

• Risultati APPELLO DEL 21/06/2011: OMISSIS

• Risutati APPELLO DEL 07/07/2011: OMISSIS

• Risutati APPELLO DEL 09/09/2011: OMISSIS

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