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

Περιγράμματα Προπτυχιακών Μαθημάτων - Τμήμα Μαθηματικών

Γενικά

Σχολή	Σχολή Θετικών Επιστημών
Τμήμα	Τμήμα Μαθηματικών
Επίπεδο Σπουδών	Προπτυχιακό
Κωδικός Μαθήματος	MAE745
Εξάμηνο	7
Τίτλος Μαθήματος	Θεωρία Υπολογισμού
Αυτοτελείς Διδακτικές Δραστηριότητες	Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
Τύπος Μαθήματος	Ειδικού Υποβάθρου
Προαπαιτούμενα Μαθήματα
Γλώσσα Διδασκαλίας και Εξετάσεων	Ελληνική
Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus	Ναι (στην Αγγλική γλώσσα)
Ηλεκτρονική Σελίδα Μαθήματος (URL)	Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.

Μαθησιακά Αποτελέσματα

Μαθησιακά Αποτελέσματα	Σκοπός είναι η κατανόηση με τις βασικές έννοιες που σχετίζονται με τη Θεωρία Υπολογισμού. Αναλυτικότερα περιλαμβάνει τις ακόλουθες έννοιες: Πεπερασμένα αυτόματα, κανονικές εκφράσεις, κανονικές γλώσσες, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι. Αιτιοκρατία, μη αιτιοκρατία. Aυτόματα στοίβας, γραμματικές χωρίς συμφραζόμενα, γλώσσες χωρίς συμφραζόμενα, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι. Κανονική μορφή Chomsky. Mηχανές Turing, ισοδυναμία διαφορετικών μοντέλων. Αναγνωρίσιμες, διαγνώσιμες, απαριθμήσιμες γλώσσες. Tο δόγμα των Church-Turing. Eπιλύσιμα και μη επιλύσιμα προβλήματα, το πρόβλημα αποδοχής για μηχανές Turing (halting problem), το πρόβλημα αντιστοιχίας του Post. Οι κλάσεις πολυπλοκότητας P και NP. Στο μάθημα περιλαμβάνονται ατομικές και ομαδικές ασκήσεις. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση: να κατανοήσουν βασικούς τύπους αυτομάτων να χειρίζονται κανονικές γλώσσες και μοντέλα υπολογισμού να κατανοήσουν επιλύσιμα και μη επιλύσιμα αλγοριθμικά προβλήματα
Γενικές Ικανότητες	Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών Αυτόνομη εργασία Ομαδική εργασία

Περιεχόμενο Μαθήματος

Εισαγωγικά και Χρήσιμες Έννοιες
Κανονικές Γλώσσες, Κανονικές Εκφράσεις
Πεπερασμένα Αυτόματα, Γλώσσες που δεν είναι Κανονικές
Γλώσσες Ανεξάρτητες Συμφραζομένων - Αυτόματα Στοίβας
Μηχανές Turing, Αναγνωρίσιμες και διαγνώσιμες γλώσσες, Απαριθμήσιμες γλώσσες, το δόγμα Church-Turing
Διαγνωσιμότητα, το Πρόβλημα του Τερματισμού
Αναγωγές, μη διαγνώσιμες γλώσσες
Οι κλάσεις πολυπλοκότητας P και NP

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παράδοσης

Πρόσωπο με πρόσωπο

Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών

Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-course.

Οργάνωση Διδασκαλίας

Δραστηριότητα	Φόρτος Εργασίας Εξαμήνου
Διαλέξεις (13Χ3)	39
Αυτοτελής Μελέτη	78
Επίλυση Ασκήσεων - εργασίες	33
Σύνολο Μαθήματος	150

Αξιολόγηση Φοιτητών

Τελική γραπτή εξέταση

Συνιστώμενη Βιβλιογραφία

Δείτε την υπηρεσία Εύδοξος ή το τοπικό αποθετήριο του Τμήματος Μαθηματικών για τα παρεχόμενα συγγράμματα ανά ακαδημαϊκό έτος. Συγγράμματα και άλλες πηγές εκτός της υπηρεσίας Εύδοξος:

[11776]: Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
[257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, SIPSER MICHAEL.