Corelab : Μαθήματα

Για ανακοινώσεις σχετικές με τα μαθήματα δείτε τις σελίδες των μαθημάτων.

Προπτυχιακά μαθήματα

Προγραμματισμός Ηλεκτρονικών Υπολογιστών (χειμερινό εξάμηνο)
Εισαγωγή στην Πληροφορική. Αλγόριθμοι και δομές δεδομένων, προγράμματα, γλώσσες προγραμματισμού. Προδιαγραφές, σχεδίαση, κωδικοποίηση, επαλήθευση, απόδειξη ορθότητας με αξιωματική σημασιολογία, τεκμηρίωση, συντήρηση προγραμμάτων. Η γλώσσα προγραμματισμού Pascal. Απλοί τύποι δεδομένων, σταθερές και μεταβλητές, εκφράσεις, απλές εντολές. Δομές ελέγχου, συναρτήσεις και διαδικασίες, πέρασμα παραμέτρων, επανάληψη και αναδρομή. Σύνθετες δομές δεδομένων και εφαρμογές: πίνακες, εγγραφές, σύνολα, δείκτες, συνδεδεμένες λίστες, δέντρα. Εργαστήριο: Μια σειρά προβλημάτων που θα λυθούν με προγράμματα Pascal.

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

Διακριτά Μαθηματικά (εαρινό εξάμηνο)

Θεμελιώδη Θέματα Επιστήμης Η/Υ (χειμερινό εξάμηνο)
Εισαγωγή στις βασικές αρχές και έννοιες του υπολογισμού: υπολογιστικά προβλήματα ως τυπικές γλώσσες, μοντέλα υπολογισμού, υπολογισιμότητα, αλγόριθμοι, κλάσεις πολυπλοκότητας, πληρότητα, αυτόματα, τυπικές γραμματικές, αποτελέσματα δυσκολίας, λογική στην επιστήμη των υπολογιστών. Το μάθημα προσφέρει επίσης μια εισαγωγή στο μοντέλο του συναρτησιακού προγραμματισμού με τη γλώσσα Haskell και περιλαμβάνει εργαστηριακές ασκήσεις που βοηθούν στην εμπέδωση των διδασκόμενων θεωρητικών εννοιών.

Αλγόριθμοι & Πολυπλοκότητα (χειμερινό εξάμηνο)
Τεχνικές για ασυμπτωτική ανάλυση προγραμμάτων και κριτήρια για την επιλογή αλγορίθμων. Μέθοδοι σχεδιασμού καλών αλγορίθμων: “διαίρει και βασίλευε”, δυναμικός προγραμματισμός, άπληστοι αλγόριθμοι. Εφαρμογές στη θεωρία γραφημάτων (αναζήτηση σε βάθος, αναζήτηση σε πλάτος, ελάχιστο δένδρο-σκελετός, διαδρομή ελαχίστου κόστους). Επεξεργασία δεδομένων (διάταξη και αναζήτηση). Αλγεβρικά προβλήματα (υπολογισμός πολυωνύμων, πολλαπλασιασμός πινάκων). Αλγόριθμοι πολυωνυμικού χρόνου και ΝΡ-πλήρη προβλήματα.

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

Στοιχεία Θεωρίας Αριθμών & Εφαρμογές στην Κρυπτογραφία (χειμερινό εξάμηνο)
Κλασική κρυπτογραφία: κρυπτοσυστήματα Καίσαρα, Vigenere, μέθοδος δείκτη σύμπτωσης, Kasiski test. Τέλεια μυστικότητα (Shannon), one-time pad. Συμμετρική κρυπτογραφία. Κρυπτοσυστήματα πακέτου (block cryptosystems): δίκτυα Feistel, DES, AES. Τρόποι λειτουργίας. Κώδικες πιστοποίησης γνησιότητας (MACs). Κρυπτοσυστήματα ροής. Στοιχεία θεωρίας αριθμών: διαιρετότητα, αριθμητική υπολοίπων, τετραγωνικά υπόλοιπα, Κινέζικο Θεώρημα Υπολοίπων. Στοιχεία θεωρίας ομάδων: ομάδες, σύμπλοκα, θεώρημα Legendre. Συνάρτηση φ του Euler, σύμβολα Legendre και Jacobi. Primality tests: Fermat, Solovay-Strassen, Miller-Rabin, αλγόριθμος AKS. Παραγοντοποίηση: μέθοδος ρ, μέθοδος Dixon, B-smoothness. Κρυπτογραφία δημοσίου κλειδιού. Κρυπτοσυστήματα RSA και Rabin και η σχέση τους με την παραγοντοποίηση. Το πρόβλημα του διακριτού λογαρίθμου, σύστημα El Gamal. Ανταλλαγή κλειδιού Diffie – Hellman. Κρυπτογραφικές υποθέσεις και αναγωγές. Ψηφιακές Υπογραφές: RSA, El Gamal, DSS, υπογραφές μιας χρήσης, τυφλές υπογραφές, αδιαμφισβήτητες υπογραφές. Συναρτήσεις κατακερματισμού (hash functions). Σχήματα αναγνώρισης μηδενικής γνώσης: Fiat-Shamir και Feige-Fiat-Shamir. Στοιχεία θεωρίας πολυπλοκότητας. Παίγνια Arthur-Merlin και συστήματα διαλογικών αποδείξεων. Αποδείξεις μηδενικής γνώσης.

Αυτόματα & Τυπικές Γραμματικές (εαρινό εξάμηνο)
Οι γλώσσες και οι αναπαραστάσεις τους. Γραμματικές, context-sensitive και context-free γραμματικές. Πεπερασμένα αυτόματα και κανονικές γραμματικές. Pushdown Αυτόματα. Μηχανές Turing. Αυτόματα και αναγνώριση γλωσσών. Εφαρμογές στη σύνταξη των γλωσσών προγραμματισμού. Προβλήματα (αν)αποκρισιμότητας και πολυπλοκότητας.