Θεωρία Γραφημάτων

Τύπος
Κατ' επιλογήν υποχρεωτικό
Ομάδα
Γ
Περιγραφή μαθήματος

Ισομορφισμοί, αυτομορφισμοί, ομάδες αυτομορφισμών. Μετασχηματισμοί και σχέσεις σε γραφήματα. Βαθμοί, πυκνότητα, ελαχιστομέγιστο θεώρημα εκφυλισμού. Μονοπάτια, κύκλοι, διάμετρος, ακτίνα, κέντρο, απόκεντρο, περιφέρεια, περίμετρος. Συνεκτικότητα, δισυνεκτικά γραφήματα, το Θεώρημα του Menger, Το Θεώρημα του Tutte για την 3-συνεκτικότητα. Δάση και δέντρα, δεντροπαράγοντες. Επίπεδα γραφήματα, τοπολογικός ισομορφισμός, δυικά γραφήματα, πυκνότητα και επιπεδότητα, Το θεώρημα του Kuratowski. Χρωματισμοί γραφημάτων, Χρωματικότητα και εκφυλισμός, Το θεώρημα του Heawood, Το θεώρημα του Erdős για την περιφέρεια και τον χρωματικό αριθμό. Η εικασία του Hadwiger. Κλίκες, ανεξάρτητα σύνολα, Αριθμοί Ramsey. Καλύμματα, ταιριάσματα, Τέλεια γραφήματα. Το θεώρημα του Lovasz για τα τέλεια γραφήματα, Το θεώρημα του Dilworth. Μονοπάτια Euler και Hamilton. Η πιθανοτική τεχνική, τυχαία γραφήματα. Ακραία γραφοθεωρία, τοπολογική θεωρία γραφημάτων. Η θεωρία των ελασσόνων γραφημάτων.

Απεικόνιση Γραφημάτων

Τύπος
Επιλογής
Περιγραφή μαθήματος

Απεικόνιση γραφημάτων και εφαρμογές. Απεικόνιση επιπέδων γραφημάτων. Απεικόνιση δένδρων και Series-Parallel γραφημάτων. Απεικόνιση βασιζόμενη σε νόμους της φυσικής. Ιεραρχική απεικόνιση γραφημάτων. Ορθογώνια απεικόνιση γραφημάτων. Τρισδιάστατη απεικόνιση γραφημάτων. Δυναμική απεικόνιση γραφημάτων. Πακέτα λογισμικού.

Κρυπτογραφία

Τύπος
Επιλογής
Περιγραφή μαθήματος

Μελέτη σύγχρονων κρυπτογραφικών πρωτοκόλλων με έμφαση στην τεκμηρίωση ιδιοτήτων ασφάλειας. Η ύλη περιλαμβάνει σχήματα δέσμευσης, coin flipping, ανταλλαγή κλειδιού Diffie-Hellman, ψηφιακές υπογραφές, μηδενική γνώση, κρυπτογραφία δημόσιου κλειδιού (RSA, ElGamal), secret sharing, κρυπτονομίσματα.

Υπολογιστική Άλγεβρα

Τύπος
Επιλογής
Περιγραφή μαθήματος

Πολυώνυμα πολλών μεταβλητών: Ιδεώδη, ποικιλότητες (varieties), βάσεις Groebner, αλγόριθμος Buchberger. Μελέτη συστημάτων, καταμέτρηση ριζών (φράγμα Bezout, Μικτός όγκος), επίλυση με μεθόδους γραμμικής άλγεβρας. Απαλοίφουσα (resultant). Κλασική και αραιή απαλοίφουσα. Κατασκευή πινάκων απαλοίφουσας (Sylvester, Macaulay, αραιής απαλοίφουσας). Εφαρμογές: Kινηματική των ρομπότ και γράφοι αποστάσεων. Γεωμετρική σχεδίαση. Υπολογιστική θεωρία Παιγνίων.

Υπολογιστική Επιστήμη και Τεχνολογία

Τύπος
Επιλογής
Περιγραφή μαθήματος

Προσομοίωση, σφάλματα, αριθμητική υπολογιστών. Ιεραρχίες μνήμης, οι πυρήνες BLAS. Αλγόριθμοι εφαρμοσμένης γραμμικής άλγεβρας, LAPACK. Μέθοδοι Monte Carlo. Προβλήματα αρχικών τιμών και συνοριακά προβλήματα για συνήθεις διαφορικές εξισώσεις. Μη-γραμμικές εξισώσεις πολλών μεταβλητών. Υπολογισμοί με αραιούς πίνακες και εφαρμογές σε μερικές διαφορικές εξισώσεις και σε επίλυση γραμμικών συστημάτων. Επαναληπτικές μέθοδοι Krylov, πολυπλεγματικές μέθοδοι.

