Σύστημα Ηλεκτρονικής Μάθησης Πανεπιστημίου Κρήτης

Το μάθημα "HY-280 Θεωρία Υπολογισμού" καλύπτει βασικές έννοιες και θεμελιώδη ζητήματα της θεωρίας υπολογισμού, εξετάζοντας την υπολογιστική ισχύ και τα όρια των διαφόρων μοντέλων υπολογισμού. Τα κεντρικά ερωτήματα που θα μας απασχολήσουν είναι:

• Τι μπορούμε να υπολογίσουμε;
• Πόσο εφικτοί είναι οι υπολογισμοί;

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

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