Programma Dettagliato di Ricerca Operativa per la triennale in Matematica

Data	Argomenti
3-3-2015 (2 ore)	Introduzione al corso. Problemi, istanze, e algoritmi: Trovare il massimo in un vettore. Invarianti e monovarianti. Invarianti di ciclo. Dire di si, dire di no, buone caratterizzazioni:: Tiling di una griglia mxn. GCD di Euclide. Home: tiling di scacchiera con due angoli opposti rimossi.
5-3-2015 (2 ore)	Ricorsione/Induzione: Induzione=ricorsione come tecnica per produrre certificati positivi. Tiling di $2^k \times 2^k$ con tromini ad $L$. Induzione=ricorsione come tecnica per risolvere problemi di counting e listing, ed arrivare all'elaborazione di un algoritmo. Contare le piastrellature di un corridoio $1 \times n$ con piastrelle $1\times 1$ e $1\times 2$. Chiave d'oro ricorsiva. Problema proposto per casa: bagno a 2 corsie.
10-3-2015 (2 ore)	Invarianti/monovarianti: robot XOR su stringa binaria Induzione/ricorsione: corridoio $2 \times n$ Induzione=ricorsione come tecnica per risolvere problemi ed arrivare all'elaborazione di un algoritmo: SelectionSort, InsertSort e loro analisi (criterio caso peggiore e caso medio, complessità asintorica).
12-3-2015 (2 ore)	Ricerca binaria: efficacia, significato, e storia. Information theoretic lower bound. Merge sort: motivazione, analisi, e storia. Information theoretic lower bound per l'ordinamanto basato su confronto. Algoritmi di ordinamento lineari. Divide et Impera: una tecnica algoritmica, una tecnica per affrontare i problemi. Accenni storici ed esempi.
17-3-2015 (2 ore)	Invarianti/Monovarianti: Problemi (ri)proposti: problema delle stanze in gita, problema prefixSort di Knuth Intervallo di Somma Massima: Algoritmi polinomiali. Algoritmi e strutture dati. Le somme prefisse. Modello con queries. Approccio divide et impera.
24-3-2015 (2 ore)	Approccio divide et impera.: suggerisco una via per affrontare maxSommaIntervallo con approccio divide et impera. Obiettivo: un algoritmo nlog n. Ars inductandi.: il problema borse. Cosa sono la PL e la PLI ed il loro ruolo nella Ricerca operativa. Complessità*: il passaggio dal continuo al discreto rende il problema NP-completo. Scopriamo che la PLI è NP-completa e che sappiamo fare dimostrazioni di NP-completezza (prima riduzione da maxClique, solo per renderci conto quanto sia espressiva e quindi quanto possa essere utile disporre di un PLI Solver, poi anche riduzione da SAT).
26-3-2015 (1 ora)	la prima ora è stata dedicata alla presentazione della magistrale. Poi abbiamo lavorato sul problema triangolo. Abbiamo esplorato una soluzione proposta da un compagno. Era una soluzione di programmazione dinamica, molto bene! L'abbiamo esplorata per comprenderla meglio. Io ho preso una strada larga, approccio ricorsivo, ricorsione con memoizzazione, per riatterrare infine sulla soluzione proposta dal compagno.
31-3-2015 (2 ore --> 1 ora)	Oggi siamo stati in laboratorio ciberfisico. Siccome siamo partiti proprio da zero con la programmazione, ci siamo accordati che la conteggiamo come una sola ora. Siamo partiti col problema di acclimatamento al CMS (io), e vi ho inviato per mail quanto prodotto. Poi su piastrelle abbiamo implementato una soluzione ricorsiva, abbiamo toccato con mano quanto sia lenta, abbiamo introdotto la memoizzazione, ed abbiamo toccato con mano quanto accelleri la situazione. Abbiamo parlato di programmazione dinamica.
14-4-2015 (2 ore)	Abbiamo esplorato il problema pirellone. Abbiamo visto che in generale è possibile concentrarsi sulla forma di decisione di un problema. Abbiamo visto che pirellone, come problema di decisione, era in NP. Abbiamo formulato una sequenza di buone congetture sul problema.
21-4-2015 (2 ore)	Abbiamo dimostrato varie buone caratterizzazioni per il problema pirellone, e contemporaneamente ottenuto un algoritmo basato sul portare il pirellone a forma canonica. Ho richiamato alcuni problemi assegnati su invarianti e monovarianti, e ne ho assegnati di nuovi. Ho richiesto di camminare anche in autonomia su versante programmazione dinamica, avvalendosi delle dispense al sito del corso (in particolare il capitolo di Papadimitriou e Vazirani) e proponendo i seguenti problemi sul CMS: minato, triangolo, somme, poldo. Abbiamo iniziato la nostra teoria dei grafi. Siamo partiti dal buon teorema di Eulero sui ponti di Konigsberg, evidenziando: i grafi offrono un ottimo linguaggio per la modellizzazione di problemi; la buona congettura di Eulero; il lemma delle strette di mano; dimostrando la congettura otteniamo un algoritmo. Come esercizi: estendere al caso di grafi diretti. Ricerca della supersequenza universale di lunghezza minima per stringhe di lunghezza k. Il problema matita sul CMS.
23-4-2015 (2 ore)	Abbiamo parlato di cammini e cicli. Abbiamo definito la relazione "esiste un cammino da $u$ a $v$" ed osservato che per grafi diretti essa è una relazione di equivalenza. Abbiamo definito alberi e foreste ed elencato diverse proprietà degli alberi tutte deducibili per induzione dal lemma zero degli alberi: ogni albero tranne il seme ha almeno una foglia. Ci siamo posti il problema di caratterizzare cosa voglia dire essere connesso e contemporanemante di ottenere un algoritmo per la verifica della connessione. C'e' stato un bell'interplay tra questi due versanti: abbiamo scoperto che i certificati di si erano sottografi minimali criticamente connessi, ossia alberi, mentre per il certificato di no Re Artù ha regalato a Mago Merlino dei pennarelli con cui colorare i nodi. Come algoritmo, ne abbiamo sviluppato uno procedendo incrementalmente, con prime versioni già funzionanti senza bisogno di scrivere codice. Abbiamo scoperto che l'algoritmo computava anche le distanze da un nodo e costruiva un albero dei cammini minimi. Per raffinarne l'implementazione abbiamo introdotto le code FIFO e siamo pervenuti alla BFS.
28-4-2015 (2 ore)	Algoritmo di Dijkstra e code di priorità. riduzioni pseudopolinomiali. il problema del cammino semplice di peso minimo è NP-completo se i pesi degli archi possono essere anche negativi senza restrizioni. Il problema del ciclo e del cammino Hamiltoniano e riduzioni tra gli stessi.
30-4-2015 (2 ore)	La coda di priorità come struttura di dati astratta. Implementazione della coda di priorità tramite i binary heaps.
5-5-2015 (2 ore)	Programmazione dinamica: massima sottosequenza crescente. Esercizi proposti: massima sottosequenza palindroma e massima sottosequenza comune. Grafi bipartiti. Caratterizzazione e riconoscimento.
7-5-2015 (2 ore)	Programmazione dinamica: abbiamo visto insieme collage. Cicli e tagli. Il problema dell'albero ricoprente di peso minimo. L'algoritmo di Kruskal e l'algoritmo di Prim con accenno alle rispettive implementazioni. Cicli e tagli come linguaggi certificanti.
12-5-2015 (2 ore)	Programmazione dinamica: abbiamo visto insieme collage. Massima sottosequenza comune: abbiamo svolto insieme un esercizio da tema d'esame. Abbiamo mostrato come certificare l'ottimalita' di una sottosequenza crescente. Abbiamo dato un algoritmo $n\log n$. Parlato di DAGs e teorema di Dilworth. Caratterizzato i DAGs. Esempi di programmazione dinamica su DAGs. Esempi di giochi a due giocatori.
14-5-2015 (2 ore)	Problema dello zaino: abbiamo svolto insieme un esercizio da tema d'esame. Massimo flusso: definizione del problema, scomposizione di un flusso in cicli e cammini, i cammini come flussi elementari a supporto minimale, schema di massima dell'algoritmo.
18-5-2015 (2 ore)	Problema dei 4 colori. Grafi planari. Grafo duale. Chromatic number e chromatic index. Tait's proof. Petersen graph and Tutte's graph. Dimostrazione di NP-completezza di Holyer.
19-5-2015 (2 ore)	Formula di Eulero. Teorema di Kuratowski. Congettura di Wagner.
20-5-2015 (3 ore)	Algoritmo per il massimo flusso. Mac-flow min-cut theorem.
26-5-2015 (2 ore)	Introduzione alla programmazione lineare. Un problema in due variabili. Risoluzione geometrica.
27-5-2015 (3 ore)	Introduzione al metodo del simplesso. Le variabili di slack. Prima fase del metodo del simplesso.
28-5-2015 (2 ore)	Problemi a origine non ammissibile. Il problema ausiliario. La fase uno del metodo del simplesso. La PLI è NP-completa. Regola di Bland.
3-6-2015 (3 ore)	Il pivot come operazioni di riga. Il metodo delle permutazioni. Il metodo lessicografico. Teorema fonsamentale della PL. Cubo di Klee-Minty. Complessià media del metodo del simplesso. Accenno al metodo dell'elissoide. Equivalenza di ottimizzazione e separazione. Menzione all'algoritmo di Karmarkar.
3-6-2015 (2 ore)	Teoria della dualità. Duale di forma standard. Duale del duale. Teorema della dualità debole. Teorema della dualità forte. Algoritmo primale duale.
4-6-2015 (2 ore)	Teorema degli scarti complementari. Le soluzioni primale e duale di base associate ad uno stesso tableau soddisfano le condizioni degli scarti complementari; quando entrambe ammissibili allora entrambe ottime. La ricostruibilità del certificato di ottimalità per soluzioni di base non degeneri.
4-6-2015 (2 ore)	Interpretazione economica delle variabili duali e del metodo del simplesso. Analisi dimensionale e ricostruzione di semantica. Prezzi ombra. Significato dei prezzi ombra per ottimi non degeneri ed entro un'intorno. Analisi di sensitività: valutazione dell'ambito di validità dei prezzi ombra.
4-6-2015 (2 ore)	Svolgimento insieme di esercizi per esami, ma anche applicazione della cornice della PL per l'indagine di problemi di ottimizzazione combinatorica.

created: 1 marzo 2015
updated: 26 giugno 2015