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 semestre dal 1 mar 2021 al 11 giu 2021.

Orario Lezioni Moodle Seminari 0

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 principali 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 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 si 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 richieste, rimandiamo ai temi e correzioni dei temi svolti nelle varie edizioni del corso.
Nel tempo i temi tendono ad arricchirsi per includere competenze comunque impartite tra quelle poi richieste all'esame. Confidiamo che le nozioni di complessita` computazionale introdotte e l'attenzione ai certificati conducano lo studente a riconoscere con maggior consapevolezza la struttura di una dimostrazione rigorosa. L'esposizione a istanze, problemi, e modelli, con occhio sia agli algoritmi che alle formulazioni, rafforzera` la capacita` ed attitudine a formalizzare matematicamente problemi espressi nel linguaggio naturale. Nei risultati paradigmatici (dualita`, scarti complementari, interpretazione economica, analisi di sensitivita`) della programmazione lineare lo studente incontrera` modi importanti e non banali per trarre profitto da queste formulazioni per meglio chiarire ed affrontare le reali problematiche di interesse sottese.
Il linguaggio dei grafi, e gli strumenti della PL e della PLI, data la loro importanza e centralita` sia storica che attuale, rimangono a tutt'oggi temi d'avanguardia nel campo della Matematica Applicata. La loro padronanza consente di svolgere compiti professionali definiti, ad esempio come supporto modellistico-matematico e computazionale ad attivita` dell'industria, dei servizi e nella pubblica amministrazione, come anche nel campo dell'insegnamento della matematica o della diffusione della cultura scientifica.

Programma

La Ricerca Operativa mira a fornire dei metodi quantitativi per la gestione delle risorse e l'ottimizzazione dei profitti, dei servizi, delle strategie.
Questo corso di Ricerca Operativa muove alla Programmazione Matematica partendo
dall'Algoritmica a dalla Complessità 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
complessità

2. Introduzione agli algoritmi
analisi di alcuni algoritmi
tecniche di progetto (ricorsione, divide et impera, ricorsione con memoizzazione, programmazione dinamica, greedy)
teoria della complessità computazionale (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, complessità, ruolo)
metodo geometrico e visione geometrica della PL (spazio delle soluzioni,
pivot, dualità, variabili duali, problemi degeneri, scarti complementari)
forme standard e canonica
il metodo del simplesso per la PL (descrizione ed analisi)
teoria della dualità
condizioni degli scarti complementari
interpretazione economica per le variabili duali
analisi di sensitività

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

TESTI, DISPENSE E MATERIALI:

Trovi elenco completo dei materiali resi disponibili o comunque utilizzabili proficuamente alla pagina:

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

Se individui efficaci materiali che valuti compendiare utilmente tale lista, o se comunque la scopri incompleta, ti preghiamo di suggerirci le eventuali integrazioni.


TUTORAGGIO (SE SARA` DISPONIBILE):

Per l'anno 2020-21 prevediamo di introdurre un tutoraggio che accompagnera` gli studenti a percorrere effettivamente e toccare con mano le proposte e controparti pratiche avanzate durante le ore di teoria.

Modalità d'esame

A fine corso un esame scritto con diverse tipologie di esercizi e domande su vari aspetti di quanto esposto a lezione. Il voto di tale esame può essere integrato (in tutto o in parte) con eventuali progetti ideati insieme per migliorare aspetti o materiali del corso.
Fino all'edizione 2018/19 gli appelli avvenivano in un'aula.
Nell'edizione 2019/20 (insorgenza del COVID-19) sono avvenuti da remoto, ed è seguito un breve orale di accertamento e come occasione per un confronto diretto.
Quali saranno le modalità nelle prossime edizioni verrà deciso dinamicamente, ormai ci siamo attrezzati in ogni caso e siamo preparati per un ampio ventaglio di possibilità. I materiali degli anni precedenti (tutti i testi degli appelli e relative correzioni dal 2011 in poi) restano in ogni caso ottimi riferimenti (da sempre abbiamo improntato gli appelli all'insegna della Glasnost (i.e., trasparenza) e ora che lavoriamo su formati elettronici il grado di trasparenza raggiunto su ogni aspetto è notevole).
Piuttosto: siccome delle cose sono in continua evoluzione e le nostre tecnologie sono in aggiornamento continuo, ed è in tutto richiesta la collaborazione dello studente anche per quello che è la verifica delle competenze che ha raggiunto e del lavoro fatto, rimandiamo l'eventuale studente smarrito al sito di servizio e riferimento che possiamo tenere costantemente aggiornato:

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

Altrettanto preziosi per rimanere in buon contatto sono il gruppo Telegram dell'edizione corrente del corso (anche se hai seguito in anni precedenti ma devi ancora sostenere l'esame non mancare di iscriverti al gruppo dell'ultima edizione) e quelli per la sperimentazione delle installazioni, configurazioni, ed ambienti realizzati per l'esame. Tutte queste risorse possono essere convenientemente raggiunte partendo dallo URL riportato qui sopra.

Vogliamo evidenziare una particolarità marcata di questo che è l'unico corso in ambito matematica discreta offerto alla triennale: Lo spirito con cui l'esame va affrontato e di cosa e come elaborare e proporre in risposta agli esercizi e` in linea con alcuni dei messaggi metodologici che si mira a trasmettere con il corso. Speriamo lo studente possa fare propri questi approcci e queste metodologie, che specie quando operavamo col cartaceo potevano apparire come sfumature o stranezze. Più lo studente saprà interpretare e fare proprie le nostre prospettive, e si approccerà in modo collaborativo e propositivo al corso ed alla verifica, più l'esame potrà essere divertente e di soddisfazione.

Ogni anno accademico prevede 4 appelli (giugno, luglio, settembre, febbraio). Il testo d'esame e le modalità della sua valutazione sono le medesime per studenti frequentanti o non frequentanti, senza alcuna distinzione. E` chiaro e risulta nei fatti che lo studente che non ha frequentato sia penalizzato da una minore chiarezza su quali siano le richieste avanzate dal docente con gli esercizi. Per questo abbiamo curato l'archivio dei temi passati con relativi svolgimenti, con particolare attenzione al chiarire cosa debba essere prodotto dallo studente per ottenere dei punti a fronte di un esercizio. Allo stesso scopo rendiamo disponibili i video delle lezioni da diversi anni a questa parte. Nonostante questo alcuni messaggi restano difficili da acquisire senza una partecipazione attiva al corso ed una frequenza delle lezioni.