Υπολογιστική Γεωμετρία

Τύπος
Επιλογής
Περιγραφή μαθήματος

Κυρτό περίβλημα σε 2, 3 και μεγαλύτερες διάστασεις, αλγόριθμος περιτύλιξης (πολυπλοκότητα ευαίσθητη εξόδου) και αυξητικός αλγόριθμος. Αθροισμα Minkowski. Τριγωνοποίηση πολυγώνου. Eκφυλισμένα δεδομένα, διαταραχή. Γραμμικός Προγραμματισμός, αλγόριθμος Simplex και αντίστροφη αναζήτηση, δυϊσμός και πόλωση. Διάγραμμα Voronoi, αναγωγή σε ΚΠ. Τριγωνοποίηση Delaunay, α-σχήματα και εφαρμογές στην δομική βιοπληροφορική, στην κίνηση ρομπότ ανάμεσα σε εμπόδια. Διατάξεις ευθυγράμμων τμημάτων, ευθειών. Δομές γεωμετρικών δεδομένων. Εντοπισμός και εξόρυξη δεδομένων, ορθoγώνια αναζήτηση, kd-δένδρα, δένδρα περιοχών. Προσεγγιστική εύρεση πλησιέστερου γείτονα με δενδρικές δομές ή πίνακες κατακερματισμού σε μεγάλες διαστάσεις και γενικούς μετρικούς χώρους. Locality-sensitive Hashing για την αντιμετώπιση της "κατάρας της διάστασης". Mείωση διάστασης με τυχαιοκρατικές προβολές και το Λήμμα Johnson-Lindenstrauss. Εφαρμογές στη συσταδοποίηση. Υλοποίηση σε Python και στην C++ βιβλιοθήκη γεωμετρικού λογισμικού CGAL.

Υπολογιστική Κρυπτογραφία

Τύπος
Επιλογής
Περιγραφή μαθήματος

Κλασική κρυπτογραφία: κρυπτοσυστήματα αντικατάστασης, Καίσαρα, Vigenere, μέθοδοι κρυπτανάλυσης. Τέλειαμυστικότητα (Shannon), one-time pad. Semantic security, CPA, CCA, PCPA. Συμμετρική κρυπτογραφία. Ψευδοτυχαιότητα, κρυπτοσυστήματα ροής. Κρυπτοσυστήματα τμήματος: δίκτυα Feistel, DES, AES. Τρόποι λειτουργίας. Κώδικες πιστοποίησης γνησιότητας (MACs). Συναρτήσεις κατακερματισμού (hash functions). Στοιχεία θεωρίας αριθμών: διαιρετότητα, αριθμητική υπολοίπων, τετραγωνικά υπόλοιπα, Κινέζικο Θεώρημα Υπολοίπων. Στοιχεία θεωρίας ομάδων, θεώρημα Legendre, συνάρτηση φ του Euler. Έλεγχος πρώτων αριθμών. Κρυπτογραφία δημοσίου κλειδιού. Κρυπτοσυστήματα RSA και Rabin, σχέση με πρόβλημα παραγοντοποίησης. Το πρόβλημα του διακριτού λογαρίθμου, σύστημα El Gamal. Ανταλλαγή κλειδιού Diffie – Hellman. Ψηφιακές Υπογραφές: RSA, DSS, τυφλές υπογραφές. Κρυπτογραφικά πρωτόκολλα: διαμοιρασμός μυστικού, σχήματα αναγνώρισης, e-voting, ασφαλής υπολογισμών πολλών μερών, Bitcoin. Αποδείξεις μηδενικής γνώσης. Στοιχεία θεωρίας πολυπλοκότητας, μονόδρομες συναρτήσεις. Προχωρημένα θέματα: ελλειπτικές καμπύλες, κρυπτογραφία βασισμένη σε lattices, κρυπτογραφία συζεύξεων, συσκότιση κώδικα, μετα-κβαντική κρυπτογραφία.

Υπολογιστική Πολυπλοκότητα

Τύπος
Κατ' επιλογήν υποχρεωτικό
Ομάδα
Α
Περιγραφή μαθήματος

