CODICE 80155 ANNO ACCADEMICO 2019/2020 CFU 9 cfu anno 1 INGEGNERIA INFORMATICA 8733 (LM-32) - GENOVA 7 cfu anno 3 MATEMATICA 8760 (L-35) - GENOVA 7 cfu anno 1 MATEMATICA 9011 (LM-40) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE MAT/09 LINGUA Italiano 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" in ambito informatico. OBIETTIVI E CONTENUTI OBIETTIVI FORMATIVI 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. Vengono considerati vari contesti applicativi e sono trattati in dettaglio alcuni "case-study" in ambito informatico. 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. 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) FEDERICA BRIATA MAURO GAGGERO DANILO MACCIO' MASSIMO PAOLUCCI LEZIONI INIZIO LEZIONI 23 settembre 2019 Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME 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 06/02/2020 09:00 GENOVA Scritto 09/06/2020 09:00 GENOVA Scritto 30/06/2020 09:00 GENOVA Scritto 10/09/2020 09:00 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