Algoritmi II

Laurea magistrale

Prof. Giuseppe Persiano

Finalità
Algoritmi II è un corso della Laurea Magistrale che intende approfondire lo studio degli algoritmi iniziato nei corsi di Algoritmi e di Strutture Dati della laurea triennale. Il concetto di algoritmo risulta essere centrale nell'Informatica, nello specifico, e nelle Scienze in generale (vedi questo saggio di Chazelle) ed in questo corso cercheremo di fornire evidenze a supporto sia della tesi specifica che della tesi generale. Cercheremo inoltre di studiare algoritmi in situazioni reali e di eliminare le assunzioni irrealistiche (il problema computazionale può essere risolto in maniera ottima ed efficientemente, l'input è disponibile, la computazione è effettuata da un solo computer,....) che ci hanno facilitato nel primo corso.

Orario delle lezioni
Lunedì 9-11 aula P6 16-18 aula P4
Martedì 16-18 aula P6 11-13 aula F1
Venerdì 14-18 aula Turing
Il corso inizia il 3 ottobre, 2011.

Ricevimento studenti
Il prof. G. Persiano riceve gli studenti presso il proprio studio (Stanza 3, Piano 4, Stecca 7, Campus di Fisciano) o presso il laboratorio Sistemi Globali (Stanza 1, Piano 2, Stecca 7, Campus di Fisciano) il lunedì prima della lezione e il martedì dopo la lezione. Alternativamente, si può richiedere appuntamento (e-mail consigliata).

Impegno richiesto
Il corso ha 9(=7+2) CFU e quindi 80(=56+24) ore di lezione frontale e di laboratorio. Ogni ora di lezione frontale richiede due ore di studio individuale ed ogni ora di laboratorio un'ora di studio individuale.

Lezioni Frontali

1. Perché Algoritmi e perché II

2. Extending the limits of tractability:
   
   • Vertex Cover [KT 10.1];
   • MIS su alberi [KT 10.2]
   • Path coloring su ring [KT 10.3]
   • Esercizi consigliati:
     • Hitting Set [KT Esercizio 10.1]
     • 3-SAT [KT Esercizio 10.2]
     • Hamiltonian Path [KT Esercizio 10.3]
     • Partial Assignment for 3-SAT [KT Esercizio svolto]
     • Dominating Set [KT Esercizio 10.5.a]
     • 3SAT [KT Esercizio 10.8]

3. Approximation algorithms:
   • Load Balancing [KT 11.1]
   • Center Selection [KT 11.2]
   • Set Cover [KT 11.3]
   • Riduzioni e Approssimazione [KT 11.4]
   • Vertex Cover via Pricing [KT 11.4]
   • Vertex Cover via Linear Programming [KT 11.6]
   • Disjoint Paths [KT 11.5]
   • Knapsack [KT 11.8]
   • Esercizi consigliati:
     • Load balancing [KT Esercizi 11.5,6,8]
     • Subset Sum [KT Esercizio 11.3]
     • Hitting Set [KT Esercizio 11.4]
     • Interval Coloring [KT Esercizio Svolto Cap. 11]
     • Bin Packing [KT Esercizio 11.1]
     • Ads for a web site [KT Esercizio 11.7]
     • Three Dimensional Matching [KT Esercizio 11.9]
     • Independent Set on a Grid [KT Esercizio 11.10]
     • Knapsack [KT Esercizio 11.11]

4. Randomized algorithms:
   • Contention resolution [KT 13.1]
   • Minimum Cut [KT 13.2]
   • Expected value and MAX 3-SAT [KT 13.3-13.4]
   • Verifying equations [MR 7.1-7.2]
   • Esercizi consigliati:
     • Dominating set [KT Esercizio Svolto Cap. 13]
     • Systems of equations [KT Esercizio Svolto Cap. 13]
     • 3Coloring [KT Esercizio 13.1]
     • Shapley values [KT Esercizio 13.5]
     • SAT [KT Esercizio 13.7] <

5. Local search algorithms:
   • Metropolis and simulated annealing [KT 12.1-12.2]
   • Hopfield Neural Networks [KT 12.3]
   • Maximum Cut via Local Search [KT 12.4]
   • Esercizi consigliati:
     • Center Selection Problem [KT Esercizio Svolto Cap. 12]
     • Maximum cut on bipartite graphs [KT Esercizio 12.1]
     • Matching in Bipartite Graphs [KT Esercizio 12.2]
     • Load balancing [KT Esrercizio 12.4]

6. Streaming algorithms
   Introduction (vedi questo tutorial)