20410626 - IN440 - OTTIMIZZAZIONE COMBINATORIA

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.

Canali

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

Canali

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

Canali

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.

BONIFACI VINCENZO

scheda docente | materiale didattico

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.html

Modalità Valutazione

Esame orale.