Docenti: Roberto Grossi, Linda Pagli, Nadia Pisanti

La prova di verifica intermedia si terrà in data 26.01.2011 dalle ore 9 alle ore 11 in aula D4. Gli argomenti degli esercizi saranno basati sulle lezioni e sulle esercitazioni tenute fino al giorno 19/01/2011.

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: 24, 17 -> 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 21, DINELLI 14, DONDIO 20, GRIOLI 20, GUIDOTTI 24, MEDICI 20, MASCITTI 23, MILLI 27, PASTORINI 15, STRONATI 24, TAMBUSCIO 23, VOLPI 21.