Obiettivi Formativi

OF1 (Conoscenza e comprensione) - 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. OF2 (Capacità di applicare conoscenza e comprensione) - 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. OF3 (Autonomia di giudizio)- 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. OF4 (Abilità comunicative) - 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. OF5 (Capacità di apprendimento) - 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

OF1 (Knowledge and understanding) - 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. OF2 (Ability to apply knowledge and understanding) - 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. OF3 (Autonomy of judgment) - 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. OF4 (Communication skills) - 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. OF5 (Learning skills) - 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

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A Lezioni frontali Esercitazioni in aula Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Lezioni frontali e lezioni nel laboratorio informatico

Teaching Methods

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A Lectures Classworks Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Frontal Lectures and experimental works in the Computer Science Lab

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

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A Test a risposta multipla Esame orale Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Scritto con test on-line su Piattaforma di Ateneo, ed Orale con Progetto opzionale nell'Ambito degli Algoritmi Avanzati.

Assessment

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A Multiple choice test Oral exam Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Test on-line on University e-learning platform Oral with an optional elaboration design in the context of Advanced Algorithms .

Programma del Corso

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A 1. Introduzione a Python Introduzione a Python – Oggetti in Python: identificativi, oggetti, assegnazioni, creazione e utilizzo di oggetti, classi built-in – Espressioni, operatori e precedenza – Flusso di controllo: condizioni, iterazioni – Funzioni: trasmissione di informazioni, funzioni built-in – Gestione dell’I/O in Python – Gestione delle eccezioni: sollevazione e cattura di un’eccezione – Iteratori e generatori – Visibilità e spazio dei nomi – Moduli 2. Programmazione orientata agli oggetti Obiettivi, principi di progettazione e pattern della programmazione orientata agli oggetti – Sviluppo software: progettazione, pseudo-codice – Definizione delle classi: overloading e metodi speciali, iteratori – Ereditarietà – Spazio dei nomi e orientazione agli oggetti – Copia superficiale e profonda 3. Analisi degli Algoritmi Operazioni primitive – Analisi asintotica: notazione Theta, notazione O, notazione Omega 4. 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 5. Introduzione alla Network Science Grado, grado medio e distribuzione di grado – Reti pesate, reti bipartite – Percorsi e distanze – Connessione – Coefficiente di clustering 6. Reti random Il modello di rete random – Numero di link – Distribuzione di grado – Le reti reali non sono poissoniane – Evoluzione di reti random – Le reti reali sono supercritiche – Small world – Coefficiente di clustering 7. Proprietà scale-free Leggi di potenza e reti scale-free – Hub – Significato di scale-free 8. Il modello di Barabasi-Albert Introduzione – Crescita e aggregazione preferenziale – Il modello di Barabasi-Abert – Dinamica del grado, distribuzione di grado – Assenza di crescita o aggregazione preferenziale 9. Reti in evoluzione Il modello di Bianconi-Barabasi – Misura della fitness 10. Correlazione di grado Introduzione – Assortatività e disassortatività – Misura delle correlazioni di grado 11. Comunità Introduzione – Fondamenti delle comunità – Clusterizzazione gerarchica (algoritmo di Ravasz, algoritmo di Girvan-Newman) – Modularità – Individuazione di comunità: algoritmo goloso di Newman 12. Fenomeni diffusivi Introduzione – Modellazione di epidemie: modelli SI, SIS, SIR – Epidemie su reti Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Introduzione Al Corso. Cinque problemi: Abbinare gli studenti della scuola di medicina agli ospedali. Programmazione degli intervalli. Problema di corrispondenza stabile e corrispondenza perfetta. Implementazione efficiente. Pianificazione degli intervalli ponderati. Tracciabilità computazionale, ordine asintotico di crescita Implementazione dell'algoritmo di corrispondenza stabile utilizzando liste e array Definizioni e applicazioni di base, connettività e attraversamento del grafico Implementazione dell'attraversamento dei grafici utilizzando code e stack, testando la bipartizione: Un'applicazione della connettività di ricerca in profondità nei grafici diretti Programmazione degli intervalli: L'algoritmo dell'avidità rimane in anticipo, programmando per ridurre al minimo il ritardo: Un argomento di scambio, Caching ottimale: un argomento di scambio più complesso Percorsi più brevi in un grafico Implementare l'algoritmo di Kruskal: I dati di Unione-Trova l'albero minimo Problem Dividere e conquistare Una prima ricorrenza: L'algoritmo di Mergesort Conteggio delle inversioni, ricerca della coppia di punti più vicina, moltiplicazione dei numeri interi Programmazione degli intervalli ponderati: Una procedura ricorsiva Principi di programmazione dinamica: Memoization o Iterazione su sottoproblemi Segmentati Piazza Meno: Scelte a più vie. Sottoinsieme Somma e zaini. Struttura secondaria RNA: Programmazione dinamica su intervalli Il problema del flusso massimo e l'algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. La scelta di buoni percorsi di incremento L'algoritmo di massima portata Pre Flow-Push. Una prima applicazione: Il problema della corrispondenza bipartita Progettazione del sondaggio - Programmazione delle compagnie aeree - Segmentazione delle immagini - Eliminazione del baseball. Un'ulteriore direzione: Aggiungere costi al problema della corrispondenza Algoritmi nei sistemi distribuiti. L'approccio Map-reduce Dettagli Hadoop: Installazione e utilizzo Entropia: Scelta e incertezza, scelta con probabilità conosciuta, entropia condizionata, determinazione assiomatica dell'entropia. Informazione e la sua misura: Osservazioni ed eventi, informazioni e domande, informazione reciproca e divergenza Kullback-Leibler, sorpresa, entropia e informazione, probabilità come informazione. Codifica efficiente delle informazioni: Codifica di una singola variabile casuale, codici senza prefissi, alberi n-ary per la codifica, disuguaglianza Kraft, efficiente, quali sono i codici efficienti? Lunghezza del percorso e incertezza, Teorema di codifica senza rumore, Codici Huffman. Codifica per la trasmissione rumorosa: Canali di comunicazione, canali di comunicazione, capacità dei canali, canali di ingresso-simmetrici, canali di uscita-simmetrici, canali simmetrici, velocità di trasmissione, Lemma di Fano, il teorema di codifica del rumore, codici di ripetizione. Codifica efficiente delle informazioni: Codifica di una singola variabile casuale, codici senza prefissi, alberi n-ary per la codifica, disuguaglianza Kraft, efficiente, quali sono i codici efficienti? Lunghezza del percorso e incertezza, Teorema di codifica senza rumore, Codici Huffman. Codifica per Rumoroso. Complementi alla codifica efficiente delle informazioni: Codifica di lunghezza da variabile a fissa: Codice di Tunstall, set di set appropriati, set di messaggi Tunstall, algoritmo di costruzione del codice Tunstall, algoritmo di costruzione del codice Tunstall, codifica degli interi positivi, codifica delle fonti con la memoria, codifica Huffman delle fette, schema di codifica delle fonti Elias-Willems, codifiche Lempel-Ziv, trasmissione gzip e bzip2: Canali di comunicazione, canali di comunicazione, capacità dei canali, canali di ingresso-simmetrici, canali di uscita-simmetrici, canali simmetrici, velocità di trasmissione, Lemma di Fano, il teorema di codifica rumoroso, codici di ripetizione.

