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

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

Κωδικός:
Εξάμηνο:
Κατηγορία:
Ροή:

ICE-7002
7ο
Υποχρεωτικό (Υ)

Ώρες:
Διδάσκοντες:
Σύνδεσμοι:

3 Θ – 1 ΑΠ/Φ 
Ιωάννα Καντζάβελου (ΔΕΠ)

Περιγραφή

Αλφάβητα και Γλώσσες. Κανονικές Εκφράσεις και Γλώσσες. Πεπερασμένα αυτόματα. Μη ντετερμηνισμός: αυτόματα και ισοδυναμίες. Μη κανονικές γλώσσες και το Λήμμα της Άντλησης. Γραμματικές ανεξάρτητες συμφραζομένων (ΓΑΣ), κανονικές γραμματικές. Αυτόματα στοίβας και ισοδυναμία με ΓΑΣ. Μηχανές Turing, Αποφασισιμότητα και  Αναγνωρισιμότητα: τα όρια του υπολογισμού. Τάξεις προβλημάτων: P, NP , NP-πλήρες, co-NP, αναγωγές και  δύσκολα προβλήματα.