Λυπούμαστε, αυτή η δραστηριότητα είναι προς το παρόν κρυμμένη
Section outline
-
-
Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
-
Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές.
Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.
-
-
- Άρης Παγουρτζής, Καθηγητής ( pagour@cs.ntua.gr )
- Δημήτρης Φωτάκης, Καθηγητής ( fotakis@cs.ntua.gr )
Ώρες Γραφείου Διδασκόντων
- Άρης Παγουρτζής: Τρίτη 14:00-15:00, γραφείο 1.1.6, (Παλαιό) Κτήριο Ηλεκτρολόγων.
- Δημήτρης Φωτάκης: Δευτέρα 14:45 - 15:30, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
Βοηθοί Διδασκαλίας
- Θάνος Τόλιας
- Μαριάννα Σπυράκου
-
Οι διαλέξεις του μαθήματος γίνονται κάθε Τετάρτη, ώρα 09:45-12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 003.
H πρώτη διάλεξη για το εαρινό εξάμηνο του 2025 θα γίνει την Τετάρτη 12 Φεβρουαρίου.
-
- Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, 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 Zurich 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.
- Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
- Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, 2016. Δείτε ακόμη τα lecture notes και τις video-διαλέξεις από παλαιότερο σχετικό μάθημα του Tim Roughgarden.
- Tim Roughgarden. Complexity Theory, Game Theory, and Economics: The Barbados Lectures. Foundations and Trends in Theoretical Computer Science: Vol. 14: No. 3–4, pp 222-407, now publishers inc., 2020. Δείτε ακόμη εδώ.
- Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016.
- Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
- M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.
- R. G. Downey, M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
-
-
- Υλικό για πιθανοτικούς αλγόριθμους:
- Αλγόριθμος του Karger για το πρόβλημα Ελάχιστης Τομής (wikipedia και σημειώσεις).
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995: κεφάλαιο 1, ενότητες 3.1, 3.2, 3.6, 4.1, 5.1, 5.2, 5.5, 6.1, 6.2, 6.3, 10.2.
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005: κεφάλαια 1 και 2, ενότητες 3.1-3.3, 4.1-4.5, 6.1, 6.2, 6.4, 6.7, 7.1.
- Βιβλία / υλικό για την πιθανοτική μέθοδο:
- Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK (6th edition). Springer, 2018.
- Noga Alon Joel and H. Spencer. The Probabilistic Method. Wiley, 2008. Παλαιότερη έκδοση.
- Σχετικά με το secretary problem:
- Thomas S. Ferguson. Who Solved the Secretary Problem? Statist. Sci. 4(3): 282-289, 1989.
- Anupam Gupta, Sahil Singla. Random-Order Models.
- Σχετικά με prophet inequalities:
- Brendan Lucier. An Economic View of Prophet Inequalities.
- Υλικό για προσεγγιστικούς αλγόριθμους:
- V.V. Vazirani. Approximation Algorithms. κεφ. 1, 2.1, 2.2, 3, 4, 8, 10.
- S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. 5.4, 9.2.1, 9.2.3, 9.2.4.
- Survey του Avrim Blum για χρήση online αλγορίθμων για μάθηση και σημειώσεις για τους αλγόριθμους weighted majority και randomized weighted majority (και κάποιες επιπλέον σημειώσεις: 1ο μέρος και 2ο μέρος).
- Σημειώσεις με βασικές έννοιες σχετικές με κυρτά σύνολα και κυρτή βελτιστοποίηση.
- Σημειώσεις για κυρτή βελτιστοποίηση και για τη μέθοδο gradient descent.
- Σημειώσεις και διαφάνειες σχετικές με Γραμμικό Προγραμματισμό (γεωμετρία, βασικά θεωρήματα και ιδιότητες, μέθοδος Simplex, δυϊκότητα, εφαρμογές):
- Σημειώσεις που αναφέρονται στο Λήμμα του Farkas, στη γεωμετρική του ερμηνεία, και στις εφαρμογές του.
- Υλικό για παραμετρικούς αλγορίθμους και πολυπλοκότητα:
- 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 (συνοπτικά, ορισμούς μόνο).
- Υλικό για προσεγγιστικούς αλγορίθμους:
- V.V. Vazirani. Approximation Algorithms. κεφ. 1, 2.1, 2.2, 3, 4, 8, 10.
- S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. 5.4, 9.2.1, 9.2.3, 9.2.4.
- Υλικό για προσεγγιστικούς αλγόριθμους βασισμένους σε γραμμικό προγραμματισμό:
- D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 1.3-1.7, 5.1-5.2, 5.4-5.5, 6.1-6.3 και 11.1.
- Σχετικά με approximation hardness:
- Σημειώσεις του L. Trevisan για τη χρήση του θεωρήματος PCP.
- Υλικό για παραμετρικούς αλγόριθμους: [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 (συνοπτικά, ορισμούς μόνο).
- Υλικό για πιθανοτικούς αλγόριθμους:
-
- Διάλεξη 12/2/2025. Εισαγωγή - Διαδικαστικά. Εισαγωγή στους πιθανοτικούς αλγόριθμους, πιθανοτικός αλγόριθμος για το πρόβλημα Ελάχιστης Τομής (δείτε ακόμη wikipedia και σημειώσεις για τον αλγόριθμο Karger), πιθανοτικός αλγόριθμος για το πρόβλημα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT).
- Διάλεξη 19/2/2025. Πιθανοτικός αλγόριθμος για το πρόβλημα 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problems (δείτε ακόμη εδώ για secretary problems). Prophet inequalities. Συγκέντρωση γύρω από τη μέση τιμή, Chernoff-Hoeffding bounds (δείτε lecture notes), εφαρμογές, τυχαία δειγματοληψία.
- Διάλεξη 5/3/2025. Προσεγγιστικοί αλγόριθμοι. Βασικές Έννοιες. Ιεραρχία κλάσεων προσεγγισιμότητας. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι.
- Διάλεξη 12/3/2025. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα (Weighted) Set Cover. Ανάλυση λόγου προσέγγισης του άπληστου αλγόριθμου (Greedy). Tight examples. Το πρόβλημα Maximum Coverage: (1-1/e)-προσεγγιστικός αλγόριθμος.
- Διάλεξη 19/3/2025. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα TSP, μη προσεγγισιμότητα. Προσεγγιστικοί αλγόριθμοι για το Metric TSP. Το πρόβλημα Steiner Tree. Αναγωγές διατήρησης προσεγγισιμότητας. 2-προσεγγιστικός αλγόριθμος για Steiner Tree.
- Διάλεξη 26/3/2025. Προσεγγιστικοί αλγόριθμοι: προβλήματα τομών, Multiway Cut, Minimum k-Cut. Δένδρα Gomory-Hu. Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. Διαφάνειες (25-34).
- Διάλεξη 2/4/2025. Ανισότητα προφήτη (επανάληψη και απόδειξη λόγου προσέγγισης). Online learning, learning from experts advice: αλγόριθμοι weighted majority και randomized weighted majority.
- Διάλεξη 11/4/2025. PAC learning, ERM, μάθηση με ομοιόμορφη και ανομοιόμορφη σύγκλιση, VC dimension, θεμελιώδες θεώρημα μηχανικής μάθησης. Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent. Εισαγωγή στο γραμμικό προγραμματισμό: γεωμετρία, κορυφές και βασικές εφικτές λύσεις.
- Διάλεξη 30/4/2025. Εισαγωγή στον γραμμικό προγραμματισμό: γεωμετρία, κορυφές, βασικό θεώρημα γραμμικού προγραμματισμού, βασικές εφικτές λύσεις. Η μέθοδος simplex. Δυϊκότητα στο γραμμικό προγραμματισμό.
- Διάλεξη 5/5/2025. Δυϊκότητα στο γραμμικό προγραμματισμό. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον γραμμικό προγραμματισμό, η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε γραμμικό προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations,τυχαία στρογγυλοποίηση (randomized rounding) για το πρόβλημα Set Cover, randomized (και deterministic) rounding για το πρόβλημα VLSI routing. Δείτε ακόμη την αντίστοιχη βιντεοσκοπημένη διάλεξη (από το 38ο λεπτό περίπου μέχρι το τέλος, κωδικός: Adv-Algo!2021+ ) για προσεγγιστικούς αλγόριθμους βασισμένους σε γραμμικό προγραμματισμό.
- Διάλεξη 7/5/2025. Εισαγωγή σε παραμετρικούς αλγορίθμους και παραμετρική πολυπλοκότητα:
- Η κλάση FPT. FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization). Διαφάνειες (1-8) και διαφάνειες συμπληρωματικές (1-7).
- Παραμετρικός αλγόριθμος για Independent Set με παράμετρο το treewidth (δενδροπλάτος). Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά). Διαφάνειες (1-18).
- Διάλεξη 12/5/2025. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: χρήση τυχαιότητας για τα προβλήματα Max-Cut, Max-k-Cut, Max-k-SAT, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα Max-Cut (δείτε και lecture notes). Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Η δημοπρασία 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. (σημειώσεις το μάθημα του Tim Roughgarden: σχεδιασμός μηχανισμών και Myerson's Lemma).
-
- Θα ανακοινωθούν δύο (2) σειρές γραπτών ασκήσεων.
- Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
- Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
Εκφωνήσεις Γραπτών Ασκήσεων
- 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 4/5/2025.
- 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής (εκτιμώμενη): 30/5/2025.