Στόχος Μαθήματος

Ο στόχος του μαθήματος είναι να παρουσιάσει ποια είναι τα είδη των προβλημάτων που μπορούν να επιλύσουν οι σημερινοί, αλλά και οι μελλοντικοί, ηλεκτρονικοί υπολογιστές.

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

Το μάθημα καλύπτει τα εξής θέματα:

• Αλφάβητα και γλώσσες.
• Πεπερασμένα αυτόματα. Ιδιότητες των αυτομάτων και των γλωσσών που δέχονται. Κανονικές εκφράσεις και κανονικές γλώσσες.
• Γραμματικές και ιεραρχία του Chomsky. Γραμματικές και γλώσσες χωρίς συμφραζόμενα.
• Αυτόματα στοίβας και λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα.
• Η έννοια της υπολογισιμότητας. Mηχανές Turing. Η θέση των Church-Turing.
• Eπιλύσιμα και μη επιλύσιμα προβλήματα.
• Υπολογιστική πολυπλοκότητα. 
• Αναγωγή και πληρότητα. Μη-ντετερμινισμός και NP-πληρότητα, σχέση Ρ και ΝΡ.

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

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

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

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

Χρήση ηλεκτρονικών σημειώσεων.

Υποστήριξη μαθησιακής διαδικασίας μέσω της Πλατφόρμας Τηλεκπαίδευσης Ιονίου Πανεπιστημίου (https://opencourses.ionio.gr/courses/DDI188/) 

Γραπτή εξέταση (επίλυση προβλημάτων), 100% τελικής βαθμολογίας.

Οι όροι βαθμολόγησης αναφέρονται ρητά στην ιστοσελίδα του μαθήματος.