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

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

Γενικά

Διδάσκοντες

  • Άρης Παγουρτζής, Επίκ. Καθηγητής ()
  • Ιωάννης Αβραμόπουλος, επισκέπτης ερευνητής ()

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

  • Γιώργος Ζηρδέλης, Υ.Δ. ()

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

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

Διαλέξεις

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

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

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

  • Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Maximum Edge-Disjoint Paths, 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 και σχεδίαση μηχανισμών.

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

  • [16/05/13] Θα πρέπει να επιλέξετε ένα θέμα παρουσίασης (δείτε παρακάτω) το αργότερο μέχρι την 1/6/2013.

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

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

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

    Διάλεξη 5/3:

    Διάλεξη 12/3:

      Συζητήθηκε η 1η ενότητα (slides 43-66): Eυεπίλυτα γραφοθεωρητικά προβλήματα: MST, Max Flow - Min Cut, Matching, Bipartite Edge Coloring.

    Διάλεξη 19/3:

      Συζητήθηκαν οι διαφάνειες 1-27 από την 2η ενότητα: Προσεγγιστικοί αλγόριθμοι: Vertex Cover, Set Cover, Maximum Coverage.

    Διάλεξη 26/3:

      Συζητήθηκαν οι διαφάνειες 28-45 από την 2η ενότητα: Προσεγγιστικοί αλγόριθμοι: TSP, Steiner Tree, Multiway Cut, Min k-Cut.
    • Πρόταση για περαιτέρω μελέτη:
      H.-C. An, R. Kleinberg, and D. B. Shmoys. Improving Christofides' Algorithm for the s-t Path TSP In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012).

    Διάλεξη 2/4:

    Διάλεξη 9/4:

      2ος προσεγγιστικός αλγόριθμος για k-center (Williamson-Shmoys, κεφ.2.2). FPTAS για το πρόβλημα Knapsack και strong NP-hardness (Vazirani, κεφ. 8). Πρόβλημα Minimum Makespan Scheduling (Vazirani, κεφ. 10).

    Διάλεξη 16/4:

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

    Διάλεξη 23/4:

      Αλγόριθμοι δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα πολλαπλών ινών. Σχετικές διαφάνειες (1-27). Αλγόριθμοι / πρωτόκολλα κατανεμημένων δικτύων. Εκλογή αρχηγού σε δακτυλίους και γενικούς γράφους. Σχετικές διαφάνειες (Washington University in St Louis).

    Διάλεξη 14/5:

    Διάλεξη 21/5:

    Διαλέξεις 28/5, 4/6, και 11/6:

    18/6 και 28/6:

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

    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.

    Ασκήσεις

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

    • Πληκτρολογήστε το URL http: //www.corelab.ntua.../courses/netalg/papers2read/ και επιλέξτε το folder '2013' (κατά προτίμηση, αλλά δείτε και τα προτεινόμενα προηγουμένων ετών). Μπορείτε να παρουσιάσετε και κάποιο άλλο paper που θεωρείτε αξιόλογο (κατόπιν συνεννόησης).

    Links

    Πληροφορίες

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

    Τελευταία ανανέωση: 15/07/2013