Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- air:start [01/12/2008 alle 17:30 (17 anni fa)] – Paolo Ferragina
+++ air:start [26/03/2010 alle 15:08 (15 anni fa)] (versione attuale) – peppe
@@ Linea 1: / Linea 1: @@
 ====== Algoritmi per Information Retrieval [AA293] ======
-**Docente**: [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]]
-===== Informazioni Generali =====
-  * **Impegno:** 6 CFU tra teoria ed esercitazioni.
-  * **Orario delle lezioni:** Lunedì ore 16-18 (aula C1), Mercoledì ore 16-18 (aula C1).
-  * **Ricevimento studenti:** Lunedì 9-12 e dopo ogni lezione.
-===== Obiettivi del corso =====
-Studio, progetto e analisi di sistemi software efficienti ed efficaci per l’Information Retrieval nell’ambito di collezioni di documenti testuali, html e semi-strutturati (p.e. XML). Questo studio si concentrerà su tutti i componenti princiali di un moderno motore di ricerca: Crawler, Parser, Compressor, Indexer, Query resolver, Ranker. Esamineremo le soluzioni algoritmiche correntemente adottate per ciascuno di essi in maniera approfondita, valutando le loro prestazioni e i loro limiti computazionali. Discuteremo anche i fondamenti pratici e teorici per l’organizzazione e l’analisi dei sistemi di IR, con valutazione delle loro prestazioni. Infine analizzeremo numerose altre tecniche algoritmiche per il: data streaming, data compression, data indexing, data sketching, data searching, e (cenni di) text mining.
-===== Modalità di esame =====
-L'esame consiste di una prova scritta, contenete domande sul programma del corso, e di un colloquio di approfondimento.
-Vi allego un [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Vecchi_testi_AIR.pdf|insieme di compiti]] relativi a prove di anni precedenti. Alcuni quesiti potrebbero riferirsi ad argomenti non trattati quest'anno, nel caso contattatemi!
-==== Prossimi Appelli ====
-^ Data ^ Ore ^ Aula ^ Prova ^
-| 13 Gennaio '09 | 14:30 | B1 | [[|testo]] |
-| 3 Febbraio '09 | 09:30 | B e E | [[|testo]] |
-===== Libri di testo =====
-  * I.H. Witten, A. Moffat, T.C. Bell. //Managing Gigabytes//. Morgan Kaufmann, 1999 (second edition).
-  * S. Chakrabarti. //Mining the Web: discovering knowledge from hypertext data//. Morgan Kaufmann, 2003.
-  * Articoli forniti dal docente (in //attach// a ogni lezione)
-=====  Programma del corso =====
-^ Argomento ^ Riferimenti ^
-| Introduzione al corso: grandi collezioni di dati, motori di ricerca e il Web 2.0. Una //nuova// algoritmica?  |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Google_distributed.pdf|Google]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Economist.pdf|The Economist]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/time_2006a.pdf|Time (parte a)]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/time_2006b.pdf|Time (parte b)]] |
-| Modelli di calcolo: External-memory model, Data Streaming model, Cache-Oblivious model | slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/0-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/0-Lecture.pps|pps]] |
-|Alcuni problemi interessanti: Max subarray, Elementi di max-frequenza, DB //vs// IR-approach al progetto di un motore di ricerca|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Bentley.pdf|Bentley]]|
-|Il problema dell'ordinamento su grandi collezioni di dati: single //vs// multiple disks, disk striping, multi-way merge-sort, distribution sort, permuting //vs//sorting, limiti inferiori| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/GreedSort.pdf|Greed Sort]] (saltare i dettagli del ColumnSort e le dimostrazioni), [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Libro_Vitter.pdf|Libro Vitter]] (saltare il dettaglio delle formule 5.2 e 5.4),[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LowerBound.pdf|limiti inferiori]]|
-| Nozione di Entropia: ordine zero e ordine k. Codici univocamente decodificabili e loro ottimalità (cenni ai Teoremi di Shannon)|  |
-| Huffman code: definizione, ottimalità, variante canonica| Sezioni 2.1-2.3 di Managing-Gigabytes **tranne** "Computing Huffman code lengths", e slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/1-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/1-Lecture.pps|pps]]|
-| CGrep: Byte-Aligned & Tagged Huffword, Ricerca sul compresso |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Huffword.pdf|CGrep]]|
-|Alcuni algoritmi di pattern-matching: Karp & Rabin (ricerca esatta e //fingerprinting//), Agrep  (ricerche regex e approssimate)| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/KR.pdf|KR]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Agrep.pdf|AGrep]]|
-| Un semplice compressore: ordina simboli per frequenza e codifica i loro ranghi (anche //(s,c)-dense codes// su slides)|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/IntegerCodes.pdf|codes]]|
-|Compressione in streaming: Move-to-Front, Run-Length encoding (RLE)|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/MoveToFront.pdf|MTF]]|
-| Arithmetic coding: statico, dinamico e schema PPM | Sezione 2.4 e 2.5 (Prediction by Partial Matching) di Managing-Gigabytes, e slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/2-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/2-Lecture.pps|pps]]|
-| Dictionary-based compression: LZ77, LZ78, LZW. | Sezione 2.6 di Managing-Gigabytes, e slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/3-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/3-Lecture.pps|pps]]|
-| Burrows-Wheeler Transform: properietà, costruzione e inversione. Il compressore Bzip2. | Sezione 2.5 (Block-sorting compression) di Managing-Gigabytes, e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/BW.pdf|articolo originale]]|
-| Il grafo del Web: proprietà e compressione. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/4-Lecture.pdf|slides]]|
-| Compressione e Sincronizzazione di (collezioni di) file | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/5-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/survey_rsync.pdf|rsync]] |
-| Data Sketching e Data Streaming: Bloom Filter, Spectral Bloom Filter, Count Min Sketch, e loro applicazioni| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/6-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/BloomFilterSurvey.pdf|Bloom Filter]],  [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/CMS.pdf|Count Min Sketch]]|
-| Full-indexing: definizione, suffix tree, suffix array, lcp array. Text mining.| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/7-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/TextIndexing.pdf|Text Indexing]]|
-| Motori di Ricerca: introduzione, struttura, e crawling. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/8-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/SearchEngines.pdf|Struttura]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/chap2.pdf|Crawling]]|
-| Motori di Ricerca: parsing, modelli statistici dei testi (Zipf Law, Heaps Law, Luhn). | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/9-Lecture.pdf|slides]]|
-| Motori di Ricerca: Inverted Lists = Dizionario + Postings. Indicizzazione del dizionario. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/10-Lecture.pdf|slides]]|
-| Motori di Ricerca: Memorizzazione dei Postings e risoluzione di Query. |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/11-Lecture.pdf|slides]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/InvertedFiles.pdf|articolo]] |
-| Motori di Ricerca: Text-based ranking, Link-based ranking. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/12-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/chap7-chakrabharti.pdf|articolo]] |
-| Motori di Ricerca: Qualità dei risultati, Visualizzazione snippets e loro clustering. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/13-Lecture.pdf|slides]]|
-| Miscellanea: Latent Semantic Indexing e Random Projections. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/14-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LatentSemanticIndexing.pdf|articolo]] |
-| Miscellanea: Web SPAM, Web Advertising. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/15-Lecture.pdf|slides]]|
+La pagina è stata spostata [[magistraleinformatica:ir:|qui]].