Στο μάθημα αυτό αναλύεται η έννοια του υπολογισμού και των μηχανών ή συσκευών που τον επιτυγχάνουν. Το κύριο ερώτημα είναι: «τί μπορούμε να υπολογίσουμε και τί όχι, ανάλογα με την συσκευή που έχουμε στη διάθεσή μας;» Η ανάπτυξη γίνεται σε τρία μέρη: τα δύο πρώτα είναι απλές συσκευές αλλά μη-τετριμμένες, και πρακτικώς πολύ χρήσιμες. Στο τρίτο μέρος αναλύονται οι συσκευές με «πλήρη» υπολογιστική ισχύς. Το μάθημα είναι ιδιαίτερα «εννοιοκεντρικό», καθώς εισάγει μια σειρά από θεμελιακές έννοιες, εξειδικευμένες σε αυτό το θέμα – το θέμα του «υπολογισμού».
Περιεχόμενα:
Εισαγωγή (Γενική εισαγωγή, Τρία κεντρικά παραδείγματα τρόπων υπολογισμού, «Συμβολικός» τρόπος υπολογισμού)
Μέρος (1) Oμαλές γραμματικές και πεπερασμένα αυτόματα (Ισοδυναμία αιτιοκρατικών και αναιτιοκρατικών αυτομάτων, θ. «κλειστότητας», λήμμα άντλησης, θ. Myhill-Nerode. θ. διαγνωσιμότητας, Ομαλές εκφράσεις)
Μέρος (2) Ασυμφραστικές γραμματικές και στοιβακτικά αυτόματα (ανάλυση και στοιβακτικά αυτόματα, αιτιοκρατικές εκδοχές, Μορφή Chomsky και διαγνωσιμότητα, Κλειστότητα και «άντληση»)
Μέρος (3) Μηχανές Turing & άλλοι τρόποι υπολογισμού (Διάφορα είδη προγραμματισμού, θ. ισοδυναμίας, ανεπίλυτα προβλήματα, θ. Rice, θ. Gödel )
Μαθησιακοί στόχοι:
Το μάθημα είναι «εννοιοκεντρικό», και εστιάζει στις έννοιες που συγκρότησαν την θεωρία υπολογισμού και οδήγησαν στην ανάπτυξη της σχετικής τεχνολογίας.
Οι ικανότητες που επιδιώκουμε να αναπτύξουν οι φοιτητές είναι οι εξής:
να κατέχουν τις βασικές έννοιες της θεωρίας υπολογισμού: αλφάβητα, γλώσσες, ιδεατές μηχανές, σύνταξη και σημασιολογία.
να αναγνωρίζουν τις υπολογιστικές διαδικασίες ως πεπερασμένες διαδικασίες με αρχή, βήματα και τερματισμό, οδηγημένες από σαφείς και πεπερασμένες οδηγίες.
να είναι σε θέση να ορίζουν και να χειρίζονται τυπικές (συμβολικές) γλώσσες, ιδίως των απλών μορφών (ομαλές και ασυμφραστικές).
να εντάσσουν απλά υπολογιστικά προβλήματα στις παραπάνω βασικές κατηγορίες γλωσσών.
να μπορούν να χειρίζονται τα εργαλεία ανάλυσης τυπικών γλωσσών (διαγράμματα μεταβάσεων, συντακτική ανάλυση, συντακτικά δένδρα).
Αξιολόγηση:
Λεπτομέρειες για την βαθμολόγηση του μαθήματος περιέχονται στην ιστοσελίδα του μαθήματος
Τα μαθήματα του Τμήματος Επιστήμης Υπολογιστών κωδικοποιούνται με τα γράμματα "ΗΥ" και με τρία ψηφία. Το πρώτο ψηφίο δηλώνει το έτος κατά το οποίο συνήθως παρακολουθείται το μάθημα, το δε δεύτερο την επιστημονική περιοχή του μαθήματος:
Πρώτο Ψηφίο
Κανονικό Έτος Παρακολούθησης
1,2,3,4
Πρώτο, Δεύτερο, Τρίτο, Τέταρτο
5,6
Μεταπτυχιακά μαθήματα
7,8,9
Ειδικά θέματα
Δεύτερο Ψηφίο
Επιστημονική Περιοχή
0
Εισαγωγικά - Γενικά
1
Υπόβαθρο (Μαθηματικά, Φυσική)
2
Υλικό και Συστήματα Υπολογιστών
3
Τηλεπικοινωνίες και Δίκτυα
4,5
Συστήματα Λογισμικού και Εφαρμογές
6
Πληροφοριακά Συστήματα
7
Υπολογιστική Όραση και Ρομποτική
8
Αλγοριθμική και Θεωρία Υπολογισμού
9
Ειδικές Εργασίες
Ακολουθούν συνοπτικοί κατάλογοι κατά κατηγορίες των μαθημάτων του προγράμματος βασικών σπουδών του Τμήματος Επιστήμης Υπολογιστών του Πανεπιστημίου Κρήτης. Μαθήματα των οποίων οι κωδικοί αρχίζουν με "ΜΕΜ" ή "ΦΥΣ" διδάσκονται από το Τμήμα Μαθηματικών Εφαρμοσμένων Μαθηματικών ή το Φυσικό αντιστοίχως και αναφέρονται με τους οικείους κωδικούς. Τα προαπαιτούμενα που αναφέρονται μέσα σε παρενθέσεις συνιστώνται έντονα, αλλά δεν είναι υποχρεωτικά.