Algoritmi e Strutture Dati: internet e web

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I111

Crediti:

Semestre:

Sigla:

ASW

Docente

Roberto Grossi

Tel. 0502212793

Prerequisiti

Conoscenze di base degli algoritmi e delle strutture di dati, dell'architettura degli elaboratori, di calcolo delle probabilità, e delle reti di calcolatori.

Obiettivi di apprendimento

Esporre le basi teoriche e le strutture dati fondamentali su cui poggiano alcuni degli algoritmi utilizzati in Internet e nel World Wide Web, illustrando alcuni esempi di algoritmi impiegati nei sistemi software attualmente disponibili.

Descrizione

Un crescente numero di applicazioni informatiche vedono il World Wide Web e Internet come una sorgente di informazioni e/o una risorsa di calcolo su cui progettare i propri strumenti software. Il corso si propone di esporre le basi teoriche, le tecniche di base e le strutture di dati fondamentali su cui poggiano alcuni degli algoritmi utilizzati in Internet, in particolare per:

Gestione e spedizione efficiente di pagine Web (Prof. L. Pagli)
Protezione crittografica dell'informazione (Prof. F. Luccio)
Indicizzazione di testi e motori di ricerca (Prof. R. Grossi)
Compressione e motori di ricerca avanzati (Prof. P. Ferragina)

Il corso è diviso in quattro parti di 10 ore ciascuna. Si prevede di illustrare alcuni esempi di algoritmi impiegati nei sistemi software attualmente disponibili su Internet.

English Description

To present the theoretical principles and the fundamental data structures on which Internet algorithms are based, with reference to:

Page management and routing in the Web.
Cryptographic protection.
Text indexing and search engines.
Compression and advanced search engines.

To illustrate some examples of algorithms used in the software systems presently available for Internet.

Programma

Parte I - Gestione e spedizione efficiente di pagine Web (L. Pagli - 10 ore)
1. Ripasso sulle gerarchie di memoria e sui problemi di paginazione. Analisi di competitività.
2. Algoritmi randomizzati. Sequenze di richieste con località di riferimenti.
3. Web caching.
4. Internet routing.
5. Altri tipi di routing.
Parte II - Protezione crittografica dell'informazione (F. Luccio - 10 ore)
1. Ripasso sulle classi P e NP e sui problemi NP-ardui. Introduzione alla crittografia. One-time pad.
2. Data Encription Standard.
3. Cifrari a chiave pubblica e RSA.
4. RSA (continuazione).
5. Applicazioni: SSL e Smart Card.
Parte III - Indicizzazione di testi e motori di ricerca (R. Grossi - 10 ore)
1. Modelli e parametri per le informazioni testuali.
2. Strutture di dati per la costruzione di indici testuali (I).
3. Strutture di dati per la costruzione di indici testuali (II).
4. Algoritmi di ricerca per la risoluzione delle interrogazioni.
5. Gestione delle ricerche nel Web: ranking, crawling, ecc.
Parte IV - Compressione e motori di ricerca avanzati (P. Ferragina - 10 ore)
1. Entropia: definizione e teorema principale. Compressione di interi.
2. Run-length encoding e Move-to-Front encoding. Huffman e Arithmetic coding.
3. Compressione Lempel-Ziv (LZ77, LZ78, LZW): gzip.
4. Compressione Burrows-Wheeler: bzip.
5. Compressione e liste invertite: Altavista vs. Glimpse.

Ore lezione:

Ore esercitazione:

Bibliografia

Dispense e articoli distribuiti dai docenti.
R. Baeza-Yates, B. Ribeiro-Neto. Modern Information Retrieval. ACM Press e Addison-Wesley, 1999.
D. Salomon. Data Compression: the Complete Reference. Springer Verlag, 1997.
I. H. Witten, A. Moffat, T. C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers, second edition, 1999.

Modalità di esame

Scritto e orale