Natural Distributed Algorithms

Informazioni sul corso

Docente: Emanuele Natale

A.A.: 2019/2020

Date e orario del corso: Si veda il diario delle lezioni fornito di seguito.

Aula: Aula 7 dell'edificio della Macroarea di Scienze M.F.N. (approssimativamente qui).

Corso di laurea: Laurea Magistrale in Informatica

CFU: 3

Modalità d'esame: Presentazione di un progetto, tipicamente lettura di uno o due articoli scientifici attinenti e scrittura di un esposto delle idee principali. Proposte di progetto saranno fornite al termine di ogni lezione, e gli studenti sono incoraggiati ad avanzare proprie eventuali proposte.

Modalità di verbalizzazione: Il docente proporrà un voto all'elaborato inviato dallo studente (preferibilmente per posta elettronica). Nel caso in cui lo studente accetti il voto, questo verrà comunicato dal docente al Prof. Clementi il quale lo verabalizzerà contestualmente alla verabilizzazione del corso di ADRC. Nel caso lo studente non sia soddisfatto del voto proposto, il docente proporrà come migliorare il progetto presentato per aumentarne la valutazione. Non ci sono limiti formali a quante revisioni del progetto possono essere presentate al fine di ottenere un voto migliore (con l'ovvio invito al buon senso). N.B. Per formalità, sono state fissate due date di appello per l'esame, il 21 e 28 Febbraio 2020. Il docente è disponibile in tali date nel caso lo studente volesse presentare il proprio progetto di persona (su orario da concordare). Nel caso in cui lo studente volesse presentare il proprio progetto di persona, ma in date successive alle precedenti, il docente è disponibile a fissare un incontro in videoconferenza. Naturalmente, presentare il progetto di persona o in videochiamata non comporta un punteggio aggiuntivo ai fini della valutazione finale.

Presentazione del corso: Il corso presenterà recenti risultati di ricerca nell’ambito degli “algoritmi naturali”, ovvero l’analisi di processi algoritmici riscontrati in natura. Trattandosi di un corso orientato alla ricerca, il programma sarà adattabile alle preferenze degli studenti che vi parteciperanno. Argomenti possibili includono: come l’organismo Physarum Polycephalum risolve il problema dei cammini minimi, come varie specie di formiche calcolano la densità della popolazione all’interno della propria colonia, come il sistema nervoso di alcune mosche appare risolvere il problema indipendent set in modo distribuito, e molti altri. Il corso è pertanto di interesse sia a coloro che siano interessati alla modellizazione matematica di processi biologici, che a coloro interessati ad apprendere gli strumenti per anlizzare una varietà di algoritmi molto semplici ma efficaci.

Programma del corso: Si veda il diario delle lezioni fornito di seguito.

Materiale didattico: Slides del docente e articoli indicati nel programma fornito di seguito. Gli articoli dovrebbero essere scaricabili dalla rete di ateneo. Una copia può essere richiesta direttamente al docente tramite email.

Diario delle lezioni (Lunedì 16:30-18:30)

4/11/2019 - Lezioni "0" e 1

Introduzione alla ricerca sugli algoritmi naturali.

Il problema del Rumor Spreading in modelli di interazione stocastica in presenza di communication noise, motivato dal problema del reclutamento nella specie di formiche cataglyphis niger.

11/11/2019 - Lezioni 2 e 3

Continuazione della lezione precedente sui modelli di interazione stocastica in presenza di communication noise.

18/11/2019 - Lezione 4

Lezione tenuta dal Dott. Vincenzo Bonifaci, sul tema "Physarum polycephalum e il problema del cammino minimo".

Il seguente articolo costituisce una buona introduzione al tema:

Gli articoli del Dott. Bonifaci sono liberamente scaricabili dalla sua pagina web personale.

25/11/2019 - Lezione 5

Una semplice soluzione al problema della stima della densità ispirata dalle formiche.

2/12/2019 - Lezione 6

La lezione sarà tenuta dal Dott. Vito Trianni, sul tema "Le api e il problema della decisione collettiva nella scelta del nido, con applicazioni in swarm robotics".

9/12/2019 - Lezione 7 e 8

Quanta memoria serve per risolvere il problema del Majority Consensus nel modello Population Protocols? (Parte della lezione è già stata discussa durante la lezione del 25/11/2019 e sarà brevemente richiamata.)

Breve panoramica su aspetti algoritmici in neuroscienze. Il problema della sparsificazione distribuita di grafi expander.

16/12/2019 - Lezione

Discussione dei progetti.