Strumenti Utente

Strumenti Sito


magistraleinformatica:alg2:algo2_09:start

Algoritmica 2

Docenti: Paolo Ferragina, Roberto Grossi, Fabrizio Luccio, Linda Pagli, Nadia Pisanti

News

ATTENZIONE: Corona e Lima hanno un risultato diverso dalla prima pubblicazione dei risultati del compito del 1/2/2010

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

  • PROBLEMI DIFFICILI E APPROSSIMAZIONE dispensa_1.pdf
    • 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.
  • ALGORITMI RANDOMIZZATI alg-random.pdf
  • DATA COMPRESSION: 07_mg-partchap2.pdf
    • Non studiare “Computing Huffman code lengths” e “Maintaining cumulative counts”
    • Studiare anche “Huffman canonico”
    • Esempio per BWT
    • Dimostrazione performance di MTF (Teo 1 e Cor 1)
  • BLOOM FILTER survey e slides
  • HASH UNIVERSALE E HASH PERFETTO clr-hash.pdf
  • MOTORI DI RICERCA (cenni, note)
  • ALGORITMI ON LINE
    • MOVE TO FRONT mtf.pdf
    • Algoritmi per il problema del paging paging.pdf
    • La dimostrazione dell'analisi competitiva dell'algoritmo DG è dubbia anche nell'articolo originale, non è da studiare.
    • WEB-Caching, studiare paragrafo 3 e 4 gds.pdf
  • HASHING DISTRIBUITO
  • Consisitent Hashing
  • Dalla tesi di master di Daniel M. Lewinprima parte

seconda parte. Studiare fino all'enunciato del teorema 2.2.3. Poi i lemmi 2.2.5 e 2.2.6.

Risultati e Soluzioni

Compitino del 17/12/2009 Soluzione

Primo Appello (11/1/2010) Soluzione

Secondo Appello dell'1/2/2010 Testo

Terzo Appello del 2/6/2010 Testo

Quarto Appello del 22/6/2010 Testo

Quinto Appello del 13/7/2010 Testo

Sesto Appello del 7/9/2010

magistraleinformatica/alg2/algo2_09/start.txt · Ultima modifica: 04/10/2015 alle 10:09 (9 anni fa) da Roberto Grossi