September 21, 2017, Thursday

From BIMIB

Jump to: navigation, search

0708 - Analisi di Algoritmi (LS)

Questa è la home page del modulo "Analisi di Algoritmi" del corso della laurea specialistica in informatica "Tecniche di analisi e di verifica" - anno accademico 2007/08. Il docente di riferimento di questo modulo è Prof. Paola Bonizzoni.


Contents

Avvisi

  • Esame completato. Il corso è ufficialmente terminato.
  • Aggiunte le modalità di esame. La consegna è stata fissata per il 15 luglio 2008.
  • Aggiunti link a materiale riguardante le tecniche di manipolazione di bit in parole di memoria nel materiale del corso.
  • Cambiamento orario esercitazione. Come concordato durante la prima esercitazione è stata effettuata una modifica all'orario del corso. Dal 29 aprile, le esercitazioni si terranno il martedì dalle 9.30 alle 11.30 in aula U14-03 (T014).
  • Pubblicato un commento riguardante la discussione della prima esercitazione tra il materiale del corso.


Orario

Periodo: dal 07 apr 08 al 06 giu 08.

Lezione: Lunedì, ore 10.30-13.30, aula U6-37, Prof. Paola Bonizzoni.

Esercitazione: Dott. Yuri Pirola
fino al 22 aprile compreso: Martedì, ore 8.30-10.30, aula U6-23,
dal 29 aprile compreso: Martedì, ore 9.30-11.30, aula U14-03 (T014).

Nota: Controllare sempre l'orario ufficiale.


Programma

Il programma di riferimento del modulo comprende le seguenti voci:

  • Tecniche di analisi degli algoritmi. Algoritmi su grafi.
  • Algoritmi di approssimazione per problemi NP-difficili e accenni agli algoritmi probabilistici e randomizzati.
  • Applicazioni di algoritmi. I contenuti varieranno di anno in anno e riguarderanno:
    1. algoritmi per la clusterizzazione di dati, la compressione dei dati, strutture dati di indicizzazione: trie, suffix tree e suffix array,
    2. algoritmi per motori di ricerca.


Lezioni svolte

  • Introduzione agli algoritmi di ricerca di testo nel Web:
    1. string matching mediante automi a stati finiti (14-15 aprile);
    2. algoritmo Knuth-Morris-Pratt (21 aprile);
    3. algoritmo Boyer-Moore (29 aprile);
    4. matching di espressioni regolari (5 maggio);
      • costruzione dell'automa non deterministico per il riconoscimento di espressioni regolari (12 maggio);
      • utilizzo nella ricerca di pattern definiti mediante espressioni regolari (12 maggio);
    5. introduzione ai suffix-tree e ai suffix-tree generalizzati (6-13 maggio):
      • costruzione di suffix tree e suffix tree generalizzati;
      • matching di pattern su una o più stringhe;
      • estrazione della più lunga sottostringa comune a più stringhe in tempo lineare;
    6. string matching tramite metodi aritmetici:
      • manipolazione di singoli bit all'interno di parole di memoria (13 maggio);
      • metodo dello "shift-and" (20 maggio);
      • metodi di bit counting (26 maggio);
    7. uso delle espressioni regolari nel linguaggio Perl (19-26 maggio, Dott. Raffaella Rizzi).
  • Analisi ammortizzata:
    1. analisi aggregata della complessità computazionale di tabelle dinamiche (22 aprile);
    2. analisi della complessità computazionale di tabelle dinamiche con il metodo del banchiere e con il metodo del potenziale (28 aprile);
    3. analisi della complessità computazionale della procedura KMP-compute-prefix-function con il metodo del potenziale (28 aprile).


Modalità di esame

L'esame consiste in una prova scritta individuale riguardante i contenuti del corso. Il testo di tale prova è stato inviato agli indirizzi mail raccolti durante il corso. Il termine improrogabile di consegna è fissato per il 15 luglio 2008. Se uno studente interessato non avesse ancora ricevuto il testo è pregato di comunicarlo quanto prima a Yuri Pirola.


Materiale del corso


Riferimenti