Strumenti Utente

Strumenti Sito


magistraleinformatica:alg2:algo2_11:start

Anno 2011-2012

Docente: Roberto Grossi

Avviso

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.

Date d'esame

Data Ora Luogo Tipo Prova Note
21/12/2011 15:00 Aula C1 Compitino Iscriversi all'esame
11/01/2012 09:00 Aula A Primo appello Iscriversi all'esame
16/01/2012 09:00 studio Orali Partecipare per fissare il calendario
01/02/2012 09:00 Aula A Secondo appello Iscriversi all'esame
06/02/2012 09:00 studio Orali Partecipare per fissare il calendario

Obiettivi di apprendimento

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ì).

Programma di massima

Accesso ai dati e loro compressione
  • Compressione di testi e di interi
  • Strutture di dati randomizzate
  • Motori di ricerca: liste invertite
Memorie gerarchiche
  • Modelli di computazione
  • Permutazioni e ordinamenti
  • Dizionari
Stringologia
  • Algoritmi di pattern matching
  • Trie
  • Array dei suffissi
  • Albero dei suffissi
Strutture di dati evolute
  • Strutture di dati distribuite
  • Analisi competitiva
  • Algoritmi on-line
Problemi "difficili" e loro soluzione
  • I problemi NP-hard
  • Algoritmi di approssimazione
  • Algoritmi randomizzati
Registro delle lezioni

Materiale didattico

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

Risultati e Soluzioni

magistraleinformatica/alg2/algo2_11/start.txt · Ultima modifica: 04/10/2015 alle 10:07 (3 anni fa) da Roberto Grossi