Programmazione Matematica

Programma d'Esame

Programmazione Lineare

• I seguenti capitoli del Chvátal: 1, 2, 3, 4, 5, 15;
• La dispensa sul tableau disponibile in Web;
• Avere una certa padronanza della visione geometrica. In particolare tramite la visione geometrica si sappiano motivare:
  • il teorema della dualità forte;
  • i Teoremi 5.4 e 5.5 del Chvátal.

Ottimizzazione Combinatoria

• Il capitolo ``Algoritmi e Complessità'' del testo di Maffioli (dimostrare di averlo letto tutto e di averci pensato almeno un po');
• Le dispense e gli svolgimenti di provette disponibile in Web:
  • Svolgimento della Provetta sulla PL;
  • Svolgimento della Provetta sulla PC;
  • ``Algoritmi Combinatori per la ricerca di Cammini Ottimi'' in Note per il Corso;
  • ``Flusso massimo e cammini aumentanti: Esempi Patologici'' in Note per il Corso;
  • ``Introduzione al tableau'' in Esercizi vari e supplettivi'';
• avere solamente la nozione di totale unimodularità e di quale sia il suo ruolo;
• I seguenti capitoli del testo di Cook, Cunningham, Pulleyblank e Schrijver:
  • Problems, Algorithms and Bounds;
  • Optimal Trees and Paths;
  • Maximum Flow Problems. ---esclusa la Sezione 4 ("Push-Relabel Maximum Flow Algorithms"), esclusa inoltre la parte "Minimum Cuts and Linear Programming";
  • Optimal Matchings. ---escluse le due parti: "Implementation of the Blossom Algorithm" e "Implementation of the Weighted Matching Algorithm";
  • The Travelling Salesman Problem (avere colto il quadro generale e le tematiche principali);
  • Matroids. ---più precisamente:
    SI greedy, SI conoscenza di vari tipi di matroidi e loro costruzioni; Intersezione di Matroidi: solo enunciato del teorema fondamentale e sapere che il problema è risolvibile in tempo polinomiale.

  Nota: Gli esercizi del testo di Cook, Cunningham, Pulleyblank sono fortemente consigliati.

Il presente programma è disponible anche in forma di .ps file