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.
• 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'. Il problema dell'approviggionamento.
* A - Algoritmi fondamentali
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.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Formulazione di problemi con la programmazione lineare e soluzione con il metodo primale-duale. Interpretazione combinatorica del metodo primale-duale. Metodo primale-duale applicato al vertex-cover.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
Algoritmi approssimati. Vertex cover pesato e non: formulazione in programmazione lineare. Soluzione approssimata con la tecnica di rounding.
* ASC - Algoritmi su Strutture Combinatorie
Grafi e decomposizione con bounded tree-width. Weight-max independent set: soluzione basata sulla programmazione dinamica per alberi. Weight-max independent set su grafi con tree-width limitata.
* ASC - Algoritmi su Strutture Combinatorie
Colorazione di grafi.