Programma Dettagliato di Ricerca Operativa per Ingegneria Gestionale

Cerchiamo di riportare qui di seguito il programma svolto giorno per giorno:

Data	Docente	Argomenti
5-10-2011	Romeo Rizzi	ricerca del minimo per scansione. Induzione: ogni insieme finito ha minimo. Somma di Gauss. Intuizione e codifica di BubbleSort, MaxSort, InsertSort (Sottolineando invarianti di ciclo ed interpretazione induttiva). Problema: ordinare con un numero subquadratico di confronti.
6-10-2011	Romeo Rizzi	MergeSort: intuizione, analisi, codifica. Divide et impera. fast-number-multiplication, intuizione dietro fast-matrix-multiplication, e menzione a fast-Fourier-transform.
12-10-2011	Romeo Rizzi	Induzione: piastrellature, ricorrenza del MergeSort, proposta Hanoi. Senso, storia ed alcuni successi ed esempi della Ricerca Operativa. Ragionamento per assurdo: i primi sono infiniti, proposta del problema dei cappelli.
13-10-2011	Romeo Rizzi	Soluzione problema cappelli. Induzione: torre Hanoi. Altre piastrellature. Numero di ordinamenti. Piccoli esercizi su probabilità classica. Proposta: in quanti modi posso scrivere un naturale come somma di naturali positivi. Proposta: problema delle uova marziane.
19-10-2011	Romeo Rizzi	Monovarianti, invarianti e loro uso (esempi: tilings di scacchiere, le streghe, stanze al college, robottino). Introduzione ai grafi. Problema dei ponti di Konighsberg. Tecniche base del matematico ed il primo grafo della storia. Cammini e cicli Euleriani. NP e coNP. Congettura di Eulero è una buona congettura. Teorema di Eulero. Teorema di Eulero è un buon teorema. Lemma delle strette di mano. Altri esempi di buoni teoremi: la caratterizzazione del GCD di Euclide.
20-10-2011	Romeo Rizzi	In aula informatica. Esperienza nella codifica di soluzioni ricorsive: codifica di 2^n, n!, torre di Hanoi. (Fiducia in ricorsione).
26-10-2011	Romeo Rizzi	In aula tradizionale, ma lavorando con un portatile. Listare piastrellature. Esperienza Fibonacci, ricorsione con memoizzazione, programmazione dinamica. (Vista da fuori dell'albero di ricorsione).
27-10-2011	Romeo Rizzi	Programmazione dinamica e ricorsione con memoizzazione: il problema triangolo e problemi di cammini su griglia.
2-11-2011	Romeo Rizzi	Programmazione dinamica: problema di massima sottosequenza crescente e problema di massima sottosequenza comune.
3-11-2011	Romeo Rizzi	Relazione esistente tra i due problemi di massima sottosequenza crescente e di massima sottosequenza comune. Accenno all'importanza ed ai ruoli del mestiere di ridurre da un problema all'altro e proposta del problema dello zaino. Problemi di decisione, di ottimizzazione, di costruzione.
9-11-2011	Romeo Rizzi	Ancora riduzioni tra problemi. Alcune versioni del problema dello zaino. (Knapsack e partition - decisione, ottimizzazione e search).
10-11-2011	Romeo Rizzi	Ancora riduzioni tra problemi. Problema dello zaino con pesi e valori.
16-11-2011	Romeo Rizzi	Connessione di grafi e cammini minimi.
17-11-2011	Romeo Rizzi	Alberi ricoprenti di peso minimo, algoritmi di Prim e Kruska. Formula di Eulero. Enunciato del teorema di Kuratowski e del graph minor theorem.
23-11-2011	Romeo Rizzi	Problema di ciclo Hamiltoniano e riduzioni tra vari problemi di quel tipo. Riduzioni tra problemi di SAT. Caratterizzazioni di grafi bipartiti.
24-11-2011	Romeo Rizzi	Matching bipartito. Teorema di Hall e teorema di Konig e loro equivalenza.
30-11-2011	Romeo Rizzi	Riduzioni tra problemi di SAT. Algoritmo delle foreste aumentanti per il matching bipartito.
1-12-2011	Romeo Rizzi	Massimo flusso e minimo taglio.
14-12-2011	Romeo Rizzi	Introduzione alla programmazione lineare con un problema il 2 variabili. Risoluzione grafica, regione ammissibile, poliedri e politopi, certificato di ottimalità, analogia fisica, moltiplicatori di Lagrange.
15-12-2011	Romeo Rizzi	Programmazione lineare e programmazione lineare intera. La programmazione lineare intera è NP-completa. Un problema in 3 variabili. Problemi in forma standard. Esemplificazione della fase 2 del metodo del simplesso sul problema in 3 variabili.
21-12-2011	Romeo Rizzi	Degenerazione, cycling, regola di Bland, metodo lessicografico, teorema fondamentale della programmazione lineare, considerazioni computazionali, metodo dell'elissoide ed algoritmi di punto interno.
22-12-2011	Romeo Rizzi	Il metodo del simplesso eseguito sul problema in 2 variabili, visione geometrica. Introduzione alla teoria della dualità, il primale è il duale del duale, e teorema della dualità debole.
22-12-2011	Romeo Rizzi	Il teorema della dualità forte. Il tableau. Algoritmo duale-primale. Il teorema degli scarti complementari a suo uso.
11-01-2012	Romeo Rizzi	La fase 1 del metodo del simplesso con il problema ausiliario. Interpretazione economica delle variabili duali.
11-01-2012	Romeo Rizzi	Buona caratterizzazione per massime sottosequenze crescenti. Un problema di zaino.
12-01-2012	Romeo Rizzi	Post-ottimalità ed analisi di sensitività.
12-01-2012	Romeo Rizzi	Esercizi in preparazione all'esame.

created: 12 ottobre 2011
updated: 12 gennaio 2012