Συστήματα Τύπων των Γλωσσών Προγραμματισμού

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

Το μάθημα αυτό έχει ως σκοπό τη μελέτη των συστημάτων τύπων (type systems) που χρησιμοποιούνται στις σύγχρονες γλώσσες προγραμματισμού.  Μέσω των συστημάτων τύπων μελετώνται σε βάθος τα κυριότερα χαρακτηριστικά των προστακτικών και συναρτησιακών γλωσσών προγραμματισμού: βασικοί τύποι, συναρτήσεις, αναδρομή, αναφορές, εξαιρέσεις, υποτύποι, αναδρομικοί τύποι, αντικείμενα, πολυμορφισμός, υπαρξιακοί και εξαρτώμενοι τύποι. Έμφαση δίνεται στη συνεισφορά των συστημάτων τύπων για τον τυπικό ορισμό των γλωσσών καθώς και για τη μελέτη ιδιοτήτων ασφάλειας των προγραμμάτων. Για την περιγραφή της σημασιολογίας των υπό μελέτη γλωσσών χρησιμοποιείται η προσέγγιση της δομημένης λειτουργικής σημασιολογίας (structural operational semantics). 

Θεωρία Γραμμικού Προγραμματισμού

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

Κυρτά σύνολα, πολύεδρα, κώνοι. Θεώρημα Minkowski-Weyl. Λήμματα Farkas, δυϊκότητα. Όψεις και έδρες πολυέδρων. Διάσταση.  Ελαχιστικές αναπαραστάσεις. Total unimodularity. Ολική Δυϊκή Ακεραιότητα. Tα πολύτοπα των ταιριασμάτων και των συνδετικών δένδρων. Εκτεταμένες Διατυπώσεις.

Στοχαστικά Μοντέλα

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

Ανανεωτικές διαδικασίες με κόστη: Ορισμοί και παραδείγματα. Μέσος ρυθμός κόστους και υπολογισμοί με το στοιχειώδες ανανεωτικό θεώρημα με κόστη. Αναγεννητικές διαδικασίες και υπολογισμοί μέσου ρυθμού κόστους. Εφαρμογές. Μαρκοβιανές αλυσίδες με κόστη: Ορισμοί και παραδείγματα. Υπολογισμοί μέσους ρυθμούς κόστους. Εφαρμογές. Εισαγωγή στο Δυναμικό προγραμματισμό: Βασική θεωρία για προβλήματα πεπερασμένου ορίζοντα. Εφαρμογές με επαγωγικά επιχειρήματα. Εφαρμογές με το επιχείρημα της ανταλλαγής. Προβλήματα βέλτιστου σταματήματος. Εισαγωγή στις Ουρές Αναμονής: Περιγραφή, ονοματολογία και μέτρα απόδοσης. Βασικά αποτελέσματα. Ανάλυση μέσης τιμής. Μαρκοβιανές ουρές. Βέλτιστος σχεδιασμός συστημάτων. Εισαγωγή στη Στοχαστική Θεωρία Ελέγχου Αποθεμάτων: Το μοντέλο του εφημεριδοπώλη, μοντέλα πολλών περιόδων. Στοιχεία Θεωρίας Παιγνίων: Παιχνίδια σε κανονική μορφή. Σημείο στρατηγικής ισορροπίας (ΣΣΙ ή σημείο Nash). Πεπερασμένα παιχνίδια δύο παικτών μηδενικού αθροίσματος (πινακοπαιχνίδια) και θεώρημα Mínimax. Εξισωτικές στρατηγικές και αλγόριθμοι επίλυσης πινακοπαιχνιδιών. Απλοποιήσεις.

Στοχαστικές Διαδικασίες

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

