Codice insegnamento

4S00001

Docente

Romeo Rizzi

Coordinatore

Romeo Rizzi

Crediti

6

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

MAT/09 - RICERCA OPERATIVA

Periodo

II sem. dal 1-mar-2017 al 9-giu-2017.

Moodle Seminari

Obiettivi formativi

Lo studente di matematica incontrera` in concretezza i concetti di: problemi, modelli e formulazioni della ricerca operativa, ma anche di istanze, algoritmi, riduzioni e mappature tra problemi dell'informatica. Il corso proporra` alcuni dei modelli della ricerca operativa, quantomeno i seguenti: programmazione lineare (PL), programmazione lineare intera (PLI), massimo flusso e minimo taglio, accoppiamenti massimi e coperture minime in grafi bipartiti, alberi ricoprenti di peso minimo, cammini minimi, cammini Euleriani, alcuni modelli di programmazione dinamica tra cui delle varianti dello zaino. Per tutti questi modelli/problemi tranne la PLI lo studente apprendera` degli algoritmi risolutori, le proprieta` su cui poggiano, e come condurne l'esecuzione.
Tuttavia, il corso si prefigge anche di costruire un buon rapporto e dimestichezza dello studente con tecniche e metodologie matematiche generali (certo piu` proprie della matematica del discreto e per questo non ancora assimilate dai nostri studenti) e con alcuni capisaldi delle discipline informatiche. Si insiste sul dialogo coi problemi e con l'arte e tecnica del congetturare, non si perde occasione di mettere in evidenza dove lavorino invarianti e monovarianti nelle dimostrazioni, algoritmi e strutture dati. Si sviluppa confidenza con l'induzione matematica e coi suoi dialetti all'insegna dell'efficienza (divide et impera, ricorsione con memoizzazione, programmazione dinamica). Si evidenziano alcuni principi base dell'informatica, quali la codifica, gli algoritmi, le strutture dati, la ricorsione come controparte dell'induzione e del computabile. (In alcune edizioni del corso si sono offerti accenni su numerabilita` e computabilita`). Sul piano dell'efficienza, cui la nostra impostazione e` devota, si giustifica ed utilizza la notazione asintotica e vengono introdotte le classi P, NP, coNP ed i concetti di buone caratterizzazioni, buone congetture e buoni teoremi e si illustra e pubblicizza come la teoria della complessita` possa fungere da fucina metodologica nell'arte di affrontare problemi e condurne indagine delle proprieta` strutturali intrinseche. Vengono ampiamente discussi e chiariti alcuni aspetti del ruolo ed importanza dell'arte del ridurre un problema ad un altro. Viene illustrato il flusso di lavoro attorno ad una buona congettura, la produzione ed interpretazione di controesempi come dialogo col problema e l'eventuale utilizzo degli stessi per ottenere dimostrazioni di NP-completezza. Costantemente, viene data esplicita enfasi al ruolo ed utilizzo dei certificati. Mentre si consegnano e di insiste su queste competenze trasversali ed alte, di stampo metodologico, diverse sono le competenze di tipo procedurale che lo studente viene chiamato ad apprendere e sviluppare, in particolare nell'ambito della PL, ed in una trattazione algoritmica alla teoria dei grafi, introdotti come modelli versatili e linguaggio immediato ed espressivo alla formulazione di problemi.
Per un elenco completo e puntuale di tutte le competenze procedurali impartite e richieste, rimandiamo ai temi e correzioni dei temi svolti nelle varie edizioni del corso.

Programma

La Ricerca Operativa mira a fornire dei metodi quantitativi
per la gestione delle risorse e l'ottimizzazzione
dei profitti, dei servizi, delle strategie.
Questo corso di Ricerca Operativa
muove alla Programmazione Matematica partendo
dall'Algoritmica a dalla Complessita` Computazionale.
Richiamata l'induzione matematica, la ricorsione ed il divide et impera,
si cerca di trasmettere in modo ampio ed approfondito l'approccio della
programmazione dinamica esemplificandolo in vari contesti tra cui
alcuni modelli classici della Ricerca Operativa.
Con enfasi sulle tecniche, si discute di formulare, codificare e modellare problemi,
di ridurre problemi ad altri, e di ben caratterizzare problemi.
Il corso offre un'introduzione approfondita alla programmazione lineare.
Motivati dalla modellistica, e seguendo percorsi storici,
si introducono i grafi e si esplorano alcuni risultati fondamentali di ottimizzazione combinatoria e teoria dei grafi.

ELENCO DEGLI ARGOMENTI:

1. Nozioni di base
problemi
modelli
algoritmi
complessita`

2. Introduzione agli algoritmi
analisi di alcuni algoritmi
tecniche di progetto (ricorsione, divede et impera, ricorsione con memoizzazione, programmazione dinamica, greedy)
complexity theory (P, NP, co-NP, buone caratterizzazioni, buone congetture, esempi di dimostrazioni di NP-completezza)

3. Alcuni modelli di ottimizzazione combinatoria
problemi di zaino
problemi su sequenze
problemi su DAGs

4. Fondamenti di Programmazione Lineare (PL)
la PL e la PLI (definizione, motivazioni, complessita`, ruolo)
metodo geometrico e visione geometrica della PL (spazio delle soluzioni,
pivot, dualita`, variabili duali, problemi degeneri, scarti complementari)
forme standard e canonica
il metodo del simplesso per la PL (descrizione ed analisi)
teoria della dualita`
condizioni degli scarti complementari
interpretazione economica per le variabili duali
analisi di sensitivita`

5. Introduzione alla teoria dei grafi
grafi e digrafi come modelli
alcune buone caratterizzazioni
(grafi bipartiti, euleriani, hamiloniani, planari)
cammini minimi
alberi ricoprenti di peso minimo
flussi massimi
accoppiamenti bipartiti

Modalità d'esame

A fine corso un esame scritto con diverse tipologie di esercizi e domande,
e molti modi di raccogliere punti per dimostrare la propria preparazione.
Nel preparare il tuo esame,
ti converra` prendere a riferimento i testi e le correzioni dei temi precedenti
come scaricabili al sito del corso:

http://profs.sci.univr.it/~rrizzi/classes/RO/index.html

Testare la tua preparazione su questi esercizi e confrontare le tue soluzioni (presta attenzione non solo alle risposte ma anche a come saprai offrirle all'esaminatore/verificatore, ossia alla qualita` dei tuoi certificati) ti consentira` di verificare la tua comprensione degli argomenti trattati e degli algoritmi e metodologie illustrati durante il corso. Ti aiutera` inoltre ad affinare la tua preparazione ai fini dell'esame, mettendo a punto le tue procedure ed approcci, e chiarendo cosa l'esaminatore chiede venga prodotto con chiarezza.
Durante l'esame, dovrete lavore per almeno 4 ore a quella che definisco "una prova di cromatografia su carta". Serve per riconoscervi con ragionevole confidenza quanto avete lavorato, appreso, e sedimentato. E trasformare questo in una proposta di voto.
La logica dello svolgimeto dell'esame deve essere quella di dimostrare
al meglio le competenze acquisite andando con efficienza a raccogliere,
dei molti punti messi in palio a vario titolo,
quelli che vi risultano piu` funzionali.
Se avrai ben compreso cosa ti si chiede di fare e come esprimerlo in modo conveniente nel tuo elaborato, svolgere con concretezza la parte di esercizi che riterrai piu` opportuno portera` il tuo voto a saturazione.
Contano le risposte corrette, fornite in chiarezza, ed i certificati.
Tutto il resto e` a misura nulla.
In questo la struttura dell'esame ribadisce il ruolo metodologico ed ubiquito dei concetti di complessita` computazionale propagandati nel corso.

Bibliografia