Algoritmica per il web

A.A. 2024/2025
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'insegnamento si propone di mettere lo studente a contatto con tecniche avanzate relative alla raccolta di grandi collezioni documentali e alla costruzione di motori di ricerca, con particolare attenzione al web e ai suoi meccanismi di ranking.
Risultati apprendimento attesi
Lo studente dovrà essere in grado di progettare e implementare un crawler e un indicizzatore di testi di grandi dimensioni, con particolare attenzione agli algoritmi utilizzati per ordinare i risultati.
Corso singolo

Questo insegnamento può essere seguito come corso singolo.

Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre

Programma
Il corso si propone di mettere lo studente a contatto con tecniche avanzate relative alla raccolta di grandi collezioni documentali e alla costruzione di motori di ricerca, con particolare attenzione al web e ai suoi meccanismi di ranking. Il corso richiede una conoscenza delle tecniche algoritmiche di base e dei protocolli di rete. Verrà trattato un sottoinsieme degli argomenti seguenti, anche in base all'interesse degli studenti:

Anatomia di un motore di ricerca e tecniche di indicizzazione.
Raccolta di informazioni: problemi algoritmici, tecnici e sociali nella creazione di crawler.
Strategie di visita a confronto.
Struttura globale del web e strumenti algoritmici per la sua analisi.
Rappresentazione del grafo del web: problemi di compressione.
Crawler paralleli e distribuiti. Tecniche di hashing coerente.
Centralità di reti: vicinanza, centralità armonica, Katz, PageRank, autovettore dominante, ecc.
Tecniche per la costruzione di indici inversi.
Metodologie per la costruzione di indici distribuiti di grandi dimensioni.
Metodologie per la costruzione di dizionari di grandi dimensioni: tabelle di hash minimale perfetto ordinate, dizionari di prefissi, compressione lessicografica.
Codici istantanei per la compressione di indici: unario, Elias γ, Elias δ, Golomb, ecc.
Rappresentazione di Elias-Fano e indici quasi-succinti.
Tecniche di ranking testuali (TF/IDF, BM25, LSI, coseno, ecc.).
Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
Quantizzazione dei prodotti vettoriali e database vettoriali.
Prerequisiti
Matematica discreta, algebra lineare, programmazione, algoritmi.
Metodi didattici
Lezioni frontali.
Modalità di verifica dell’apprendimento e criteri di valutazione
Oral exam.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Turni:
Turno
Docente: Vigna Sebastiano