Θεωρία Υπολογισμού

Το μάθημα αυτό ασχολείται με τον υπολογισμό και τα μέσα που χρησιμοποιούμε για τον υπολογισμό. Ειδικότερα ανάμεσα σε άλλα εξετάζονται οι γραμματικές, τα πεπερασμένα αυτόματα, ο μη ντετερμινισμός, οι Γλώσσες Χωρίς Συμφραζόμενα, οι Μηχανές Turing, η μη επιλυσιμότητα. Το μάθημα αυτό εισάγει έννοιες που θεμελιώνουν την επίλυση προβλημάτων και την κατασκευή μεταγλωττιστών.

Στόχοι Μαθήματος

Mαθησιακοί στόχοι Οι φοιτητές αναμένεται στα πλαίσια του μαθήματος να κατανοήσουν την έννοια του υπολογισμού και τις δυνατότητες των υπολογιστικών μας μηχανών γνωρίσουν τις θεμελιώσεις και τις αρχές της επιστήμης των υπολογιστών αφομοιώσουν ύλη πάνω στην οποία στηρίζονται άλλα αντικείμενα, όπως η Θεωρία Γλωσσών Προγραμματισμού και η Αλγοριθμική καλλιεργήσουν την ικανότητα να αναπτύσσουν τυπικά ορισμένους και μαθηματικώς τεκμηριωμένους συλλογισμούς γνωρίσουν ανοικτά προβλήματα και εφαρμογές της Θεωρίας Υπολογισμού στην επιστήμη και την τεχνολογία   Δεξιότητες-γενικοί μαθησιακοί στόχοι Γενικότερα, οι φοιτητές αναμένεται μετά το πέρας του μαθήματος       να εφαρμόζουν τη γνώση της θεωρίας στην πράξη αναζητούν, αναλύουν και συνθέτουν δεδομένα και πληροφορίες, με τη χρήση απαραίτητων τεχνολογιών στο πεδίο της πληροφορικής

Προαπαιτούμενες Γνώσεις

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

Περιεχόμενα

Εισαγωγή (σύνολα, σχέσεις και γλώσσες) Κανονικές Γλώσσες: Κανονικές εκφράσεις και κανονικές γλώσσες, Ντετερμινιστικά και μη ντετερμινιστικά πεπερασμένα αυτόματα Ιδιότητες κλειστότητας κανονικών γλωσσών Το λήμμα της άντλησης Γλώσσες Χωρίς Συμφραζόμενα: Γραμματικές γλωσσών χωρίς συμφραζόμενα Αυτόματα στοίβας Ιδιότητες γλωσσών χωρίς συμφραζόμενα Ντετερμινιστικές γλώσσες χωρίς συμφραζόμενα και καθοδική συντακτική ανάλυση Μηχανές Turing Μη επιλυσιμότητα