2. Docenti
  3. Didattica

TECNICHE ALGORITMICHE AVANZATE PER SISTEMI DISTRIBUITI

Annalisa DE BONIS TECNICHE ALGORITMICHE AVANZATE PER SISTEMI DISTRIBUITI

0522500105
DIPARTIMENTO DI INFORMATICA
CORSO DI LAUREA MAGISTRALE
INFORMATICA
2016/2017



ANNO CORSO 2
ANNO ORDINAMENTO 2015
SECONDO SEMESTRE
CFUOREATTIVITÀ
648LEZIONE
ANNALISA DE BONIS T Curriculum
Obiettivi
CONOSCENZA E COMPRENSIONE: QUESTO INSEGNAMENTO SI PREFIGGE L'OBIETTIVO DI ILLUSTRARE LE TECNICHE PER LA PROGETTAZIONE, ANALISI E DIMOSTRAZIONE DEI LIMITI DEGLI ALGORITMI DISTRIBUITI. GLI ARGOMENTI DELL' INSEGNAMENTO POSSONO ESSERE SUDDIVISI IN TRE GRUPPI PRINCIPALI:
•STUDIO DEL CONCETTO DI LOCALITA` NEI PROBLEMI SU GRAFI. L' INSEGNAMENTO INVESTIGHERA` I PROBLEMI DI SYMMETRY-BREAKING LOCALE QUALI LA COLORAZIONE DEI GRAFI E IL PROBLEMA DELL’INSIEME INDIPENDENTE MASSIMALE. VERRANO INOLTRE STUDIATE DIVERSE TECNICHE DI DECOMPOSIZIONE DELLE RETI CON PROPRIETA` DI LOCALITY-PRESERVING.
•STUDIO DEL PROBLEMA DELLA CONGESTIONE COME EFFETTO DEI LIMITI DELLA COMUNICAZIONE SUGLI ALGORITMI DISTRIBUTI. I PROBLEMI INVESTIGATI ESIBIRANNO CARATTERISTICHE NON LOCALI IN QUANTO LA LORO SOLUZIONE RICHIEDERA` L’APPRENDIMENTO DI INFORMAZIONI NON LOCALI. NELL’AMBITO DI QUESTE PROBLEMATICHE, VERRANNO STUDIATI LIMITI INFERIORI ALLA COMPLESSITA` DI COMUNICAZIONE E VERRANNO ILLUSTRATI I PIU` RECENTI ALGORITMI DISTRIBUITI PER PROBLEMI QUALI IL PROBLEMA DEI CAMMINI MINIMI E IL PROBLEMA DEL MINIMO ALBERO RICOPRENTE. L' INSEGNAMENTO COPRIRA` ANCHE ALCUNI STRUMENTI ALGORITMICI GENERALI QUALI GLI SPANNERS E LA SPARSIFICAZIONE DEI GRAFI.
•ALGORITMI DI BROADCAST PER LE RETI WIRELESS. L' INSEGNAMENTO INVESTIGHERA` ALGORITMI DETERMINISTICI E RANDOMIZZATI DI BROADCAST. IN RELAZIONE AGLI ALGORITMI DETERMINISTICI VERRANO INTRODOTTI CONCETTI COMBINATORIALI, QUALI LE FAMIGLIE SELETTIVE, CHE SONO ALLA BASE DEI PIU` RECENTI ALGORITMI DI BROADCAST PER LE RETI WIRELESS.

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE: L' INSEGNAMENTO HA COME OBIETTIVO QUELLO DI RENDERE LO STUDENTE CAPACE DI UTILIZZARE LE TECNICHE PIU` RILEVANTI DELLA PROGETTAZIONE E ANALISI DEGLI ALGORITMI DISTRIBUITI E DI FORNIRE ALLO STUDENTE UNA COMPRENSIONE PROFONDA DI COME QUESTE TECNICHE IMPATTINO SULLA SOLUZIONE DEI NUMEROSI PROBLEMI CONCRETI CHE SCATURISCONO DALL’USO DELLE MODERNE TECNOLOGIE PER LA COMUNICAZIONE SULLE RETI.

ABILITÀ COMUNICATIVE :
L' INSEGNAMENTO FAVORIRÀ LO SVILUPPO DELLE SEGUENTI ABILITÀ DELLO STUDENTE: CAPACITÀ DI ESPORRE IN TERMINI PRECISI E FORMALI MODELLI ASTRATTI PER PROBLEMI CONCRETI, INDIVIDUANDO LE CARATTERISTICHE SALIENTI DI ESSI E SCARTANDONE LE CARATTERISTICHE INESSENZIALI.

