CODICE 111097 ANNO ACCADEMICO 2024/2025 CFU 6 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. Si consigliano gli studenti lavoratori e gli studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali di contattare il docente all’inizio del corso per concordare modalità didattiche e d’esame che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali. 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 Case-study di di applicazione della PL nell'Ingegneria 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 Case-study di di applicazione della PLI Inell'Ingegneria 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” Case-study di applicazione dell'ottimizzazione su grafi nell'Ingegneria 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 Case-study di applicazione della PNL nell'Ingegneria 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 Case-study di applicazione della Programmazione Dinamica nell'Ingegneria 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 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) DANILO MACCIO' MASSIMO PAOLUCCI (Presidente Supplente) MAURO GAGGERO (Supplente) ANGELA LUCIA PUSILLO (Supplente) LEZIONI INIZIO LEZIONI https://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso 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 23/12/2024 10:00 GENOVA Scritto Aula B5 23/01/2025 10:00 GENOVA Scritto Aula B5 10/02/2025 10:00 GENOVA Scritto Aula G2B 03/06/2025 10:00 GENOVA Scritto Aula G2A 17/06/2025 10:00 GENOVA Scritto Aula G2A 02/09/2025 10:00 GENOVA Scritto Aula G2A