AA490/IND - Algoritmi per Internet e Web: Indicizzazione e Ricerca nei Testi

Prof. Roberto Grossi

Anno Accademico 2007/2008
Corsi di Studio in Informatica
Università degli Studi di Pisa
I semestre (6 crediti)

AVVISI

• Appello per fuori corso: 5 marzo 2009 ore 16 presso lo studio del docente
• Risultati dell'appello del 24.09.2008:

  n.matr.  voto   giudiz.es.
  293207   20     +-+
  293746   20     +-+
  296647   18     ~-+
  

• Risultati dell'appello del 31.01.2008:

  n.matr.  voto   giudiz.es.
  418232   26     +~+
  405181   27     +++
  291815   23     +-+
  292870   22     +~~
  303100   28     +++
  277984   29     +++
  290006   28     +++
  232831   24     +-+
  

  Legenda:
  I tre simboli accanto al voto indicano il giudizio su ciascuno dei tre esercizi (in quell'ordine, ossia il primo simbolo è per il primo esercizio e così via). Il significato va interpretato secondo il seguente schema.

  • simbolo '+': l'esercizio è stato concettualmente risolto, eventualmente con sviste, ottenendo più del 65% del punteggio.
  • simbolo '~': l'esercizio è stato parzialmente risolto e si intravede un'idea di risoluzione, ottenendo tra il 40% e il 65% del punteggio.
  • simbolo '-': l'esercizio non è stato risolto oppure l'idea di risoluzione è sbagliata, ottenendo meno del 40% del punteggio.
  
  
• Risultati dell'appello del 10.01.2008:

  n.matr.  voto   giudiz.es.
  190751   24     +~+
  235250   27     ++~
  246341   22     +-+
  272045   28     ++~
  290728   22     ~+~
  290968   10     --~
  

• Risultati del compitino del 20.12.2007:

  n.matr.  voto   giudiz.es.
  224481   22     +-+
  232518   27     ++~
  232831   15     ~~-   es.1 vedi 242564
  235250   18     +-~
  238802   18     +~-
  242564   18     ~+-   es.1 vedi 232831
  246341   14     ~-~
  252430   27     +~+
  252603   24     ++-
  290455   28     ++~
  291815   18     ~~~   
  292870   10     --~
  303100   18     +~-
  

• Orario delle lezioni: martedi' 11-13 in aula O1, venerdi' 14-16 in aula B.

PROGRAMMA

• Introduzione al corso. Tecniche di ricerca e indicizzazione.
• Pattern matching esatto: automi, Knuth-Morris-Pratt, Boyer-Moore-Horspool, Aho-Corasick.
• Pattern matching con espressioni regolari: automi non-deterministici e scansione del testo.
• Pattern matching approssimato: distanze di Hamming e di edit, tabella di programmazione dinamica.
• Algoritmi di ricerca testuale con paradigma shift-and (agrep).
• Indici "word-based" di motori di ricerca: Liste invertite e algoritmi di interrogazione.
• Trie e ternary search tree.
• Indici "full-text": suffix tree e suffix array.

MATERIALE DIDATTICO

• [Gr07] R. Grossi, Dispense del corso (in parte), file PDF, 2007.
• [GI98] R. Grossi, G. F. Italiano, Rassegna su suffix tree (in parte), file PDF, 1998.
• [Gu02] A. Gullì. Web crawling e ranking. Lucidi powerpoint (2004), rassegna PDF(2002).
• [Gu97] D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Capitoli 5 e 7 (suffix tree e suffix array), Cambridge University Press, 1997.

• Altro materiale reso disponibile durante il corso (contattare il docente).

  ---

• Testi di alcuni esami precedenti: 20.12.01, 25.01.02, 12.02.02, 13.09.02, 18.12.02, 20.01.03, 10.02.03, 27.05.03, 20.06.03, 08.07.03, 18.09.03, 19.05.04, 01.06.04, 22.06.04, 30.05.05, 18.12.06, 20.12.07, 10.01.08.