CODICE 80155 ANNO ACCADEMICO 2022/2023 CFU 9 cfu anno 1 COMPUTER ENGINEERING 11160 (LM-32) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE MAT/09 LINGUA Inglese SEDE GENOVA PERIODO 1° Semestre MATERIALE DIDATTICO AULAWEB PRESENTAZIONE Il Corso introduce a modelli e metodi di ottimizzazione utilizzabili per la soluzione di problemi decisionali. Si articola nei temi fondamentali della modellazione di problemi, dello studio della trattabilità computazionale e della risoluzione tramite algoritmi implementabili su un calcolatore. La materia viene presentata nei suoi aspetti metodologici, teorici ed applicativi. Vengono considerati vari contesti applicativi e sono trattati in dettaglio "case-studies" ingegneristici, con particolare attenzione a quelli in ambito informatico. Le lezioni sono organizzate in i) metodologia e ii) "case-study" provenienti da applicazioni "real-world". Esercizi addizionali e utilizzo di strumenti software sono presentati durante ore di esercitazione. OBIETTIVI E CONTENUTI OBIETTIVI FORMATIVI The Course introduces to optimization models and methods for the solution of decision problems. It is structured in the main topics of problem modelling, computational tractability, and solution by means of algorithms that can be implemented on a computer. Several applications are considered and various case studies are detailed. The target of the Course consists in making the students acquire the expertise to face decision problems by means of models and methods that can operate in the presence of limited resources. The students will be taught to: understanding and modelling a decision process in terms of an optimization problem by defining the decision variables, the cost function to be minimized (or the figure of merit to be maximized), and the constraints; framing the obtained problem within the range of the reference optimization problems (linear/nonlinear, discrete/continuous, deterministic/stochastic, static/dynamic, etc); achieving the matching between the corresponding solving algorithm and a suitable software. OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO Scopo del Corso è far acquisire le competenze che consentano di affrontare problemi applicativi, sviluppando modelli e metodi che operino in modo efficiente in presenza di risorse limitate. Agli studenti verrà insegnato a: interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli; inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.); realizzare il "matching" tra l’algoritmo risolutivo (da scegliere tra quelli esistenti o da progettare) e un adeguato supporto software di elaborazione. PREREQUISITI Algebra lineare. Calcolo vettoriale e matriciale. Fondamenti di Analisi Matematica e Geometria. MODALITA' DIDATTICHE Lezioni frontali ed esercitazioni. PROGRAMMA/CONTENUTO INTRODUZIONE ALLA RICERCA OPERATIVA (RO) Le origini della RO Problemi reali e modelli matematici Obiettivi, variabili decisionali, vincoli Esempi introduttivi e limiti dei modelli Dimensione dei problemi Inefficienza degli algoritmi “brute force” La RO sul grande schermo, ovvero “Hollywood e la RO” Classificazioni dei problemi di ottimizzazione Il ruolo della RO nell’Informatica PROGRAMMAZIONE LINEARE (PL) Esempio introduttivo: un modello di PL nell’Informatica Altri modelli di PL di importanza applicativa Esempio grafico introduttivo Algebra e geometria della PL Algoritmo del simplesso: punto di vista algebrico e punto di vista geometrico Simplesso sul tableau Analisi di post-ottimalità DUALITÀ Modelli duali di importanza applicativa Dualità debole e dualità forte Interpretazione economica della dualità (prezzi ombra) Slackness complementare PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI) Esempio introduttivo: un modello di PLI nell’Informatica Alcuni modelli di PLI di importanza applicativa Matching Sequencing Fixed-Charge Knapsack Algebra e geometria della PLI Il concetto di “enumerazione implicita” Algoritmo di tipo branch-and-bound. Criteri di esplorazione dell’albero di branch-and-bound Algoritmo basati su piani di taglio. Tagli di Gomory Algoritmi di tipo branch-and-cut CENNI ALLA COMPLESSITÀ Concetto di istanza e dimensione di un'istanza Complessità computazionale di un algoritmo Problemi trattabili e problemi intrattabili Problemi in forma decisionale Classi P, NP e co-NP Trasformazioni polinomiali La classe dei problemi NP-completi Forma normale congiuntiva nella logica Booleana ll problema della soddisfacibilità Il Teorema di Cook Esempi di problemi NP-completi e NP-hard Ricadute applicative e computazionali della Teoria della Complessità GRAFI E RETI Grafi e loro rappresentazioni Grafi orientati e non orientati Sottografi e sottografi indotti Grado, stella, grafi completi, densità, grafi densi e grafi sparsi Clique massime e massimali Matrice di incidenza e matrice di adiacenza Grafi connessi e componenti connesse Cammini, cammini semplici, cicli Percorsi e cicli hamiltoniani Percorsi e cicli euleriani Alberi, foreste, alberi ricoprenti Esempi di problemi di Informatica modellabili su grafi Shortest Path (SP) Modello su grafo Modello di PLI Studio della complessità Algoritmo di Dijkstra Algoritmo di Bellman-Ford Algoritmo di Floyd-Warshall Shortest Spanning Tree (SST) Modello su grafi Modello di PLI Studio della complessità Algoritmo di Kruskal. Il concetto di “algoritmo greedy” Algoritmo di Prim-Dijkstra Cenni al Travelling Salesman Problem (TSP) Modello su grafo Modello di PLI Studio della complessità Aspetti computazionali: i “TSP test data” disponibili in rete e il “TSP challange” PROGRAMMAZIONE NON-LINEARE (PNL) Esempio introduttivo: un modello di PLI nell’Informatica PNL libera Esistenza e caratterizzazione dei minimi Ottimalità: condizioni necessarie e condizioni sufficienti Velocità di convergenza degli algoritmi di PNL Algoritmo del gradiente e algoritmi “gradient-based” Algoritmo di Newton-Raphson “Test functions” per la valutazione delle prestazioni degli algoritmi di PNL Benchmark computazionali disponibili in rete PNL vincolata Esistenza e caratterizzazione dei minimi Ottimalità: condizioni necessarie e condizioni sufficienti Gradiente proiettato Moltiplicatori di Lagrange Metodi basati sui Moltiplicatori di Lagrange Metodi basati su funzioni di penalità Metodi barriera o a punto interno PROGRAMMAZIONE DINAMICA (PD) Esempio introduttivo Problemi di ottimizzazione a stadi. Contesto deterministico Fase backward e fase forward Principio di ottimalità Le equazioni di Bellman Cenni all’estensione al contesto stocastico La “maledizione della dimensionalità” Risoluzione del problema del Shortest Path (SP) mediante la PD Risoluzione del Travelling Salesman Problem (TSP) mediante la PD ALCUNI CASE-STUDY IN AMBITO INFORMATICO Il problema dell’Index Selection Problem (ISP) nei database relazionali Modello di PLI per ISP Complessità di ISP Risoluzione di ISP mediante algoritmo branch-and-cut Considerazioni computazionali Confronto fra branch-and-bound e branch-and-cut per ISP Un problema di ottimizzazione su reti di computer Formulazione come modello di PL Risoluzione mediante l’algoritmo del simplesso Stima di worst-case execution time di un programma Modello su grafo: control flow graph Modello di PLI Modelli di PNL per l’apprendimento da dati INTRODUZIONE AGLI STRUMENTI SOFTWARE PER LA RICERCA OPERATIVA LINGO CPLEX Optimization Studio MATLAB Optimization Toolbox EXCEL ESERCITAZIONI Svolte in modo distribuito durante il Corso TESTI/BIBLIOGRAFIA Dispense fornite dal Docente e disponibili in formato elettronico. DOCENTI E COMMISSIONI MARCELLO SANGUINETI Ricevimento: Su appuntamento Commissione d'esame MARCELLO SANGUINETI (Presidente) MAURO GAGGERO DANILO MACCIO' ANGELA LUCIA PUSILLO MASSIMO PAOLUCCI (Presidente Supplente) LEZIONI INIZIO LEZIONI https://courses.unige.it/11160/p/students-timetable Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME Scritto, se sarà possibile fare esami in presenza. Altrimenti, il Docente deciderà se l'esame su Teams sarà orale o scritto. MODALITA' DI ACCERTAMENTO Comprensione dei concetti esposti durante il Corso. Capacità di: - interpretare e modellare un processo decisionale nei termini di un problema di ottimizzazione, individuando cioè le variabili decisionali, la funzione di costo da minimizzare (o la cifra di merito da massimizzare) e i vincoli; - inquadrare il problema nella gamma dei problemi considerati “canonici” (lineari/non lineari, discreti/continui, deterministici/stocastici, statici/dinamici, ecc.); - scegliere e/o sviluppare un algoritmo risolutivo e utilizzarlo per risolvere il problema. Calendario appelli Data appello Orario Luogo Tipologia Note 09/01/2023 10:30 GENOVA Scritto 02/02/2023 10:30 GENOVA Scritto 29/05/2023 10:30 GENOVA Scritto 17/07/2023 10:30 GENOVA Scritto 11/09/2023 10:30 GENOVA Scritto ALTRE INFORMAZIONI Per il Corso di Laurea im Matematica, che mutua solo 7 cfu, sono esclusi dal programma i "capitoli" PROGRAMMAZIONE DINAMICA (PD) ALCUNI CASE-STUDY IN AMBITO INFORMATICO
