Comunicazioni
APPELLI DI SETTEMBRE07-09-2018 12:36SI AVVISANO tutti gli studenti interessati che e' possibile da oggi prenotarsi su delphi per gli appelli autunnali. SI RICHIEDE cortesemente ad ogni studente interessato di inviare a clementi@mat.uniroma2.it una email in cui si specifica *quali* moduli intende fare nell'appello da lui prenotato.
|
MODULO I: APPELLO DI GIUGNO 201814-06-2018 19:12Scusandomi per la situazione, informo gli studenti interessati che potranno svolgere la prova di esame relatica al I modulo del corso il giorno martedi 19-06-2018 alle ore 15.00 nel mio uffcio a SOGENE. Prego gli studenti interessati di inviarmi una email entro domenica per prenotare l'esame. Inoltre li invito a seguire questo sito nei prossimi giorni per eventuali comunicazioni sulla situazione medica. Andrea Clementi |
CAMBIAMENTO AULA MOD. III06-06-2018 14:32Si informa che la lezionie di giovedì 07/06 del prof Trevisan avra' luogo dalle 17.15 alle 18.30 in AULA T5.
|
III modulo: SITO WEB03-05-2018 16:51Il prof. Trevisan ha aperto un sito relativo al modulo di ADRC che insegnera' in cui si possono trovare tutte le informazioni ed il materiale didattico relativi al suddetto modulo. Il sito e' :
https://people.eecs.berkeley.edu/~luca/bwca18/ |
III MODULO: PROF. TREVISAN II10-04-2018 11:49Si informano gli studenti che il modulo del Prof. Trevisan di ADRC avra' inizio GIOVEDI 17 MAGGIO con i seguenti orario E luogo:
- Lunedì 11/13 aula 7PP2;
NOTA IMPORTANTE: Si informano gli studenti del II anno o fuoricorso che, al fine di non creare problemi di collisione con i corsi del II anno, essi *possono* anche portare come programma di esame quello dello scorso anno accademico che non prevede il modulo del Prof. Trevisan. E' sufficiente comunicarlo via email al Prof. Clementi o in sede di esame. |
ESITO ESONERO DEL 01/201815-01-2018 11:33RISULTATI ESONERO (Gli studenti che hanno consegnato il compito ma che non appaiono in questa lista hanno riportato un risultato non sufficiente)
MATRICOLA/NOME/NICKNAME SCORE
0217260 ............................... 18/30
0246425 ................................ 28/30
BONAVITA D. ........................ 25/30
0258412 .......................... 20/30
0202133 ........................... 18/30
|
ESONERO 11/01/1811-01-2018 10:25L'esonero avra' luogo alle ore 14.30 in aula 7. Si pregano gli studenti di arrivare 10 minuti prima per effettuare le operazioni iniziali in anticipo.
|
KOLMOGOROV MEETS TURING 201716-11-2017 11:28Per gli studenti della LM che vogliono farsi un'idea delle applicazioni più avanzate dei metodi ed degli algoritmi probabilistici in Computer Science, c'e' un'ottima occasione a ROMA 3. La partecipazione e' gratuita ma, chi decide di venire, e' cortesemente pregato di inviare una email ad Andrea Clementi. Friday December 1st 2017, Roma Tre University Kolmogorov meets Turing 4th edition,
a workshop on probabilistic methods for the analysis of stochastic processes and randomized algorithms.
*********************************
Aula F, Dipartimento di Matematica e Fisica, Roma Tre
Largo S. Murialdo 1, 00146 Roma
14:30-15:20
Chris Schwiegelshohn
PCA for k-means: Preserving Cost, Clusters, And Beyond
|
Lezioni
| 18 | 07-12-2017 La dinamica del 3 majority Analisi in media del suo tempo di completamento |
| 17 | 04-12-2017 Il modello Gossip Il problema del consenso binario Dinamiche di consenso il voter model Analisi in media del voter model |
| 16 | 30-11-2017 Modifica del protocollo select ed analisi corretta Risultato negativo: il lower bound deterministico (senza prova) l'analisi del protocollo BGI randomizzato IL gap esponenziale |
| 15 | 27-11-2017 Protocolli di Broadcast per Radio Networks efficienti nel caso di reti sparse. Le famiglie selettive Il protocollo di Broadcast basato sulle famiglie selettive Una prima analisi che non funziona |
| 14 | 23-11-2017 IL protocollo Round Robin con D e/o n sconosciuti: indovinare i parametri in modo efficiente (ricerca binaria) Analisi del completamento e delle terminazione
Aspetti negativi del Round Robin |
| 13 | 20-11-2017 Analisi della correttezza, convergenza e terminazione del protocollo Round Robin. Assunzioni sulla conoscenza dei parametri iniziali D e N della rete. Analisi del tempo di completamento e del numero di trasmissioni/lavoro di un nodo |
| 12 | 16-11-2017 IL problema del Broodcast sulle Radio Networks. Risultati negativi per il protocollo Flooding Un primo algoritmo basato sul Round Robin |
| 11 | 13-11-2017 IL Modello Radio Networks: Introduzione, esempi, il problema dell'Interferenza. Differenze con il modello link-based |
| 10 | 09-11-2017 La Leader Election su un anello: La tecnica ''Controlled Distance'' in fasi Il protocollo Controlled Distance Correttezza e msg complexity Un semplice protocollo per Meshes Considerazioni finali per la Leader Election |
| 9 | 06-11-2017 Il problema dell'elezione di un Leader Condizioni Iniziali Risultati di impossibilita' Condizione: Unique IDs Schemi di pìrotocolli per topologie generali Leader Election su anelli Due protocolli semplici ma non ottimali: All-to-All e All-to-All modificato Analisi della correttezza e msg complexity |
| 8 | 02-11-2017 Il problema della DFS in distribuito condizioni iniziali Un protocollo di Traversal strettamente sequenziale Una sua variante ''parallela'' Correttezza e Msg complexity Considerazioni nel caso Multiple Inititators |
| 7 | 30-10-2017 IL problema dello Spanning Tree Distribuito Analsisi del Problema e condizioni iniziali Unique Initiator IL protocollo Shout e Shout+ Risultati di impossibilita' nel caso multiple initiators |
| 6 | 26-10-2017 IL protocollo HyperFlood su Hypercube Analisi della correttezza Analisi della msg complexity |
| 5 | 23-10-2017 Il problema del Wake-Up Condizioni ed ipotesi Un protocollo ottimale analisi della msg complexity in funzione del numero di initiators Reti sparse, scalable, efficienti La struttura ad Hypercube |
| 4 | 16-10-2017 Verifica dell'analisi della message complexitiydi FLOOD rispetto agli archi Le tecniche di Lower Bound nei sistemi distribuiti: l'ambiente e la localita'. Un lower bound banale per il Broadcast Un lower bound ottimo per il Broadcast: dimostrazione formale |
| 3 | 12-10-2017 Il protocollo FLOOD: 2 versioni Analisi e dimostrazione della correttezza La Message complexity : analisi con due approcci diversi l'ideal time del protocollo
|
| 2 | 05-10-2017 Il modello di calcolo distribuito. Le entita' locali: i nodi La comunicazione: i messaggi Le azioni locali Gli eventi I protocolli I concetti di Task, Processo, stato/configurazione del sistema Correttezza di un Protocollo La message complexity Sistemi asincroni e sincroni Le restrizioni standard Esempio di task: il Broadcast
|
| 1 | 02-10-2017 - Presentazione del Corso - Collocazione del corso rispetto alla Laurea Magistrale - Informazioni generali - Introduzione informale ai modelli distribuiti di calcolo ed agli algoritmi distribuiti - L'esempio degli alunni in classe |
Materiale didattico
Materiale didattico relativo al Modulo del Prof. Clementi |  |
Articoli sul modello Gossip relativo alle ultime lezioni del Prof. Clementi | |
Informazioni
| Anno accademico | 2017-2018 |
|---|---|
| Crediti | 9 |
| Settore | INF/01 |
| Anno | 1 |
| Semestre | 1 |
| Propedeuticità | Nessuna |
Programma
Il corso quest'anno avra' un'importante novita'.
Oltre ai due moduli standard di:
a) Calcolo Distribuito (Prof. Clementi) b) Teoria Algoritmica dei Giochi (Dr. Gualà)
vi sara' un ulteriore modulo (di circa 10 ore di lezione) (Modulo c) che verra' svolto dal Prof. Luca Trevisan che sara' Visiting Professor nel nostro Dipartimento in cui verranno trattati argomenti fondamentali dell'analisi di grafi di grandi dimensioni. Luca Trevisan è full professor all'Università di Berkeley (CA - USA) e Senior Scientist al Simons Institute for the Theory of Computing. https://people.eecs.berkeley.edu/~luca/ Il Prof. Trevisan rappresenta uno dei più importanti scienziati in Theoretical Computer Science in campo internazionale. Questa terza parte verrà erogata nel mese di maggio 2018 e sarà parte integrante del corso ADRC.
L'esame del corso, pertanto, sarà strutturato in due parti. Negli appelli invernali (febbraio 2018) vi sarà un test intermedio sui moduli (a) e (b), mentre in tutti gli appelli successivi, gli studenti potranno dare l'esame (ed i test relativi) su tutti e tre i moduli (a,b, e c).
Il modulo (a) presenta i principi fondamentali del calcolo distribuito sia da un punto di vista dei modelli di comunicazione/computazione più importanti che per quanto riguarda i metodi algoritmici fondamentali per tali modelli. L'obiettivo formativo e' quello di fornire degli strumenti efficienti e rigorosi per il Problem Solving algoritmico in cui, rispetto ai corsi algoritmici della triennale, per la prima volta le entità computazionali (agenti) sono molteplici ed interagenti.
Il modulo (c) il prof. Trevisan introdurra' importanti tecniche di analisi e progettazione di algoritmi per problemi di ottimizzazione e/o detection su grafi di grandi dimensione. In particolare, vista la grande dimensione dei dati, verranno studiate tecniche di natura statistica che permettono l'analisi delle performance non nel ''worst-case''.
Modulo (c) (in inglese - versione preliminare) Worst-case analysis sometimes overestimates the difficulty of certain problems in practice. In this course we will review more refined methods for the analysis of algorithms, including average-case analysis for random instances, analysis of distributions with a "planted" solution, semi-random models which combine random and adversarial choices, and machine learning problems in which the input is a collection of iid samples from an arbitrary unknown distribution. We will conclude with a brief overview of the theory of average-case complexity, and the evidence that we have that certain problems remain hard even when analyzed with respect to natural classes of distributions. Here is a tentative list of topics that we will cover:
|
Testi di riferimento
N. Santoro: Distributed Algorithms + slides ed appunti |
Ricevimento studenti
Su appuntamento per email con il Docente: clementi/guala@mat.uniroma2.it |
Modalità di esame
NOTA IMPORTANTE (del 23-05-18) le modalita' di esame della parte del Prof. Trevisan saranno definite entro pochi giorni anche sulla base di un feedback da parte degli studenti. In ogni caso:
- E' prevista *per tutti* (e in ogni appello) una prova orale (durante gli appelli previsti).
- Probabilmente, saranno proposti degli homework *facoltativi* a cui verranno dati un punteggio/ "bonus" da aggiungere eventualmente alla prova orale.
- Per gli studenti lavoratori valgono le stesse condizioni di cui sopra. |