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.1. 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 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.

Un corso di algoritmi di base, di programmazione e di probabilita'.

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 e alla robotica.

[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

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto atto a verificare le conoscenze degli argomenti presentati nel corso. L'orale è obbligatorio per chi è quasi sufficiente (tra il 15 e il 17), facoltativo per chi è sufficiente. Lo scritto (e l'eventuale orale) servono a verificare le conoscenze previste dal programma del corso.
Verranno 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.

scritto e orale

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

Inglese

È 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.