Τμήμα Μαθηματικών | Πανεπιστήμιο Πατρών


Μαθηματικές Θεμελιώσεις της Θεωρίας Υπολογισμού
Περιγραφή

Μέρος πρώτο: Λογική και απόδειξη. Επανάληψη στην Προτα­σιακή Λογική: Αλφάβητο, συντακτικό και σημασιολογία. Επα­νάληψη στην Κατηγορηματική Λογική: Αλφάβητο, συντακτικό και σημασιολογία, Βασικές μέθοδοι αποδείξεων: Ευθεία από­δειξη, Απόδειξη με αντιθετοαντιστροφή, Απόδειξη ύπαρξης (με κατασκευή και χωρίς κατασκευή), Μη-ευθεία απόδειξη, Απόδειξη με μαθηματική επαγωγή (ασθενής και ισχυρή μορφή της επαγωγής). Τυπικά συστήματα παραγωγής συμπερασμά­των: Hilbert-style συστήματα, Σημαντικοί πίνακες. Αναδρομές και επαγωγή. Επιβεβαίωση προγραμμάτων με τη χρήση της Λογικής Hoare: Μερική Ορθότητα κώδικα, Ολική ορθότητα κώδικα. Σχέσεις-Σχεσιακές βάσεις δεδομένων (στοιχειώδης παρουσίαση της Prolog).
Μέρος δεύτερο. Αυτόματα και τυπικές γλώσσες. Αλφάβητα και γλώσσες. Κανονικές εκφράσεις και κανονικές γλώσσες. Ντετερμινιστικά και μη Ντετερμινιστικά πεπερασμένα Αυτό­ματα. Λήμμα άντλησης για κανονικές γλώσσες. Γραμματικές και γλώσσες ανεξάρτητες συμφραζομένων. Κανονικές γραμμα­τικές. Απλούστευση και αναγωγή γραμματικών. Λήμμα άντλη­σης για γλώσσες ανεξάρτητες συμφραζομένων. Αυτόματα στοίβας. Συντακτική ανάλυση. Μηχανές Turing. Υπολογισμοί με μηχανές Turing. Γραμματικές χωρίς περιορισμούς. Υπολο­γισιμότητα. Μη αποφασίσιμες γλώσσες. Αναδρομικά αριθ­μήσιμες γλώσσες. Τα όρια της υπολογισιμότητας. Θεώρημα του Rice.

Τομέας: Υπολογιστικών Μαθηματικών και Πληροφορικής
Διδάσκοντες:

Συγγράμματα:

Πρόγραμμα Σπουδών:
Προπτυχιακό Πρόγραμμα Σπουδών
Εξάμηνο: ΣΤ
Πιστωτικές Μονάδες (ECTS): 6
Ωρες Διδασκαλίας (Θ/Φ/Ε): 2/2/0
Κωδικός: IC233
Τύπος Μαθήματος: Επιλογής
Κατεύθυνση ΓΝΜ: Βασικό
Κατεύθυνση ΘΡΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΕΦΜ: Ελεύθερης Επιλογής
Κατεύθυνση ΠΛΗ: Υποχρεωτικό Κατεύθυνσης
Κατεύθυνση ΣΠΕ: Ελεύθερης Επιλογής
Φοιτητές Erasmus: Όχι




keyboard_arrow_up