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

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

Γενικά

Διδάσκων

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

Βοηθός διδασκαλίας

  • Χριστίνα Καρουσάτου, Υ.Δ. ()

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

Το πρώτο μάθημα θα γίνει στις 29/4/2014.

Διαλέξεις

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

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

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

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

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

    [12/07/14] Θα πρέπει να επιλέξετε ένα θέμα παρουσίασης το αργότερο μέχρι τις 15/7 σύμφωνα με τις οδηγίες που σας έχουν σταλεί με email. Οι παρουσιάσεις θα γίνουν την εβδομάδα 21/7-25/7.

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

Ύλη και διαφάνειες διαλέξεων

Η σελίδα θα ενημερώνεται τακτικά. Μπορείτε να ανατρέξετε και στη σελίδα του προηγούμενου έτους.

Διάλεξη 29/4:

    Συζητήθηκε η 1η ενότητα (slides 1-60): Επισκόπηση θεμάτων αλγορίθμων και πολυπλοκότητας, με έμφαση σε γραφοθεωρητικά προβλήματα, υπολογιστική πολυπλοκότητα, ευεπίλυτα και δυσεπίλυτα προβλήματα.

Διάλεξη 6/5:

    Σύντομη επανάληψη της 1ης διάλεξης, με έμφαση σε: Laplacian matrix, Robertson-Seymour theorem, matroids και άπληστος αλγόριθμος.
    Συζητήθηκε επίσης η συνέχεια της 1ης ενότητας (slides 60-66): Προβλήματα Max Flow - Min Cut, Matching, Stable Marriage, Edge Coloring in general and bipartite multigraphs.
    Συζητήθηκαν τέλος οι διαφάνειες 1-17 από την 2η ενότητα: Προσεγγιστικοί αλγόριθμοι: πρόβλημα Vertex Cover (unweighted & weighted versions).
    • Πρόταση για περαιτέρω μελέτη:
      Chung, Fan (1992, revised 1997), Spectral Graph Theory. American Mathematical Society. ISBN 0821803158.

Διαλέξεις 13/5 και 20/5:

    Συζητήθηκαν οι διαφάνειες 18-45 από την 2η ενότητα: Προσεγγισιμότητα των προβλημάτων Set Cover, Maximum Coverage, Traveling Salesman Problem (αλγόριθμος Χριστοφίδη), Steiner Tree, Multiway Cut, Minimum k-Cut.

    Συζητήθηκε επίσης το πρόβλημα k-Center, δείτε τις σχετικές διαφάνειες.

Διάλεξη 27/5:

    Στο 1ο μέρος ολοκληρώσαμε η συζήτηση για το πρόβλημα k-Center, με τον αλγόριθμο για την εκδοχή με βάρη και τον εναλλακτικό προσεγγιστικό αλγόριθμο (Williamson-Shmoys, κεφ.2.2).
    Στο 2ο μέρος έγινε μια εισαγωγή σε αλγόριθμους δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα. Δείτε τις σχετικές διαφάνειες (1-20).

Διάλεξη 3/6:

Διάλεξη 10/6:

    Εισαγωγή στο Γραμμικό Προγραμματισμό (Vazirani, κεφ.12). Bασικές τεχνικές Γραμμικού Προγραμματισμού για σχεδιασμό αλγορίθμων (Rounding, Dual Fitting, Primal-Dual Schema): διαφάνειες (Vazirani, κεφ. 13,14,15).

Διάλεξη 17/6:

    Δεν πραγματοποιήθηκε.

Διάλεξη 24/6:

    Ολοκληρώθηκε η συζήτηση σχετικά με αλγόριθμους δρομολόγησης και ανάθεσης συχνοτήτων σε οπτικά δίκτυα. Δείτε τις σχετικές διαφάνειες (21-24).

    Αλγόριθμοι / πρωτόκολλα κατανεμημένων δικτύων: Εισαγωγή. Σχετικές διαφάνειες (από μάθημα Μ. Μαυρονικόλα, Παν. Κύπρου).
    Αλγόριθμοι / πρωτόκολλα κατανεμημένων δικτύων: Εκλογή αρχηγού σε δακτυλίους. Σχετικές διαφάνειες (από μάθημα Μ. Μαυρονικόλα, Παν. Κύπρου).

Διάλεξη 1/7:

Διάλεξη 8/7:

    Το πρόβλημα της Ασφαλούς Εκπομπής (Secure Broadcast) σε κατανεμημένα δίκτυα, υπό την παρουσία κακόβουλων αντιπάλων (παρουσίαση: Δ. Σακαβάλας, Α. Παγουρτζής, Γ. Παναγιωτάκος). Σχετικές διαφάνειες.

Διαλέξεις 15/7 και 16/7:

    Το μάθημα θα γίνει από κοινού με το μάθημα "Θεωρία Υπολογισμού" της ΣΗΜΜΥ (παρουσιάσεις σπουδαστών). Πρόγραμμα παρουσιάσεων:

    Τρίτη 15/07/2014 (αίθ. 1.1.29):

    10:00 Καλιμάτζαλης-Λιανάς Βαγγέλης: Some NP-Reductions
    11:00 Κοντουρά Βασιλική: On-line Algorithms
    12:00 Χατζηαφράτης Βαγγέλης: On-line Scheduling
    13:00 Βλάχος Αριστοτέλης: Yao's Proof Method
    14:00 Αρσένης Μάκης: Randomized Parallel and Distributed Algorithms
    15:00 Βλατάκης Μανώλης: Markovian Applications to Pagerank
    16:00 Ποδηματά Χαρά: Congestion Games
    17:00 Κουτσός Βλάσης: Elliptic Curves

    Τετάρτη 16/07/2014 (αίθ. 1.1.31):

    11:00 Κουλούρης Νίκος: Fuzzy Join
    12:00 Μονάχου Φαίδρα-Γεωργία: Shop Scheduling
    13:00 Καφφές Κωνσταντίνος: Luby's Algorithm
    14:00 Παπαδιγενόπουλος Ορέστης: Randomized Graph Algorithms
    15:00 Νομικού Σοφία: Comparing Matching Algorithms
    16:00 Λυμούρη Χριστιάνα: Approximation Algorithms for k-center and k-means

Παρουσιάσεις μαθήματος


    Τρίτη 22/07/2014 (αίθ. 1.1.29):

    Αγγελόπουλος Αλέξανδρος: Coloring Circular Arc Graphs. Διαφάνειες

    Γροντάς Παναγιώτης: Secure Two-Party Computation. Διαφάνειες

    Κατσίνης Γιώργος: Scheduling on Unrelated Parallel Machines. Διαφάνειες

    Κωνσταντινίδης Ορέστης: Semidefinite Programming. Διαφάνειες

    Μάντης Ανδρέας: On Nash Equilibria for a Network Creation Game. Διαφάνειες

    Μπακάλη Ελένη: Spectral Sparsification on Network Algorithms. Διαφάνειες

    Στούκα Κατερίνα-Παναγιώτα & Λάμπρου Νίκος: Μulticut and Ιnteger Μulticommodity Flow in Trees & Multicommodity demand flow in a tree and packing integer programs. Διαφάνειες

    Τελώνη Πέλη: Large Scale Generalized Matching. Διαφάνειες

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

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

Ασκήσεις

Links

Πληροφορίες

  • Άρης Παγουρτζής, Γραφείο 1.1.4, Σχολή ΗΜΜΥ Ε.Μ.Π. Τηλ: 210 7721640