Αλγόριθμοι Δικτύων και Πολυπλοκότητα


Κωδικός 446
Εξάμηνο Εαρινό
Ώρες Διδασκαλίας - Ώρες Εργαστηρίου 3 - 0
Διδάσκοντες Αριστείδης Παγουρτζής, Δημήτριος Φωτάκης
Σύνδεσμοι Ιστοσελίδα Μαθήματος

Περιγραφή

Θεωρητική μελέτη υπολογιστικών προβλημάτων που σχετίζονται με δίκτυα. Υπολογιστική πολυπλοκότητα και προσεγγισιμότητα σχετικών γραφοθεωρητικών προβλημάτων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling. Κατανεμημένοι αλγόριθμοι: εκπομπή, εκλογή αρχηγού, Βυζαντινή συμφωνία, διαμοιρασμός μυστικών. Πρωτόκολλα επικοινωνίας σε ασύρματα / μεταβαλλόμενα δίκτυα. Οπτικά δίκτυα: δρομολόγηση και ανάθεση συχνοτήτων, δίκτυα πολλαπλών ινών. Πρωτόκολ¬λα δρομολόγησης. Εγωιστική δρομολόγηση, «κόστος της αναρχίας», ισορροπίες Nash, ηλεκτρονικές δημοπρασίες. Προβλήματα αυτόνομων οντοτήτων: συνάντηση, συντονισμός, εξερεύνηση δικτύων, εντοπισμός βλαβών, αλγόριθμοι πλοήγησης.