Annalisa DE BONIS | TECNICHE ALGORITMICHE AVANZATE PER SISTEMI DISTRIBUITI
Annalisa DE BONIS TECNICHE ALGORITMICHE AVANZATE PER SISTEMI DISTRIBUITI
cod. 0522500105
TECNICHE ALGORITMICHE AVANZATE PER SISTEMI DISTRIBUITI
| 0522500105 | |
| DIPARTIMENTO DI INFORMATICA | |
| CORSO DI LAUREA MAGISTRALE | |
| INFORMATICA | |
| 2017/2018 |
| ANNO CORSO 2 | |
| ANNO ORDINAMENTO 2016 | |
| SECONDO SEMESTRE |
| SSD | CFU | ORE | ATTIVITÀ | |
|---|---|---|---|---|
| INF/01 | 6 | 48 | LEZIONE |
| Obiettivi | |
|---|---|
| QUESTO INSEGNAMENTO SI PREFIGGE L'OBIETTIVO DI ILLUSTRARE LE TECNICHE PER LA PROGETTAZIONE, ANALISI E DIMOSTRAZIONE DEI LIMITI DEGLI ALGORITMI DISTRIBUITI. LE PRINCIPALI CONOSCENZE ACQUISITE POSSONO ESSERE SUDDIVISE IN TRE GRUPPI PRINCIPALI: • STUDIO DEL CONCETTO DI LOCALITÀ NEI PROBLEMI SU GRAFI. L'INSEGNAMENTO INVESTIGHERÀ I PROBLEMI DI SYMMETRY BREAKING LOCALE QUALI LA COLORAZIONE DEI GRAFI E IL PROBLEMA DELL’INSIEME INDIPENDENTE MASSIMALE. VERRANNO INOLTRE STUDIATE DIVERSE TECNICHE DI DECOMPOSIZIONE DELLE RETI CON PROPRIETÀ DI LOCALITY-PRESERVING • STUDIO DEL PROBLEMA DELLA CONGESTIONE COME EFFETTO DEI LIMITI DELLA COMUNICAZIONE SUGLI ALGORITMI DISTRIBUITI. I PROBLEMI INVESTIGATI ESIBIRANNO CARATTERISTICHE NON LOCALI IN QUANTO LA LORO SOLUZIONE RICHIEDERÀ L’APPRENDIMENTO DI INFORMAZIONI NON LOCALI. NELL’AMBITO DI QUESTE PROBLEMATICHE, VERRANNO STUDIATI LIMITI INFERIORI ALLA COMPLESSITÀ DI COMUNICAZIONE E VERRANNO ILLUSTRATI I PIÙ RECENTI ALGORITMI DISTRIBUITI PER PROBLEMI QUALI IL PROBLEMA DEI CAMMINI MINIMI E IL PROBLEMA DEL MINIMO ALBERO RICOPRENTE. L'INSEGNAMENTO COPRIRÀ ANCHE ALCUNI STRUMENTI ALGORITMICI GENERALI QUALI GLI SPANNERS E LA SPARSIFICAZIONE DEI GRAFI. • ALGORITMI DI BROADCAST PER LE RETI WIRELESS. L'INSEGNAMENTO INVESTIGHERÀ ALGORITMI DETERMINISTICI E RANDOMIZZATI DI BROADCAST. IN RELAZIONE AGLI ALGORITMI DETERMINISTICI VERRANNO INTRODOTTI CONCETTI COMBINATORIALI, QUALI LE FAMIGLIE SELETTIVE, CHE SONO ALLA BASE DEI PIÙ RECENTI ALGORITMI DI BROADCAST PER LE RETI WIRELESS LE PRINCIPALI ABILITÀ (OSSIA LA CAPACITÀ DI APPLICARE LE CONOSCENZE ACQUISITE) SARANNO: • CAPACITÀ DI UTILIZZARE LE TECNICHE PIÙ RILEVANTI DELLA PROGETTAZIONE E ANALISI DEGLI ALGORITMI DISTRIBUITI • COMPRENSIONE PROFONDA DI COME LE SUDDETTE TECNICHE IMPATTANO SULLA SOLUZIONE DEI NUMEROSI PROBLEMI CONCRETI CHE SCATURISCONO DALL’USO DELLE MODERNE TECNOLOGIE PER LA COMUNICAZIONE SULLE RETI. |
| Prerequisiti | |
|---|---|
| LO STUDENTE DEVE AVER ACQUISITO LE NOZIONI DEGLI INSEGNAMENTI DI MATEMATICA DELLA LAUREA TRIENNALE IN INFORMATICA E AVER APPRESO I CONCETTI DI BASE DI UN INSEGNAMENTO DI PROGETTAZIONE E ANALISI DEGLI ALGORITMI. |
| Contenuti | |
|---|---|
| IL CORSO SI CONCENTRERÀ SUI SEGUENTI ARGOMENTI: • PANORAMICA DELL'INSEGNAMENTO E CONCETTI INTRODUTTIVI • COLORAZIONE DISTRIBUITA DI UN GRAFO: COLORAZIONE IN GRAFI DI GRADO COSTANTE, ALGORITMI E LIMITI INFERIORI; LA TECNICA DI RIDUZIONE DEI COLORI E ALGORITMO DI KUHN ATTRAVERSO LA TECNICA DELLA COLORAZIONE “DIFETTOSA” • INSIEME INDIPENDENTE MASSIMALE: ALGORITMI RANDOMIZZATI E LORO APPLICAZIONE ALLA SOLUZIONE DI ALTRI PROBLEMI COLLEGATI QUALI IL PROBLEMA DEL MATCHING E DELLA COLORAZIONE DEI VERTICI. • DECOMPOSIZIONE DI RETI: ALGORITMO DISTRIBUITO DI AWERBUCH, GOLDBERG, LUBY, PLOTKIN. • MINIMO ALBERO RICOPRENTE: UNA VERSIONE RIVISTATA DELL’ALGORITMO DI KUTTEN E PELEG. • 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. • 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. • SPANNERS E SPARSIFICAZIONE. • IL PROBLEMA DEL BROADCAST SU RETI WIRELESS: ALGORITMI RANDOMIZZATI, IL CONCETTO DI SELECTIVE FAMILY, PROTOCOLLI DI BROADCAST DETERMINISTICI BASATI SU SELECTIVE FAMILY. |
| Metodi Didattici | |
|---|---|
| L'INSEGNAMENTO PREVEDE UNA PARTE DI LEZIONI DI CARATTERE TEORICO E UNA PARTE DI LEZIONI DI TIPO SEMINARIALE CHE POTRANNO VEDERE COINVOLTI ANCHE GLI STUDENTI NELLA PRESENTAZIONE DI UNA SELEZIONE DI ARGOMENTI. |
| Verifica dell'apprendimento | |
|---|---|
| LA VERIFICA E LA VALUTAZIONE DEL LIVELLO DI APPRENDIMENTO DELLO STUDENTE AVVERRÀ TRAMITE UN ESAME FINALE ORALE CHE CONSISTERÀ IN • UN COLLOQUIO CON DOMANDE E DISCUSSIONE SUI CONTENUTI TEORICI E METODOLOGICI INDICATI NEL PROGRAMMA DELL’INSEGNAMENTO • UN BREVE SEMINARIO SU UN ARGOMENTO SCELTO IN UNA SELEZIONE DI ARGOMENTI PROPOSTI DAL DOCENTE |
| Testi | |
|---|---|
| IL MATERIALE DIDATTICO SARÀ RESO DISPONIBILE A LEZIONE E/O SUL SITO WEB DELL'INSEGNAMENTO. |
BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-05-14]