Ορισμός κλάσεων πολυπλοκότητας με βάση τις ακόλουθες παραμέτρους: α) Το υπολογιστικό μοντέλο (προγράμματα σε γλώσσα υψηλής βαθμίδος, μηχανές Turing κτλ.), β) Τον τρόπο υπολογισμού (ντετερμινιστικό, μη ντετερμινιστικό, πιθανοτικό κτλ.), γ) Τον περιορισμό των πόρων (πολυωνυμικός χρόνος, λογαριθμικός χώρος, σταθερός αριθμός επεξεργαστών, κτλ.). Μελέτη κλάσεων πολυπλοκότητας και των μεταξύ τους σχέσεων. Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Ιεραρχίες, αναγωγές και πληρότητα, ΝΡ - πλήρη προβλήματα, Co-NP και κλάσεις συναρτήσεων. Πιθανοτικοί υπολογισμοί και πολυπλοκότητα κυκλωμάτων, κρυπτογραφία, μονόδρομες συναρτήσεις. Πρωτόκολλα, προσεγγισιμότητα και μη προσεγγισιμότητα, P vs. NP. Ισομορφισμός, μαντεία, μονότονα κυκλώματα, παράλληλοι υπολογισμοί. Κλάσεις NC και RNC, λογαριθμικός χώρος, κλάση L. Προσεγγιστικοί αλγόριθμοι. Η πολυωνυμική ιεραρχία. Προβλήματα βελτιστοποίησης, μετρητικές κλάσεις, η κλάση #P. Πολυωνυμικός χώρος, PSPACE. Παίγνια και διαλογικά πρωτόκολλα, εκθετικός χρόνος κ.α..

Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα

Τύπος
Επιλογής
Περιγραφή μαθήματος

Υπολογισιμότητα: Λογική θεμελίωση πληροφορικής. Ιστορική αναδρομή στο πρόβλημα αποκρισιμότητας μαθηματικών προτάσεων, επιλυσιμότητας ή υπολογισιμότητας προβλημάτων με μηχανιστικό, δηλαδή αλγοριθμικό, τρόπο. Απλά ισοδύναμα υπολογιστικά μοντέλα: μηχανές Turing, προγράμματα WHILE. Επαγωγή και αναδρομή, κωδικοποίηση και σημασιολογία. Θεωρία σταθερού σημείου. Μαντεία και Αριθμητική ιεραρχία. Θεωρία αυτομάτων και τυπικών γραμματικών: Πεπερασμένα αυτόματα. Κανονικά σύνολα και ισοδύναμοι χαρακτηρισμοί. Ιεραρχία Chomsky. Αποδείξεις για το εάν L∈C ή L∉C. Εφαρμογές στο συντακτικό γλωσσών προγραμματισμού. Πολυπλοκότητα: Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Αναγωγές και Πληρότητα.  Πολυωνυμική ιεραρχία. Πιθανοτικές, διαλογικές και μετρητικές κλάσεις. Παραμετρική πολυπλοκότητα. Κβαντική πολυπλοκότητα.

Συνδυαστική

Τύπος
Κατ' επιλογήν υποχρεωτικό
Ομάδα
Γ
Περιγραφή μαθήματος

Απαρίθμηση και γεννήτριες συναρτήσεις, μεταθέσεις και πολυώνυμα Euler, εκθετικές γεννήτριες συναρτήσεις, ο εκθετικός τύπος, ο τύπος αντιστροφής του Lagrange και εφαρμογές στην απαρίθμηση δένδρων. Η αρχή εγκλεισμού-αποκλεισμού και εφαρμογές. Μερικώς διατεταγμένα σύνολα, η συνάρτηση του Möbius, αντιστροφή Möbius, semimodular και γεωμετρικοί σύνδεσμοι, το θεώρημα NBC του Rota, το χαρακτηριστικό πολυώνυμο, εφαρμογές σε παρατάγματα υπερεπιπέδων και χρωματισμούς γραφημάτων, το πολυώνυμο ζήτα μιας μερικής διάταξης. Στοιχεία τοπολογικής συνδυαστικής, το σύμπλεγμα μιας μερικής διάταξης και η χαρακτηριστική Euler, μονοπλεκτικά και κυτταρικά συμπλέγματα, αποφλοιώσιμα (shellable) και Cohen-Macaulay συμπλέγματα και μερικώς διατεταγμένα σύνολα, μερικές διατάξεις του Euler και οι εξισώσεις Dehn-Sommerville. Ρητές γεννήτριες συναρτήσεις, θεωρία των P-διαμερίσεων και P-πολυώνυμα Euler, quasi-συμμετρικές συναρτήσεις.