Θεωρία Υπολογισμού και Πολυπλοκότητα

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• H θεωρία υπολογισμού περιέχει τρεις κεντρικές περιοχές: τα αυτόματα, την υπολογισιμότητα, και την πολυπλοκότητα. Η βασική ερώτηση που συνδέει τις περιοχές αυτές είναι: Ποιες είναι οι θεμελιώδεις δυνατότητες και ποιοι οι εγγενείς περιορισμοί των υπολογιστών; Η ερώτηση αυτή ερμηνεύεται διαφορετικά σε κάθε μία από τις τρεις παραπάνω περιοχές και ανάλογα διαμορφώνονται και οι σχετικές απαντήσεις. Στη θεωρία υπολογισιμότητας, ο στόχος είναι να χαρακτηριστούν τα διάφορα προβλήματα ως επιλύσιμα ή μη. Στη θεωρία πολυπλοκότητας στόχος είναι η ταξινόμηση των επιλύσιμων προβλημάτων σε εύκολα και δύσκολα και το κεντρικό ερώτημα είναι: Τι είναι αυτό που κάνει κάποια προβλήματα υπολογιστικώς δύσκολα και κάποια άλλα εύκολα; Ένα από τα σημαντικότερα επιτεύγματα της θεωρίας πολυπλοκότητας είναι η ένα κομψό σύστημα ταξινόμησης των προβλημάτων με βάση την υπολογιστική τους δυσκολία. Στο πλαίσιο του συγκεκριμένου μαθήματος, εστιάζουμε, ουσιαστικά, στη θεωρία αυτομάτων η οποία ασχολείται με τους ορισμούς και τις ιδιότητες των μαθηματικών μοντέλων της υπολογιστικής επιστήμης. Τα μοντέλα αυτά χρησιμοποιούνται στην πράξη σε αρκετές περιοχές της επιστήμης των υπολογιστών. Για παράδειγμα, τα πεπερασμένα αυτόματα χρησιμοποιούνται στην επεξεργασία κειμένου, στο σχεδιασμό μεταϕραστών και στο σχεδιασμό υλικού (hardware). Ένα άλλο μοντέλο, οι γραμματικές χωρίς συμφραζόμενα, χρησιμοποιείται στη σχεδίαση γλωσσών προγραμματισμού και στην τεχνητή νοημοσύνη. Η θεωρία αυτομάτων είναι ιδιαίτερα ενδιαφέρουσα περιοχή που επιτρέπει την εξοικείωση με τυπικούς ορισμούς της υπολογιστικής, με εξαιρετική χρησιμότητα στις θεωρίες της υπολογισιμότητας και της πολυπλοκότητας, που απαιτούν σαϕή ορισμό του υπολογιστή. Τα άτομα που συμμετέχουν συστηματικά στις δραστηριότητες του μαθήματος και ολοκληρώνουν επιτυχώς την παρακολούθησή του:

• διαθέτουν αποδεδειγμένη γνώση και κατανόηση για τους ορισμούς και τις ιδιότητες των μαθηματικών μοντέλων της υπολογιστικής επιστήμης (όπως π.χ., πεπερασμένα αυτόματα, αυτόματα στοίβας, μηχανές Turing) καθώς και για αντίστοιχες μεθόδους πεπερασμένης αναπαράστασης σχετικών κλάσεων προβλημάτων (όπως, π.χ., κανονικές εκφράσεις, γραμματικές, αλγόριθμοι) και, επομένως, είναι σε θέση να παρακολουθούν τις σύγχρονες εξελίξεις στην αιχμή του γνωστικού τους πεδίου

• είναι σε θέση να χρησιμοποιούν τη γνώση και την κατανόηση που απέκτησαν με τρόπο που δείχνει επαγγελματική προσέγγιση της εργασίας ή του επαγγέλματός τους και διαθέτουν ικανότητες που αποδεικνύονται με τη χρήση μαθηματικών μοντέλων της υπολογιστικής επιστήμης για μελέτη και επίλυση προβλημάτων στο πλαίσιο του γνωστικού τους πεδίου
• διαθέτουν την ικανότητα να συγκεντρώνουν και να ερμηνεύουν συναφή στοιχεία (κατά κανόνα εντός του γνωστικού τους πεδίου) για να διαμορφώνουν κρίσεις που περιλαμβάνουν προβληματισμό σε συναφή κοινωνικά, επιστημονικά ή ηθικά ζητήματα
• είναι σε θέση να κοινοποιούν πληροφορίες, ιδέες, προβλήματα και λύσεις τόσο σε ειδικευμένο όσο και σε μη-εξειδικευμένο κοινό
• έχουν αναπτύξει εκείνες τις δεξιότητες απόκτησης γνώσεων, που τους χρειάζονται για να συνεχίσουν σε περαιτέρω σπουδές με μεγάλο βαθμό αυτονομίας
• αποκτούν εξοικείωση με τον "υπολογιστικό τρόπο σκέψης" (computational thinking)

Ειδικότερα, τα άτομα που συμμετέχουν συστηματικά στις δραστηριότητες του μαθήματος και ολοκληρώνουν επιτυχώς την παρακολούθησή του:

