Αλγόριθμοι Δικτύων και Πολυπλοκότητα (ΣΗΜΜΥ, ΣΕΜΦΕ, ΜΠΛΑ)
εαρινό εξάμηνο 2014-15

● Γενικά ● Ανακοινώσεις ● Υλικό ● Παρουσιάσεις εργασιών ●

Γενικά

Διδάσκων

  • Άρης Παγουρτζής, Αν. Καθηγητής ()

Βοηθός διδασκαλίας

  • Αγγελική Χαλκή, Υ.Δ. ()

Έναρξη μαθήματος

Το πρώτο μάθημα θα γίνει στις 10/3/2015.

Διαλέξεις

  • Τρίτη 12:00-16:00 Παλιό Κτήριο Ηλεκτρολόγων ΕΜΠ, αίθουσα 1.1.29.
  • Το 2ο μισό κάθε μαθήματος γίνεται σε συνδιδασκαλία με το μάθημα 8ου εξ της ΣΗΜΜΥ "Θεωρία Υπολογισμού".

Περιεχόμενο μαθήματος

Το αντικείμενο του μαθήματος είναι η μελέτη αλγοριθμικών μεθόδων και η ανάλυση πολυπλοκότητας για υπολογιστικά προβλήματα και θεμελιώδεις διαδικασίες που σχετίζονται με δίκτυα, κυρίως υπολογιστών και επικοινωνιών. Ορισμένα από τα θέματα που θα καλυφθούν:

  • Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling.
  • Κατανεμημένα πρωτόκολλα: εκλογή αρχηγού, broadcasting, gossiping, byzantine agreement, secret sharing. Ασύρματα ad hoc δίκτυα. Συγχρονισμένοι και ασύγχρονοι αλγόριθμοι. Fault tolerance. Κίνηση αυτόνομων οντοτήτων, εντοπισμός βλαβών, συναντήσεις, εξερεύνηση δικτύων.
  • Ειδικά θέματα: χρονοδρομολόγηση (scheduling), δρομολόγηση και ανάθεση συχνοτήτων σε οπτικά δίκτυα, αλγόριθμοι πλοήγησης, προγραμματισμός δρομολογίων οχημάτων. Πρωτόκολλα δρομολόγησης, compact routing, geometric routing. Ο αλγόριθμος PageRank.
  • Στοιχεία θεωρίας παιγνίων: σημεία ισορροπίας Nash, "κόστος της αναρχίας". Εγωιστική δρομολόγηση σε κλασικά, ασύρματα και οπτικά δίκτυα. Σύγκλιση σε ισορροπίες Nash και σχεδίαση μηχανισμών.

Ανακοινώσεις

  • [30/05/2015] Θα πρέπει να επιλέξετε ένα θέμα παρουσίασης το αργότερο μέχρι τις 3/6 σύμφωνα με τις οδηγίες που θα βρείτε εδώ. Οι παρουσιάσεις θα γίνουν την εβδομάδα 15-19/6.
  • [30/05/2015] Ανακοινώθηκε η δεύτερη σειρά ασκήσεων (δείτε παρακάτω). Ημερομηνία παράδοσης: 15/06/2015.
  • [07/04/2015] Ανακοινώθηκε η πρώτη σειρά ασκήσεων (δείτε παρακάτω). Ημερομηνία παράδοσης: 27/04/2015.

Υλικό μαθήματος

Ύλη και διαφάνειες διαλέξεων

Η σελίδα θα ενημερώνεται τακτικά. Για ενδεικτική ύλη και διαφάνειες μπορείτε να ανατρέξετε στη σελίδα του προηγούμενου έτους.

Διάλεξη 10/3:

    1η ενότητα (slides 1-43): Επισκόπηση θεμάτων αλγορίθμων και πολυπλοκότητας, με έμφαση σε γραφοθεωρητικά προβλήματα, υπολογιστική πολυπλοκότητα, ευεπίλυτα και δυσεπίλυτα προβλήματα. Πρόσθετα θέματα: Laplacian matrix, Robertson-Seymour theorem, αναγωγές.
    • Πρόταση για περαιτέρω μελέτη:
      Chung, Fan (1992, revised 1997), Spectral Graph Theory. American Mathematical Society. ISBN 0821803158.

Διάλεξη 17/3:

Διάλεξη 24/3:

    Στο 1ο μέρος έγινε μια εισαγωγή σε αλγόριθμους δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα. Δείτε τις σχετικές διαφάνειες (1-15).

    Στο 2ο μέρος συζητήθηκαν τα προβλήματα stable matching/marriage (αλγόριθμος Gale-Shapley), και edge coloring in general and bipartite multigraphs (αλγόριθμος Konig). Σχετικές διαφάνειες: 1η ενότητα (slides 66-68).

