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

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

Γενικά

Διδάσκων

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

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

  • Γιάννης Παπαϊωάννου, Υ.Δ. ()

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

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

Διαλέξεις

  • Τρίτη 14:00-18:00 Παλιό Κτήριο Ηλεκτρολόγων ΕΜΠ, αίθουσα 1.1.29.

Περιεχόμενο μαθήματος (ενδεικτικό)

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

  • Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: 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.
  • Προβλήματα αυτόνομων οντοτήτων, εξερεύνηση δικτύων, προβλήματα συνάντησης (rendezvous), εντοπισμός βλαβών σε δίκτυα. Πρωτόκολλα δρομολόγησης, compact routing, geometric routing.
  • Ειδικά θέματα: χρονοδρομολόγηση (scheduling), δρομολόγηση και ανάθεση συχνοτήτων σε οπτικά δίκτυα, αλγόριθμοι πλοήγησης, προγραμματισμός δρομολογίων οχημάτων.
  • Στοιχεία θεωρίας παιγνίων: σημεία ισορροπίας Nash, "κόστος της αναρχίας". Εγωιστική δρομολόγηση σε κλασικά, ασύρματα και οπτικά δίκτυα. Παίγνια συμφόρησης. Σύγκλιση σε ισορροπίες Nash και σχεδίαση μηχανισμών.

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

  • [25/03/2017] Ανακοινώθηκε η πρώτη σειρά ασκήσεων (δείτε παρακάτω). Ημερομηνία παράδοσης: 10/04/2017.
  • [22/05/2017] Ανακοινώθηκε η δεύτερη σειρά ασκήσεων (δείτε παρακάτω). Ημερομηνία παράδοσης: 08/06/2017.

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

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

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

Διάλεξη 7/3:

    1η ενότητα (slides 1-30): Επισκόπηση θεμάτων αλγορίθμων και πολυπλοκότητας, με έμφαση σε γραφοθεωρητικά προβλήματα, υπολογιστική πολυπλοκότητα, ευεπίλυτα και δυσεπίλυτα προβλήματα. Ειδικά θέματα: Laplacian matrix, ελάσσονα γραφήματα, Robertson-Seymour theorem, Unique Games Conjecture, αναγωγές, Restricted Shortest Paths problem.
    Προτάσεις για περαιτέρω μελέτη:

Διάλεξη 14/3:

Διάλεξη 21/3:

    2η ενότητα (slides 13-39): Weighted Vertex Cover. Set Cover, Maximum Coverage. Traveling Salesman Problem (TSP): μη-προσεγγισιμότητα και αλγόριθμος Χριστοφίδη για το Metric TSP. Πρόβλημα s-t Path TSP. Steiner Tree. Αναγωγές διατήρησης προσεγγιστικού λόγου.

Διάλεξη 4/4:

    Εισαγωγή στο Γραμμικό Προγραμματισμό, δυϊκότητα, αλγοριθμικές τεχνικές βασισμένες στο γραμμικό προγραμματισμό, integrality gap: βιβλίο Vazirani, κεφ.12.

Διάλεξη 25/4:

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

Διάλεξη 2/5:

Διάλεξη 9/5:

Διάλεξη 16/5:
    Κατανεμημένοι αλγόριθμοι για προβλήματα δένδρων: διαφάνειες (από μάθημα Roger Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
    Αλγόριθμοι και πρωτόκολλα κατανεμημένων ασύρματων δικτύων: broadcasting and gossiping in radio networks: διαφάνειες.
Διάλεξη 23/5:
    Προβλήματα Συμφωνίας και Εκπομπής (με Βυζαντινό Αντίπαλο): διαφάνειες
Διάλεξη 30/5:
    Υπολογιστικό Μοντέλο για Σύγχρονα Συστήματα, Leader Election και αποδείξεις με αναλλοίωτες: διαφάνειες
    Κάτω φράγμα για την πολυπλοκότητα μηνυμάτων & γύρων του Leader Election: διαφάνειες

Ασκήσεις

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

  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.

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

Links

Πληροφορίες

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