1. γνωρίζουν ορισμούς και ιδιότητες των μαθηματικών μοντέλων της υπολογιστικής επιστήμης και αντιστοιχους τρόπους πεπερασμένης αναπαράστασης σχετικών κλάσεων προβλημάτων
2. κατανοούν σχετικά προβλήματα μοντελοποίησης ανάλογα με την υπολογιστική δυσκολία τους
3. εφαρμόζουν αφαιρετικές προσεγγίσεις και μεθόδους μοντελοποίησης για την επίλυση αλγοριθμικών προβλημάτων ανάλογα με την υπολογιστική τους δυσκολία, δηλ., τους υπολογιστικούς πόρους που απαιτούνται για την επίλυσή τους
4. αναλύουν προβλήματα/ερωτήματα με στόχο την κατανόηση της δομής τους και των συστατικών τους μερών
5. συνθέτουν λύσεις για τα προβλήματα αυτά καθοδηγούμενοι από την κλάση στην οποία εντάσσονται με βάση την υπολογιστική τους δυσκολία
6. αξιολογούν τα ευρήματα (λύσεις ή αποτελέσματα δυσκολίας εντοπισμού βέλτιστης λύσης ή αποτελέσματα μη επιλυσιμότητας) μέσω ανάλυσης
7. αποκτούν εξοικείωση με τον "υπολογιστικό τρόπο σκέψης" (computational thinking)

Περιεχόμενο (ύλη)

H θεωρία υπολογισμού περιέχει τρεις κεντρικές περιοχές: τα αυτόματα, την υπολογισιμότητα, και την πολυπλοκότητα. Η βασική ερώτηση που συνδέει τις περιοχές αυτές είναι: Ποιες είναι οι θεμελιώδεις δυνατότητες και ποιοι οι εγγενείς περιορισμοί των υπολογιστών;

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

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

Στη θεωρία πολυπλοκότητας στόχος είναι η ταξινόμηση των επιλύσιμων προβλημάτων σε εύκολα και δύσκολα και το κεντρικό ερώτημα είναι: Τι είναι αυτό που κάνει κάποια προβλήματα υπολογιστικώς δύσκολα και κάποια άλλα εύκολα; Ένα από τα σημαντικότερα επιτεύγματα της θεωρίας πολυπλοκότητας είναι η ένα κομψό σύστημα ταξινόμησης των προβλημάτων με βάση την υπολογιστική τους δυσκολία.

Στο πλαίσιο του συγκεκριμένου μαθήματος, εστιάζουμε, ουσιαστικά, στη θεωρία αυτομάτων η οποία ασχολείται με τους ορισμούς και τις ιδιότητες των μαθηματικών μοντέλων της υπολογιστικής επιστήμης. Τα μοντέλα αυτά χρησιμοποιούνται στην πράξη σε αρκετές περιοχές της επιστήμης των υπολογιστών. Για παράδειγμα, τα πεπερασμένα αυτόματα χρησιμοποιούνται στην επεξεργασία κειμένου, στο σχεδιασμό μεταϕραστών και στο σχεδιασμό υλικού (hardware). Ένα άλλο μοντέλο, οι γραμματικές χωρίς συμφραζόμενα, χρησιμοποιείται στη σχεδίαση γλωσσών προγραμματισμού και στην τεχνητή νοημοσύνη. Η θεωρία αυτομάτων είναι ιδιαίτερα ενδιαφέρουσα περιοχή που επιτρέπει την εξοικείωση με τυπικούς ορισμούς της υπολογιστικής, με εξαιρετική χρησιμότητα στις θεωρίες της υπολογισιμότητας και της πολυπλοκότητας, που απαιτούν σαϕή ορισμό του υπολογιστή.

Η εξέλιξη του μαθήματος πραγματοποιείται με βάση το εξής πρόγραμμα ενοτήτων διαλέξεων (ορισμοί, ιδιότητες, αποδείξεις) και αντίστοιχων φροντιστηρίων (επίλυση ασκήσεων):

Στοιχεία Θεωρίας Συνόλων

Τεχνικές απόδειξης

Σύνολα, πράξεις με σύνολα, αλφάβητα, συμβολοσειρές, γλώσσες, πράξεις με γλώσσες

Κανονικές γλώσσες

Ορισμός

Υπολογιστικό μοντέλο: πεπερασμένα αυτόματα

Τρόπος πεπερασμένης αναπαράστασης: κανονικές εκφράσεις

Ισδουναμία πεπερασμένων αυτομάτων - κανονικών εκφράσεων

Κλειστότητα στην κλάση των κανονικών γλωσσών

Γλώσσες που δεν είναι κανονικές

Γλώσσες χωρίς συμφραζόμενα

Υπολογιστικό μοντέλο: (μη ντετερμινιστικά) αυτόματα στοίβας

Τρόπος πεπερασμένης αναπαράστασης: γραμματικές χωρίς συμφραζόμενα

Ισοδυναμία (μη ντετερμινιστικών) αυτομάτων στοίβας - γραμματικών χωρίς συμφραζόμενα

Κλειστότητα στην κλάση των γλωσσών χωρίς συμφραζόμενα

Γλώσσες που δεν είναι χωρίς συμφραζόμενα

Η θέση των Church-Turing

Υπολογιστικό μοντέλο: μηχανή Turing

Τρόπος πεπερασμένης αναπαράστασης: αλγόριθμοι

Αξιολόγηση

Γραπτή εξέταση κατά την εξεταστική περίοδο Φεβρουαρίου ή Ιουνίου (για άτομα επί διπλώματι) ή την αντίστοιχη Σεπτεμβρίου

Βιβλιογραφία

ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, Michael Sipser (Κωδικός Βιβλίου στον Εύδοξο: 257) ΣΤΟΙΧΕΙΑ ΘΕΩΡΙΑΣ ΥΠΟΛΟΓΙΣΜΟΥ, Harry R. Lewis, Χρίστος Χ. Παπαδημητρίου (Κωδικός Βιβλίου στον Εύδοξο: 11776)

-Συναφή επιστημονικά περιοδικά:

Theoretical Computer Science, Elsevier

Theory of Computing Systems, Springer