Generali:

  • Dipartimento: Ingegneria
  • Settore Ministeriale: MAT/09
  • Codice di verbalizzazione: 8037587
  • Metodi di insegnamento: Frontale
  • Metodi di valutazione: Scritto
  • Prerequisiti: Algebra Lineare. Elementi base di calcolo e di informatica.
  • Obiettivi: Problemi di decisione e di programmazione matematica. Problemi di ottimizzazione combinatoria. Problemi di programmazione lineare (PL) e lineare intera (PLI). Ottimizzazione convessa. Definizioni e proprietà di base. Elementi di geometria di R^n e geometria della PL. Metodo del simplesso e sue varianti. Rilassamenti di un problema di PL. Teoria della dualità per la PL. Calcolo del duale di PL in formati diversi. Proprietà del duale di un PL e condizioni di ottimalità. Analisi di sensibilità. Simplesso duale. Formulazione di problemi di PL: esempi. Teoria dei Grafi. Relazioni binarie e grafi non orientati: definizioni. Handshaking Lemma. Cammini. Sottografi. Grafi euleriani. Connessione e aciclicità. Alberi. Grafi bipartiti. Algoritmi di visita di un albero. Insiemi indipendenti di vertici e di lati. Matching su grafo bipartito. Vertex cover. Elementi di conteggio. Notazioni asintotiche ("Big-O", Omega, Theta). Complessità computazionale di un algoritmo. Grafi orientati. Definizioni. Algoritmi di visita. Numerazione topologica. Alberi ricoprenti di peso minimo (MST) per grafi non orientati e connessi. Algoritmi di Kruskal e Prim. Cammini minimi su grafi orientati. Algoritmo di Dijkstra. Algoritmo di Floyd-Warshall. Flusso su reti: Massimo flusso. Algoritmo di Ford e Fulkerson. Problemi di flusso a costo minimo: Simplesso su reti.
  • Ricevimento: Per appuntamento da concordare via email.

Didattica:

  • A.A.: 2016/2017
  • Canale: UNICO
  • Crediti: 6
  • Obbligo di Frequenza: No