Docente: Roberto Grossi

Oggi usciranno i risultati del compitino.

In questo corso vengono studiate, progettate e analizzate soluzioni algoritmiche e strutture di dati evolute per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dati, per esempio, interi, stringhe, punti (geometrici), alberi e grafi.

Questo corso costituisce un naturale approfondimento e ampliamento delle conoscenze di base apprese nel percorso della laurea triennale. Tuttavia, essendo rivolto a studenti più maturi scientificamente, è orientato al brainstorming e al problem solving su tematiche più complesse. Lo scopo non è semplicemente quello di presentare ulteriori N algoritmi e tecniche risolutive, ma di affinare le capacità risolutive degli studenti.

Più precisamente, le lezioni del martedì e del mercoledì tratteranno gli argomenti canonici del corso, proponendo problemi ad essi collegati da risolvere durante il resto della settimana: il lunedì successivo, tali problemi verranno approfonditi e osservati da più punti di vista, anche sbagliati, in quanto l'errore è funzionale all'apprendimento di situazioni complesse. Viene data enfasi al percorso mentale che porta alla soluzione (piuttosto che la soluzione stessa), sotto la guida del docente in base alla reazione dei partecipanti. E a proposito di errori e intelligenza, Alan Turing nel 1947 scrive: “… if a machine is expected to be infallible, it cannot also be intelligent”, che può essere preso come motto del corso e come un invito a partecipare attivamente alle discussioni in aula senza timore di proporre idee sbagliate.

Dal punto di vista del programma da svolgere e degli esami, il lunedì non verranno aggiunti nuovi argomenti ma si studieranno problemi correlati: l'esame scritto conterrà alcuni di questi problemi discussi il lunedì; l'esame orale si baserà sugli argomenti presentati il martedì e il mercoledì.

Il 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.

Per gli studenti degli anni precedenti: i contenuti del corso non cambieranno significativamente rispetto a quelli degli anni precedenti, ma l'esame scritto sarà basato su problemi più complessi, che però saranno stati discussi e rielaborati durante il semestre (ogni lunedì).

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

• Modelli di computazione
• Permutazioni e ordinamenti
• Dizionari

• Algoritmi di pattern matching
• Trie
• Array dei suffissi
• Albero dei suffissi

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

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

• Collegamento a UNIMAP

• ESERCITAZIONI - PROBLEM SOLVING
  • Problemi discussi (non è detto che abbiano un'unica soluzione) [Elenco]

• STRINGOLOGIA e COMPRESSIONE DI DATI
  • Stringologia [dispensa: tutta, escluse sez.2.4,2.5,4.4,5.3]
  • Compressione di dati [cap.2:inizio-pag.36,sez.2.4,sez.2.5(solo BWT), sez.2.6] [cap 3: fino pag.119]
  • Suffix tree [Cap.5; fino pag.93]
  • Suffix array [Cap.7: fino pag.154] [DC3: solo Sezione 3]

• MEMORIE GERARCHICHE
  • Modelli di computazione EMM e CO: [Libro: introduzione, cap.2 e 3 (porre D=1 dischi)]
  • EMM Mergesort e limiti inferiori: [Dispensa MS] [Dispensa LB]
  • MapReduce: [Mini tutorial]
  • van Emde Boas (vEB) layout [sez.4.1]
  • paginazione alberi [sez.3.1] [sez.5.1] [esempio]

• ALGORITMI ON LINE E RANDOMIZZATI
  • Algoritmi per il problema del paging [sez.3] [sez.2 e 3]
  • QUICKSORT randomizzato [sez.2.5.4]
  • CUCU Hashing [dispensa]
  • Skip list [sez.3.3]

• PROBLEMI DIFFICILI E APPROSSIMAZIONE
  • NP-completezza e approssimazione I [cap.9] [appunti Dinelli]
  • Approssimazione II [cap.2:pp.39-47, paragrafo 2.2.2]

• Compitino del 21.12.2011:

   273411    18
   290098    30-
   423175    28
   423957    30
   426385    30
   437816    30
   479661    28
   481873    26
   482602    18
   484823    22
   484936    27

   [mancano ancora alcuni voti]

• 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