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

Προγραμματισμένη ώρα και αίθουσα διαλέξεων: βλ. ωρολόγιο πρόγραμμα εαρινού εξαμήνου 2025

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

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