ALGORITMI RANDOMIZZATI E APPROSSIMATI
Anno accademico 2024/2025 - Docente: Vincenzo CUTELLORisultati di apprendimento attesi
Conoscenza e capacità di comprensione: saranno acquisite le conoscenze relative alla progettazione ed analisi di Algoritmi randomizzati ed approssimati.
Capacità di applicare conoscenza e comprensione: saranno acquisite le capacità per applicare le nozioni imparate in vari campi ad in particolare la risoluzione di problemi combinatorialmente molto difficili.
Autonomia di giudizio : Lo studente sarà in grado di valutare la possibilità di sviluppare algoritmi randomizzati e approssimati nella risoluzione algoritmica di problemi in diversi ambiti applicativi.
Abilità comunicative: saranno acquisite le necessarie abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli algoritmi avanzati e le loro applicazioni.
Capacità di apprendimento : lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti e di comprendere i limiti di applicabilità delle tecniche algoritmiche.
Capacità di applicare conoscenza e comprensione: saranno acquisite le capacità per applicare le nozioni imparate in vari campi ad in particolare la risoluzione di problemi combinatorialmente molto difficili.
Autonomia di giudizio : Lo studente sarà in grado di valutare la possibilità di sviluppare algoritmi randomizzati e approssimati nella risoluzione algoritmica di problemi in diversi ambiti applicativi.
Abilità comunicative: saranno acquisite le necessarie abilità comunicative ed un'adeguata appropriatezza espressiva nella comunicazione di problematiche inerenti gli algoritmi avanzati e le loro applicazioni.
Capacità di apprendimento : lo studente avrà la capacita di adattare le conoscenze acquisite anche a nuovi contesti e di comprendere i limiti di applicabilità delle tecniche algoritmiche.
Modalità di svolgimento dell'insegnamento
Le lezioni saranno di presenza in classe.
Prerequisiti richiesti
Il corso presuppone una buona conoscenza di strumenti matematici discreti e continui, ed una conoscenza approfondita di algoritmi.
Frequenza lezioni
La frequenza è fortemente consigliata per comprendere meglio gli argomenti trattati e come sono correlati.
Contenuti del corso
Contenuti di massima del Corso:
- Fondamenti di calcolo delle probabilità
- Algoritmi randomizzati
- Analisi probabilistica di algoritmi
- Esempi di Algoritmi approssimati per problemi NP-hard
Testi di riferimento
Oltre agli appunti e slides fornite dal docente, sarà adottato il seguente testo:
TH Cormen, CE Leiserson, RL Rivest, C Stein, Introduzione agli Algoritmi e strutture dati
Programmazione del corso
| Argomenti | Riferimenti testi | |
|---|---|---|
| 1 | Fondamenti di calcolo delle probabilità | Appendice C |
| 2 | Analisi Probabilistica di Algoritmi | Capitolo 5 |
| 3 | Algoritmi Randomizzati | Capitolo 5 |
| 4 | Introduzione alla NP-completezza | Capitolo 34 |
| 5 | Algoritmi di approssimazione | Chapter 35 |
| 6 | Esempi di problemi e progetti implementativi |
Verifica dell'apprendimento
Modalità di verifica dell'apprendimento
L'esame consisterà in un progetto implementativo seguito da discussione orale.
Gli studenti con disabilità e/o DSA dovranno contattare con sufficiente anticipo rispetto alla data dell'esame il docente, il referente CInAP del DMI (prof.ssa Daniele) e il CInAP per comunicare che intendono sostenere l'esame fruendo delle opportune misure compensative.
Esempi di domande e/o esercizi frequenti
1. Qual è il valore atteso di questa distribuzione di probabilità?
2. Qual è il rapporto di approssimazione di questo algoritmo e qual è la sua complessità?