Università Roma Tre

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.

Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2013.