CODICE 80155 ANNO ACCADEMICO 2017/2018 CFU 9 cfu anno 1 INGEGNERIA INFORMATICA 8733 (LM-32) - 7 cfu anno 3 MATEMATICA 8760 (L-35) - 7 cfu anno 1 MATEMATICA 9011 (LM-40) - SETTORE SCIENTIFICO DISCIPLINARE MAT/09 LINGUA Italiano SEDE PERIODO 1° Semestre 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. MODALITA' DIDATTICHE Lezioni frontali ed esercitazioni. PROGRAMMA/CONTENUTO INTRODUZIONE ALLA RICERCA OPERATIVA Le origini della Ricerca Operativa. Problemi reali e modelli matematici. Limiti dei modelli. Obiettivi, variabili decisionali, vincoli. Classificazioni dei problemi di ottimizzazione. Dimensione dei problemi e inefficienza degli algoritmi “brute force”. Un esempio numerico introduttivo. Il ruolo e l’utilità della Ricerca Operativa nell’ambito dell’ICT. PROGRAMMAZIONE LINEARE (PL) Modelli di PL di importanza applicativa. Esempio grafico introduttivo. Algebra e geometria della PL. Algoritmo del simplesso. Interpretazioni algebrica e geometrica. Simplesso sul tableau. Analisi di post-ottimalità. DUALITÀ Problemi duali: modelli di PL di importanza applicativa. Dualità debole e dualità forte. Interpretazione economica della dualità (prezzi ombra). Slackness complementare. PROGRAMMAZIONE LINEARE A NUMERI INTERI (PLI) Modelli di PLI di importanza applicativa (Matching, Sequencing, Fixed-Charge, Knapsack, Steiner Tree, Plant Location, Scheduling). Algebra e geometria della PLI. Matrici totalmente unimodulari. Algoritmo di tipo branch-and-bound. Algoritmo basati su piani di taglio. Tagli di Gomory. Algoritmi di tipo branch-and-cut. GRAFI E RETI Definizioni e generalità sui grafi. Rappresentazione dei grafi. Il problema di Shortest Path (SP) e il suo modello di PLI. Algoritmo di Dijkstra. Algoritmo di Bellman-Ford. Il problema di Shortest Spanning Tree (SST) e il suo modello di PLI. Algoritmo di Kruskal. Algoritmo di Primm-Dijkstra. Algoritmi greedy. Cenni al Travelling Salesman Problem (TSP) e al suo modello di PLI. “CASE-STUDIES” IN AMBITO INFORMATICO Stima del worst-case execution time (WCETP: “Worst-Case Execution Time Problem”) di un programma Control flow graph per WCETP Modello di PLI per WCETP Il problema della selezione degli indici (ISP: “Index Selection Problem”) nei database relazionali Modello di PLI per ISP Risoluzione di ISP con mediante branch-and-bound Risoluzione di ISP con mediante branch-and-cut Confronto numerico fra le due metodologie di risoluzione per ISP CENNI ALLA TEORIA DELLA COMPLESSITÀ Concetto di istanza e dimensione di un'istanza. Complessità computazionale di un algoritmo. Problemi trattabili ed intrattabili. Problemi in forma decisionale. Classi P, NP e co-NP. Concetto di algoritmo non-deterministico. Il teorema di Cook. La classe dei problemi NP-completi. Esempi di problemi NP-completi e rispettivi modelli di PLI: knapsack, Steiner tree, … Problemi NP-hard. PROGRAMMAZIONE DINAMICA (PD) Esempio introduttivo. Problemi di ottimizzazione a stadi. Contesto deterministico. Fase backward e fase forward. Principio di ottimalità. Le equazioni di Bellman. Estensione al contesto stocastico. La “maledizione della dimensionalità”. CENNI ALLA PROGRAMMAZIONE NON LINEARE (PNL) PNL libera: Esistenza e caratterizzazione dei minimi. Condizioni necessarie e sufficienti. Metodi del gradiente. Metodo di Newton-Raphson. Velocità di convergenza. PNL vincolata: Esistenza e caratterizzazione dei minimi. Condizioni necessarie e sufficienti. Moltiplicatori di Lagrange. Metodi con funzioni di penalità. Metodi barriera o a punto interno. ESERCITAZIONI Esercizi sugli argomenti del Corso. Strumenti software per la Ricerca Operativa (Lingo, Matlab Optimization Toolbox, ecc.). TESTI/BIBLIOGRAFIA Dispense fornite dal Docente. DOCENTI E COMMISSIONI MARCELLO SANGUINETI Ricevimento: Su appuntamento Commissione d'esame MARCELLO SANGUINETI (Presidente) FEDERICA BRIATA MAURO GAGGERO DANILO MACCIO' LEZIONI INIZIO LEZIONI 18 settembre 2017 Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME Scritto Calendario appelli Data appello Orario Luogo Tipologia Note 29/01/2018 10:00 GENOVA Scritto 16/02/2018 14:00 GENOVA Scritto 28/05/2018 10:00 GENOVA Scritto 03/07/2018 10:00 GENOVA Scritto 13/09/2018 10:00 GENOVA Scritto