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

Το μάθημα επιδιώκει την εμπέδωση από την πλευρά των φοιτητριών και φοιτητών της έννοιας του υπολογισμού, καθώς και των σημαντικότερων μοντέλων υπολογισμού.

          Με την επιτυχή ολοκλήρωση των σπουδών στο μάθημα οι φοιτήτριες και φοιτητές θα είναι σε θέση:

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

Το μάθημα απευθύνεται σε φοιτήτριες και φοιτητές του δεύτερου έτους σπουδών. Καλύπτει τα εξής θέματα:

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

1. “Εισαγωγή στη Θεωρία Υπολογισμού”, Sipser Michael, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-558-0, 2019
2. “Στοιχεία θεωρίας υπολογισμού”, Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική ΑΕ, ISBN 978-960-218-397-7, 2005