Università degli Studi di Perugia

• Algoritmi I modulo
• Algoritmi II modulo

Esame orale

Le date saranno pubblicate sul sito del Corso di Laurea in Informatica. Inolte, è possibile concordare date flessibili con il docente, contattandolo via email.

Introduzione agli Ambienti Distribuiti: Entità, Eventi, Azioni e Comunicazioni. Assiomi e Restrizioni. Costo e Complessità. Esempio del Broadcast. Algoritmo Flooding. Complessità dell'Algoritmo looding. Stati, Eventi e Configurazioni. Problemi e Soluzioni. Terminazione e Correttezza. Lower bounds per il problema del Broadcast. Broadcast su alberi e grafi completi. Topologia dell'ipercubo. Ipercubi dimensionali. Broadcasting sugli ipercubi. Problema del Wake-Up. Wake-Up su ipercubi. Prova dell'assenza di cicli in Hk(x). Wake-Up su alberi. Wake-up su grafi completi. Tecnica dell'avversario. Probelma dell'attraversamento. Algoritmo DF_Traversal. Miglioramenti dell'algoritmo DF_Traversal: DF+, DF++. Costruzione di uno Spanning Tree. Protocollo Shout. Correttezza, costi computazionali e miglioramento del protocollo Shout. Esplorazione di un grafo anonimo tramite automa a stati finiti. Orientamento locale ad-hoc per la costruzione di uno Spanning Tree. Regola della mano destra. Spanning tree con iniziatori multipli. Spanning Tree con Identificatori unici. Protocollo MultiShout. Introduzione alla tecnica della saturazione. Tecnica della saturazione. Ricerca del minimo tramite saturazione. Leader Election: Risultati di impossibilità, topologia ad albero, topologia a ring. Protocollo AsFar. Problema del Gathering. Modello Look-Compute-Move. Gathering su Ring, Alberi e Grliglie. Ambienti sincroni: protocollo TwoBits, protocollo Speed.

Introduzione agli Ambienti Distribuiti. Algoritmi distribuiti e misure di costo. Algoritmi classici rivisitati in ambienti distribuiti. Comportamento rispetto a varie topologie di grafo. Approfondimenti di tematiche di ricerca recenti in tale ambito e sul software di simulazione per ambienti distribuiti.

lezioni frontali

N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons

Il modulo del corso e' relativo agli Algoritmi Distribuiti e prevede l'acquisizione da parte degli studenti di elementi di base relativi agli ambienti distribuiti. Si vogliono rendere familiari agli studenti problematiche, tecniche e metodologie di ricerca proprie degli ambienti distribuiti.

1 ottobre - 28 gennaio

6 ore settimanali nel primo semestre

facoltativa

Dipartimenmto di Matematica e Informatica

martedì 15:00 - 17:00 o su appuntamento

Dipartimento di Matematica e Informatica

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'. Il problema dell'approviggionamento. 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. Enumerazione e NP-completezza. Algoritmi non deterministici. Algoritmi approssiamti. 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. Weight-max 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.
Colorazione di grafi.

Algoritmi avanzati su reti. Enumerazione e NP-completezza. Algoritmi non deterministici. Decomposizione grafi con bounded tree-width.
Algoritmi di colorazione: soluzione esatte e soluzioni approssimate. Algoritmi approssimati.

Lezione frontale

Dispense delle lezioni tenute.

Testi di consultazione:

Korte B., Vygen J., Combinatorial Optimization,  Springer

Kleinberg J., Tardos E, Algorithm Design, Pearson International Edition

Conoscenza di tecniche avanzate di valutazione degli algoritmi. Algortimi avanzati su reti. Conoscenza di base di problemi difficili.

Segue il calendario delle lezioni di Informatica

corso II semestre

Consigliata

Dipartimento Matematica e Informatica
Via Vanvitelli 1
06123 Perugia