Network Algorithms and Complexity

Type
Elective
Course Description

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

Name Year Semester Taught by
Network Algorithms and Complexity 2021-2022 Spring Aristeidis Pagourtzis, Dimitris Fotakis
Network Algorithms and Complexity 2020-2021 Spring Aristeidis Pagourtzis, Dimitris Fotakis
Network Algorithms and Complexity 2019-2020 Spring Aristeidis Pagourtzis, Dimitris Fotakis
Network Algorithms and Complexity 2018-2019 Spring Aristeidis Pagourtzis
Network Algorithms and Complexity 2017-2018 Spring Aristeidis Pagourtzis
Network Algorithms and Complexity 2016-2017 Spring Aristeidis Pagourtzis