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

General

Το μάθημα για το ακ. έτος 2022-23 αποτελείται από δύο μέρη που διεξάγονται παράλληλα. Το πρώτο μέρος γίνεται σε συνδιδασκαλία με το μάθημα "Προηγμένα Θέματα Αλγορίθμων". Για τις αντίστοιχες διαλέξεις και ασκήσεις παρακολουθείτε παράλληλα την σχετική ιστοσελίδα και εγγραφείτε σε αυτήν.

Η τρέχουσα σελίδα αφορά το δεύτερο μέρος, που γίνεται για τους μεταπτυχιακούς φοιτητές και για τους ενδιαφερόμενους προπτυχιακούς.

Αντικείμενο και Στόχοι

Το δεύτερο μέρος του μαθήματος εστιάζει στην εκμάθηση και εξάσκηση σε γενικές και αποτελεσματικές στρατηγικές σκέψης, για την επίλυση μαθηματικών/αλγοριθμικών προβλημάτων. Οι στρατηγικές αυτές είναι ιδιαίτερα χρήσιμες για να λύνουμε προβλήματα που απαιτούν καινούργιες ιδέες, και για τα οποία οι γνωστές τεχνικές αποτυγχάνουν (όπως συμβαίνει στην έρευνα). Η εξάσκηση στις στρατηγικές θα γίνει ταυτόχρονα με την εισαγωγή σας σε βασικές έννοιες και αλγορίθμους κυρτής βελτιστοποίησης (convex optimization), καθώς και σε τεχνικές μείωσης διάστασης (dimension reduction). Θα δείτε πώς ευφυείς ιδέες σε αυτές τις περιοχές προκύπτουν φυσιολογικά, εφαρμόζοντας τις στρατηγικές σκέψης που θα μάθουμε.

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

Προαπαιτούμενα

Χρειάζεται να έχετε στερεές βάσεις σε γραμμική άλγεβρα, θεωρία πιθανοτήτων, και ανάλυση πολλών μεταβλητών.

Διδάσκοντες

Δημήτρης Φωτάκης, Καθηγητής (fotakis@cs.ntua.gr)
Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής (lianeas@corelab.ntua.gr)
Ορέστης Πλευράκης, Μεταδιδακτορικός ερευνητής (or.plevrakis@gmail.com)

Ώρες Γραφείου

Ορέστης Πλευράκης: Δευτέρα 15:00-16:30, στην αίθουσα 1.1.29, (Παλαιό) Κτήριο Ηλεκτρολόγων.

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

Αλβέρτος Καλαβάσης, Υ.Δ.
Μαριάννα Σπυράκου, Υ.Δ.

Διαλέξεις

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

Προβλήματα

1 πρόβλημα/εβδομάδα.
Deadline: αρχή της επόμενης διάλεξης.
Μετά το deadline θα αναρτάται η λύση στο site με εξήγηση του πώς φτάνουμε σε αυτή μέσω των στρατηγικών.
Δείτε επίσης αυτό για οδηγίες σχετικές με τα προβλήματα.

(Αναμενόμενα) Θέματα Διαλέξεων

Κυρτά σύνολα, κυρτές συναρτήσεις και βασικές ιδιότητες. Θεώρημα διαχωριστικού υπερεπιπέδου.
Ο αλγόριθμος Gradient Descent και η ανάλυσή του για strongly-convex και smooth συναρτήσεις.
Cutting Plane μέθοδοι, και επίλυση γραμμικών προγραμμάτων σε πολυωνυμικό χρόνο.
Singular Value Decomposition.
Power method για υπολογισμό ιδιοτιμών και ιδιοδιανυσμάτων.
Johnson-Lindenstrauss (JL) μετασχηματισμός.
Spectral methods for the Stochastic Block Model

Βιβλιογραφία και Συμπληρωματικό υλικό

Κυρτή βελτιστοποίηση:

Εξαιρετικές σημειώσεις του Amir Ali Ahmadi [link]
S. Boyd and L. Vandenberghe, Convex Optimization [link]
N. Vishnoi, Algorithms for Convex Optimization [link]
Yin Tat Lee, S. Vempala, Techniques in Optimization and Sampling [link]

Τεχνικές ελάττωσης διάστασης: σημειώσεις αντίστοιχου μαθήματος στο Princeton [link]

Στρατηγικές σκέψης:

Terence Tao, "Ask yourself dumb questions". Κοιτάξτε και εδώ για περαιτέρω συμβουλές του Tao.
Michael Atiyah, "Advice to a young mathematician". Η άποψή του για τη σημασία των παραδειγμάτων έχει ιδιαίτερο ενδιαφέρον.
Ed Burger, Michael Starbird, "The 5 elements of effective thinking" (εφαρμογή τέτοιων στρατηγικών πέρα απο τα μαθηματικά και τη θεωρητική πληροφορική).