Περιγραφή θέματος

  • Γενικά - Ανακοινώσεις - Forum

    • Ανακοινώσεις Φόρουμ
      Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.

    • Forum Ερωτήσεων/Απαντήσεων Φόρουμ

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

      Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.


  • Διδάσκοντες / Βοηθοί Διδασκαλίας

    • Άρης Παγουρτζής, Καθηγητής ()
    • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ()
    • Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής ()


    Ώρες Γραφείου Διδασκόντων

    • Άρης Παγουρτζής: θα ανακοινωθούν.
    • Δημήτρης Φωτάκης: Τρίτη 14:00 - 15:00, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
    • Θανάσης Λιανέας: θα ανακοινωθούν.


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

    • Άλκης Καλαβάσης
    • Μαριάννα Σπυράκου
    • Μίλτος Στούρας

    • Γενικές Πληροφορίες

      Οι διαλέξεις του μαθήματος γίνονται κάθε Τετάρτη, ώρα 16:15-19:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 009.

      • Περιεχόμενα

        • Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, Vertex Cover, Set Cover, TSP σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, PTAS και FPTAS, Knapsack.
        • Βασικές έννοιες γραμμικού προγραμματισμού, η μέθοδος Simplex, δυϊκότητα στον γραμμικό προγραμματισμό, complementary slackness.
        • Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό, στρογγυλοποίηση, τυχαία στρογγυλοποίηση, η μέθοδος primal-dual.
        • Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία, ελάχιστη τομή, balls and bins και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές sparsification.
        • Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας.
        • Σχεδιασμός μηχανισμών, κοινωνική επιλογή, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, VCG.
        • Αλγόριθμοι μάθησης, no-regret, multiplicative updates, regression, kNN, SVMs.
        • Παραμετρικοί αλγόριθμοι και πολυπλοκότητα. 
        • Κατανεμημένοι αλγόριθμοι, αξιόπιστη εκπομπή, Βυζαντινά πρωτόκολλα, consensus. Αλγόριθμοι κινητών οντοτήτων (mobile agents). 

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

          • 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.
          • K. Steiglitz and C.H. Papadimitriou. Combinatorial Optimization: Algorithms and Complexity. 
          • V. Chvatal. Linear Programming. W.H. Freeman and Co., 1984. 
          • H. Karloff. Linear Programming. Birkhäuser, 1991. 
          • D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 2008. 
          • 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. 
          • M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. 
          • N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. 
          • Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
          • Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
          • M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.

          • Παλαιότερα Έτη


            • Εκπαιδευτικό Υλικό / Προτεινόμενη Μελέτη


              • Διαλέξεις

                • Διάλεξη 2/3/2022. Εισαγωγή - Διαδικαστικά. Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent. Γραμμικός προγραμματισμός, βασικές έννοιες και γεωμετρία. 
                • Διάλεξη 9/3/2022. Γραμμικός προγραμματισμός, κορυφές και βασικές εφικτές λύσεις, η μέθοδος Simplex.
                • Διάλεξη 16/3/2022. Δυϊκότητα στον γραμμικό προγραμματισμό. Εισαγωγή στους πιθανοτικούς αλγόριθμους, πιθανοτικός αλγόριθμος για το πρόβλημα Ελάχιστης Τομής, balls and bins. 
                • Διάλεξη 23/3/2022. Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds).
                  Διαφάνειες (1-28). Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.
                • Διάλεξη 30/3/2022. Το πρόβλημα (Weighted) Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).  Το πρόβλημα Maximum Coverage. 
                  Διαφάνειες (29-41). Προτεινόμενη μελέτη: Vazirani 2.1, και άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή). Επίσης: DPV 5.4 και 9.2.3.
                • Διάλεξη 6/4/2022. Επανάληψη σε Set Cover και Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem, TSP), μη-προσεγγισιμότητα, αλγόριθμος Χριστοφίδη. Προβλήματα TSP(s-t path), Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης. Τα προβλήματα Mutiway Cut και Minimum k-Cut. 
                  Διαφάνειες (42-59). Προτεινόμενη μελέτη: Vazirani, κεφ. 3 και 4.
                • Διάλεξη 13/4/2022. Επανάληψη σε Mutiway Cut και Minimum k-Cut. Δένδρα Gomory-Hu.
                  Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. 
                  Διαφάνειες (25-34). Προτεινόμενη μελέτη: Vazirani κεφ. 8.
                • Διάλεξη 4/5/2022. 
                  • Το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS.
                    Διαφάνειες. Προτεινόμενη μελέτη: Vazirani κεφ. 10.

                  • Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (Ι): Εισαγωγή στη θεωρία αριθμών. Ο έλεγχος πρώτων αριθμών κατά Fermat. 
                    Διαφάνειες (23-25). Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 4.4, 4.5, 4.6. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).

                • Διάλεξη 11/5/2022. Πιθανοτικοί Αλγόριθμοι: η πιθανοτική μέθοδος (απλά παραδείγματα εφαρμογής σε max-cut και maximum independent set), πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problem, (δείτε ακόμη εδώ για secretary problems).  
                • Διάλεξη 25/5/2022. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙI): Αντίστροφος modulo n, επαναλαμβανόμενος τετραγωνισμός, Κινέζικο Θεώρημα Υπολοίπων (CRT). Ο έλεγχος πρώτων αριθμών Miller-Rabin. Απόδειξη ορθότητας βάσει Θ. Lagrange.
                  Διαφάνειες (1-30). Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 4.4, 4.5, 4.6. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).
                • Διάλεξη 1/6/2022: Πιθανοτικοί αλγόριθμοι: Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, deterministic rounding για το πρόβλημα της ανάθεσης εργασιών σε μη συσχετιζόμενες παράλληλες μηχανές (δείτε lecture notes), Max-Cut, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT (δείτε lecture notes).
                • Διάλεξη 8/6/2022: Εισαγωγή σε παραμετρικούς αλγορίθμους και παραμετρική πολυπλοκότητα
                  • Η κλάση FPT.  FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). Διαφάνειες (1-20). Δείτε και Διαφάνειες (συμπληρωματικές, 1-7).
                  • Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος). Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά). Διαφάνειες (1-18).
                  • Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά). Διαφάνειες (1-17 συνοπτικά). 
                  • Προτεινόμενη μελέτη: [M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.], κεφ. 1, 2.1, 2.2.1, 3.1, 7.1-7.4, και 13.1-13.3 (συνοπτικά, ορισμούς μόνο).

                   

                Πρόσθετες διαλέξεις για μεταπτυχιακούς φοιτητές

                • Διάλεξη 4/5/2022: Εισαγωγή στα προβλήματα broadcast και consensus (Byzantine Generals - Byzantine Agreement). Διαφάνειες (1-15).
                • Διάλεξη 11/5/2022: Exponential information gathering tree και exponential algorithm για την επίλυση των broadcast και consensus. Διαφάνειες (1-33). Παραδείγματα.
                • Διάλεξη 8/6/2022: Η μέθοδος Weak-Graded-King Consensus για την επίλυση των broadcast και consensus με πολυωνυμική πολυπλοκότητα. Διαφάνειες (21-29).


                • Γραπτές Ασκήσεις

                  • Θα ανακοινωθούν δύο (2) σειρές γραπτών ασκήσεων. 
                  • Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
                  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.

                  Εκφωνήσεις Γραπτών Ασκήσεων

                • Προγραμματιστικές Ασκήσεις

                  • Θα ανακοινωθεί μία (1) σειρά προγραμματιστικών ασκήσεων, με δύο σκέλη. 
                  • Οι προγραμματιστικές ασκήσεις αφορούν την μοντελοποίηση απλών πρακτικών προβλημάτων βελτιστοποίησης σε (Ακέραιο) Γραμμικό Προγραμματισμό και στη χρήση της πλατφόρμας OR-tools της Google για την επίλυσή τους. 
                  • Οι λύσεις των προγραμματιστικών ασκήσεων υποβάλλονται (σε μορφή notebooks και python scripts) στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
                  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τον κώδικά του. Πανομοιότυποι κώδικες θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές προγραμματιστικών και γραπτών ασκήσεων.