Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Ingegneria
INGEGNERIA INFORMATICA
Insegnamento
RICERCA OPERATIVA 1
IN11112347, A.A. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2019/20

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INGEGNERIA INFORMATICA
IN0521, ordinamento 2009/10, A.A. 2019/20
N0
porta questa
pagina con te
Crediti formativi 9.0
Tipo di valutazione Voto
Denominazione inglese OPERATIONS RESEARCH 1
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Sito E-Learning https://elearning.dei.unipd.it/course/view.php?idnumber=2019-IN0521-000ZZ-2019-IN11112347-N0
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile MATTEO FISCHETTI MAT/09

Mutuazioni
Codice Insegnamento Responsabile Corso di studio
INL1000878 RICERCA OPERATIVA MATTEO FISCHETTI IN0527

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
AFFINE/INTEGRATIVA Attività formative affini o integrative MAT/09 9.0

Organizzazione dell'insegnamento
Periodo di erogazione Primo semestre
Anno di corso I Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 9.0 72 153.0

Calendario
Inizio attività didattiche 30/09/2019
Fine attività didattiche 18/01/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2009

Commissioni d'esame
Commissione Dal Al Membri
10 A.A. 2019/2020 01/10/2019 15/03/2021 FISCHETTI MATTEO (Presidente)
SALVAGNIN DOMENICO (Membro Effettivo)
FERRANTE AUGUSTO (Supplente)
FERRARI CARLO (Supplente)
9 A.A. 2018/2019 01/10/2018 15/03/2020 FISCHETTI MATTEO (Presidente)
SALVAGNIN DOMENICO (Membro Effettivo)
FERRANTE AUGUSTO (Supplente)
PIETRACAPRINA ANDREA ALBERTO (Supplente)

Syllabus
Prerequisiti: Nozioni di base di informatica e di calcolo matriciale
Conoscenze e abilita' da acquisire: Conoscere i fondamenti della Ricerca Operativa, ed in particolare le tecniche di ottimizzazione per problemi di tipo lineare e di tipo combinatorio, applicandole ad esempi (semplificati) di interesse applicativo. Essere in grado di classificare un modello matematico di decisione (decisori, obiettivi, variabili, vincoli, dati, contesto decisionale).
Modalita' di esame: Tradizionale
Criteri di valutazione: Prova scritta
Contenuti: Problemi di ottimizzazione. Programmazione Lineare (PL). Programmazione Lineare Intera (PLI). Teoria della Complessita` Computazionale. Teoria dei Grafi. Problemi NP-completi.
Attivita' di apprendimento previste e metodologie di insegnamento: Problemi di ottimizzazione: Programmazione matematica e programmazione convessa.
Programmazione Lineare (PL) : Generalita`. Modelli di PL. Geometria della PL. Algoritmo del simplesso: metodo delle 2 fasi, forma matriciale e tableau, simplesso rivisto. Degenerazione. Dualita` in PL. Algoritmo del simplesso duale. Analisi di sensitivita`.
Programmazione Lineare Intera (PLI): Modelli di PLI. Totale unimodularita`. Metodo dei piani di taglio di Chvatal-Gomory. Algoritmo branch-and-bound. Problema di separazione ed algoritmo branch-and-cut.
Teoria della Complessita` Computazionale: Classi P, NP, co-NP e problemi NP-completi. Riduzioni polinomiali.
Teoria dei Grafi: Definizioni. Problemi polinomiali (con modelli ed algoritmi di risoluzione): albero minimo, cammini minimi, flussi.
Problemi NP-completi (con modelli ed algoritmi di risoluzione): knapsack, commesso viaggiatore, set covering e set packing, alberi di Steiner, plant location.
Eventuali indicazioni sui materiali di studio:
Testi di riferimento:
  • Matteo Fischetti, Lezioni di Ricerca Operativa. Padova: Progetto, 1999. Cerca nel catalogo