Ti trovi qui: Home » Didattica » Insegnamento: Algoritmi di approssimazione

Insegnamento: Algoritmi di approssimazione (Offerta Formativa a.a. 2015/2016)

Corso di studio: MATEMATICA (D.M. 270/04)

CFU6
Moduli

Modulo: Algoritmi di approssimazione
TAF: Affine/Integrativa; SSD: INF/01; Ambito: Attività formative affini o integrative
Docenti: Mauro LEONCINI, Manuela MONTANGERO

Dolly Accedi ai dati dell'insegnamento su Dolly
Orario Lezioni Accedi all'orario settimanale dell'insegnamento
Propedeuticità obbligatorie
Modalità di accertamento del profitto Orale
Modalità di valutazione Voto
Esse3 Accedi ai dati dell'insegnamento su Esse3
Lingua di insegnamento

Italiano

Partizionamento studenti

Nessun partizionamento

Obiettivi

E' consigliato il corso di Algoritmi e Strutture dati.

Prerequisiti

Modelli di calcolo, tesi di Church-Turing. Problemi decisionali e problemi di ottimizzazione. Le classi di complessità P ed NP- Nozione di riducibilità polinomiale. Problemi NP-hard e NP-completi, Algoritmi di approssimazione. Garanzie assolute e relative.
Programmazione lineare intera e modellazione di problemi di ottimizzazione. Esempi. Tecniche risolutive: rilassamento, dualità, branch and bound, metodo primale-duale.
Altre tecniche risolutive (greedy, programmazione dinamica, ...).
Alcuni esempi importanti in dettaglio: Traveling Salesman Problem, Shortest superstring, Bin-packing.

Contenuti

L'insegnamento introduce le principali nozioni di complessità computazionale, in particolare la teoria della NP-completezza, e quelle legate alla teoria dell'approssimazione per problemi di natura combinatoria. Introduce inoltre alcune tecniche per lo sviluppo di algoritmi approssimati (greedy, programmazione dinamica, branch-and-bound, metodo primale-duale).

Metodi didattici

Lezioni frontali ed esercitazioni in aula.

Verifica dell'apprendimento

Esame orale

Risultati attesi

Dispense e articoli scientifici forniti dai docenti (anche in lingua inglese). Course notes and scientific papers provided by the instructors (in Italian and in English).

Testi

- Conoscenza e comprensione
Gli studenti avranno solide conoscenze e capacità di comprensione delle principali problematiche collegate allo studio della complessità dei problemi e delle tecniche di progetto di algoritmi approssimati per problemi di natura combinatoria difficili.

- Capacità di applicare conoscenza e comprensione.
Lo studente sarà portato a sviluppare autonome capacità di applicazione delle conoscenze acquisite riconducibili a: (1) classificazione della difficoltà di problemi computazionali; (2) sviluppo di algoritmi approssimati per problemi categorizzati come "difficili" (NP-hard).

- Autonomia di giudizio
Lo studente avrà una buona capacità di reperire dati e informazioni utili allo svolgimento del proprio lavoro, particolarmente in relazione alla formalizzazione di problemi e alla scelta e messa a punto di strategie algoritmiche efficienti per la loro risoluzione. Sarà in grado di fornire giudizi autonomi sulle scelte operate e di valutare criticamente i risultati ottenuti, anche in funzione di tali scelte.

- Abilità comunicative
Nel contesto della risoluzione algoritmica di problemi computazionali, lo studente sarà in grado, utilizzando argomenti quantitativi e un linguaggio tecnico appropriato, di dare ragione delle varie opzioni progettuali, evidenziandone vantaggi e svantaggi in termini di efficienza. Avrà capacità di leggere con profitto la letteratura tecnica in lingua inglese su argomenti di algoritmica.

- Capacità di apprendimento
Questo insegnamento aiuterà lo studente a maturare ed affinare capacità di apprendimento continuo e autonomo, indispensabili per stare al passo di una disciplina tecnica in continua e rapida evoluzione.

Docenti

Manuela MONTANGERO
Mauro LEONCINI