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

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

Γενικά

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

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

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

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

Γενικές Ικανότητες

Προσαρμογή σε νέες καταστάσεις Λήψη αποφάσεων Υλοποίηση - Εμπέδωση

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

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

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

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

Τρόπος Παράδοσης	Πρόσωπο με πρόσωπο
Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών	Ναι. Χρήση του Εργαστηρίου Επεξεργασίας Φυσικής Γλώσσας και Μαθηματικών προβλημάτων
Οργάνωση Διδασκαλίας	Δραστηριότητα Φόρτος Εργασίας Εξαμήνου Διαλέξεις (13Χ3) 39 Αυτοτελής Μελέτη 78 Επίλυση Ασκήσεων - εργασίες 33 Σύνολο Μαθήματος 150
Αξιολόγηση Φοιτητών	Τελική γραπτή εξέταση

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

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

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