Course Syllabus

Modulo: 6094/1 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS A 1. Python Primer Python Overview - Objects in Python: identifiers, objects, assignment, creating and using objects, built-in classes - Expressions, Operators and Precedence - Control Flow: conditionals, loops - Functions: Information passing, built-in functions - I/O management in Python - Exception Handling: raising an exception, catching an exception - Iterators and Generators - Scopes and Namespaces - Modules 2. Object-Oriented Programming Object-Oriented design goals, design principles and design patterns - Software Development: design, pseudo-code - Class Definitions: overloading and special methods, iterators - Inheritance - Namespaces and Object-Orientation - Shallow and Deep Copying 3. Algorithm Analysis Primitive operations - Asymptotic Analysis: Theta-notation, O-notation, Omega-notation 4. 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 5. Network Science: Introduction Degree, average degree and degree distribution - Weighted networks, bipartite networks - Paths and Distances - Connectedness - Clustering Coefficient 6. Network Science: Random Networks The random network model - Number of links - Degree distribution - Real Networks are not Poisson - Evolution of a random network - Real networks are supercritical - Small worlds - Clustering coefficient 7. Network Science: The scale-free property Power laws and scale-free networks - Hubs - The meaning of scale-free 8. Network Science: The Barabasi-Albert model Introduction - Growth and preferential attachment - The Barabasi-Albert model - Degree dynamics, degree distribution - The absence of growth or preferential attachment 9. Network Science: Evolving Networks The Bianconi-Barabasi model - Measuring fitness 10. Degree correlation Introduction - Assortativity and disassortativity - Measuring degree correlations 11. Communities Introduction - Basics of Communities - Hierarchical Clustering (Ravasz algorithm, Girvan-Newman algorithm) - Modularity - Community detection: the greedy Newman algorithm 12. Spreading phenomena Introduction - Epidemic modeling: SI, SIS, SIR models - Network epidemics Modulo: 6094/2 - ADVANCED ALGORITHMS AND COMPUTATIONAL MODELS B Course Structure: 0-Introduction, 01-StableMatching, 02-AlgorithmAnalysis, 03-Graphs, 04-GreedyAlgorithmsI, 04-GreedyAlgorithmsII, 05-DivideAndConquerI, 05-DivideAndConquerII, 06-DynamicProgrammingI, 06-DynamicProgrammingII, 07-NetworkFlowI, 07-NetworkFlowII, 07-NetworkFlowIII, 08-hadoopI, 08hadoopII, , 09-information-theoryI, 09-information-theoryII Five Problems: Matching med-school students to hospitals. Interval scheduling Stable matching problem and Perfect matching. Efficient implementation. Weighted interval scheduling Computational Tractability, Asymptotic Order of Growth Implementing the Stable Matching Algorithm Using Lists and Arrays Basic Definitions and Applications, Graph Connectivity and Graph Traversal Implementing Graph Traversal Using Queues and Stacks, Testing Bipartiteness: An Application of Breadth-First Search Connectivity in Directed Graphs Interval Scheduling: The Greedy Algorithm Stays Ahead, Scheduling to Minimize Lateness: An Exchange Argument, Optimal Caching: A More Complex Exchange Argument Shortest Paths in a Graph Implementing Kruskal’s Algorithm: The Union-Find Data The Minimum Spanning Tree Problem Divide and Conquer A First Recurrence: The Mergesort Algorithm Counting Inversions, Finding the Closest Pair of Points, Integer Multiplication Weighted Interval Scheduling: A Recursive Procedure Principles of Dynamic Programming: Memoization or Iteration over Subproblems Segmented Least Squares: Multi-way Choices. Subset Sums and Knapsacks. RNA Secondary Structure: Dynamic Programming over Intervals The Maximum-Flow Problem and the Ford-Fulkerson Algorithm. Maximum Flows and Minimum Cuts in a Network. Choosing Good Augmenting Paths The Preflow-Push Maximum-Flow Algorithm. A First Application: The Bipartite Matching Problem Survey Design - Airline Scheduling - Image Segmentation - Baseball Elimination. A Further Direction: Adding Costs to the Matching Problem Algorithms in Distributed Systems. The Map-reduce approach Hadoop Details: Installation and Usage Entropy: Choice and Uncertainty, Choice with Known Probability, Conditional Entropy, Axiomatic Determination of Entropy. Information And Its Measure: Observations And Events, Information and Questions, Mutual Information and Kullback-Leibler Divergence, Surprise, Entropy and Information, Probability as Information Efficient Coding of Information: Coding a Single Random Variable, Prefix-Free Codes, n-ary Trees for Coding, Kraft Inequality, Efficient , What Are Efficient Codes?, Probabilized n-ary Trees: Path Length and Uncertainty, Noiseless Coding Theorem, Huffman Codes. Coding for Noisy Transmission: Communication Channels, Communication Channels, Channel Capacity, Input-Symmetric Channels, Output-Symmetric Channels, Symmetric Channels, Transmission Rate , Fano’s Lemma , The Noisy Coding Theorem, Repetition Codes Efficient Coding of Information: Coding a Single Random Variable, Prefix-Free Codes, n-ary Trees for Coding, Kraft Inequality, Efficient , What Are Efficient Codes?, Probabilized n-ary Trees: Path Length and Uncertainty, Noiseless Coding Theorem, Huffman Codes. Coding for Noisy. Complements to Efficient Coding of Information: Variable-to-Fixed Length Coding: Tunstall’s Code, Proper Sets, Tunstall message sets, Tunstall Code Construction Algorithm, Coding the Positive Integers, Coding of Sources with Memory Huffman coding of slices, Elias-Willems Source Coding Scheme, Lempel-Ziv Codings, gzip and bzip2 Transmission: Communication Channels, Communication Channels, Channel Capacity, Input-Symmetric Channels, Output-Symmetric Channels, Symmetric Channels, Transmission Rate , Fano’s Lemma , The Noisy Coding Theorem, Repetition Codes