ADVANCED ALGORITHMS AND PROGRAMMING METHODS - 1

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 passera' poi a considerare i sistemi distribuiti, verranno introdotti algoritmi in tale contesto e verra' mostrata qualche applicazioni pratica di algoritmi distribuiti nel campo della robotica. Lo studente acquisirà alcune competenze che servono per progettare e analizzare algoritmi piu' complessi ed. avanzati di quelli visti nel percorso di studi triennale.

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 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 e di probabilita'.

Per la parte di progettazione pratica saranno necessare delle conoscenze fornite dal corso di Advanced Algorithms mod II.

Ripasso di concetti di NP-completezza

Algoritmi di approssimazione. I problemi:
- vertex cover
- load balancing
- center selection
- metric TSP
- weighted vertex cover
- un algoritmo per il problema max cut

Tecniche di ricerca locale
- Gradient Discent
- l'algoritmo Metropolis
- Simulated Annealing
- Hopfield Neural Networks
Algoritmi genetici
L'equilibrio di Nash

Algoritmi probabilistici
- Classificazione (numerici, Monte Carlo, Las Vegas)
- il problema della risoluzione delle contese
- Randomized quicksort
- algoritmo di Buffon

Algoritmi Distribuiti
- Modelli e misure di complessità
- Reti di interconnessione e proprieta' delle reti
- il problema del broadcast
- la costruzione del distributed spanning tree
- gli algoritmi Shout e Shout+
- DFS distribuita
- il problema dell'elezione del leader
- algoritmi di saturazione sugli alberi
- il calcolo del minimo
- il problema del ranking
- sistemi P2P
- agenti e robot mobili: modelli e algoritmi

[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 Advanced Algorithms 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.
I venti studenti che avranno superato la prima prova con il voto più alto, se vorranno, potranno sostituire la seconda prova con un progetto pratico da fare in gruppo. Per il progetto dovranno progettare un algoritmo distribuito e realizzarlo con dei robot programmabili in linguaggio C, ecc.. Dovranno poi presentare singolarmente una relazione e fare una dimostrazione pratica (in gruppo). Dovranno inoltre dimostrare di aver partecipato ad almeno 3/4 delle lezioni della seconda parte del corso.

Insegnamento organizzato in lezioni frontali, esercizi su carta e online, qualche attivita' laboratoriale.

Inglese

È richiesto che gli studenti si registrino sulla pagina del corso presente nella piattaforma e-learning moodle.unive.it

scritto e orale