Weekly outline

  • General


    Το μάθημα για το ακ. έτος 2023-24 αποτελείται από δύο μέρη που διεξάγονται παράλληλα. Το πρώτο μέρος γίνεται σε συνδιδασκαλία με το μάθημα

    "Προηγμένα θέματα αλγορίθμων". 

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


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

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

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


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

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


    Διδάσκοντες


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

    Ορέστης Πλευράκης: Δευτέρα 15:00-16:00 μέσω Webex. 

    Meeting link:
    https://meet357.webex.com/meet357/j.php?MTID=m5f9d3cf2962ad95cf787110184d218eb

    Meeting number:
    2741 512 5365

    Meeting password:
    Uue66mvt6yM


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

    • Θάνος Τόλιας
    • Μαριάννα Σπυράκου


    Διαλέξεις

    • Κάθε Τετάρτη, ώρα 10:45-14:45, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 004. Το δεύτερο μέρος διαρκεί 13:40-14:40.
    • Έναρξη β' μέρους 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


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

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

    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]


    Tεχνικές αποτελεσματικής σκέψης:

    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" (εφαρμογή τέτοιων στρατηγικών πέρα απο τα μαθηματικά και τη θεωρητική πληροφορική).