- Oggetto:
- Oggetto:
Ottimizzazione Combinatoria
- Oggetto:
Combinatorial Optimization
- Oggetto:
Anno accademico 2023/2024
- Codice attività didattica
- MFN1349
- Docenti
- Andrea Cesare Grosso (Titolare)
Pierre Hosteins (Titolare) - Corso di studio
- [008515] Laurea magistrale in informatica
- Anno
- 1° anno, 2° anno
- Periodo
- Secondo semestre
- Tipologia
- Affine o integrativo
- Crediti/Valenza
- 6 CFU - Numero di ore - Number of hours: 48 (in aula)
- SSD attività didattica
- MAT/09 - ricerca operativa
- Erogazione
- Tradizionale
- Lingua
- Italiano
- Frequenza
- Facoltativa
- Tipologia esame
- Orale
- Prerequisiti
-
Per seguire il corso è consigliabile avere chiare alcune nozioni apprese durante il corso di Calcolo Matriciale e Ricerca Operativa e, in particolare, quelle di modelli di programmazione lineare e dell'algoritmo del simplesso.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): Calcolo Matriciale e Ricerca Operativa.In order to be able to successfully attend the course, the student is expected to have some (not necessarily deep) basic knowledge of matrix calculus and the basics of linear programming especially the simplex method and modeling techniques in linear programming.
Preparatory courses (providing the expected entry skills): Matrix Calculus and Operational Research. - Oggetto:
Sommario insegnamento
- Oggetto:
Avvisi
- Oggetto:
Obiettivi formativi
Il corso verte sulla discussione di problemi di ottimizzazione, in particolare di problemi di ottimizzazione combinatoria. Si pone come obiettivo quello di familiarizzare lo studente con problemi di ottimizzazione che occorrono frequentemente in applicazioni pratiche, permettendogli di riconoscere la difficoltà del problema e fornendogli gli strumenti per risolvere tali problemi.L'obiettivo di insegnare modelli di ottimizzazione fa parte degli obiettivi formativi specifici del CdS in Informatica (LM18), in particolare è tra quelli relativi all´indirizzo orientato ai sistemi per il trattamento dell'informazione.
The course deals with optimization problems, with a special emphasis on combinatorial optimization problems. The course provides the student with knowledge about the main combinatorial optimization problems arising in practical situations, making him/her able to determine the complexity of the problem and master the algorithmic techniques required to solve such problems.The objective of teaching optimisation models is part of the specific educational objectives of the BSc in Computer Science (LM18), in particular, it is among those related to the systems-oriented field of information processing.
- Oggetto:
Risultati dell'apprendimento attesi
Al termine del corso lo/la studente/ssa dovrebbe essere in grado di riconoscere un problema di ottimizzazione combinatoria, definirne la complessità o almeno congetturarla, saperne costruire un modello matematico ed essere in grado di applicare le tecniche di risoluzione (esatte, approssimate o euristiche) viste.CONOSCENZA E CAPACITA' di COMPRENSIONE. Acquisizione delle conoscenze fondamentali sulla complessità dei problemi di ottimizzazione combinatoria, e delle principali tecniche per la loro risoluzione.
CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Capacità di riconoscerte problemi di ottimizzazione combinatoria, selezionando gli strumenti più adatti alla loro risoluzione.
AUTONOMIA DI GIUDIZIO. Acquisizione di autonomia di giudizio nel valutare i tipi di problemi di ottimizzazione combinatoria che si presentano in pratica, discutendo efficacia ed efficienza di algoritmi risolutivi esatti o approssimati.
ABILITÀ COMUNICATIVE. Acquisizione di competenze e strumenti per poter discutere difficioltà dei problemi e validità di algoritmi risolutivi.
CAPACITÀ DI APPRENDIMENTO Acquisizione di capacità autonome di apprendimento in campo modellistico e algoritmico per problemi combinatori.
At the end of the course the student should be able to recognize a combinatorial optimization problem, define its complexity or at least conjecture it, know how to build a mathematical model and be able to apply the resolution techniques (exact, approximate or heuristic ) views.KNOWLEDGE AND UNDERSTANDING. Acquisition of fundamental knowledge on the complexity of combinatorial optimization problems, and of the main techniques for their resolution.
ABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING. Ability to recognize combinatorial optimization problems, selecting the most suitable tools for their resolution.
AUTONOMY OF JUDGMENT. Acquisition of independent judgment in evaluating the types of combinatorial optimization problems that arise in practice, discussing the effectiveness and efficiency of exact or approximate solution algorithms.
COMMUNICATION SKILLS. Acquisition of skills and tools to be able to discuss the difficulty of problems and the validity of solution algorithms.
LEARNING SKILLS Acquisition of autonomous learning skills in the field of modeling and algorithmic for combinatorial problems.
- Oggetto:
Programma
- Introduzione alla Ricerca Operativa: dal problema reale agli algoritmi di risoluzione. Esempi di modelli matematici.
- Richiami di Programmazione Lineare. Teoria della Dualità.
- Problemi PLI: rilassamenti, branch and bound, algoritmi basati su piani di taglio. Applicazione a problemi classici (TSP, zaino).
- Problemi di flusso su reti: cammino minimo, flusso massimo, flusso di costo minimo; modellazione ed algoritmi di soluzione.
- Programmazione Dinamica.
- Algoritmi di approssimazione.
- Introduction to Operations Research: from the problem to the solution algorithm. Examples of mathematical programming models.
- Basics of Linear Programming. Duality theory.
- PLI: relaxations, branch and bound, cutting planes. Applications to classic problems (TSP, knapsack).
- Network flow problems: shortest path, maximum flow, min cost flow; models and algorithms.
- Dynamic programming.
- Approximation algorithms.
- Oggetto:
Modalità di insegnamento
Lucidi proiettati in aula e tradizionali spiegazioni alla lavagna.Traditional slides and blackboard-supported class lectures.- Oggetto:
Modalità di verifica dell'apprendimento
L'esame consta di due parti obbligatorie.La prima è una prova scritta che ha lo scopo di verificare la conoscenza dei principali temi trattati durante il corso. La seconda è una prova orale che ha come oggetto la discussione di un progettino assegnato ad inizio sessione.
Il progetto consta di una parte teorica obbligatoria e di una parte implementativa facoltativa. Il progetto può essere svolto a gruppi di al più 2 persone. La discussione del progetto avviene soltanto dopo aver superato la prova scritta.
In termini di punteggio la prova scritta permette di ottenere un punteggio massimo pari a 28/30. Il progetto aumenta il voto della prova scritta di 3 punti per la parte teorica e 3 punti per la parte implementativa.
The exam consists of two compulsory parts.The first is a written test which aims to verify knowledge of the main topics covered during the course.
The second is an oral test whose object is the discussion of a project assigned at the beginning of the session.
The project consists of a compulsory theoretical part and an optional implementation part. The project can be carried out in groups of at most 2 people. The discussion of the project takes place only after passing the written test. In terms of scores, the written test allows the student to obtain a maximum score of 28/30. The project increases the mark of the written test by 3 points for the theoretical part and 3 points for the implementation part.
- Oggetto:
Attività di supporto
Verranno forniti appunti disponibili alla pagina I-learn dell'insegnamento.Lecture notes will be made available on the I-lear page for the course.Testi consigliati e bibliografia
- Oggetto:
C.H. Papadimitriou, K.R. Steiglitz, "Combinatorial optimization: algorithms and complexity", Prentice Hall (solo per eventuali approfondimenti - reperibile in biblioteca).
- Oggetto:
