Obiettivi di apprendimento

Il corso offre un'introduzione alla Programmazione Lineare (PL: metodo del simplesso, teoria della dualità), all'uso della Programmazione Lineare Intera (PLI: modellazione matematica), e all'Ottimizzazione Combinatorica (OC: cammini minimi, massimo flusso e minimo taglio, accoppiamenti bipartiti) con l'esplorazione di alcuni nessi tra queste discipline. Il taglio del corso e nostro approccio è algoritmico. Verranno sottolineate e riscoperte tecniche e metodologie di base e fondamentali per l'indagine matematica anche prendendo spunto dalla teoria della Complessità Computazionale.

Prerequisiti e nozioni di base

rudimenti di analisi, calcolo e algebra lineare

Programma

1. Buone caratterizzazioni, ricorsione e programmazione dinamica (DP)
1.1] problemi di piastrellatura ed enigmi: certificati di SI e NO e loro ruolo
1.2] buone congetture, il loro sapore e come testarle
1.3] dalla ricorsione/induzione alla programmazione dinamica
2. Introduzione alla Programmazione Lineare (LP)
2.1] Problemi LP e problemi ILP, una prospettiva di complessità computazionale
2.2] il metodo del simplesso
2.3] teoria della dualità
2.4] scarti complementari
2.5] interpretazione economica
3. Introduzione ai grafi e all'ottimizzazione combinatoria (CO)
3.1] grafi e digrafi come modelli
3.2] alcune buone caratterizzazioni (connettività, grafi euleriani, grafi bipartiti, DAG)
3.3] Algoritmo di Bellman-Ford. Reti Temporali Semplici (STN) e scheduling

Bibliografia

Quando e Dove

Gli incontri si svolgeranno a Povo ma sarà possibile accedere anche via streaming (per gli studenti di Verona). L'impegno da parte nostra è quello di rendere gli incontri quanto più interattivi possibile (anche per quegli studenti che partecipassero da remoto).
Un server Discord o un gruppo Telegram aiuterà non solo a restare in contatto, ma offrirà anche un canale efficace per comunicare tra di noi.

Modalità di verifica dell'apprendimento

Partecipa attivamente agli incontri e ottieni punteggi sufficienti sugli esercizi proposti come compiti a casa. Potete riunirvi in ​​gruppi per alcuni o tutti gli esercizi (questo è in realtà incoraggiato affinché questo primo corso della nostra scuola di dottorato possa essere anche un'occasione per conoscervi tra di voi), Tuttavia, dovresti avere buona conoscenza di ogni soluzione che invii a tuo nome.
Non è fissata alcuna scadenza per presentare le tue soluzioni; ognuno potrà seguire il proprio ritmo e prendersi il proprio tempo per svolgere gli esercizi e sviluppare le proprie soluzioni. Tuttavia, prova a sottoporre almeno alcune o parte delle soluzioni già nel periodo degli incontri, in modo da avere occasioni di discuterle, offrire suggerimenti, risolvere alcuni problemi, risolvere ambiguità o fornire i pezzi mancanti. Alcuni esercizi potrebbero richiedere la scrittura di codice in esecuzione (solo poche righe, nel linguaggio che preferisci, ad esempio C/C++, Pascal, Python. La programmazione non sarà un tuo problema anche se sei nuovo (se sì, sarà una buona occasione per fare una prima esperienza o prendere confidenza con essa). Per questi esercizi, avrai l'opportunità di inviare questi piccoli codici al nostro sistema che testerà e valuterà le tue soluzioni e ti fornirà convalida e feedback immediati.
Ogni problema ha un proprio punteggio massimo (di solito 100), che otterrai per intero se la tua soluzione algoritmica è più intelligente ed efficiente (altrimenti raccoglierai punti parziali su più esercizi). Dovrai raccogliere almeno 1000 punti in totale per superare l'esame.

Valutazione

La valutazione è binaria: dopo aver raccolto sufficiente punteggio lo studente mi chiede di notificare il suo superamento dell'esame alla rispettiva scuola di dottorato/ente di afferenza.