Γενικές πληροφορίες

 

Προγραμματισμένη ώρα και αίθουσα διαλέξεων:

Δευτέρα, 15.00-17.00 @αίθουσα Γ & Πέμπτη, 18.00-20.00 @αίθουσα Γ

Ακαδημαϊκό ημερολόγιο

H θεωρία υπολογισμού περιέχει τρεις κεντρικές περιοχές: τα αυτόματα, την υπολογισιμότητα, και την πολυπλοκότητα. Η βασική ερώτηση που συνδέει τις περιοχές αυτές είναι: Ποιες είναι οι θεμελιώδεις δυνατότητες και ποιοι οι εγγενείς περιορισμοί των υπολογιστών;

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

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

Στη θεωρία πολυπλοκότητας στόχος είναι η ταξινόμηση των επιλύσιμων προβλημάτων σε εύκολα και δύσκολα και το κεντρικό ερώτημα είναι: Τι είναι αυτό που κάνει κάποια προβλήματα υπολογιστικώς δύσκολα και κάποια άλλα εύκολα; Ένα από τα σημαντικότερα επιτεύγματα της θεωρίας πολυπλοκότητας είναι η ένα κομψό σύστημα ταξινόμησης των προβλημάτων με βάση την υπολογιστική τους δυσκολία.

Στο πλαίσιο του συγκεκριμένου μαθήματος, εστιάζουμε, ουσιαστικά, στη θεωρία αυτομάτων η οποία ασχολείται με τους ορισμούς και τις ιδιότητες των μαθηματικών μοντέλων της υπολογιστικής επιστήμης. Τα μοντέλα αυτά χρησιμοποιούνται στην πράξη σε αρκετές περιοχές της επιστήμης των υπολογιστών. Για παράδειγμα, τα πεπερασμένα αυτόματα χρησιμοποιούνται στην επεξεργασία κειμένου, στο σχεδιασμό μεταϕραστών και στο σχεδιασμό υλικού (hardware). Ένα άλλο μοντέλο, οι γραμματικές χωρίς συμφραζόμενα, χρησιμοποιείται στη σχεδίαση γλωσσών προγραμματισμού και στην τεχνητή νοημοσύνη. Η θεωρία αυτομάτων είναι ιδιαίτερα ενδιαφέρουσα περιοχή που επιτρέπει την εξοικείωση με τυπικούς ορισμούς της υπολογιστικής, με εξαιρετική χρησιμότητα στις θεωρίες της υπολογισιμότητας και της πολυπλοκότητας, που απαιτούν σαϕή ορισμό του υπολογιστή.