Παρουσίαση/Προβολή

Αντικείμενο του μαθήματος είναι μια βασική ερώτηση: Ποιες είναι οι θεμελιώδεις δυνατότητες και ποιοι οι εγγενείς περιορισμοί των υπολογιστών;

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

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

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

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

Συγγράμματα (διαθέσιμα μέσω του Εύδοξου και στη βιβλιοθήκη):

• Lewis & Παπαδημητρίου "Στοιχεία θεωρίας υπολογισμού"
• Sipser "Εισαγωγή στη θεωρία υπολογισμού"

Μαθηματικά προαπαιτούμενα: κάποιες ενότητες των Διακριτών Μαθηματικών του 1ου έτους.

Εξέταση: Μόνο τελική εξέταση στο τέλος Ιανουαρίου. Προσοχή: θα πρέπει να ασχολήστε με το μάθημα από λίγο κάθε εβδομάδα -- είναι αδύνατο να το αφήσετε για το τέλος!

Κτίριο ΜΠΕΣ, γραφείο Β-10

Για σύντομες ερωτήσεις (διαδικαστικά του μαθήματος, διευκρινήσεις):
aleros at aegean dot gr ή με μήνυμα μέσω eclass

Για ερωτήσεις στο υλικό του μαθήματος και οποιοδήποτε άλλο θέμα στις ώρες γραφείου: Τρίτη 6.30--7.30, Τετάρτη 4--6, Πέμπτη 2--4.