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.

Si consiglia di aver seguito 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 (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

La verifica dell'apprendimento avviene attraverso il superamento di un esame scritto atto a verificare le conoscenze degli argomenti presentati nel corso. L'esame scritto e l'eventuale orale comprendono sia domande teoriche sugli argomenti del corso, sia esercizi.
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. 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. In caso di eccesso di richieste di progetto per la selezione si terrà conto del voto della prima prova intermedia.

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.

scritto e orale