Università degli Studi dell'Aquila
Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica.
Anno Accademico 2013/2014
|
News (Clicca qui)
Algoritmi e Strutture Dati 2 (6 CFU).
Link al sito ufficiale del Corso di laurea in informatica - Università degli Studi dell'Aquila (click here).
Orario:
Primo Semestre (30 Settembre, 2013 - 24 Gennaio, 2014), Martedi: 11.00–13.00 (Aula A1.2) e Mercoledi: 09.00–11.00 (Aula A.1.2)
Ricevimento Studenti:
Martedi: 15.00 – 17.00. Ufficio: Blocco 0, ultimo piano, stanza 220.
Libri di testo:
Vijay V. Vazirani: "Approximation algorithms". Springer 2001.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
"Complexity and Approximation". Springer. 1999.
Slides del corso:
Prima parte (Clicca qui)
Seconda parte (Clicca qui)
Terza parte (Clicca qui)
Syllabo:
- Richiami di complessità ed intrattabilità. Problemi di ottimizzazione. Algoritmi di approssimazione.
- Tecniche algoritmiche: greedy.
- Tecniche algoritmiche: ricerca locale e programmazione dinamica.
- Tecniche di programmazione lineare: metodo dell'arrotondamento e metodo del primale-duale.
- Schemi di approssimazione polinomiali e pienamente polinomiali.
- Risultati negativi di approssimabilità e tecnica del Gap. Classi di complessità per problemi di ottimizzazione e loro contenimenti.
Modalità d'Esame:
Prova scritta ed un'eventuale discussione orale sulla prova scritta.
Testi d'Esame anni precedenti:
(Clicca qui)
Diario delle lezioni:
1 Ottobre 2013: Introduzione al corso. Richiami di complessità: problemi di decisione,
di ricerca e di ottimizzazione; complessità asintotica di algoritmi e problemi,
trattabilità e risolubilità polinomiale.
Richiami di complessità: robustezza risolubilità polinomiale.
Richiami di complessità: classi P ed NP, problemi NP-completi,
congettura P!=NP. Problemi di ottimizzazione: definizione ed esempi,
problemi di decisione soggiacenti. Problemi di ottimizzazione: definizione
ed esempi, problemi di decisione soggiacenti, classi PO e NPO, problemi NP-hard.
2 Ottobre 2013: Algoritmi di approssimazione: definizione, algoritmo
2-approssimante per Min Vertex Cover. Tecnica greedy: descrizione, algoritmo 1/2-approssimante
per Max Sat, esempi esecuzione algoritmo 1/2-approssimante per Max Sat.
8 Ottobre 2013: Algoritmo greedy per Max 0-1 Knapsack, algoritmo pseudo(modified)-greedy 1/2-approssimante per Max 0-1 Knapsack,
euristica Nearest-Neighbor per Min Metrical TSP, algoritmo 2-1/h-approssimante per Min Multiprocessor Scheduling.
9 Ottobre 2013: Algoritmo Greedy per Min Vertex Cover, algoritmo greedy 1/2-approssimante per Max Cut.
15 Ottobre 2013: Tecnica della ricerca locale: descrizione, algoritmo ottimo per Max Matching, algoritmo 1/2-approssimante per Max Cut.
16 Ottobre 2013: cenni euristica per Min TSP euclideo, Tecnica della programmazione dinamica: descrizione, algoritmo ottimo pseudo-polinomiale per Max 0-1 Knapsack: inizio.
22 Ottobre 2013: algoritmo ottimo pseudo-polinomiale per Max 0-1 Knapsack: fine, tecnica della programmazione lineare e metodo dell’arrotondamento:
descrizione, algoritmo 2-approssimante per Min Weighted Vertex Cover.
23 Ottobre 2013: Metodo dell’arrotondamento: Algoritmo f-approssimante per Min Weighted Set Cover, Tecnica della programmazione lineare e metodo del primale-duale: descrizione.
29 Ottobre 2013: Metodo del primale-duale: algoritmo 2-approssimante per Min Weighted Vertex Cover, esempi esecuzione algoritmo (primale-duale) 2-approssimante per
Min Weighted Vertex Cover.
30 Ottobre 2013: Metodo del primale-duale: algoritmo f-approssimante per Min Weighted Set Cover, esempi esecuzione algoritmo (primale-duale) f-approssimante per
Min Weighted Set Cover.
5 Novembre 2013: Algoritmo greedy Hn-approssimante per Min Weighted Set Cover. Tecnica del Dual Fitting e applicazione alla
dimostrazione di Hn-approssimazione dell’algoritmo greedy per Min Weighted Set Cover. Cenni stima migliore del
rapporto di approssimazione tramite dual-fitting nel caso di insiemi di cardinalità limitata
6 Novembre 2013: Algoritmo greedy (4/3 - 1/3h)-approssimante per Min Multiprocessor Scheduling. Approcci alternativi all’approssimazione.
12 Novembre 2013: Algoritmi randomizzati: definizione di approssimazione, algoritmo 1/2-approssimante per Max Weighted Cut.
13 Novembre 2013: Algoritmi randomizzati: algoritmi 1/2-approssimante e 3/4-approssimante per Max Weighted Sat.
19 Novembre 2013: Esercitazione (alla lavagna) di preparazione alla prova intermedia.
20 Novembre 2013: Esercitazione (alla lavagna) di preparazione alla prova intermedia.
29 Novembre 2013: Esame Parziale.
3 Dicembre 2013: Correzione (alla lavagna) dell'esame parziale.
Schemi di approssimazione polinomiali (PTAS): definizione, PTAS per Min Partition.
4 Dicembre 2013: Schemi di approssimazione pienamente polinomiali (FPTAS): definizione, FPTAS per Max 01-Knapsack.
10 Dicembre 2013: FPTAS più efficiente mediante l’utilizzo dell’algoritmo pseudo(modified)-greedy 1/2-approssimante per Max 01-Knapsack,
esempi di esecuzione algoritmo FPTAS-Knapsack, Tecnica del partizionamento fisso e FPTAS per Max 01-Knapsack (inizio).
11 Dicembre 2013: Tecnica del partizionamento fisso e FPTAS per Max 01-Knapsack (fine), confronto tra FPTAS-Knapsack
e Knapsack con partizione fissa, tecnica del partizionamento variabile e FPTAS per Max 01-Product Knapsack (inizio).
17 Dicembre 2013: Tecnica del partizionamento variabile e FPTAS per Max 01-Product Knapsack (fine), Classi di complessità per
problemi di ottimizzazione e loro contenimenti. Contenimento proprio di EXP-APX in NPO. Contenimento proprio di PO in FPTAS.
18 Dicembre 2013: Classi di complessità per
problemi di ottimizzazione e loro contenimenti: contenimento proprio di FPTAS in PTAS.
7 Gennaio 2014: Risultati negativi di approssimazione e tecniche di delimitazione del
rapporto di approssimazione raggiungibile. Tecnica del Gap. Contenimento proprio di APX in EXP-APX.
8 Gennaio 2014: Contenimento proprio di PTAS in APX.
14 Gennaio 2014: Euristica di Christofides per Min Metrical TSP.
15 Gennaio 2014: Esempi esecuzione algoritmo di Christofides. Algoritmo greedy per Max Independent Set (inizio).
21 Gennaio 2014: Algoritmo greedy per Max Independent Set (fine).
22 Gennaio 2014: Esercizi d’esame (alla lavagna).
News:
9 Ottobre 2013: I lucidi (Prima parte) 91,92,93 sono stati leggermente modificati. La versione aggiornata è disponibile online. (clicca qui) .
23 Ottobre 2013: E' stata aggiunta la pagina 19 ai lucidi "Seconda parte". La versione aggiornata è disponibile online. (clicca qui) .
6 Novembre 2013: Sono state aggiunte le pagine da 163 a 177 ai lucidi "Seconda parte". La versione aggiornata è disponibile online. (clicca qui) .
7 Novembre 2013: Data e Luogo prova parziale e appello di recupero per laureandi e fuoricorso: Mercoledi 27/11/2013, ore 14:30, aula 1.6 (COppito 1).
13 Novembre 2013: I lucidi "Terza parte" sono stati leggermente modificati. La versione aggiornata è disponibile online. (clicca qui) .
26 Novembre 2013: A causa delle condizioni metereologiche in corso, l'esame
(prova parziale e appello di recupero per laureandi e fuoricorso) di domani 27 Novembre è rimandato a data da definirsi.
27 Novembre 2013: La prova parziale e l'appello di recupero per laureandi e fuoricorso si terrà Venerdi 29/11/2013, ore 10:00, aula C 1.10 (Coppito 2)
30 Novembre 2013: Disponibili i risultati della prova di recupero di "Algoritmi e Strutture Dati 2" del 29 Novembre 2013.
(Clicca qui)
6 Dicembre 2013: Disponibili i risultati della prova parziale di "Algoritmi e Strutture Dati 2" del 29 Novembre 2013.
(Clicca qui)
9 Gennaio 2014: I lucidi "Terza parte" sono stati leggermente modificati. La versione aggiornata è disponibile online. (clicca qui) .
27 Gennaio 2014: A causa dei possibili problemi di mobilità dovuti alla neve, il ricevimento studenti di martedi 28 Gennaio 2014 è posticipato a mercoledi 29 Gennaio, dalle 11:00 alle 13:00.
4 Febbraio 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 3 Febbraio 2014.
(Clicca qui)
19 Febbraio 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 17 Febbraio 2014.
(Clicca qui)
26 Febbraio 2014: Causa missione di ricerca all'estero, il ricevimento studenti è sospeso fino al 8 Aprile 2014. Per urgenze, contattare il docente via e-mail.
2 Aprile 2014: Il ricevimento studenti di martedi 8 aprile è spostato a mercoledi 9 aprile dalle ore 10 alle 12.
9 Aprile 2014: Il ricevimento studenti di martedi 15 aprile è annullato. Il ricevimento studenti di martedi 22 aprile è spostato a mercoledi 23 Aprile dalle 10 alle 12.
Per urgenze, contattare il docente via e-mail.
3 Giugno 2014: Il ricevimento studenti di martedi 10 Giugno è spostato a Lunedi 9 Giugno dalle 15 alle 17, causa festività di San Massimo.
22 Giugno 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 20 Giugno 2014.
(Clicca qui)
24 Giugno 2014: Il ricevimento studenti di martedi 1 Luglio è annullato, causa missione di ricerca all'estero. Per urgenze, contattare il docente via e-mail.
8 Luglio 2014: Il ricevimento studenti di martedi 15 Luglio è annullato, causa missione di ricerca all'estero. Per urgenze, contattare il docente via e-mail.
27 Luglio 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 25 Luglio 2014.
(Clicca qui)
30 Luglio 2014: Si avvisano gli studenti che nel mese di Agosto il ricevimento è sospeso. Il prossimo ricevimento studenti sarà martedi 2 Settembre dalle 15 alle 17.
Per urgenze, contattare il docente via e-mail.
2 Settembre 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 1 Settembre 2014.
(Clicca qui)
21 Settembre 2014: Disponibili i risultati della prova di "Algoritmi e Strutture Dati 2" del 19 Settembre 2014.
(Clicca qui)
6 Ottobre 2014: Si avvisano gli studenti che nell'A.A. 2014/2015 il corso di "Algoritmi e Strutture Dati II" è tenuto dal Prof. Flammini.
6 Ottobre 2014: Si avvisano gli studenti che dal mese di Ottobre il ricevimento studenti è su appuntamento da concordare via email con il docente.