 |
Giacomo CABRI
Professore Ordinario
Dipartimento di Scienze Fisiche, Informatiche e Matematiche sede ex-Matematica
|
Insegnamento: Algoritmi distribuiti
Informatica (Offerta formativa 2021)
Obiettivi formativi
L'insegnamento si propone di fornire le basi teoriche e pratiche per lo studio e la progettazione e l'implementazione di algoritmi distribuiti e qualche fondamento teorico sulla teoria della complessità.
Al termine dell'insegnamento lo studente sarà in grado di:
- studiare e progettare algoritmi distribuiti
- sfruttare tecnologie per lo sviluppo di sistemi distribuiti
Inoltre, avrà acquisito conoscenza sull'esistenza di problemi NP-hard e alcune tecniche utilizzabili per approcciarli.
Prerequisiti
Per affrontare il corso, agli studenti sono richieste le seguenti conoscenze pregresse:
- Algoritmi di base e strutture dati fondamentali, come quelli presentati in un insegnamento di base di algoritmi di laurea triennale.
- Esperienze di programmazione di almeno un linguaggio di programmazione.
- Matematica dell'insegnamento di Analisi I.
- Conoscenze di sistemi operativi e reti di calcolatori.
Programma del corso
L'insegnamento si svolge nel primo semestre del secondo anno, per un totale di 63 ore (9 CFU) di didattica frontale, suddivise tra lezioni teoriche e di laboratorio.
L'insegnamento è diviso in due moduli, uno da 6 CFU e uno da 3 CFU, tenuti da due docenti diversi.
Modulo da 6 CFU (42 ore)
- Introduzione al corso, alla computazione distribuita e al modello di calcolo multi processore/agente (6 ore).
- Algoritmi fondamentali nella computazione distribuita per i seguenti problemi: elezione del leader, boradcast, costruzione di minimum spanning tree, routing (12 ore).
- Problema del consenso e studio di soluzioni anche in presenza di errori: link e node failures, bizantine failures (8 ore).
- Strutture dati distribuite: tabelle hash, block-chain (8 ore).
- Elementi di teoria della complessità: Problemi NP-completi, NP-hard, esempi selezionati di riduzioni e algoritmi di approssimazione in ottimizzazione combinatoria per i problemi del commesso viaggiatore e del vertex cover (8 ore).
Modulo da 3 CFU (21 ore):
- Programmazione socket (4 ore).
- File system distribuiti (4 ore).
- Tecnologie ad oggetti per lo sviluppo di applicazioni distribuite; problematiche; esempio: Java RMI (13 ore)
La distribuzione delle ore tra gli argomenti trattati è da considerarsi indicativa e può subire delle variazioni dipendentemente dalla partecipazione degli studenti e dei loro riscontri.
Metodi didattici
Le lezioni frontali (6 CFU) e le esercitazioni in laboratorio (3 CFU), sono erogati entrambi in presenza (a meno che la situazione pandemica non richieda un ritorno alla didattica a distanza) tramite l'ausilio di lucidi e/o lavagna.
La frequenza non è obbligatoria. Gli studenti lavoratori o non frequentanti avranno la possibilità di accedere al materiale fornito dai docenti sulla pagina moodle del corso.
L'insegnamento è in italiano ma il materiale è in inglese.
Tutte le informazioni relative all'insegnamento saranno disponibili sulla pagina moodle dell'insegnamento. Gli studenti potranno trovare le informazioni tecniche e organizzative dell'insegnamento, nonché il materiale didattico, tra cui: lucidi delle lezioni, altro materiale reso disponibile per le esercitazioni e indicazioni dei testi adottati.
Testi di riferimento
Per entrambi i moduli:
- i docenti forniranno del materiale, tra cui: appunti di lezioni di altre università italiane e straniere disponibili on-line e note e appunti scritti dal docente.
Per il modulo da 6 CFU, selezione di capitoli dai seguenti testi:
- T.H. Cormen, C.E. Leoserson, R.L. Rivest, C. Stein,
Introduction to Algorithms ,
Mc-Graw Hill, II o III Edizione
- Nicola Santoro
Design and Analysis of Distributed Algorithms
WILEY 2007
Verifica dell'apprendimento
L'esame si compone di due parti, una per ogni modulo del corso:
- Per il modulo da 6 CFU: un esame esame orale di circa 20 minuti il cui obiettivo è verificare sia la conoscenza dei concetti e degli algoritmi visti a lezione che la capacità di analizzare e progettare algoritmi distribuiti; il voto di questa prova contribuisce per 2/3 al voto complessivo;
- Per il modulo da 3 CFU: presentazione di un progetto in cui viene richiesto lo sviluppo di una applicazione software distribuita per verificare la capacità di applicare i concetti; il voto di questa prova contribuisce per 1/3 al voto complessivo.
Le due parti possono essere sostenute in appelli diversi, in un ordine qualsiasi. Il voto finale sarà calcolato solo dopo il superamento di entrambe le parti e sarà calcolato come la media pesata dei voti delle due parti.
Le prove si svolgeranno in presenza, a meno che la situazione pandemica non richieda un ritorno degli esami a distanza. Nel caso fosse necessario, tutte le informazioni relative agli esami a distanza saranno date agli studenti, seguendo quelle che saranno le indicazioni e le regole stabilite dal Dipartimento e dall'Ateno.
Risultati attesi
* Conoscenza e comprensione
Alla fine dell'insegnamento, lo studente avrà acquisito conoscenze e tecnologie per sviluppare algoritmi e applicazioni distribuite. Lo studente avrà conoscenza di un nucleo importante di problemi, soluzioni e strutture dati nell'ambito distribuito. Inoltre, lo studente avrà comprensione di alcune tecniche algoritmiche standard per la risoluzione (esatta o approssimata) di problemi computazionalmente difficili.
* Capacità di applicare conoscenza e comprensione
Lo studente sarà in grado di progettare e sviluppare applicazioni software distribuite, scegliendo le piattaforme e le tecnologie più appropriate.
Inoltre, saprà riconoscere problemi computazionalmente difficili quando questi emergeranno nelle applicazioni concrete.
* Autonomia di giudizio
Lo studente sarà in grado di scegliere in maniera autonoma o contribuire, all'interno di un team, alla scelta delle migliori soluzioni per problemi affrontati nel corso.
* Abilità comunicative
Lo studente avrà acquisito conoscenze e competenze tali da permettergli di discutere, proporre e condividere in modo efficace problemi, idee e soluzioni in campi applicativi nei quali scaturiscono le problematiche oggetto di studio.
* Capacità di apprendimento
Lo studente sarà in grado di affrontare lo studio di problemi nuovi (noti o non noti), della stessa natura di quelli affrontati nel corso, che si troverà eventualmente ad affrontare nella sua carriera lavorativa.