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

Εξάμηνο:
6ο
Τύπος Μαθήματος:
Κατ’ Επιλογή Υποχρεωτικό Μάθημα (ΕΥΜ)
Κατεύθυνση:
Α
Κωδικός:
Κ25
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
0
Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (Ε1):
-
Διαχείριση Δεδομένων και Γνώσης (Ε2):
(Υ) Υποχρεωτικό
Λογισμικό (Ε3):
-
Υλικό και Αρχιτεκτονική (Ε4):
-
Επικοινωνίες και Δικτύωση (Ε5):
-
Επεξεργασία Σήματος και Πληροφορίας (Ε6):
-
Σχετικά Μαθήματα
Περιγραφή Μαθήματος

Το μάθημα καλύπτει βασικά και προχωρημένα θέματα της Θεωρίας Υπολογισμού που αποτελούν απαραίτητο υπόβαθρο σε διάφορους κλάδους της Θεωρητικής Πληροφορικής. Τυπικές γλώσσες. Ντετερμινιστικά και μη-ντετερμινιστικά πεπερασμένα αυτόματα. Κανονικές γλώσσες. Γλώσσες χωρίς συμφραζόμενα. Μη-ντετερμινιστικά αυτόματα στοίβας. Μηχανές Turing. Αναδρομικές γλώσσες. Αναδρομικά απαριθμήσιμες γλώσσες. Η Θέση των Church-Turing. Αποφασισιμότητα. Εισαγωγή στην υπολογιστική πολυπλοκότητα.

Βιβλιογραφία

Βασικά συγγράμματα: H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική.
M. Sipser, Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης.
Επιπλέον παρέχονται διαφάνειες του Π. Ροντογιάννη, οι οποίες βρίσκονται στη σελίδα του μαθήματος, καθώς και συνιστώμενη ξενόγλωσση βιβλιογραφία.

Αναλυτική Περιγραφή