Διάλεξη 31/3:

    Στο 1ο μέρος ολοκληρώσαμε την εισαγωγή σε αλγόριθμους δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα. Δείτε τις σχετικές διαφάνειες (16-24).

    Στο 2ο μέρος συζητήσαμε τις διαφάνειες 1-17 από την 2η ενότητα: Προσεγγιστικοί αλγόριθμοι: πρόβλημα Vertex Cover (unweighted & weighted versions).
    • Πρόταση για περαιτέρω μελέτη:
      D. S. Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics, 6:243–254, 1983. (βρείτε το πληκτρολογώντας το URL http://www.corelab.ntua.../courses/netalg/book)

Διάλεξη 21/4:

    Στο 1ο μέρος συζητήσαμε σχετικά με αλγόριθμους δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα πολλαπλών ινών. Σχετικές διαφάνειες (1-27) .

    Στο 2ο μέρος συζητήσαμε τις διαφάνειες 18-27 από την 2η ενότητα: Προσεγγισιμότητα των προβλημάτων Set Cover, Maximum Coverage.

Διάλεξη 28/4:

    Στο 1ο μέρος συζητήσαμε το πρόβλημα μέγιστης ανάθεσης και χρωματισμού μονοπατιών. Σχετικές διαφάνειες (28-46) .
    • Πρόταση για περαιτέρω μελέτη:
      Ioannis Caragiannis, Wavelength Management in WDM Rings to Maximize the Number of Connections, SIAM Journal on Discrete Mathematics, 2009, Vol. 23, No. 2 : pp. 959-978 (doi: 10.1137/06067660X).

    Στο 2ο μέρος παρουσιάστηκε το πρόβλημα της μεγιστοποίησης επιρροής σε κοινωνικά δίκτυα (Influence Maximization in Social Networks) Σχετικές διαφάνειες (Παρουσίαση: Β. Χατζηαφράτης).
    Δείτε και το σχετικό paper.

Διάλεξη 5/5:

Διάλεξη 12/5:

    Συζητήθηκε το πρόβλημα Blue-Red Matching. Προσεγγιστικός και πιθανοτικός (RNC) αλγόριθμος. Η σχέση με το πρόβλημα Exact Matching. Εφαρμογή σε προβλήματα χρωματισμού μονοπατιών. Σχετικές διαφάνειες (1-37).
    • Πρόταση για περαιτέρω μελέτη:
      Fabrizio Grandoni, Rico Zenklusen: Approximation Schemes for Multi-Budgeted Independence Systems. ESA (1) 2010: 536-548 (link)
      K. Mulmuley, V. Vazirani, U. Vazirani: Matching is as Easy as Matrix Inversion

Διάλεξη 19/5:

    Δεν πραγματοποιήθηκε.

Διάλεξη 26/5:

    Συζητήθηκαν τα προβλήματα Metric TSP (s,t)-path, Steiner Tree/ Metric Steiner Tree και Multiway Cut/ Minimum k-Cut και οι αντίστοιχοι προσεγγιστικοί αλγόριθμοι.
    Σχετικές διαφάνειες: 2η ενότητα (34-45).

Διάλεξη 2/6:

    Εισαγωγή στο Γραμμικό Προγραμματισμό (Vazirani, κεφ.12). Bασικές τεχνικές Γραμμικού Προγραμματισμού για σχεδιασμό αλγορίθμων (Dual Fitting): διαφάνειες (Vazirani, κεφ. 13).

Διάλεξη 9/6:

    Bασικές τεχνικές Γραμμικού Προγραμματισμού για σχεδιασμό αλγορίθμων (Rounding, Primal-Dual Schema): διαφάνειες (Vazirani, κεφ. 14,15).

Διαλέξεις 12/6, 16/6 και 19/6:

    Παρουσιάσεις από κοινού με το μάθημα "Θεωρία Υπολογισμού" της ΣΗΜΜΥ. Πρόγραμμα παρουσιάσεων:

    Παρασκευή 12/06/2015:

    Παναγιώτης Δημητρέλλος: Bin Packing
    Λεωνίδας Τσεπενέκας: Scheduling in switching networks
    Αικατερίνη Κούκιου: Παραλληλοποίηση του αλγορίθμου του Prim

    Τρίτη 16/06/2015:

    Αντώνιος Αγγελάκης: Unique games conjecture
    Ορέστης Πλευράκης: Πιθανοτικός αλγόριθμος για εύρεση κύκλου Hamilton
    Σπύρος Τσουκαλάς: Online algorithms

    Παρασκευή 19/6/2015

    Ανδρέας Ματζόρι: Αλγόριθμος μέγιστης ροής preflow-push
    Έλενα Παρταλίδου: Reliable Broadcast in Unknown Fixed-Identity Networks
    Ορέστης Παπαδιγενόπουλος: Scheduling MapReduce Tasks on Unrelated Processors
    Αγγελική Χαλκή: Approximation Algorithms for Max Cut

Παρουσιάσεις μαθήματος

Βιβλιογραφία

  1. Vijay V. Vazirani. Approximation Algorithms. Springer, 2001. (Preliminary draft: πληκτρολογήστε το URL http://www.corelab.ntua.../courses/netalg/book)
  2. David P. Williamson, David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010. (online draft version)
  3. Roger Wattenhofer. Principles of Distributed Computing. ETH Zuerich course notes, 2011.
  4. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996.
  5. Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.
  6. Robert E. Tarjan. Data Structures and Network Algorithms. SIAM, 1983.
  7. Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network flows. Theory, Algorithms, and Applications. Prentice-Hall, 1993.
  8. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms, 2nd edition. The MIT Press, 2001.

Ασκήσεις

  • 1η σειρά ασκήσεων (προθεσμία: 27/4/2015)
    Προσοχή: έγιναν διορθώσεις στην εκφώνηση των ασκήσεων 4 και 5.

Προτεινόμενα θέματα για παρουσίαση

Θα πρέπει να επιλέξετε ένα θέμα παρουσίασης το αργότερο μέχρι τις 3/6 σύμφωνα με τις οδηγίες που θα βρείτε εδώ. Οι παρουσιάσεις θα γίνουν την εβδομάδα 15-19/6.

Πρόσθετο υλικό (από παρουσιάσεις φοιτητών προηγουμένων ετών)

Links

Πληροφορίες

  • Άρης Παγουρτζής, Γραφείο 1.1.4, Σχολή ΗΜΜΥ Ε.Μ.Π. Τηλ: 210 7721640