Politecnico di Torino | |||||||||||||||||||||||||
Anno Accademico 2014/15 | |||||||||||||||||||||||||
01OUJNG Discrete Mathematics/Graphs and dynamics over networks |
|||||||||||||||||||||||||
Corso di Laurea Magistrale in Ingegneria Matematica - Torino |
|||||||||||||||||||||||||
|
|||||||||||||||||||||||||
|
|||||||||||||||||||||||||
Presentazione
The course is taught in English.
Il corso consiste di due parti: (1) Discrete Mathematics. Scopo di questa parte 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. (2) Graphs and dynamics over networks. In questa parte del corso verranno presentati alcuni elementi più avanzati della teoria dei grafi e vari modelli matematici che descrivono dinamiche su grafi sia deterministiche che probabilistiche. Saranno discusse varie applicazioni: algoritmi su reti per stime e inferenze distribuite, dinamiche di agenti mobili, modelli per la dinamica delle opinioni e modelli epidemici |
Risultati di apprendimento attesi
Conoscenza del principio di induzione e suo utilizzo nella teoria e nella applicazioni.
Conoscenza dei principali strumenti combinatori e di conteggio. Capacità di impostare, formalizzare e risolvere alcuni tipici problemi di conteggio e combinatoria. Conoscenza, utilizzo e risoluzione esplicita delle ricorsioni lineari. Conoscenza degli elementi di base di teoria dei grafi. Capacità di mettere in relazione proprietà qualitative e quantitative di un grafo con informazioni parziali sul suo spettro. Capacità di tradurre alcune istanze di problemi concreti (ad esempio procedure ricorsive o semplici problemi di tassellamento e di combinatoria enumerativa) nell’equivalente oggetto matematico/combinatorio. Conoscenza di elementi di base della teoria dei grafi diretti Conoscenza della teoria delle matrici stocastiche e substocastiche e delle loro proprietà spettrali. Conoscenza degli elementi di base delle catene di Markov, delle catene reversibili e del metodo dell’analogia elettrica. Capacità di costruire modelli matematici che descrivono dinamiche su reti e che hanno utilizzi dalla robotica, all’inferenza statistica, allo studio di modelli socio-economici. Capacità di analizzare le prestazioni di un algoritmo distribuito su una rete, la sua complessità e la sua velocità di convergenza con particolare riferimento alle proprietà di scalabilità rispetto al numero di nodi nel grafo. |
Prerequisiti / Conoscenze pregresse
Sono richieste le nozioni di base su insiemi e funzioni, i fondamenti del calcolo in una variabile, dell’algebra lineare e della probabilità elementare.
|
Programma
(1) Discrete Mathematics.
L'assioma del buon ordinamento, forma forte e debole del principio di induzione. Primi problemi di conteggio. Alberi decisionali e processi ricorsivi. Invarianti. 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. Funzioni generatrici e ricorsioni lineari. Grafi 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. Matrice di adiacenza e teoria spettrale dei grafi. Esempi di spettri. Stime da sotto per la complessità tramite gli alberi decisionali e strategie ottimali. Esempi e applicazioni, in particolare ai problemi di tassellamento e agli algoritmi di ordinamento. (2) Graphs and dynamics over networks. Grafi diretti, cammini, circuiti, cicli. Connessione e forte connessione. Periodo di un nodo, grafi aperiodici. Componenti connesse e grafo di condensazione. Laplaciano di grafi, forma di Dirichlet, funzioni armoniche. Matrici stocastiche e loro utilizzo nelle dinamiche di consenso. Convergenza per le potenze di una matrice stocastica. Proprietà spettrali. Diseguaglianza di Cheeger Grafi come circuiti elettrici e collegamento con le matrici stocastiche reversibili. Applicazioni: algoritmi per la stima distribuita, dinamiche di opinione. Elementi della teoria delle catene di Markov. Probabilità invarianti. Stati assorbenti. Comportamenti transienti e asintotici. Modelli ad agenti interagenti. Dinamiche gossip. Modelli per la diffusione delle epidemie. Modelli per la dinamica delle opinioni. L’approssimazione di campo medio. Dinamiche su alberi. Processi di ramificazione. Modelli soglia |
Organizzazione dell'insegnamento
Durante il corso verranno discussi e svolti dai docenti numerosi esercizi, che copriranno tutti gli argomenti trattati.
|
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
Il corso sarà coperto per intero da dispense e altro materiale (comprendente esempi ed esercizi svolti) preparato dai docenti e reso disponibile online agli studenti iscritti al corso.
Per possibili approfondimenti della prima parte del corso, sarà adatto allo scopo qualsiasi testo dal titolo "Discrete Mathematics", "Graph Theory" o analoghe varianti. Alcuni esempi specifici sono i seguenti: L. Lovász e K. Vesztergombi , "Lecture Notes on Discrete Mathematics" (disponibile online). N. L. Biggs, "Discrete Mathematics". Clarendon Press, Oxford, 1985. A. E. Brower e W. H. Haemers, "Spectra of graphs". Springer, New York, 2012 Per gli aspetti probabilistici della seconda parte del corso si suggerisce il testo D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (disponibile online). |
Criteri, regole e procedure per l'esame
L’esame consiste di una prova scritta con esercizi e domande teoriche che riguardano entrambe le parti del corso. Alcune parti dell’esame potranno essere preventivamente superate durante il corso tramite lavori individuali di tipo homework ed in tal modo eliminate dalla prova scritta finale.
|
Orario delle lezioni |
Statistiche superamento esami |
|