Αλγόριθμοι Δικτύων και Πολυπλοκότητα
Περιγραφή εβδομάδας
- Γενικά
Γενικά
Το μάθημα για το ακ. έτος 2023-24 αποτελείται από δύο μέρη που διεξάγονται παράλληλα. Το πρώτο μέρος γίνεται σε συνδιδασκαλία με το μάθημα"Προηγμένα θέματα αλγορίθμων". Για οτιδήποτε αφορά στο πρώτο μέρος θα πρέπει να παρακολουθείτε την σχετική ιστοσελίδα.
Η τρέχουσα σελίδα αφορά το δεύτερο μέρος, που γίνεται για μεταπτυχιακούς και ενδιαφερόμενους προπτυχιακούς φοιτητές.
Αντικείμενο και Στόχοι
Το δεύτερο μέρος του μαθήματος εστιάζει στην εκμάθηση και εξάσκηση σε κάποιες γενικές τεχνικές για την επίλυση μαθηματικών/αλγοριθμικών προβλημάτων. Οι τεχνικές αυτές είναι ιδιαίτερα χρήσιμες για να λύνουμε προβλήματα που απαιτούν καινούργιες ιδέες, και για τα οποία οι γνωστές μέθοδοι αποτυγχάνουν (όπως συμβαίνει στην έρευνα). Ο στόχος είναι μετά το τέλος του μαθήματος, να εφαρμόζετε τις τεχνικές και σε άλλα μαθήματα, στο προσωπικό σας ανεξάρτητο διάβασμα, και στην έρευνα.
Η εξάσκηση θα γίνει ταυτόχρονα με την εισαγωγή σε βασικές έννοιες και αλγορίθμους κυρτής βελτιστοποίησης (convex optimization). Στο χρόνο που θα απομείνει θα μελετήσουμε τεχνικές μείωσης διάστασης (dimension reduction).
Προαπαιτούμενα
Χρειάζεται να έχετε στερεές βάσεις σε γραμμική άλγεβρα, θεωρία πιθανοτήτων, και ανάλυση πολλών μεταβλητών.
Διδάσκοντες
- Δημήτρης Φωτάκης, Καθηγητής (fotakis@cs.ntua.gr)
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
- Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής (lianeas@corelab.ntua.gr)
- Ορέστης Πλευράκης, Μεταδιδακτορικός Ερευνητής (or.plevrakis@gmail.com)
Ώρες ΓραφείουΟρέστης Πλευράκης: Δευτέρα 19:00-20:00 μέσω Zoom.Meeting link:https://us05web.zoom.us/j/86458796180?pwd=toKDnh6X2j3aFNvNvRc2V8EaWT89ce.1Βοηθοί Διδασκαλίας- Θάνος Τόλιας
- Μαριάννα Σπυράκου
Διαλέξεις
- Κάθε Τετάρτη, ώρα 10:45-14:50, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 004. . Το δεύτερο μέρος διαρκεί 13:50-14:50.
- Έναρξη β' μέρους Tετάρτη 28/2.
Προβλήματα
- 1 πρόβλημα/εβδομάδα.
- Deadline: αρχή της επόμενης διάλεξης.
- Μετά το deadline θα αναρτάται η λύση στο site με εξήγηση του πώς φτάνουμε σε αυτή μέσω των τεχνικών.
- Δείτε επίσης αυτό για οδηγίες σχετικές με τα προβλήματα.
Θέματα Διαλέξεων
- Κυρτά σύνολα, κυρτές συναρτήσεις και βασικές ιδιότητες. Θεώρημα διαχωριστικού υπερεπιπέδου.
- Ο αλγόριθμος Gradient Descent και η ανάλυσή του για strongly-convex και smooth συναρτήσεις.
- Ellipsoid method, και επίλυση γραμμικών προγραμμάτων σε πολυωνυμικό χρόνο.
- Singular Value Decomposition.
- 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]
Tεχνικές αποτελεσματικής σκέψης:
- Terence Tao, "Ask yourself dumb questions". Κοιτάξτε και εδώ για περαιτέρω συμβουλές του Tao.
- Michael Atiyah, "Advice to a young mathematician". Η άποψή του για τη σημασία των παραδειγμάτων έχει ιδιαίτερο ενδιαφέρον.
- Ed Burger, Michael Starbird, "The 5 elements of effective thinking" (εφαρμογή τέτοιων στρατηγικών πέρα απο τα μαθηματικά και τη θεωρητική πληροφορική).
- 1η Διάλεξη (22/3)
- 2η Διάλεξη (29/3)
- 3η Διάλεξη (5/4)
- 4η Διάλεξη (26/4)
- 5η Διάλεξη (3/5)
- 6η Διάλεξη
- 7η Διάλεξη
7η Διάλεξη
Εξαιρετικό βίντεο του 3b1b που εξηγεί γιατί αν θέλουμε να samplάρουμε ένα διάνυσμα ώστε 1) οι συντεταγμένες να είναι ανεξάρτητες τυχαίες μεταβλητές, και 2) το μοναδιαίο να είναι ομοιόμορφα κατανεμημένο πάνω στη σφαίρα, τότε η γκαουσιανή είναι η μοναδική επιλογή! Το σχετικό απόσπασμα είναι 12:48-22:00. To δείχνει για δύο διαστάσεις, αλλά γενικεύεται και για n.
- 8η Διάλεξη
- 9η Διάλεξη