Acquisire competenze sulle principali tecniche di risoluzione per problemi di ottimizzazione combinatoria; approfondire le competenze sulla teoria dei grafi; acquisire competenze tecniche avanzate per la progettazione, l'analisi e l'implementazione al calcolatore di algoritmi per la risoluzione di problemi di ottimizzazione su grafi, alberi e reti di flusso.
Curriculum
scheda docente materiale didattico
2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Programma
1. Problemi di ottimizzazione e di ottimizzazione combinatoria. Enumerazione delle soluzioni.2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Testi Adottati
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Bibliografia Di Riferimento
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, 3a edizione, 2010. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Ottimizzazione combinatoria. Springer, 2011. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Modalità Erogazione
Lezioni frontali con esercitazioni frontali e di laboratorio. Per il diario delle lezioni si consulti il sito del docente: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlModalità Valutazione
Esame orale. scheda docente materiale didattico
2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Mutuazione: 20410626 IN440 - OTTIMIZZAZIONE COMBINATORIA in Scienze Computazionali LM-40 BONIFACI VINCENZO
Programma
1. Problemi di ottimizzazione e di ottimizzazione combinatoria. Enumerazione delle soluzioni.2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Testi Adottati
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Bibliografia Di Riferimento
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, 3a edizione, 2010. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Ottimizzazione combinatoria. Springer, 2011. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Modalità Erogazione
Lezioni frontali con esercitazioni frontali e di laboratorio. Per il diario delle lezioni si consulti il sito del docente: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlModalità Valutazione
Esame orale. scheda docente materiale didattico
2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Programma
1. Problemi di ottimizzazione e di ottimizzazione combinatoria. Enumerazione delle soluzioni.2. Fondamenti di analisi degli algoritmi. Trattabilità computazionale. Ordine asintotico di crescita.
3. Grafi. Connettività ed attraversamento. Bipartizioni. Connettività in grafi diretti. Grafi diretti aciclici ed ordinamento topologico.
4. Algoritmi avidi. Schedulazione di intervalli. Caching ottimo. Cammini minimi in un grafo. Albero ricoprente a costo minimo.
5. Divide et impera. Il mergesort. Conteggio di inversioni. Coppia di punti più vicina.
6. Programmazione dinamica. Schedulazione di intervalli pesati. Principi della programmazione dinamica. Somme di sottoinsiemi e problema della bisaccia. Cammini minimi tra tutte le coppie. Cammini minimi e protocollo basato su vettori delle distanze.
7. Flussi di rete. Flusso massimo e algoritmo di Ford-Fulkerson. Flussi massimi e tagli minimi in una rete. Cammini aumentanti. Abbinamenti bipartiti. Cammini disgiunti in grafi diretti e non diretti.
8. Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni attraverso "gadget". Certificazione efficiente e definizione di NP. Problemi NP-completi. Problemi di copertura, impaccamento, partizionamento, sequenziamento, numerici. Altri esempi.
Testi Adottati
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.Bibliografia Di Riferimento
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi e strutture dati. McGraw-Hill, 3a edizione, 2010. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill, 2016. Bernhard Korte, Jens Vygen. Ottimizzazione combinatoria. Springer, 2011. Michael R. Garey, David S. Johnson. Computers and Intractability. Freeman, 1979.Modalità Erogazione
Lezioni frontali con esercitazioni frontali e di laboratorio. Per il diario delle lezioni si consulti il sito del docente: http://ricerca.mat.uniroma3.it/users/vbonifaci/in440.htmlModalità Valutazione
Esame orale.