Docente: Roberto Grossi

Maltempo La prova di esame di “Algoritmica e Laboratorio” e di “Algoritmica 2” dell'1.2.2012 si svolgerà regolarmente. Tuttavia, per gli studenti iscritti a tale prova (nel calendario degli appelli della sezione didattica del sito www.di.unipi.it) ma impossibilitati a partecipare a causa del maltempo, sarà fissata una prova di recupero in data da concordare direttamente con il prof. Grossi via email.

Com'è consuetudine, il voto finale dipende dal voto dell'esame scritto e da quello dell'esame orale. Per iscriversi all'esame orale, presentarsi nello studio del docente all'ora indicata, per redigere un calendario insieme agli altri studenti interessati all'esame orale. In caso di impegni, scrivere il proprio nome nel foglio/calendario che verrà successivamente appeso sulla porta del docente.

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]

• Non più disponibili

• 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