Programma Moduli I-II: Algoritmi
Algoritmi su reti: flusso massimo e taglio minimo. Formulazione di tali problemi con la
programmazione lineare e soluzione con il metodo primale-duale. Interpretazione combinatorica del
metodo primale-duale. Algoritmo per il flusso massimo di Fork Fulkerson. Algoritmo di 'scaling del
flusso massimo'. Matching su grafi bipartiti. Matching su grafi generali basati sui cammini
alternanti. Ricerca dei cammini disgiunti da una sorgente ad una destinazione su un grafo non
diretto. Algoritmi per il flusso di costo minimo. Vertex cover pesato e non: formulazione in
programmazione lineare. Soluzione approssimata con la tecnica di rounding. Metodo primale-duale
applicato al vertex-cover. Max-independent set: soluzione greedy polinomiale per alberi. Weightmax
independent set: soluzione basata sulla programmazione dinamica per alberi.
Weight-max independent set su grafi con tree-width limitata. Grafi e decomposizione con bounded
tree-width.
Introduzione agli ambienti distribuiti. Entità, Eventi e Azioni. Algoritmi di base, quali ad esempio:
Broadcasting, Wake-Up, Visita, Spanning-Tree, Gathering. Complessità Computazionale dei
problemi e dei protocolli proposti. Ottimizzazione dei protocolli. Applicazioni in particolari
topologie di rete quali ad esempio: path, anelli, alberi, grafi completi, ipercubi.
Programma Modulo III: Euristiche
Classi di complessità P e NP. Problemi NP-completi. Problemi di ottimizzazione NP-hard. Soglia di
approssimazione polinomiale. Schemi di approssimazione polinomiali. Classi SNP e MAXSNP.
Algoritmi genetici. Ottimizzazione a colonia di formiche. Ottimizzazione a sciami di particelle.