Obiettivi Formativi

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.

Learning Goals

Make the students know algorithmic theories and methodologies to solve decision problems in various contexts, in particular concerning the creation of models using graphs of relations among the entities of a complex system. Make the students aware of costs and benefits related to the adoption of algorithms and data structures. Make the students know the basic principles of a modern programming language used for an effective modeling of complex systems Make the students know the basic principles of modern distributed execution systems used for the new family of optimized algorithms useful for solving complex problems. Make the students know the basic principles of information theory useful for the data knowledge, its coding and compressions. Make the students apply algorithmic theories and methodologies to study-cases that must be critically analyzed. To this purpose, frontal lectures are accompanied with practical exercises concerning coding and analysis. Make the students recognize: 1) the significant aspects (entities and relations) in a problem that will be modeled, 2) the consequences, in terms of model results, of the starting hypotheses. Students skills development an adequate level of independency in judgments and analysis of complex problems. Make the students know the course specific language. Achieving the ability to communicate effectively with technical language in the context of defining and describing problems in complex systems and outlining algorithmic solutions. Make the students acquire a methodology of study and analysis adequate to the autonomous analysis of advanced problems. Make the students able to accomplish verification and updating in software sector necessary for implementing new possible solutions.

Metodi didattici

Al fine di raggiungere gli obiettivi formativi previsti, il corso si articola attraverso lezioni frontali, esercitazioni in aula, esercitazioni guidate dal docente. Tutte le attività sono svolte con supporto di slide delle lezioni. Le slide presentate sono condivise tramite la classe MS Teams dedicata.

Teaching Methods

In order to achieve the expected objectives, the course is organized in lectures, practical based lessons in the class and guided exercises with teacher support. All activities are carried out with the support of lecture slides. Slides presented during the lecture are shared through the MS Teams classroom.

Prerequisiti

Conoscenze di base di Algoritmi e Strutture Dati, conoscenza di un linguaggio di programmazione. Conoscenza di base di architetture di calcolo distribuito.

Prerequisites

Basic knowledge about Algorithms and Data Structures, and a programming language. A basic knowledge of distributed computational architectures

Verifiche dell'apprendimento

L'esame è costituito da una verifica orale. La verifica orale ha una valutazione compresa tra 0 e 25. L’esame prevede un progetto opzionale, scelto dello studente assieme ai professori del corso. Il progetto viene discusso in sede di verifica orale ed ha una valutazione compresa tra 0 e 6. Il voto finale, in trentesimi, è dato dalla somma della prova orale ed, eventualmente, del progetto.

Assessment

The final verification consists of an oral exam. The oral exam has an evaluation between 0 and 25. The exam includes an optional project, chosen by the student together with the professors. The project is discussed during the oral examination and has an evaluation between 0 and 6. The final mark, out of thirty, is given by the sum of the oral exam and, possibly, of the project.

Programma del Corso

------------------------------------------------------------ Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A ------------------------------------------------------------ MODULO A -INTRODUZIONE A PYTHON: Oggetti in Python, Espressioni, operatori e precedenza, Flusso di controllo, Funzioni, Gestione dell’I/O, Gestione delle eccezioni, Iteratori e generatori, Visibilità e spazio dei nomi, Moduli -PROGRAMMAZIONE ORIENTATA AGLI OGGETTI: Obiettivi, principi di progettazione e pattern della programmazione orientata agli oggetti, Definizione delle classi: overloading e metodi speciali, iteratori, Ereditarietà, Spazio dei nomi e orientazione agli oggetti, Copia superficiale e profonda -ANALISI DEGLI ALGORITMI: Operazioni primitive, Analisi asintotica: notazione Theta, O e Omega -ALGORITMI SUI GRAFI: Il tipo di dato astratto grafo, Strutture dati per i grafi: lista di archi, lista di adiacenza, mappa di adiacenza, matrice di adiacenza, Attraversamento dei grafi: ricerca in profondità, ricerca in ampiezza, Chiusura transitiva, Grafi diretti aciclici: ordinamento topologico, Percorsi minimi: grafi pesati, algoritmo di Dijkstra, Alberi di ricopertura minimi: algoritmo di Prim-Jarnik, algoritmo di Kruskal -INTRODUZIONE ALLA NETWORK SCIENCE: Grado, grado medio e distribuzione di grado, Reti pesate, reti bipartite, Percorsi e distanze – Connessione – Coefficiente di clustering, Leggi di potenza e reti scale-free, Hub, Invarianza di scala -RETI MODELLO: Il modello di rete random, Numero di link, Distribuzione di grado, Evoluzione di reti random, Le reti reali sono supercritiche, Small world, Coefficiente di clustering, Crescita e aggregazione preferenziale, Il modello di Barabasi-Abert, Dinamica del grado, distribuzione di grado, Assenza di crescita o aggregazione preferenziale, Il modello di Bianconi-Barabasi – Misura della fitness -CORRELAZIONE DI GRADO: Introduzione, Assortatività e disassortatività, Misura delle correlazioni di grado -COMUNITÀ: Introduzione – Fondamenti delle comunità, Clusterizzazione gerarchica (algoritmo di Ravasz, algoritmo di Girvan-Newman), Modularità, Individuazione di comunità: algoritmo goloso di Newman -FENOMENI DIFFUSIVI: Introduzione, Modellazione di epidemie: modelli SI, SIS, SIR, Epidemie su reti. ------------------------------------------------------------ Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B ------------------------------------------------------------ - 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: algoritmi ad anello, 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: elezione in un anello, 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 Eco con estinzione, algoritmo Itai-Rodeh con dimensione dell'anello, 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++.

