Μάθημα Κωδικός  Εξάμηνο Τύπος Ώρες Εργαστήριο /
Φροντιστήριο
ECTS Διδάσκοντες
Θεωρία Υπολογισμού ΗΥ025  Δ Επιλογής  4
4
Ανδρόνικος Θ.

Μαθησιακά Αποτελέσματα

Με την επιτυχή ολοκλήρωση του μαθήματος «Θεωρία Υπολογισμού» οι προπτυχιακοί φοιτητές είναι σε θέση:

  • Να κατανοήσουν την έννοια του υπολογισμού από τη σκοπιά της Θεωρητικής Πληροφορικής.
  • Να εξοικειωθούν με τα απλούστερα υπολογιστικά μοντέλα, όπως είναι τα πεπερασμένα αιτιοκρατικά και μη αιτιοκρατικά αυτόματα, καθώς και οι αντίστοιχες κανονικές γλώσσες.
  • Να εξοικειωθούν με τις γραμματικές χωρίς συμφραζόμενα, τα αυτόματα στοίβας και τις αντίστοιχες γλώσσες χωρίς συμφραζόμενα.
  • Να εξοικειωθούν με τις μηχανές Turing και τις γνωστότερες κλάσεις πολυπλοκότητας, P, ΝΡ, PSPACE, καθώς και με την έννοια της NP-πληρότητας.

Περιγραφή Μαθήματος

Αλφάβητα και γλώσσες. Πεπερασμένα αυτόματα. Ιδιότητες των πεπερασμένων αυτομάτων και των γλωσσών που δέχονται. Κανονικές εκφράσεις και κανονικές γλώσσες. Ισοδυναμία πεπερασμένων αυτομάτων και κανονικών εκφράσεων. Λήμμα άντλησης για κανονικές γλώσσες. Γραμματικές και η ιεραρχία του Chomsky. Γραμματικές και γλώσσες χωρίς συμφραζόμενα. Αυτόματα στοίβας και λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα. Ισοδυναμία γραμματικών χωρίς συμφραζόμενα και αυτομάτων στοίβας. Η έννοια της υπολογισιμότητας. Mηχανές Turing. Aποφασίσιμες και απαριθμήσιμες γλώσσες. Η θέση των Church-Turing. Eπιλύσιμα και μη επιλύσιμα προβλήματα. Το πρόβλημα του τερματισμού (halting problem). Εισαγωγή στην υπολογιστική πολυπλοκότητα. Χρονική πολυπλοκότητα, η κλάση Ρ, η θέση των Cook-Karp. Αναγωγή και πληρότητα. Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ, αλγοριθμικές συνέπειες NP-πληρότητας. Πολυπλοκότητα χώρου, η κλάση PSPACE, το θεώρημα του Savitch. PSPACE-πλήρη προβλήματα.

Υλικό Μαθήματος

https://e-class.ionio.gr/courses/NOC143/

Προτεινόμενη Βιβλιογραφία

  1. “ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ”, SIPSER MICHAEL, Εκδόσεις ΙΤΕ-ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, ISBN 978-960-524-243-5, 2009
  2. “Στοιχεία θεωρίας υπολογισμού”, Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική, ISBN 978-960-218-397-7, 2005