Weekly outline

  • General

    Το μάθημα προσφέρεται στα πλαίσια του ΔΠΜΣ "Επιστήμη Δεδομένων και Μηχανική Μάθηση" και στους Υ.Δ. της ΣΗΜΜΥ ως "Θεωρητική Πληροφορική ΙΙ", καθώς και σε άλλα μεταπτυχιακά προγράμματα (ΑΛΜΑ, ΕΜΕ).

    Οι διαλέξεις για φέτος (2019-20) ξεκίνησαν στις 27/2 και γίνονται κάθε Πέμπτη στην αίθουσα 005 του Ν. Κτ. Ηλεκτρολόγων ώρα 5:00μμ-8:00μμ

    Διδάσκοντες


    Βιβλιογραφία



  • Εβδομάδα 24/2-28/2

    27/2



    • Εβδομάδα 2/3-6/3

      5/3


      • Εβδομάδα 9/3-13/3

        Η διάλεξη της 12/3 δεν πραγματοποιήθηκε λόγω των έκτακτων μέτρων αντιμετώπισης της πανδημίας του SARS-CoV-2.

        • Εβδομάδα 16/3-20/3

          Διάλεξη 19/3: Κατακερματισμός (hashing)

          • Κατακερματισμός (hashing): κλειστή και ανοιχτή διευθυνσιοδότηση. Universal hash families. Γραμμική και τετραγωνική διερεύνηση (probing). Διπλός κατακερματισμός (double hashing).Παράγοντας φόρτου και ανάλυση χρόνου εκτέλεσης βασικών πράξεων.

            Προτεινόμενη μελέτη: σημειώσεις

          Το μάθημα πραγματοποιήθηκε διαδικτυακά. Σύνδεσμοι για τα βίντεο της διάλεξης:


          (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

          • Εβδομάδα 23/3-27/3

            Διάλεξη 26/3: Ροές δεδομένων (streaming)

            • Επεξεργασία ροών δεδομένων (streams). Δειγματοληψία σταθερής αναλογίας, δειγματοληψία παραθύρου. Αλγόριθμος προσεγγιστικής μέτρησης DGIM. 

              Διαφάνειες
              Προτεινόμενη μελέτη: [MMDS] 4.1, 4.2, 4.6.

            Το μάθημα πραγματοποιήθηκε διαδικτυακά. Σύνδεσμος:


            • Εβδομάδα 30/3-3/4

              Διάλεξη 2/4: Ροές Δεδομένων (Data Streams) II 

              • Επεξεργασία ροών δεδομένων (data streams): Bloom φίλτρα, εκτίμηση πλήθους διαφορετικών στοιχείων, εκτίμηση ροπών διανύσματος με συχνότητες εμφανίσεων στοιχείων, υπολογισμός συχνών συνόλων στοιχείων με παράθυρα που φθίνουν εκθετικά στον χρόνο (exponentially decaying windows).  Διαφάνειες

              Προτεινόμενη μελέτη: [MMDS] 4.3, 4.4, 4.5, 4.7 [FDS] 6.2.

              Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

              (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

              • 6 April - 10 April

                Διάλεξη 9/4: Heavy-Hitters σε Ροές Δεδομένων και Εύρεση Κοντινών Γειτόνων

                • Eπεξεργασία ροών δεδομένων (data streams): εκτίμηση συχνότητας εμφάνισης συχνών στοιχείων (heavy-hitters), αλγόριθμοι lossy counting και count-min sketch (προτείνεται να μελετήστε ακόμη τις σημειώσεις εδώ και εδώ, και να δείτε τις διαφάνειες εδώ, εδώ και εδώ).
                • Εύρεση κοντινών γειτόνων: ορισμός προβλήματος, επεξεργασία κειμένων, shingling, min-hashing, locality sensitive hashing. Διαφάνειες

                Προτεινόμενη μελέτη: [MMDS] 3.1 - 3.8. Σημειώσεις Jeff Philips για Min HashingLocality Sensitive Hashing, και αποστάσεις.

                Περαιτέρω μελέτη για επεξεργασία ροών δεδομένων:

                • Σημειώσεις και βιβλίο του S. Muthukrishnan για αλγόριθμους ροών δεδομένων.
                • Η εργασία των Manku και Motwani όπου παρουσιάζεται ο αλγόριθμος lossy counting. 
                • Η εργασία των Cormode και Muthukrishnan όπου παρουσιάζεται ο αλγόριθμος count-min sketch. 

                Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

                (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

                • 27 April - 1 May

                  Διάλεξη 30/4:  Σύντομη επισκόπηση του clustering.


                  • Clustering Techniques, The curse of dimensionality, Hierarchical clustering, K-means, BFR algorithm, Cure algorithm.


                       Η διάλεξη πραγματοποιήθηκε διαδικτυακά.
                       Η βιντεοσκοπημένη διάλεξη θα σταλεί στο email σας.



                       Προτεινόμενη μελέτη: [MMDS] Ενότητες: 7.1, 7.2, 7.3 και 7.4.
                       Περαιτέρω μελέτη:      [TSKK]  Κεφάλαιο 7

                  • 4 May - 8 May

                    Διάλεξη 7/5:  Community Detection I

                    • Εισαγωγή σε community detection. Edge Betweeness και Modularity. Αλγόριθμος Girvan-Newman. Διαφάνειες (1-23).
                      Προτεινόμενη μελέτη: [MMDS] 10.1 και 10.2
                    • Αλγόριθμος Louvain. Προτεινόμενη μελέτη: σχετικό paper.
                    • Εύρεση συσχετίσεων μέσω frequent itemset mining. Διαφάνειες (57-64). Προτεινόμενη μελέτη: [MMDS] 10.3


                    Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

                    (ΠΡΟΣΟΧΗ: Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η αποθήκευση, ανάρτηση ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

                    • 11 May - 15 May

                      Διάλεξη 14/5:  Community Detection II

                      • Εντοπισμός κοινοτήτων μέσω ιδιοτιμών γράφων, spectral clustering. Διαφάνειες (24-56).
                        Προτεινόμενη μελέτη: [MMDS] 10.4
                      • Εντοπισμός επικαλυπτόμενων κοινοτήτων με μεγιστοποίηση πιθανοφάνειας (MLE). Διαφάνειες (1-32)
                        Προτεινόμενη μελέτη: [MMDS]  10.5
                      • Ομοιότητες σε γράφους μέσω τυχαίων περιπάτων (Simrank).
                        Προτεινόμενη μελέτη: [MMDS] 10.6
                      • Τριαδικές σχέσεις, μέτρηση τριγώνων σε γράφο.
                        Προτεινόμενη μελέτη: [MMDS] 10.7 (έως 10.7.3)


                      Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

                      (ΠΡΟΣΟΧΗ: Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η αποθήκευση, ανάρτηση ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)

                      • 18 ΜΑΥ - 22 ΜΑΥ

                        Διάλεξη 21/5:  LINK ANALYSIS

                        • Definition of Page Rank, Structure of the Web, Avoiding Dead Ends, Spider Traps and Taxation,

                        • Efficient Computation of Page Rank, Efficient Approaches to Page Rank Iteration

                            
                             Η διάλεξη πραγματοποιήθηκε διαδικτυακά.
                             Η βιντεοσκοπημένη διάλεξη έχει σταλεί στο email σας.


                             Προτεινόμενη μελέτη: [MMDS] Ενότητες: 5.1,5.2   


                        • 15 May - 21 May

                          Διάλεξη 28/5: Αλγοριθμικά Προβλήματα που Σχετίζονται με τη Διαφήμιση στο Web 

                          • Η διαφήμιση στο Web
                          • Online αλγόριθμοι για το "ταίριασμα" των διαφημιζομένων με διαφημιστικές ευκαιρίες, ο άπληστος αλγόριθμος και ο αλγόριθμος Balance. 
                          • Μια γρήγορη εισαγωγή στις δημοπρασίες, η δημοπρασία 2ης τιμές (2nd price ή Vickey auction), η γενίκευσή της για Sponsored Search Auctions, η δημοπρασία Generalized Second Price. 

                          Προτεινόμενη μελέτη


                          Σύνδεσμος στη βιντεοσκοπημένη διάλεξη (απαιτείται συνθηματικό)

                          (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο.)