Annalisa DE BONIS | ADVANCED ALGORITHMIC TECHNIQUES FOR DISTRIBUTED SYSTEMS (ENGLISH)
Annalisa DE BONIS ADVANCED ALGORITHMIC TECHNIQUES FOR DISTRIBUTED SYSTEMS (ENGLISH)
| 0522500106 | |
| DIPARTIMENTO DI INFORMATICA | |
| CORSO DI LAUREA MAGISTRALE | |
| INFORMATICA | |
| 2016/2017 |
| ANNO CORSO 2 | |
| ANNO ORDINAMENTO 2015 | |
| PRIMO SEMESTRE |
| SSD | CFU | ORE | ATTIVITÀ | |
|---|---|---|---|---|
| INF/01 | 6 | 24 | LEZIONE |
| Obiettivi | |
|---|---|
| CONOSCENZA E CAPACITÀ DI 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 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 •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 DEL MINIMO ALBERO RICOPRENTE •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 CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE L'INSEGNAMENTO HA COME OBIETTIVO QUELLO DI RENDERE LO STUDENTE CAPACE DI UTILIZZARE LE TECNICHE PIÙ 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. |
| 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: 24 •PANORAMICA DELL'INSEGNAMENTO E CONCETTI INTRODUTTIVI (1 ORA) •COLORAZIONE DISTRIBUITA DI UN GRAFO: COLORAZIONE IN GRAFI DI GRADO COSTANTE, ALGORITMI E LOWER BOUND (4 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 (5 ORE) •MINIMO ALBERO RICOPRENTE: UNA VERSIONE RIVISITATA DELL’ALGORITMO DI KUTTEN AND PELEG (4 ORE) •LIMITI INFERIORI BASATI SULLA COMPLESSITÀ DI COMUNICAZIONE: LIMITI INFERIORI PER IL MINIMO ALBERO RICOPRENTE (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 SARÀ RESO DISPONIBILE A LEZIONE E SUL SITO WEB DELL'INSEGNAMENTO. |
BETA VERSION Fonte dati ESSE3 [Ultima Sincronizzazione: 2019-03-11]
