Obiettivi Formativi

Il modulo si pone tre obiettivi principali: - introdurre lo studente allo sviluppo di metodologie strutturare per modelizzare varie situazioni in termini di grafi - mostrare una serie di soluzioni di problemi tipiche della teoria dei grafi - migliorare le competenze dello studente in termini di analisi e codifica di algoritmi

Learning Goals

The module has three main goals: - introduce the student to the employment of structured methodologies to model various situations in terms of graphs - show a series of solutions to problems typical of the graph theory - increase the proficiencies of the student in terms of both analysis and coding of algorithms

Metodi didattici

Lezioni frontali, svolgimento di esercitazioni in aula e a casa

Teaching Methods

Frontal lectures, discussions of exercises, homeworks

Prerequisiti

Lo studente deve conoscere i fondamenti della programmazione e del corso di Algoritmi (o equivalente)

Prerequisites

The student must know the basics of Programming and Algorithms (or equivalent)

Verifiche dell'apprendimento

L'apprendimento verrà verificato mediante la valutazione di una serie di esercizi da svolgere individualmente a casa e un progetto finale da discutere durante l'esame orale.

Assessment

Learning will be verified through the evaluation of homework exercises and a final project to be discussed during the oral examination.

Programma del Corso

---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 ---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 Multiple Inheritance ---Algorithm Analysis Primitive operations Asymptotic Analysis: $\Theta$-notation, $O$-notation, $\Omega$-notation ---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 ---Network Science: Introduction Degree, average degree and degree distribution Weighted networks, bipartite networks Paths and Distances Connectedness Clustering Coefficient ---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 ---Network Science: The scale-free property Power laws and scale-free networks Hubs The meaning of scale-free Universality Ultra-small property The role of the degree exponent ---Network Science: The Barabasi-Albert model Growth and preferential attachment The Barabasi-Albert model Degree dynamics, degree distribution The absence of growth or preferential attachment Measuring preferential attachment Non-linear preferential attachment The origins of preferential attachment ---Network Science: Evolving Networks The Bianconi-Barabasi model Measuring fitness

Course Syllabus

---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 ---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 Multiple Inheritance ---Algorithm Analysis Primitive operations Asymptotic Analysis: $\Theta$-notation, $O$-notation, $\Omega$-notation ---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 ---Network Science: Introduction Degree, average degree and degree distribution Weighted networks, bipartite networks Paths and Distances Connectedness Clustering Coefficient ---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 ---Network Science: The scale-free property Power laws and scale-free networks Hubs The meaning of scale-free Universality Ultra-small property The role of the degree exponent ---Network Science: The Barabasi-Albert model Growth and preferential attachment The Barabasi-Albert model Degree dynamics, degree distribution The absence of growth or preferential attachment Measuring preferential attachment Non-linear preferential attachment The origins of preferential attachment ---Network Science: Evolving Networks The Bianconi-Barabasi model Measuring fitness