Αλγόριθμοι Δικτύων και Πολυπλοκότητα
| Κωδικός | 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, ηλεκτρονικές δημοπρασίες. Προβλήματα αυτόνομων οντοτήτων: συνάντηση, συντονισμός, εξερεύνηση δικτύων, εντοπισμός βλαβών, αλγόριθμοι πλοήγησης.