Graph Drawing

Type
Elective
Course Description

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

Cryptography

Type
Elective
Course Description

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

Computational Αlgebra

Type
Elective
Course Description

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

Computational Science and Technology

Type
Elective
Course Description

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

Computational Geometry

Type
Elective
Course Description

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

Computational Cryptography

Type
Elective
Course Description

Κλασική κρυπτογραφία: κρυπτοσυστήματα αντικατάστασης, Καίσαρα, 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, κρυπτογραφία συζεύξεων, συσκότιση κώδικα, μετα-κβαντική κρυπτογραφία.

Computational Complexity

Type
Elective Required
Group
A
Course Description

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

Computation Models, Formal Languages and Automata

Type
Elective
Course Description

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

Combinatorics

Type
Elective Required
Group
C
Course Description

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

Combinatorial Optimization

Type
Elective Required
Group
A
Course Description

Μαθηματική μοντελοποίηση προβλημάτων συνδυαστικής βελτιστοποίησης που εμφανίζονται σε πρακτικές εφαρμογές όπως των τηλεπικοινωνιακών δικτύων, των δικτύων υπολογιστών ή οδικών δικτύων, χρονοπρογραμματισμού, διαχείρισης πόρων, τοποθέτησης εξυπηρετητών και μεταφοράς. Γενικές τεχνικές επίλυσης προβλημάτων συνδυαστικής σελτιστοποίησης. Μέθοδοι διαχώρισης και αποτίμησης (Branch and Bound), ευριστικοί αλγόριθμοι, μεταευριστικοί αλγόριθμοι. Ανάδειξη των ορίων των αλγορίθμων και ανάπτυξη των πρόσφατων ερευνητικών εξελίξεων στο πεδίο. Δυναμικός Προγραμματισμός και προσεγγιστικοί αλγόριθμοι. Πολυωνυμικού χρόνου προσεγγιστικά σχήματα (PTAS, FPTAS). Μέθοδοι τοπικής αναζήτησης, PLS-completeness, δομές γειτονιών, εκθετικές γειτονιές αναζητούμενες πολυωνυμικά, προσεγγισιμότητα. Σύνδεση των μεθόδων τοπικής αναζήτησης με τη θεωρία παιγνίων και τη θεωρία τοπίων.