Dettagli sull'Insegnamento per l'A.A. 2017/2018

Le informazioni che state leggendo si riferiscono all'anno accademico 2017/2018. Per questo molti collegamenti non sono disponibili e i dati potrebbero essere incompleti. Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo. Per consultare le informazioni relative ad altri anni accademici, usa la lista in fondo a questa pagina.

A. Accademico:

2017/2018

Nome:

Web Algorithms / Web Algorithms

Tipo:

Modulo

Corso principale:

Distributed Systems and Web Algorithms / Distributed Systems and Web Algorithms

Informazioni

Codice:

DT0167

SSD:

INF/01

Crediti:

: Master Degree in Computer Science 6 CFU (b)

Periodo:

1^st semester

Erogazione:

Master Degree in Computer Science 1^st anno curriculum NEDAS Compulsory
Master Degree in Computer Science 1^st anno curriculum SEAS Elective
Master Degree in Computer Science 1^st anno curriculum UBIDIS Compulsory

Lingua:

Inglese

Docenti:

Guido Proietti

Mutua:

Algoritmi e Strutture Dati II

Prerequisiti

CONOSCENZE : fondamenti di programmazione, matematica discreta, algoritmi e strutture dati, architetture degli elaboratori, lettura e comprensione in lingua inglese CAPACITA' : capacità di integrazione dello studio in aula con lo studio personale, capacità di interazione con il docente in aula in modo da originare momenti comuni di confronto

Obiettivi

Conoscenza di tecniche algoritmiche avanzate, capacità di individuazione, formalizzazione e risoluzione di problemi di ottimizzazione, concetto di approssimazione, conoscenza delle strategie di web search e sponsored web search nei motori di ricerca, capacità di collaborazione per la realizzazione progetti applicativi di gruppo

Sillabo

Richiami di complessità ed intrattabilità. Problemi di ottimizzazione. Algoritmi di approssimazione.
Tecniche algoritmiche: greedy. ricerca locale, programmazione dinamica e programmazione lineare.
Schemi di approssimazione polinomiali (PTAS) e pienamente polinomiali (FPTAS).
Indici di centralità e prestigio nelle reti sociali
Web search: Pagerank, Topical Pagerank, TrustRank, Hubs e Authorities
Sponsored web search: matching markets e market clearing prices, aste, meccanismi VCG e GSP.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Acquire knowledge of advanced algorithmic techniques for NP-Hard optimization problems. In particular, the student will have mastery command of main algorithmic (approximation) techniques like greedy, local search, dynamic programming, linear programming: Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS). Moreover the student will acquire knowledge on the basic centrality and prestige indices in social networks, on the main popularity indices for ranking pages in web search and finally of matching markets, auctions and the most important mechanisms adopted for the ranking and payment of sponsored search links.
Acquire the ability of abstracting models and formal algorithmic problems from real computational problems, understanding the degree of approximability and designing efficient algorithmic solutions.
Acquire autonomy in individuating, formalizing and understanding the degree of approximability of real computational problems and identify independently their most efficient solutions.
Being able to understand complex algorithmic solutions and to formal proving performances of their algorithmic solutions for complex computational problems.
Acquire the ability of understanding the ranking strategies adopted by search engines in web search and sponsored web search.
The course aims to develop in graduate students competencies and abilities necessary in their future studies and/or works, especially with respect to doctoral studies and in general to any research activity on algorithmic and web search topics.

Testi di riferimento

Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-540-65431-3
Jure Leskovec, Anand Rajaraman and Jeff Ullman, Mining of Massive Datasets , Stanford University. 2011. ISBN: 9781107015357 http://infolab.stanford.edu/~ullman/mmds/book.pdf
Soumen Chakrabarti, Mining the Web – Discovering Knowledge from Hypertext Data , Morgan Kaufmann. 2003. ISBN: 9781558607545
David Easley and Jon Kleinberg, Networks, Crowds, and Markets , Cambridge University Press. 2010. ISBN: 9780521195331 https:
www.cs.cornell.edu/home/kleinber/networks-book/

Modalità d'esame

Prova scritta ed un'eventuale discussione orale sulla prova scritta

Risorse Internet

Homepage:

http://www.di.univaq.it/flammini/didattica.htm

Aggiornamenti alla pagina del corso

Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:

Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.

Ultimo aggiornamento delle informazioni sul corso: 20 dicembre 2016, 17:55