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

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

Γενικά

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

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

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

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

Εξοικείωση με:

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

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

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

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

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

Ναι. Χρήση του Εργαστηρίου Επεξεργασίας Φυσικής Γλώσσας και Μαθηματικών προβλημάτων

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

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

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

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

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

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

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