Course Syllabus

------------------------------------------------------------ Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A ------------------------------------------------------------ MODULEA -PYTHON PRIMER: Objects in Python, Expressions, Operators and Precedence, Control Flow, Functions: Information passing, built-in functions, I/O management, Exception Handling, Iterators and Generators, Scopes and Namespaces, Modules -OBJECT-ORIENTED PROGRAMMING: Object-Oriented design goals, design principles and design patterns, Class Definitions: overloading and special methods, iterators, Inheritance, Namespaces and Object-Orientation, Shallow and Deep Copying -ALGORITHM ANALYSIS: Primitive operations, Asymptotic Analysis: Theta, O and Omega notations -GRAPH ALGORITHMS: The Graph Abstract Data Type, Data structures for graphs: edge list, adjacency list, adjacency map, adjacency matrix, Graph Traversals: Depth-First Search, Breadth-First Search, Transitive closure, Directed Acyclic Graphs: topological ordering, Shortest Paths: Weighted graphs, Dijkstra's algorithm, Minimum spanning trees: Prim-Jarnik algorithm, Kruskal algorithm -INTRODUCTION TO NETWORK SCIENCE: Degree, average degree and degree distribution, Weighted networks, bipartite networks, Paths and Distances, Connectedness, Clustering Coefficient, Power laws and scale-free networks, Hubs, The meaning of scale-free -MODEL NETWORKS: The random network model, Number of links, Degree distribution, Evolution of a random network, Real networks are supercritical, Small worlds, Clustering coefficient, Growth and preferential attachment, The Barabasi-Albert model, Degree dynamics, degree distribution, The absence of growth or preferential attachment, The Bianconi-Barabasi model, Measuring fitness -DEGREE CORRELATION: Introduction, correlations, Assortativity and disassortativity, Measuring degree -COMMUNITIES: Introduction, Basics of Communities, Hierarchical Clustering (Ravasz algorithm, Girvan-Newman algorithm), Modularity, Community detection: the greedy Newman algorithm -SPREADING PHENOMENA: Introduction, Epidemic modeling: SI, SIS, SIR models, Network epidemics. ------------------------------------------------------------ Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B ------------------------------------------------------------ - INTRODUCTION TO DISTRIBUTED ALGORITHMS: communication in distributed systems, States and Events, Causal order, Execution and Computation. Logic clock, Lamport’s clock, Vector clock. Shared Memory, MSI. SNAPSHOTS: Chandy-Lamport algorithm, Lai-Yang algorithm. - WAVE ALGORITHMS: Ring algorithms, Tarry's algorithm. Depth-first search, Tree algorithm, Echo algorithm. - DEADLOCK DETECTION: Wait-for graph, Bracha-Toueg algorithm. - TERMINATION DETECTION: Dijkstra-Scholten algorithm, Shavit-Francez algorithm, Rana’s algorithm, Weight-throwing termination detection, Safra’s algorithm. - GARBAGE COLLECTION: Mark-Scan Counting, Indirect reference counting, Weighted reference counting. - ELECTION ALGORITHMS: Election in Rings, Chang-Roberts algorithm, Franklin’s algorithm, Dolev-Klawe-Rodeh algorithm. Tree election algorithm, Echo algorithm with extinction, Minimum Spanning Trees, Kruskal’s algorithm, The Gallager-Humblet-Spira algorithm. - ANONYMOUS NETWORKS: Las Vegas and Monte Carlo algorithms, Itai-Rodeh election algorithm, echo algorithm with extinction, Itai-Rodeh ring size algorithm, IEEE 1394 election algorithm. - CONSENSUS ALGORITHMS: Paxos, Multi-Paxos, Raft. The Byzantine Generals Problem, Byzantine Paxos algorithm, Byzantine Raft algorithm. - BARRIERS: synchronization, Sense-reversing barrier, Combining tree barrier, Tournament barrier, Dissemination barrier. - CONCURRENT PROGRAMMING: Thread in Python. Socket in Python. - DISCRETE-EVENT SIMULATION: Main components of a DES, Omnet++. Omnet++ modelling approach for distributed systems.