AUTONOMIA DI GIUDIZIO (MAKING JUDGEMENTS):
GLI STUDENTI SONO GUIDATI AD APPRENDERE IN MANIERA CRITICA TUTTO CIÒ CHE VIENE LORO SPIEGATO IN CLASSE, A CONFRONTARE I DIVERSI APPROCCI E TECNICHE PER LA SOLUZIONE DI PROBLEMI NELL’ AMBITO DEL MODELLO DISTRIBUITO.
Prerequisiti
LO STUDENTE DOVREBBE AVERE ACQUISITO LE NOZIONI DI MATEMATICA INSEGNATE NEI PRECEDENTI ANNI SCOLASTICI E AVER APPRESO I CONCETTI DI BASE DI UN INSEGNAMENTO DI PROGETTAZIONE E ANALISI DEGLI ALGORITMI.
Contenuti
ORE DI LEZIONE: 48
•PANORAMICA DELL' INSEGNAMENTO E CONCETTI INTRODUTTIVI (2 ORE)
•COLORAZIONE DISTRIBUITA DI UN GRAFO: COLORAZIONE IN GRAFI DI GRADO COSTANTE, ALGORITMI E LOWER BOUND; LA TECNICA DI RIDUZIONE DEI COLORI E ALGORITMO DI KUHN ATTRAVERSO LA TECNICA DELLA COLORAZIONE “DIFETTOSA” (8 ORE)
•INSIEME INDIPENDENTE MASSIMALE: ALGORITMI RANDOMIZZATI E LORO APPLICAZIONE ALLA SOLUZIONE DI ALTRI PROBLEMI COLLEGATI QUALI IL PROBLEMA DEL MATCHING E DELLA COLORAZIONE DEI VERTICI. (6 ORE)
•DECOMPOSIZIONE DI RETI: ALGORITMO DISTRIBUITO DI AWERBUCH, GOLDBERG, LUBY AND PLOTKIN (6 ORE)
•MINIMO ALBERO RICOPRENTE: UNA VERSIONE RIVISTATA DELL’ALGORITMO DI KUTTEN AND PELEG. (4 ORE)
•LIMITI INFERIORI BASATI SULLA COMPLESSITA` DI COMUNICAZIONE: LIMITI INFERIORI PER IL MINIMO ALBERO RICOPRENTE E PER IL PROBLEMA DEI CAMMINI MINIMI DA UNA SINGOLA SORGENTE. (6 ORE)
•CAMMINI MINIMI: ALGORITMI DISTRIBUITI DI APPROSSIMAZIONE PER IL PROBLEMA DEI CAMMINI MINIMI DA UNA SINGOLA SORGENTE; ALGORITMO DETERMINISTICO LINEARE PER IL PROBLEMA DEI CAMMINI MINIMI TRA TUTTE LE COPPIE DI VERTICI. (6 ORE)
•SPANNERS E SPARSIFICAZIONE (4 ORE)
•IL PROBLEMA DEL BROADCAST SU RETI WIRELESS: ALGORITMI RANDOMIZZATI, IL CONCETTO DI SELECTIVE FAMILY, PROTOCOLLI DI BROADCAST DETERMINISTICI BASATI SU SELECTIVE FAMILY. (6 ORE)
Metodi Didattici
L' INSEGNAMENTO PREVEDE UNA PARTE DI LEZIONI DI CARATTERE TEORICO E UNA PARTE DI LEZIONI DI TIPO SEMINARIALE CHE VEDRANNO COINVOLTI DIRETTAMENTE GLI STUDENTI NELLA PRESENTAZIONE DI ARGOMENTI SCELTI IN UNA SELEZIONE DI ARGOMENTI PROPOSTA DALLA DOCENTE.
Verifica dell'apprendimento
LA VERIFICA E LA VALUTAZIONE DEL LIVELLO DI APPRENDIMENTO DELLO STUDENTE AVVERRÀ TRAMITE UN ESAME FINALE ORALE.
Testi
IL MATERIALE DIDATTICO SARA` RESO DISPONIBILE A LEZIONE E SUL SITO WEB DELL' INSEGNAMENTO .
  BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-03-11]