AA046 - Algoritmi per Internet e Web: Indicizzazione e Ricerca nei Testi

Prof. Roberto Grossi

Corsi di Studio in Informatica
Università degli Studi di Pisa

AVVISI

Appello del 12.9.05: Verbalizzazione dei voti durante la settimana del 19-23 settembre presso la mia stanza. Risultati:

ARRI A.        30
BELFIORI E.    25
CAMPOSEO G.    21
FINOCCHIARO L. 25
FUSCHETTO A.   24
GIAMMARINO F.  24
LATRONICO M.   18

Appello del 18.7.05: Orali fissati per il 20 luglio 2005 alle ore 9:30 presso la mia stanza. Risultati:
```
BERTOLUCCI M. 18
LATRONICO M.  20
PFEIFHOFER S. 24 
VENTURNI R.   21
```
Appello del 27.6.05: Testo del compito. Orali fissati per l'8 luglio 2005 alle ore 9 in aula B1. Contattare il docente per casi urgenti in cui si voglia fare l'orale prima del 30 giugno. Risultati:
```
CAROVANO N.   24
DI STEFANO A. 20 
LATRONICO M.  18 (da confermare con l'orale)
VALDES F.    INS
VICHI M.      25
```
Appello del 6.6.2005: testo e risultati. Orali fissati per Venerdì 10 Giugno ore 9:00 presso l'aula L1.
Compitino del 30.5.2005: testo e soluzioni, soluzioni pervenute, risultati.
Gli appelli sono consultabili in linea.

PROGRAMMA

Introduzione al corso. Anatomia di un motore di ricerca e tecniche di indicizzazione.
Rank di pagine Web: PageRank, HITS e SALSA.
Tecniche algoritmiche per Web Spider.
Indici "word-based" di motori di ricerca: Liste invertite e algoritmi di interrogazione.
Pattern matching esatto: automi, Knuth-Morris-Pratt, Boyer-Moore-Horspool, cenni di 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 "full-text": trie, suffix tree e suffix array.

MATERIALE DIDATTICO

[Gr02a] R. Grossi, Introduzione al corso (in inglese), lucidi in formato PDF, 2002.
[Gr02b] R. Grossi, Dispense del corso (in parte), file Postscript compresso con gzip, 2002.
[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.
[BP98] S. Brin and L. Page. The anatomy of a large scale hypertextual web search engine. Proc. 7th WWW, Australia, 1998. Rapporto tecnico.
[Kl99] J. Kleinberg, Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). (cached manuscript).
[SEO02] Search Engine Optimization Support Forums, PageRank Uncovered, 2002 (segnalato da A. Gullì).
[NYT04] New York Times, articolo su Google, 2004 (segnalato da A. Gullì).
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.