Section outline

  • Ακαδ. έτος

    • 2017-18

    Διδάσκων

    Βοηθοί διδασκαλίας
    Έναρξη μαθήματος
    • Το πρώτο μάθημα θα γίνει στις 20/2/2018.
    Διαλέξεις
    • Παρασκευή 15:00-19:00 Παλιό Κτήριο Ηλεκτρολόγων ΕΜΠ, αίθουσα 1.1.31. (Προσοχή: αλλαγή ημέρας και ώρας!)
    Περιεχόμενο μαθήματος (ενδεικτικό)

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

    • Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: 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 και σχεδίαση μηχανισμών.
    Βιβλιογραφία
    • V.V. Vazirani. Approximation Algorithms. Springer Verlag, Heidelberg, 2001.
    • D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge UP, 2010.
    • S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. MacGraw-Hill, 2006.
    • H. Karloff. Linear Programming. Birkhäuser, 1991. 
    • R. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications, 1993. 
    • N. Lynch, Distributed Algorithms. Morgan Kaufmann Publishers,1996. 
    • Roger Wattenhofer. Principles of Distributed Computing. ETH Zuerich course notes, 2011.
    • R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. 
    • Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
    • Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.