The course is taught in English.
Il principale obiettivo del corso č quello di fornire una introduzione ad alcune tecniche di base della matematica combinatoria e della teoria delle strutture discrete quali grafi ed alberi. L'accento verrą posto su diverse questioni (quali ad esempio problemi di tassellamento e di conteggio, alberi decisionali, stime di complessitą per le procedure ricorsive) che ammettono una formulazione naturale nel contesto della matematica discreta.

Le conoscenza acquisite in questo corso includeranno diverse tecniche di base della matematica combinatoria, con particolare attenzione alle possibili applicazioni. In particolare, alla fine del corso, ci si aspetta che lo studente sia in grado di impostare, formulare precisamente e risolvere alcuni tipici problemi della matematica combinatoria, con particolare riferimento a quelli che nascono dalle applicazioni.

Sono richieste le nozioni di base su insiemi e funzioni, oltre ai fondamenti del calcolo in una variabile.

Discrete Mathematics

L'assioma del buon ordinamento, forma forte e debole del principio di induzione.
Primi problemi di conteggio. Alberi decisionali e processi ricorsivi.
Funzioni e conteggio, il principio dei cassetti, il principio moltiplicativo e quello additivo.
Selezioni con o senza ordine, con o senza ripetizioni. Permutazioni, coefficienti binomiali e multinomiali, formula del binomio. Il principio del crivello.
Funzioni generatrici e ricorsioni lineari.
Grafi orientati e non orientati, passeggiate, cammini e cicli. Passeggiate Euleriane e cicli Hamiltoniani. Alberi. Combinatoria dei grafi. Grafi planari, la formula di Eulero e i suoi corollari.
Stime da sotto per la complessitą tramite gli alberi decisionali e strategie ottimali. Applicazioni ed esempi, in particolare ai problemi di tassellamento e agli algoritmi di ricerca e ordinamento.

Graphs and dynamics over networks.

The Perron-Frobenius theory of matrices with non-negative elements.
Elements of algebraic graph theory: adjacency and incidence matrix of a graph. The relation
between graph and spectral properties. The entropy o a graph.
Random walks on a graph; equilibrium probabilities and convergence analysis.
Graph models for large scale networks: grids, hypercubes, geometric graphs, random graphs
(Erdos model, configuration model).

Discrete dynamics over networks. Epidemics diffusions: SI and SIR models. Discrete opinion
dynamics: voter model, majority model. Mean field approximation techniques.
Locally averaging algorithms, convergence to consensus. Gossip models. Heterogeneous models.
Syncronization problems. Applications in sensor networks. Inferential problems over networks.
Message passing algorithms.

Durante le esercitazioni, gli esercizi copriranno il materiale discusso a lezione e saranno svolti dal docente.

Lecture Notes on "Discrete Mathematics" by L. Lovįsz and K. Vesztergombi.
Norman L. Biggs, Discrete Mathematics, Clarendon Press, Oxford, 1985.

Esame scritto.