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

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

Γενικά

Διδάσκοντες

  • Άρης Παγουρτζής, Επίκ. Καθηγητής ()
  • Στάθης Ζάχος, Καθηγητής ()

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

Το πρώτο μάθημα θα γίνει στις 8/3/2011, στην αίθουσα 1.1.29 (παλιό κτ. Ηλεκτρολόγων)

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

Διαλέξεις

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

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

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

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

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

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

Πληροφορίες

  • Άρης Παγουρτζής, Γραφείο 1.1.4, Σχολή ΗΜΜΥ Ε.Μ.Π. Τηλ: 210 7721640, e-mail: pagour [AT] cs [DOT] ntua [DOT] gr

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

  • [13/04/11] Θα πρέπει να επιλέξετε θέμα παρουσίασης το αργότερο μέχρι τις 2/5/2011. Εκτός από τα προτεινόμενα paper (παρακάτω) μπορείτε να παρουσιάσετε κάποιο κεφάλαιο από τα 11, 17, 18, 19, 20, 21, 22, 23, 24, 25, και 27 του βιβλίου του Vazirani.
  • [12/04/11] Ανακοινώθηκε η πρώτη σειρά ασκήσεων εδώ. Ημερομηνία παράδοσης: 4/5/2011.

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

Διαφάνειες και ασκήσεις

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

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

  • Πληκτρολογήστε το URL http: //www.corelab.ntua.../courses/netalg/papers2read

Links

Τελευταία ανανέωση: 13/04/2011