Γενικά
| Σχολή
|
Σχολή Θετικών Επιστημών
|
| Τμήμα
|
Τμήμα Μαθηματικών
|
| Επίπεδο Σπουδών
|
Προπτυχιακό
|
| Κωδικός Μαθήματος
|
MAE745
|
| Εξάμηνο
|
7
|
| Τίτλος Μαθήματος
|
Θεωρία Υπολογισμού
|
| Αυτοτελείς Διδακτικές Δραστηριότητες
|
Διαλέξεις (Εβδομαδιαίες Ώρες Διδασκαλίας: 3, Πιστωτικές Μονάδες: 6)
|
| Τύπος Μαθήματος
|
Ειδίκευσης
|
| Προαπαιτούμενα Μαθήματα
|
|
| Γλώσσα Διδασκαλίας και Εξετάσεων
|
Ελληνική
|
| Το Μάθημα Προσφέρεται σε Φοιτητές Erasmus
|
Ναι (στην Αγγλική γλώσσα)
|
| Ηλεκτρονική Σελίδα Μαθήματος (URL)
|
Δείτε το eCourse, την Πλατφόρμα Ασύγχρονης Εκπαίδευσης του Πανεπιστημίου Ιωαννίνων.
|
Μαθησιακά Αποτελέσματα
| Μαθησιακά Αποτελέσματα
|
Σκοπός είναι η κατανόηση των βασικών εννοιών που σχετίζονται με τη Θεωρία Υπολογισμού. Αναλυτικότερα περιλαμβάνει τις ακόλουθες έννοιες:
- Πεπερασμένα αυτόματα, κανονικές εκφράσεις, κανονικές γλώσσες, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι.
- Αιτιοκρατία, μη αιτιοκρατία.
- Αυτόματα στοίβας, γραμματικές χωρίς συμφραζόμενα, γλώσσες χωρίς συμφραζόμενα, ιδιότητες κλειστότητας, λήμμα άντλησης, αλγόριθμοι.
- Κανονική μορφή Chomsky.
- Μηχανές Turing, ισοδυναμία διαφορετικών μοντέλων.
- Αναγνωρίσιμες, διαγνώσιμες, απαριθμήσιμες γλώσσες.
- Το δόγμα των Church-Turing.
- Επιλύσιμα και μη επιλύσιμα προβλήματα, το πρόβλημα αποδοχής για μηχανές Turing (halting problem), το πρόβλημα αντιστοιχίας του Post.
- Οι κλάσεις πολυπλοκότητας P και NP.
Στο μάθημα περιλαμβάνονται ατομικές και ομαδικές ασκήσεις. Στόχος του μαθήματος είναι οι φοιτητές να είναι σε θέση:
- να κατανοήσουν βασικούς τύπους αυτομάτων
- να χειρίζονται κανονικές γλώσσες και μοντέλα υπολογισμού
- να κατανοήσουν επιλύσιμα και μη επιλύσιμα αλγοριθμικά προβλήματα
|
| Γενικές Ικανότητες
|
- Αναζήτηση, ανάλυση και σύνθεση δεδομένων και πληροφοριών, με τη χρήση και των απαραίτητων τεχνολογιών
- Αυτόνομη εργασία
- Ομαδική εργασία
|
Περιεχόμενο Μαθήματος
- Εισαγωγικά και Χρήσιμες Έννοιες
- Κανονικές Γλώσσες, Κανονικές Εκφράσεις
- Πεπερασμένα Αυτόματα, Γλώσσες που δεν είναι Κανονικές
- Γλώσσες Ανεξάρτητες Συμφραζομένων - Αυτόματα Στοίβας
- Μηχανές Turing, Αναγνωρίσιμες και διαγνώσιμες γλώσσες, Απαριθμήσιμες γλώσσες, το δόγμα Church-Turing
- Διαγνωσιμότητα, το Πρόβλημα του Τερματισμού
- Αναγωγές, μη διαγνώσιμες γλώσσες
- Οι κλάσεις πολυπλοκότητας P και NP
|
Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση
| Τρόπος Παράδοσης
|
Πρόσωπο με πρόσωπο
|
| Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών
|
Υποστήριξη Μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας e-course.
|
| Οργάνωση Διδασκαλίας
|
| Δραστηριότητα
|
Φόρτος Εργασίας Εξαμήνου
|
| Διαλέξεις (13Χ3)
|
39
|
| Αυτοτελής Μελέτη
|
78
|
| Επίλυση Ασκήσεων - εργασίες
|
33
|
| Σύνολο Μαθήματος
|
150
|
|
| Αξιολόγηση Φοιτητών
|
Τελική γραπτή εξέταση
|
Δείτε την υπηρεσία Εύδοξος. Συγγράμματα και άλλες πηγές εκτός της υπηρεσίας Εύδοξος:
General
| School
|
School of Science
|
| Academic Unit
|
Department of Mathematics
|
| Level of Studies
|
Undergraduate
|
| Course Code
|
MAE745
|
| Semester
|
7
|
| Course Title
|
Theory of Computation
|
| Independent Teaching Activities
|
Lectures (Weekly Teaching Hours: 3, Credits: 6)
|
| Course Type
|
Special Background
|
| Prerequisite Courses
|
-
|
| Language of Instruction and Examinations
|
Greek
|
| Is the Course Offered to Erasmus Students
|
Yes (in English)
|
| Course Website (URL)
|
See eCourse, the Learning Management System maintained by the University of Ioannina.
|
Learning Outcomes
| Learning outcomes
|
The goal of this course is the deeper understanding of Automata Theory and Languages. During the course a detailed examination of the following topics is done:
- Introductory concepts of Automata, Computability and Complexity as well as basic definitions, basic theorems and inductive proofs
- Finite State Machines and Languages, Finite Automata (Deterministic FA, Nondeterministic FA, FA with Epsilon-Transitions) and their applications, Regular Expressions and Languages, derivation trees. Removing Nondeterminism. Equivalence NFA and NFA with ε-moves. Minimization of DFA, Pumping Lemma
- FA and Grammars. Grammars of Chomsky Hierarchy. Regular Sets (RS). Properties of Regular Languages. RS and FA. Finding a correspondence Regular Expression of a FA. Abilities and disabilities of FA.
- Context-Free Grammars and Languages, Pushdown Automata (Deterministic PDA, Acceptance by Final State, Acceptance by Empty Stack), Properties of Context-Free Languages. Correspondence PDA and Context-Free Languages.
- Introduction of Turing Machines. Standard TM, useful techniques for TM constructions. Modification of TM. TM as procedure.
- Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems.
Upon completion of the course, the students will be able to:
- understand theoretical documentation of mathematical problems
- solve exercises
- track further applications
which are related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Unsolvability, to Computational Complexity and to NP-complete problems.
|
| General Competences
|
- Handle new problems
- Decision making
- Implementation- Consolidation
|
Syllabus
- Introduction and related concepts.
- Finite automata and regular expressions, regular languages, closure properties, pumping lemma, algorithms.
- Determinism, non-determinism.
- Pushdown automata and context-free grammars, context-free languages, closure properties, pumping lemma, algorithms.
- Chomsky normal form.
- Turing machines, equivalence of different models.
- Recursive and recursively enumerable languages.
- Church-Turing thesis.
- Undecidability, the halting problem, Post’s correspondence problem.
- Classes P and NP.
|
Teaching and Learning Methods - Evaluation
| Delivery
|
Face to face
|
| Use of Information and Communications Technology
|
- Projector and interactive board during lectures.
- Course website maintenance.
- Announcements and posting of teaching material (lecture slides and notes, programs).
- Assessment marks via the ecourse platform.
|
| Teaching Methods
|
| Activity
|
Semester Workload
|
| Lectures
|
39
|
| Self study
|
78
|
| Exercises
|
33
|
| Course total
|
150
|
|
| Student Performance Evaluation
|
Final test
|
See the official Eudoxus site. Books and other resources, not provided by Eudoxus: