Corso dottorale
2° semestre
Docente Massimo Di Francesco (Dipartimento di Matematica e Informatica, Università degli Studi di Cagliari)
Corso dottorale
Docente: Massimo Di Francesco (Dipartimento di Matematica e Informatica, Università degli Studi di Cagliari)
Ore: 32
Data d’inizio: 3 aprile 2024
Il corso è articolato in 16 lezioni in inglese, che si terranno martedì, mercoledì e venerdì dalle 9:30 alle 11:10 in aula F al Palazzo delle Scienze.
Sunto del corso
Per via della pervasività delle reti nella società moderna, i metodi di ottimizzazione su rete trovano applicazione in vari ambiti come l’ingegneria, l’architettura e l’economia, ma sono solo marginalmente affrontati nei corsi istituzionali. Per ovviare a questo inconveniente, si propone uno specifico corso per il Dottorato in Ingegneria Civile e Architettura. Il corso ha l’obiettivo di fornire una profonda comprensione teorica e pratica dei metodi impiegati per la pianificazione ottima di percorsi e flussi su rete. In particolare, si illustreranno le ipotesi di applicabilità dei metodi proposti, si studieranno i loro step elementari e si opererà una loro valutazione in termini di complessità computazionale ed efficienza.
Descrizione estesa
In questo corso si studieranno i principali problemi di ottimizzazione su rete: i cammini minimi, i flussi massimi, gli alberi ricoprenti di minimo costo, i flussi di minimo costo e alcuni loro casi specifici (ad esempio, i problemi di assegnamento e trasporto). Per ogni problema, si presentano le condizioni di ottimalità e i conseguenti metodi impiegati per determinare le soluzioni ottime, mostrando come gli aspetti teorici si traducano in quelli implementativi impiegati negli applicativi informatici.
Il corso fa ampio uso di animazioni grafiche su esempi illustrativi, per illustrare i vari step dei metodi in studio e analizzare in modo critico i loro vantaggi e svantaggi. Il corso ha i seguenti obiettivi:
- Modellizzare vari problemi decisionali come problemi di ottimizzazione su rete;
- Fornire un’analisi accurata dei metodi impiegati per l’ottimizzazione su rete;
- Completare il profilo delle conoscenze matematiche e informatiche dei dottorandi su ottimizzazione, strutture dati e complessità computazionale.
Eventuali conoscenze preliminari di ottimizzazione lineare possono consentire una comprensione più profonda del corso, ma non sono indispensabili. Ad ogni modo, si richiedono conoscenze elementari di fondamenti di informatica per la lettura di pseudocodici, in modo da comprendere l’articolazione dei metodi proposti. Non si richiede invece la conoscenza di alcun software.
Alla conclusione del corso, i dottorandi dovranno impiegare alcuni metodi presentati per risolvere un problema realistico. Tale attività sarà condotta in una tesina, che può riguardare un tema proposto da docente o dottorando/a sulla base dei propri interessi di ricerca.
Programma
- I problemi di ottimizzazione su rete (lezioni 1 e 2)
- Definizioni di base (cammini, alberi e cicli), strutture dati e complessità computazionale (lezioni 3, 4 e 5)
- Il problema di cammino minimo: condizioni di ottimalità, algoritmi Label Setting e Label Correcting (lezioni 6, 7, 8, 9 e 10)
- Algoritmi di decomposizione dei flussi (lezione 11)
- Il problema del flusso massimo: condizioni di ottimalità e algoritmi di labeling (lezioni 12, 13 e 14).
- Il problema del flusso di costo minimo: condizioni di ottimalità e algoritmo di cancellazione dei cicli (lezione 15)
- Alberi ricoprenti di minimo costo: condizioni di ottimalità, algoritmi di Prim e Kruskal (lezione 16)
Contatti
mdifrance@unica.it, 0706758519
Modalità di iscrizione
Inviare email al docente.
Eventuali materiali messi a disposizione
Appunti del docente su https://elearning.unica.it/
Bibliografia e riferimenti Web
Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.
Matteo Fischetti. Introduction to Mathematical Optimization. Kindle Edition, 2019.