Weekly outline

  • General

     

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

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


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

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

    Η εξάσκηση θα γίνει ταυτόχρονα με την εισαγωγή σε βασικές έννοιες και αλγορίθμους κυρτής βελτιστοποίησης (convex optimization). Στο χρόνο που θα απομένει θα μελετήσουμε τεχνικές μείωσης διάστασης (dimension reduction).


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

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


    Διδάσκοντες


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

    Ορέστης Πλευράκης: Δευτέρα 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


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

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

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


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

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

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