Σχέσεις, Συναρτήσεις, Γλώσσες, Προβλήματα, Επαγωγή, Αποδεικτικές τεχνικές. Μηχανές Turing. Turing Απαριθμήσιμες Γλώσσες. Παραλλαγές/Επεκτάσεις Μηχανών Turing. Γενικές γραμματικές.    Πρωτογενώς Αναδρομικές Συναρτήσεις. Καθολικές Μηχανές Turing. Αυτοαναφορά, το θεώρημα της αναδρομής. Βαθμοί μη-αποφανσιμότητας.

Εισαγωγή στην παραμετρική πολυπλοκότητα, ισοδυναμίες μέτρων πολυπλοκότητας. Αλγοριθμικές τεχνικές: φραγμένα δέντρα αναζήτησης, επαναληπτική συμπίεση, άπληστος εντοπισμός, αναδρομική κατανόηση, σημαντικοί διαχωριστές, κανόνες αναγωγής, η τεχνική της ασήμαντης κορυφής. Πιθανοτικές μέθοδοι, πυρηνοποίηση, πυρηνοποίηση  Turing. Δεντροπλάτος, το θεώρημα του Courcelle, δυναμικός προγραμματισμός, διδιαστατότητα, εναλλακτικές παράμετροι πλάτους, παραμετρικές αναγωγές, μετααλγοριθμικά θεωρήματα. Οι κλάσεις para-NP και XP, η W-ιεραρχία: FPT, W[1],W[2],...,W[SAT], W[P] και ορισμοί της μέσω κυκλωμάτων, λογικών τύπων και μοντέλων μηχανών Turing. Κάτω φράγματα και υπόθεση εκθετικού χρόνου, ισχυρή υπόθεση εκθετικού χρόνου, παραμετρική πολυπλοκότητα πολυωνυμικά επιλύσιμων προβλημάτων.

Το αντικείμενο του μαθήματος είναι η μελέτη αλγοριθμικών μεθόδων και η ανάλυση πολυπλοκότητας για υπολογιστικά προβλήματα και θεμελιώδεις διαδικασίες που σχετίζονται με δίκτυα, κυρίως υπολογιστών και επικοινωνιών. Ορισμένα από τα θέματα που θα καλυφθούν: Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling. Κατανεμημένα πρωτόκολλα: εκλογήαρχηγού, broadcasting, gossiping, byzantine agreement, secretsharing. Ασύρματα ad hoc δίκτυα. Συγχρονισμένοι και ασύγχρονοι αλγόριθμοι. Fault tolerance. Προβλήματα αυτόνομων οντοτήτων, εξερεύνηση δικτύων, προβλήματα συνάντησης (rendezvous), εντοπισμός βλαβών σε δίκτυα. Πρωτόκολλα δρομολόγησης, compact routing, geometric routing. Ειδικά θέματα: χρονοδρομολόγηση (scheduling), δρομολόγηση και ανάθεση συχνοτήτων σε οπτικά δίκτυα, αλγόριθμοι πλοήγησης, προγραμματισμός δρομολογίων οχημάτων. Στοιχεία θεωρίας παιγνίων: σημεία ισορροπίας Nash, "κόστος της αναρχίας". Εγωιστική δρομολόγηση σε κλασικά, ασύρματα και οπτικά δίκτυα. Παίγνια συμφόρησης. Σύγκλιση σε ισορροπίες Nash και σχεδίαση μηχανισμών.

Σύντομη ανασκόπηση Προτασιακής Λογικής. Πρωτοτάξια Λογική. Αλήθεια και μοντέλα. Τυπικές αποδείξεις (συναγωγές). Θεώρημα αξιοπιστίας και πληρότητας. Ερμηνείες (στοιχειώδης θεωρία μοντέλων). Μη συμβατική ανάλυση. Μη-διαγνωσιμότητα και μη πληρότητα. Αναδρομικές συναρτήσεις. Αριθμητικοποίηση σύνταξης. Θεωρία αριθμών. Πρώτο και δεύτερο θεώρημα μη πληρότητας.

Ισομορφισμοί, αυτομορφισμοί, ομάδες αυτομορφισμών. Μετασχηματισμοί και σχέσεις σε γραφήματα. Βαθμοί, πυκνότητα, ελαχιστομέγιστο θεώρημα εκφυλισμού. Μονοπάτια, κύκλοι, διάμετρος, ακτίνα, κέντρο, απόκεντρο, περιφέρεια, περίμετρος. Συνεκτικότητα, δισυνεκτικά γραφήματα, το Θεώρημα του 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.