Insegnamento ADVANCED AND DISTRIBUTED ALGORITHMS
- Corso
- Informatica
- Codice insegnamento
- A002042
- Curriculum
- Comune a tutti i curricula
- Docente
- Maria Cristina Pinotti
- Docenti
-
- Maria Cristina Pinotti
- Alfredo Navarra (Codocenza)
- Ore
- 21 ore - Maria Cristina Pinotti
- 42 ore (Codocenza) - Alfredo Navarra
- CFU
- 9
- Regolamento
- Coorte 2020
- Erogato
- 2020/21
- Attività
- Caratterizzante
- Ambito
- Discipline informatiche
- Settore
- INF/01
- Tipo insegnamento
- Obbligatorio (Required)
- Tipo attività
- Attività formativa monodisciplinare
- Lingua insegnamento
- ITALIANO/INGLESE
- Contenuti
- Algoritmi combinatorici avanzati. 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.
- Testi di riferimento
- T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduzione agli algoritmi e strutture dati (terza edizione), McGraw-Hill, 2010, ISBN: 978-88-386-6515-8.
N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons. - Obiettivi formativi
- Conoscere soluzioni per problemi con numerose applicazioni.
Conoscenze avanzate su tematiche di algoritmi distribuiti. Accrescimento capacità critiche e applicative - Prerequisiti
- Conoscenze algoritmiche di livello intermedio
- Metodi didattici
- Lezione frontale
Seminari - Modalità di verifica dell'apprendimento
- Esame Orale
- Programma esteso
- Il flusso massimo
Tagli e flusso massimo
Vari algoritmi pseudopolinomiali per il flusso massimo
Preflow-Push Flusso Massimo Matching bipartito
Geometria Computazionale
Nozioni elementari
Covex Hull
Closest pair of points
Delaunay triangulation
Velocizzare la programmazione dinamica:
La proprietà di Monge
La ricerca dei massimi in una matrice monotona (
SMAWK algorithm)
Applicazioni.
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. Approfondimenti su software di simulazione per ambienti distribuiti.