Anno accademico 2021-2022

GRAPH AND GAME THEORY

Docenti

Franca Rinaldi
Totale crediti
6
Periodo didattico
Primo Periodo
Tipologia
Affine/Integrativa
Prerequisiti. Conoscenza dei concetti di base dell’algebra lineare e confidenza con il calcolo matriciale. Conoscenza dei concetti di base della probabilità.
Metodi didattici. Lezioni teoriche ed esercitazioni.
Modalità di verifica. L’esame consiste in una prova orale atta a verificare la conoscenza e la capacità di presentazione degli argomenti in programma e la capacità di applicare tale conoscenza alla modellizzazione e/o risoluzione di facili problemi teorici/applicativi.
Altre informazioni. ~~~
Obiettivi formativi
Al termine del corso lo studente dovrà:

Conoscenza e comprensione: conoscere i principali concetti, problemi e metodologie della teoria dei grafi; conoscere alcune applicazioni della teoria dei grafi per la rappresentazione e l’analisi di sistemi reali, in particulare di reti reali (web, internet, reti sociali, etc.); conoscere le proprietà fondamentali delle matrici associate ai grafi ed alcune loro applicazioni all’analisi di reti di grandi dimensioni;conoscere i principali modelli della teoria dei giochi ed i corrispondenti metodi risolutivi.

Capacità di applicare conoscenza e comprensione: essere in grado di riconoscere la struttura di rete di alcuni sistemi reali, formulare un modello appropriato in termini di grafi ed impostare l’analisi delle sue proprietà; essere in grado di formulare come problema su grafi semplici problemi combinatori e applicativi; essere in grado di rappresentare correttamente ed eventualmente risolvere semplici situazioni di gioco.

Autonomia di giudizio: essere in grado di proporre e discutere modelli e metodi appropriati per la rappresentazione e l’analisi di reti reali; essere in grado di proporre e discutere modelli e metodi appropriati per la rappresentazione e l’analisi di situazioni di gioco.

Abilità comunicative: sapere illustrare con rigore e completezza gli argomenti in programma ed eventuali approfondimenti svolti autonomamente.

Capacità di apprendimento: essere in grado di approfondire autonomamente gli argomenti del corso in relazione ad aspetti non svolti in classe; essere in grado di consultare la letteratura scientifica del settore.

Contenuti
Teoria dei grafi: vengono presentati i principali concetti e risultati della teoria dei grafi (orientati e non orientati). Il programma comprende i seguenti argomenti: proprietà dei gradi e sequenze grafiche, isomorfismi ed automorfismi, cammini, tagli e connessione, indici di centralità basati sulla distanza, alberi, circuiti euleriani ed hamiltoniani, numeri associati ad un grafo e loro relazioni, matrici associate ad un grafo e loro proprietà. Verranno anche presentati alcuni problemi su grafi ed i relativi algoritmi risolutivi.

Teoria dei giochi: verranno presentate le assunzioni, le forme di rappresentazione ed i concetti di base della teoria dei giochi ed i principali metodi di analisi e soluzione per giochi non cooperativi.

Testi di riferimento
– Dispense ed altro materiale didattico messo a disposizione dal docente

– Thomas S. Ferguson: “A Course in Game Theory”, World Scientific, 2020 (disponibile in formato elettronico presso la biblioteca di ateneo).

– altri testi consigliati.