Μαρκοβιανές αλυσίδες διακριτού χρόνου: Βασικοί ορισμοί. Υπολογισμοί για τις μεταβατικές κατανομές. Κατάταξη καταστάσεων και οριακή συμπεριφορά αδιαχώριστων αλυσίδων. Υπολογισμοί στάσιμων κατανομών. Αντιστρεψιμότητα Μαρκοβιανών αλυσίδων και εφαρμογές. Πιθανότητες και μέσοι χρόνοι απορρόφησης για διαχωρίσιμες Μαρκοβιανές αλυσίδες. Η στοχαστική διαδικασία Poisson: Υπολογισμοί και ιδιότητες. Μη-ομογενής και σύνθετη διαδικασία Poisson. Μαρκοβιανές αλυσίδες συνεχούς χρόνου: Βασικοί ορισμοί. Υπολογισμοί για τις μεταβατικές κατανομές. Κατάταξη καταστάσεων και οριακή συμπεριφορά αδιαχώριστων αλυσίδων. Υπολογισμοί στάσιμων κατανομών. Αντιστρεψιμότητα Μαρκοβιανών αλυσίδων και εφαρμογές. Πιθανότητες και μέσοι χρόνοι απορρόφησης για διαχωρίσιμες Μαρκοβιανές αλυσίδες. Ανανεωτική Θεωρία: Εισαγωγή, στοιχειώδες ανανεωτικό θεώρημα, ανανεωτική συνάρτηση και ανανεωτική εξίσωση, βασικό ανανεωτικό θεώρημα. Υπολειπόμενος και παρελθών χρόνος ανανέωσης. Εφαρμογές. Martingales διακριτού χρόνου: Βασικές ιδιότητες. Θεώρημα επιλεκτικής στάσης. Σύγκλιση martingales. Εφαρμογές. Κλαδωτές διαδικασίες. Τυχαίοι περίπατοι.

Ειδικά Θέματα Αλγορίθμων

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

Στο μάθημα αυτό θα διδάσκονται σύγχρονα θέματα αλγορίθμων που δεν καλύπτονται από τα υπόλοιπα μαθήματα του προγράμματος.

Ειδικά Θέματα Λογικής

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

Στο μάθημα αυτό θα διδάσκονται σύγχρονα θέματα λογικής που δεν καλύπτονται από τα υπόλοιπα μαθήματα του προγράμματος.

Θεωρία Συνόλων

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

Επανάληψη βασικών εννοιών, αξιώματα της ZFC, διατακτικοί αριθμοί, υπερπεπερασμένη αναδρομή και επαγωγή. Πληθάριθμοι και πληθική αριθμητική. Το Αξίωμα της Επιλογής και το Αξίωμα της Θεμελίωσης. Το σύμπαν V των καλώς θεμελιωμένων συνόλων. Σχετικοποίηση και απολυτότητα πρωτοβάθμιων τύπων, το Θεώρημα της Ανάκλασης. Το κατασκευάσιμο σύμπαν L του Godel. Η (σχετική) συνέπεια του Αξιώματος της Επιλογής και της Υπόθεσης του Συνεχούς με τα υπόλοιπα αξιώματα της ZFC συνολοθεωρίας.

Σημασιολογία Γλωσσών Προγραμματισμού

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

Δηλωτική, αξιωματική και μηχανική σημασιολογία. Ρόλος της σημασιολογίας στη σχεδίαση και ανάπτυξη σύγχρονων γλωσσών προγραμματισμού. Σημασιολογία διαδικαστικών γλωσσών. Πλήρεις σχέσεις μερικής διάταξης (cpos). Μονοτονικές και Συνεχείς Συναρτήσεις. Θεώρημα Σταθερού Σημείου του Kleene. Σημασιολογία συναρτησιακών γλωσσών με αναδρομικούς ορισμούς και συναρτήσεις υψηλής τάξης. Σημασιολογία λογικών προγραμμάτων. Μοντέλα Herbrand. Πλήρη πλέγματα και θεώρημα σταθερού σημείου των Knaster-Tarski. Θεώρημα ελάχιστου μοντέλου Herbrand. Σημασιολογία της Άρνησης στο Λογικό Προγραμματισμό.  Στρωματοποιημένα και τοπικά στρωματοποιημένα προγράμματα. Καλώς-θεμελιωμένη σημασιολογία (well-founded semantics). Σημασιολογία σταθερού μοντέλου (stable model semantics). Λογικός προγραμματισμός υψηλής τάξης. Θεωρία άπειρων παιγνίων και εφαρμογές στη σημασιολογία γλωσσών προγραμματισμού.