Far conoscere le teorie e le metodologie algoritmiche per la soluzione di problemi decisionali in differenti ambiti con particolare riguardo alla modellazione mediante grafi di relazioni tra gli elementi di un sistema complesso. Far conoscere costi e benefici legati all'adozione di algoritmi e strutture dati. Far conoscere i principi base di un moderno linguaggio di programmazione utilizzato per l'efficace modellazione di sistemi complessi.
Far conoscere i principi base dei moderni sistemi di esecuzione distribuita di algoritmi ottimizzati per la risoluzione di problemi complessi, e i principi base della teoria dell’informazione utile alla conoscenza, codifica e compressione dei dati.
Far applicare le teorie e le metodologie algoritmiche a casi di studio da analizzare criticamente affiancando alle lezioni frontali relative agli aspetti teorici esercitazioni pratiche di programmazione e analisi.
Far riconoscere: 1) gli aspetti significativi (entità e relazioni) in un problema da modellare, 2) le conseguenze, in termini di comportamento del modello, delle ipotesi di partenza. Sviluppare un adeguato grado di autonomia di giudizio nella analisi di problemi complessi.
Far apprendere un linguaggio specifico della disciplina. Sviluppare la capacità di comunicare efficacemente e con linguaggio tecnico nell’ambito della definizione e descrizione di problemi in sistemi complessi delineandone le soluzioni algoritmiche.
Fare acquisire un metodo di studio e di analisi adeguato all'analisi autonoma di problemi avanzati. Sviluppare la capacità di verifica e aggiornamento nel settore del software necessari all’implementazioni di nuove soluzioni adeguate.
Prerequisiti
Conoscenze di base di Algoritmi e Strutture Dati, conoscenza di un linguaggio di programmazione. Conoscenza di base di architetture di calcolo distribuito.
Testi
Distributed Algorithms-An Intuitive Approach, Second Edition. Wan Fokkink, MIT Press, February 2018. ISBN: 9780262037662
Distributed Computing Principles, Algorithms, and Systems. Ajay D. Kshemkalyani and Mukesh Singhal, Cambridge University Press 2008. ISBN-13 978-0-521-87634-6
Distributed Computing with Python, by Rasheedh B, Francesco Pierfederici. Packt, 2016. ISBN 9781785889691
Contenuti
- INTRODUZIONE AGLI ALGORITMI DISTRIBUITI: comunicazione nei sistemi distribuiti, stati ed eventi, ordine causale, esecuzione e computazione. Orologio logico, Orologio di Lamport, Orologio vettoriale. Memoria condivisa, MSI. - SNAPSHOTS: Algoritmo Chandy-Lamport, Algoritmo Lai-Yang. - ALGORITMI WAVE: algoritmo di Tarry. Ricerca in profondità, Algoritmo ad albero, Algoritmo Eco. - RILEVAMENTO DEADLOCK: grafo Wait-for, algoritmo Bracha-Toueg - RILEVAMENTO DELLA TERMINAZIONE: algoritmo Dijkstra-Scholten, algoritmo Shavit-Francez, algoritmo di Rana, rilevamento della terminazione con "Lancio del peso", algoritmo di Safra. - GARBAGE COLLECTION: Conteggio Mark-Scan, Conteggio a riferimenti indiretti, Conteggio dei riferimenti ponderati. - ALGORITMI DI ELEZIONE: Algoritmo di Chang-Roberts, Algoritmo di Franklin, Algoritmo di Dolev-Klawe-Rodeh. Algoritmo di elezione dell'albero, Algoritmo Eco con estinzione, Alberi di copertura minimi, Algoritmo di Kruskal, Algoritmo di The Gallager-Humblet-Spira. - RETI ANONIME: algoritmi di Las Vegas e Monte Carlo, algoritmo di elezione Itai-Rodeh, algoritmo di elezione IEEE 1394. - ALGORITMI DI CONSENSO: Paxos, Multi-Paxos, Raft. Il problema dei generali bizantini, algoritmo di Paxos bizantino, algoritmo di zattera bizantina. - BARRIERE: Barriera di inversione dei sensi, Barriera combinata degli alberi, Barriera del torneo, Barriera di diffusione. - PROGRAMMAZIONE CONCORRENTE: Thread in Python. Socket in Python. - SIMULAZIONE AD EVENTI DISCRETI: Componenti tipici in DES, Omnet++. Approccio di modellazione dei sistemi distribuiti con Omnet++.