Strumenti Utente

Strumenti Sito


magistraleinformatica:alg2:algo2_10:start

Anno 2010-2011

Docenti: Roberto Grossi, Linda Pagli, Nadia Pisanti

Avviso

Correzione compiti e verbalizzazione venerdì 18 febbraio ore 11:00 e lunedì 28 febbraio ore 11:00 presso lo studio della prof.ssa Pagli.

Obiettivi di apprendimento

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.

Programma

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
  • Matrice dei suffissi
  • Albero dei suffissi
  • Algoritmi di pattern matching
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

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

Risultati e Soluzioni

  • 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
magistraleinformatica/alg2/algo2_10/start.txt · Ultima modifica: 24/11/2015 alle 09:52 (3 anni fa) da Roberto Grossi