Obiettivi di apprendimento

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.