Dettagli sull'Insegnamento per l'A.A. 2013/2014
Nome:
Algoritmi per Sistemi Distribuiti / Algorithms for Distributed System
Informazioni
Crediti:
: Laurea in Informatica 6 CFU (b)
: Laurea Magistrale in Informatica 6 CFU (b)
Erogazione:
Laurea in Informatica 3° anno curriculum Generale Opzionale
Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio
Lingua:
Inglese
Prerequisiti
Conoscenza degli argomenti trattati nei corsi di matematica discreta e di algoritmi e strutture dati.
Obiettivi
Il corso fornisce gli elementi fondamentali di teoria e progettazione degli algoritmi in sistemi distribuiti, ovvero in sistemi in cui i soggetti computazionali coinvolti sono molteplici e possono perseguire o meno una strategia condivisa. Il corso spaziera' quindi dalla presentazione dei classici algoritmi distribuiti per il problema dell'elezione del leader in sistemi cooperativi, fino ad arrivare alla teoria degli equilibri strategici e agli algoritmi di crittografia, strumenti indispensabili per comprendere le funzionalita' dei sistemi distribuiti non cooperativi, quali la rete Internet.
Sillabo
- Algorithms for COOPERATIVE Distributed Systems (DS) 1. Leader Election 2. Minimum Spanning Tree 3. Maximal Independent Set
- Algorithms for UNRELIABLE DS: The consensus problem
- Algorithms for CONCURRENT DS: Mutual exclusion
- Security aspects of DS: Elements of cryptography
- Algorithms for NON COOPERATIVE (i.e., strategic) DS 1. Equilibria in networks 2. Algorithmic mechanism design
Descrittori di Dublino
Alla fine del corso, lo studente dovrebbe
- By the end of this module students will be able to: 1) understand the difference between a centralized and a distributed algorithm; 2) analyze the resources (space and time) needed by a distributed algorithm; 3) known efficient algorithms for basic computational distributed problems (leader election, consensus, etc.); 4) understand the difference between a canonical and a strategic distributed system.
- The aim is to make the student capable of abstracting models and formal algorithmic problems from real distibuted computational problems, and designing efficient algorithmic solutions.
- Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
- The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
- The course aims to develop in graduate students competencies and abilities necessary in their future studies, especially with respect to doctoral studies on algorithmic topics.
Testi di riferimento
- P. Ferragina e F. Luccio, Crittografia , Bollati Boringhieri.
- H. Attiya e J. Welch, Distributed Computing , Wiley.
- C. Montet e D. Serra, Game Theory & Economics , Palgrave.
Modalità d'esame
Prova parziale scritta + Prova finale orale (eventualmente limitata alla seconda parte del corso nell'eventualita' che sia stata superata con successo la prova parziale).
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 marzo 2014, 13:06