Insegnamento ALGORITMI AVANZATI
| Nome del corso di laurea | Informatica |
|---|---|
| Codice insegnamento | GP004152 |
| Curriculum | Modelli e sistemi dell'elaborazione dell'informazione |
| Docente responsabile | Maria Cristina Pinotti |
| CFU | 12 |
| Regolamento | Coorte 2019 |
| Erogato | Erogato nel 2019/20 |
| Erogato altro regolamento | |
| Anno | 1 |
| Periodo | Primo Semestre |
| Tipo insegnamento | Obbligatorio (Required) |
| Tipo attività | Attività formativa integrata |
| Suddivisione |
ALGORITMI I MODULO
| Codice | GP004160 |
|---|---|
| CFU | 6 |
| Docente responsabile | Alfredo Navarra |
| Docenti |
|
| Ore |
|
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Tipo insegnamento | Obbligatorio (Required) |
| Lingua insegnamento | ITALIANO |
| 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. |
| Testi di riferimento | N. Santoro: Design and Analysis of Distributed Algorithms. John Wiley & Sons |
| Obiettivi formativi | conoscenze avanzate su tematiche di algoritmi distribuiti. Accrescimento capacità critiche e applicative |
| Prerequisiti | conoscenze di base di algoritmi |
| Metodi didattici | lezioni frontali seminari |
| Modalità di verifica dell'apprendimento | colloquio orale |
| 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. |
ALGORITMI II MODULO
| Codice | GP004159 |
|---|---|
| CFU | 6 |
| Docente responsabile | Maria Cristina Pinotti |
| Docenti |
|
| Ore |
|
| Attività | Caratterizzante |
| Ambito | Discipline informatiche |
| Settore | INF/01 |
| Tipo insegnamento | Obbligatorio (Required) |
| Lingua insegnamento | ITALIANO |
| Contenuti | Il contenuto del corso varia di anno in anno. Quest'anno si intendono studiare in particolare strutture dati avanzate, quali Leftisti heaps, Binomial heaps, Range Searching, Interval Trees, Segment Trees , Splay trees, Treaps, Bloom Filters. |
| Testi di riferimento | Capitoli estratti da: TD. P. Mehta, S. Sahni, ¿ Handbook of Data Structures and Applications, C hapman and Hall, CRC, 2018; R.E. Tarjan, ¿ Data Structures and Network Algorithms, ¿ SIAM, 1983; M.T. Goodrich, and R. Tamassia, ¿ Algorithm Design and Applications, ¿ Wiley, 2014 |
| Obiettivi formativi | Obiettivi: 1) estendere le conoscenze acquisite nella laurea triennale, 2) vedere criteri che aiutino gli studenti a scegliere la corretta struttura dati, 3) analizzare l'importanza delle strutture dati in aree emergenti quali big data e machine learning. |
| Prerequisiti | Algoritmi e strutture dati. Teoria della complessità computazionale. |
| Metodi didattici | Lezioni frontali e presentazioni da parte degli studenti. |
| Altre informazioni | La seconda parte del corso sarà offerta in collaborazione con un prof. visitatore, se il progetto di visita sarà finanziato. |
| Modalità di verifica dell'apprendimento | Presentazioni e rapporti tecnici. Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa |
| Programma esteso | Code di priorità. Strutture dati per la ricerca binaria. Strutture dati per la Geometria computazionale. Strutture dati per i grafi. |