Insegnamento ADVANCED AND DISTRIBUTED ALGORITHMS

Corso
Informatica
Codice insegnamento
A002042
Curriculum
Comune a tutti i curricula
Docente
Alfredo Navarra
Docenti
  • Alfredo Navarra
  • Maria Cristina Pinotti (Codocenza)
Ore
  • 42 ore - Alfredo Navarra
  • 21 ore (Codocenza) - Maria Cristina Pinotti
CFU
9
Regolamento
Coorte 2022
Erogato
2022/23
Attività
Caratterizzante
Ambito
Discipline informatiche
Settore
INF/01
Tipo insegnamento
Obbligatorio (Required)
Tipo attività
Attività formativa monodisciplinare
Lingua insegnamento
ITALIANO
(INGLESE su richiesta)
Contenuti
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.

Tecniche di programmazione avanzate: programmazione dinamica (PD), algoritmi greedy (G), tecnica delle reti di flusso massimo (NF). Vari esempi saranno formiti.
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.

J. KLEINBERG and E. TARDOS: Algorithm Design. Pearson Addison Wisley, 2005

I materiali didattici utilizzati durante le lezioni del Modulo 2 (3 CFU) sono, solitamente, resi disponibili anche su Unistudium.

N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons.
Obiettivi formativi
Il corso fornisce competenze algoritmiche superiori, caratterizzanti per il CdS.
Conoscere tecniche di programmazione avanzate e saperle applicare in nuovi contesti.
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. La prova nel suo insieme consente di
accertare sia la capacità di conoscenza e comprensione, sia la capacità di applicare le
competenze acquisite, sia la capacità di esposizione.

Nel caso in cui lo studente intenda anticipare l’esame in un anno precedente a quello programmato nel piano di studio, si raccomanda di frequentare il ciclo delle lezioni e
di sostenere l’esame nel primo appello utile dopo che le lezioni medesime siano terminate, nel rispetto quindi del semestre di programmazione dell’insegnamento
Programma esteso
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.

Tecniche di programmazione avanzate: programmazione dinamica (PD), algoritmi greedy (G), reti di flusso (NF). Analisi in tempo e spazio. Esempi di PD: ordine di moltiplicazione di matrici per ottenere il minimo numero di prodotti, problema dello zaino intero con/senza ripetizioni, resto, programmazione delle catene di montaggio.
Esempi Greedy: selezione delle attività, colorazione di un grafo di intervalli, codici di Huffman, zaino frazionario. Soluzioni al problema del flusso massimo (pseudopolinomiale, debolmente polinomiale e fortemente polinomiale) ed applicazioni.
Condividi su