2. Docenti
  3. DE BONIS Annalisa
  4. 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]