ALGORITMI AVANZATI E DISTRIBUITI

Il corso fornisce tecniche di base per la progettazione e l'analisi di algoritmi avanzati quali algoritmi di approssimazione, genetici, probabilistici e tecniche di ricerca locale. Si passerà poi a considerare i sistemi distribuiti, verranno introdotti algoritmi in tale contesto e verrà mostrata qualche applicazioni di algoritmi distribuiti nel campo della sicurezza e della robotica. Lo studente acquisirà alcune competenze che servono per progettare e analizzare algoritmi complessi ed avanzati.

La frequenza e la partecipazione attiva alle attività formative proposte dal corso (lezioni frontali, esercizi, attivita' laboratoriali) e lo studio individuale consentiranno a studenti/studentesse di:

1 Conoscenza e comprensione
1.1 acquisire i fondamenti teorici e conoscenze avanzate su temi classici dell'informatica quali algoritmi di approssimazione, genetici, probabilistici, distribuiti e delle tecniche di ricerca locale;
1.2. acquisire conoscenze di alcune applicazioni pratiche degli algoritmi distribuiti nel campo della sicurezza e della robotica.

2. Capacità di applicare conoscenza e comprensione
2.1. sapere utilizzare le conoscenze acquisite per modellare e risolvere problemi algoritmici nel mondo reale.
3. Capacità di giudizio
3.1. sapere scegliere e analizzare l'algoritmo piu' appropriato da utilizzare in uno specifico contesto reale.

Si consiglia di aver seguito un corso di algoritmi di base, di programmazione e di probabilità.

Ripasso di concetti di NP-completezza.

Algoritmi di approssimazione.
Tecniche di ricerca locale.
Algoritmi genetici.
Algoritmi probabilistici.


Algoritmi Distribuiti
- Modelli e misure di complessità
- Reti di interconnessione e proprieta' delle reti
- Diversi problemi e loro soluzione tramite algoritmi distribuiti (es: il problema del broadcast, la costruzione del distributed spanning tree, il problema dell'elezione del leader, computazioni sugli alberi, ricerche in sistemi P2P).
- Esempi di applicazioni alla sicurezza (Bitcoin) e alla robotica (mobile robots).

[CLRS] Introduction to Algorithms, third edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

[KT] Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley, 2005

[S] Design and Analysis of Distributed Algorithms, Nicola Santoro, Whiley- Interscience, 2007

[L] Slides of the course

L’apprendimento viene verificato tramite un esame scritto, eventualmente seguito da una prova orale. Le domande, sia teoriche che pratiche, mirano a valutare la comprensione degli argomenti trattati, la capacità di applicarli a casi concreti e l’abilità di analizzare criticamente le soluzioni algoritmiche proposte.
L’orale è obbligatorio per chi ottiene un punteggio compreso tra 15 e 17 (su 30) allo scritto, mentre è facoltativo per chi raggiunge la sufficienza.

L’esame può essere superato in uno dei seguenti modi:
- con un’unica prova scritta finale;
- con due prove intermedie (se approvate dal collegio didattico): la prima a metà corso, la seconda al termine, accessibile solo dopo il superamento della prima;
- con una prova intermedia a metà corso (se approvata dal collegio didattico) relativa alla prima parte del programma, seguita da un progetto pratico sui robot,
focalizzato sugli algoritmi distribuiti. In caso di un numero eccessivo di richieste per il progetto, verrà effettuata una selezione sulla base del risultato della prova
intermedia.

scritto e orale

Il/la docente ha il dovere di vigilare affinché siano rispettate le regole di autenticità e originalità delle prove d'esame. Di conseguenza, nei casi in cui vi sia il sospetto di un comportamento irregolare, l'esame può prevedere un ulteriore approfondimento, contestuale alla prova d'esame, che potrà essere realizzato anche in modalità differente rispetto alle modalità sopra riportate.

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto. L'orale è obbligatorio per chi è quasi sufficiente (tra il 15 e il 17), facoltativo per chi è sufficiente. La prova orale vale un massimo di 6 punti bonus. Se superata positivamente, il bonus si somma al voto della prova scritta, formando il voto finale (se il voto finale è inferiore a 18, l'esame non è superato). Se invece la prova orale viene valutata negativamente, il bonus viene sottratto dal voto di partenza e lo studente potrebbe anche non superare l'intero esame. La valutazione dell'esame terrà conto sia della capacità di rispondere alle domande teoriche sugli argomenti dell'esame, sia sulla capacità si svolgere gli esercizi secondo un punteggio indicato in ogni domanda.
Verranno inoltre proposte due prove intermedie durante l'anno (previa approvazione del collegio didattico), una a metà del corso e una dopo la fine del corso alla quale si accede solo con il superamento della prima prova. Il superamento di entrambe le prove esonererà dall'esame scritto. Il voto finale sarà dato dalla media dei voti delle due prove. La seconda prova potrà essere sostituita da un progetto pratico con i robot.

Insegnamento organizzato in lezioni frontali, esercizi su carta e online.

È richiesto che gli studenti si registrino sulla pagina del corso presente nella piattaforma e-learning moodle.unive.it.
Il corso si terrà in lingua inglese.