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

Εξάμηνο:
6ο
Τύπος Μαθήματος:
Κατ’ Επιλογή Υποχρεωτικό (ΕΥΜ)
Κατεύθυνση:
CS (Computer Science)
Κωδικός:
Κ25
ECTS:
6
Διδακτικές Ώρες
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Ώρες Εργαστηρίου:
0
Μάθημα στις Ειδικεύσεις
Θεμελιώσεις Πληροφορικής (S1):
-
Διαχείριση Δεδομένων και Γνώσης (S2):
Υ Υποχρεωτικό
Λογισμικό (S3):
-
Υλικό και Αρχιτεκτονική (S4):
-
Επικοινωνίες και Δικτύωση (S5):
-
Επεξεργασία Σήματος και Πληροφορίας (S6):
-
Σχετικά Μαθήματα
Υποχρεωτικά Προαπαιτούμενα:
-
Συνιστώμενα Προαπαιτούμενα:
Αναλυτική Περιγραφή
DIT_PPS_K25-Θεωρία Υπολογισμού.pdf
Σύντομη περιγραφή Μαθήματος
Το μάθημα καλύπτει βασικά και προχωρημένα θέματα της Θεωρίας Υπολογισμού που αποτελούν απαραίτητο υπόβαθρο σε διάφορους κλάδους της Θεωρητικής Πληροφορικής. Τυπικές γλώσσες. Ντετερμινιστικά και μη-ντετερμινιστικά πεπερασμένα αυτόματα. Κανονικές γλώσσες. Γλώσσες χωρίς συμφραζόμενα. Μη-ντετερμινιστικά αυτόματα στοίβας. Μηχανές Turing. Αναδρομικές γλώσσες. Αναδρομικά απαριθμήσιμες γλώσσες. Η Θέση των Church-Turing. Αποφασισιμότητα. Εισαγωγή στην υπολογιστική πολυπλοκότητα.
Βιβλιογραφία
Βασικά συγγράμματα: H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική. M. Sipser, Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης. Επιπλέον παρέχονται διαφάνειες του Π. Ροντογιάννη, οι οποίες βρίσκονται στη σελίδα του μαθήματος, καθώς και συνιστώμενη ξενόγλωσση βιβλιογραφία.
e-Class link
https://di.uoa.gr/~prondo/toc.html

Διδάσκων