Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Ambienti Distribuiti: Entità, Eventi, Azioni e Comunicazioni. Assiomi e Restrizioni
* ALF - Automi e Linguaggi Formali
Stati, Eventi e Configurazioni. Problemi e Soluzioni. Terminazione e Correttezza. Lower bounds per il problema del Broadcast. Broadcast su alberi, grafi completi e ipercubi.
COM - Complessita'
Enumerazione e NP-completezza. Case study: Prove di NP-completezza per K-Uniform Channel Allocation e K-Non-Uniform Channel Allocation. Case Study: Prova di NP-completezza per la connettività  su grafi a multiinterfaccia. Case study: Prova di NP-completezza per latenza dell'operazione di data aggregation su un grafo non orientato.
• B - Algoritmi
AD - Algoritmi Distribuiti
Problema del Wake-Up. Wake-Up su ipercubi, alberi e grafi completi. Tecnica dell'avversario. Probelma dell'attraversamento. Algoritmo DF_Traversal e miglioramenti.
AD - Algoritmi Distribuiti
Costruzione di uno Spanning Tree. Protocollo Shout. Correttezza, costi computazionali e miglioramenti. Esplorazione di un grafo anonimo tramite automa a stati finiti. Spanning tree con iniziatori multipli e Identificatori unici. Protocollo MultiShout.
AD - Algoritmi Distribuiti
Tecnica della saturazione e sue applicazioni. Leader Election: Risultati di impossibilità, topologia ad albero, topologia a ring. Protocollo AsFar.
AD - Algoritmi Distribuiti
Problema del Gathering. Modello Look-Compute-Move. Gathering su Ring, Alberi e Griglie. Ambienti sincroni: protocollo TwoBits, protocollo Speed.
* A - Algoritmi fondamentali
Algoritmi su reti: flusso massimo e taglio minimo. Algoritmo per il flusso massimo di Fork Fulkerson. Algoritmo di 'scaling del flusso massimo'. Algoritmo Fat Pipe per il flusso massimo. Algoritmo Shortest Pipes. Algoritmo Preflow-Push.
* A - Algoritmi fondamentali
Circolazioni di costo minimo, con domande e lower bounds. Algoritmo del ciclo di costo medio minimo per risolvere la circolazione di costo minimo: analisi debolmente polinomiale e analisi fortemente polinomiale. Flusso massimo di costo minimo.
* A - Algoritmi fondamentali
Matching su grafi bipartiti. Certificazione dell'esistenza del matching perfetto. Matching su un grafo qualsiasi: algoritmo di Edmond's.
* ASC - Algoritmi su Strutture Combinatorie
Algoritmi su Strutture Combinatorie Grafi e decomposizione con bounded tree-width. Weightmax independent set: soluzione basata sulla programmazione dinamica per alberi. Weight-max independent set su grafi con tree-width limitata. Tecnica della riduzione: vertex cover, grafi hamiltoniani diretti, coloring. Programmazione dinamica per K-Uniform Channel Allocation e K-Non-Uniform Channel Allocation.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Algoritmi approssimati: soluzione polinomiali per ogni ogni istanza con qualità  della soluzione garantita. Inapprossimabilità : TSP e 3/2-Bin Packing. PTAS, FPTAS. Algoritmo di Christofides per 1/2-approssimazione di TSP metrico. Knapsack: 1/2-approssimazione e FPTAS (tecnica di rounding). Algoritmi di approssimazione per set cover.