Section outline

  • Διδάσκοντες

    Ώρες και Μέρος

    Κάθε Τρίτη 17:00 με 20:00, αίθουσα 1.1.29 Παλιά Κτίρια Ηλεκτρολόγων.

    Έναρξη 1 Οκτώβρη.

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

    Αλγόριθμοι ροής δεδομένων (Δομές δεδομένων υπογραμμικού χώρου)

    1. Περίληψη μαθήματος, βασικά πιθανοτικά φράγματα (Markov, Chebyshev), αλγόριθμος του Μόρις. Ιδεαλιστικός αλγόριθμος ροής για μέτρηση πλήθους διαφορετικών στοιχείων. Ανά k ανεξάρτητες συναρτήσεις κατακερματισμού.
    2. Διακριτά στοιχεία, συνέχεια. Υπολογισμοί και αναγκαιότητα της χρήσης πιθανοτικών  αλγορίθμων. Φράγματα Chernoff. AMS σκιαγράφημα.
    3.  Πολυπλοκότητα Επικοινωνίας, απόδειξη αναγκαιότητας της χρήσης πιθανοτικών και προσεγγιστικών αλγορίθμων για το πρόβλημα των διακριτών στοιχείων. Υπολογισμός συχνότητας στοιχείου: CountMin σκιαγράφημα.
    4. Ντετερμινιστικοί αλγόριθμοι για βαρέα στοιχεία, κώδικες Reed-Solomon. Βαρέα στοιχεία στην ell_2 νόρμα: CountSketch σκιαγράφημα.
    5. Βαρέα στοιχεία με γρήγορο χρόνο ανανέωσης και ο κώδικας του Spielman, υπολογισμός διαμέτρου συνόλου σημείων στο επίπεδο.

    Ελάττωση Διάστασης

    1. Λήμμα Johnson-Lindenstrauss, ανισότητα του Khintchine, ανισότητα των Hanson-Wright. Γρήγορος μετασχηματισμός Johnson-Lindenstrauss, ανισότητα Bernstein. 
    2. Αραιός μετασχηματισμός Johnson-Lindenstrauss. Απόδειξη βελτιστότητας του Johnson-Lindenstrauss.

    Ανάκτηση αραιών διανυσμάτων

    1. Γρήγορος Μετασχηματισμός Φουριέ. Επάρκεια ανάκτησης k-αραιού σήματος, μέθοδος του Πρόνυ.
    2. Πολλαπλασιασμός αραιών πολυωνύμων.
    3. Αραιός μετασχηματισμός Φουριέ

    Έλεγχος Ιδιότητας/ υπολογισμός με κατοχή μαντείου

    1. Υπολογισμός τομής πολυγώνων. Προσέγγιση του μέσου βαθμού ενός γραφήματος.
    2. Έλεγχος συνεκτικότητας γραφήματος και υπολογισμός ελάχιστου συνδετικού δέντρου σε υπογραμμικό χρόνο

    Βαθμολογία

    3 σειρές ασκήσεων, τελική παρουσίαση, διαγώνισμα.

    Επιπρόσθετοι βαθμοί θα δοθούν σε όσους βρουν κατάλληλες μεταφράσεις (από την αγγλική στην ελληνική γλώσσα) για ορολογίες του μαθήματος.

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

    Βασικές γνώσεις θεωρίας Πιθανοτήτων, Αλγόριθμοι και Πολυπλοκότητα.

    Σχετικά μαθήματα

    Jelani Nelson(Harvard) : https://www.sketchingbigdata.org/

    David Woodruff (Carnegie Mellon): http://www.cs.cmu.edu/~dwoodruf/teaching/15859-fall17/index.html

    Moses Charikar (Stanford): https://web.stanford.edu/class/cs369g/

    Piort Indy, Ronnitt Rubinfield (MIT): http://stellar.mit.edu/S/course/6/sp13/6.893/

    Piotr Indyk (MIT): http://people.csail.mit.edu/indyk/MASS/index.html

    Chandra Checkuri (UIUC): https://courses.engr.illinois.edu/cs598csc/fa2014/

    Tim Roughgarden, Gregory Valiant (Stanford): https://csci8980bigdataalgo.wordpress.com