Θεωρία Υπολογισμού (MAE745)
Από Wiki Τμήματος Μαθηματικών
Αναθεώρηση ως προς 23:45, 29 Σεπτεμβρίου 2022 από τον Mathwikiadmin (συζήτηση | συνεισφορές) (→Γενικά)
Περιγράμματα Προπτυχιακών Μαθημάτων - Τμήμα Μαθηματικών
Γενικά
| Σχολή | Σχολή Θετικών Επιστημών |
|---|---|
| Τμήμα | Τμήμα Μαθηματικών |
| Επίπεδο Σπουδών | Προπτυχιακό |
| Κωδικός Μαθήματος | MAE745 |
| Εξάμηνο | 7 |
| Τίτλος Μαθήματος | ΘΕΩΡΙΑ ΑΥΤΟΜΑΤΩΝ ΚΑΙ ΤΥΠΙΚΩΝ ΓΛΩΣΣΩΝ |
| Αυτοτελείς Διδακτικές Δραστηριότητες | Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6) |
| Τύπος Μαθήματος | Ειδικού Υποβάθρου |
| Προαπαιτούμενα Μαθήματα | |
| Γλώσσα Διδασκαλίας και Εξετάσεων | Ελληνική |
| Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus | Ναι (στην Αγγλική γλώσσα) |
| Ηλεκτρονική Σελίδα Μαθήματος (URL) | Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων. |
Μαθησιακά Αποτελέσματα
| Μαθησιακά Αποτελέσματα | Σκοπός είναι η βαθύτερη κατανόηση της Θεωρίας Αυτομάτων και Τυπικών Γλωσσών, αναλυτικότερα:
Μετά την ολοκλήρωση του μαθήματος ο φοιτητής / τρια μπορεί να χειριστεί:
Πεπερασμένα Αυτόματα, τα Πεπερασμένα Αυτόματα με Στοιβάδα και τις Μηχανές Turing, τη Μη Επιλυσιμότητα καθώς και την Πολυπλοκότητα των Υπολογισμών και προβλήματα NP-πληρότητας. |
|---|---|
| Γενικές Ικανότητες |
|
Περιεχόμενο Μαθήματος
Εξοικείωση με:
- Τις Αφηρημένες Μηχανές και Γλώσσες: Εισαγωγή, η Στοιχειώδης Μηχανή (ΣΜ), Μηχανές Πεπερασμένων Καταστάσεων (ΜΠΚ). Πεπερασμένο Αυτόματο (ΠΑ), Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΑΠΑ), Μη Αιτιοκρατικό Πεπερασμένο Αυτόματο (ΜΑΠΑ), Δένδρα Αποδοχής (ΔΑ), Πεπερασμένα Αυτόματα με ε-Μεταβάσεις (ΜΑΠΑΕΜ), Ισοδυναμία ΜΑΠΑ και ΜΑΠΑΕΜ, Ελαχιστοποίηση ενός ΑΠΑ, Θεώρημα της Επαναληπτικότητας
- Τα Πεπερασμένα Αυτόματα και Γραμματικές, Γραμματικές της Ιεραρχίας Chomsky, Κανονικά Σύνολα (ΚΣ), Κανονικά Σύνολα και Πεπερασμένα Αυτόματα, Εύρεση της Κανονικής Έκφρασης ενός ΠΑ, Ικανότητες και Ανεπάρκειες των ΠΑ
- Τα Πεπερασμένα Αυτόματα με Στοιβάδα (ΠΑΣ), Μη Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΜΑΠΑΣ), Αιτιοκρατικά Πεπερασμένα Αυτόματα με Στοιβάδα (ΑΠΑΣ), Αποδοχή με Κενή Στοιβάδα, Ισοδυναμία ΠΑΣ και Γλωσσών Ανεξάρτητων Συμφραζομένων
- Τις Μηχανές Turing (ΜΤ), Εισαγωγή, Μαθηματική Περιγραφή, Χρήσιμα Τεχνάσματα για την Κατασκευή της ΜΤ, Τροποποιήσεις της ΜΤ, η ΜΤ ως Διαδικασία
- Τη μη Επιλυσιμότητα, η Θέση των Church-Turing, η Καθολική ΜΤ, το Πρόβλημα του Τερματισμού.Υπολογιστική Πολυπλοκότητα, NP-πληρότητα.
Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση
| Τρόπος Παράδοσης | Πρόσωπο με πρόσωπο | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών | Ναι. Χρήση του Εργαστηρίου Επεξεργασίας Φυσικής Γλώσσας και Μαθηματικών προβλημάτων | ||||||||||
| Οργάνωση Διδασκαλίας |
| ||||||||||
| Αξιολόγηση Φοιτητών | Τελική γραπτή εξέταση |
Συνιστώμενη Βιβλιογραφία
Δείτε την υπηρεσία Εύδοξος ή το τοπικό αποθετήριο του Τμήματος Μαθηματικών για τα παρεχόμενα συγγράμματα ανά ακαδημαϊκό έτος. Συγγράμματα και άλλες πηγές εκτός της υπηρεσίας Εύδοξος:
- [11776]: Στοιχεία θεωρίας υπολογισμού, Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
- [257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, SIPSER MICHAEL.