Theory of Computation (MAE745): Διαφορά μεταξύ των αναθεωρήσεων
Από Wiki Τμήματος Μαθηματικών
(Νέα σελίδα με '=== General === {| class="wikitable" |- ! School | School of Science |- ! Academic Unit | Department of Mathematics |- ! Level of Studies | Undergraduate |- ! Course Code | MAE745 |- ! Semester | 7 |- ! Course Title | Automata Theory and Formal Languages |- ! Independent Teaching Activities | Lectures (Weekly Teaching Hours: 3, Credits: 6) |- ! Course Type | Special Background |- ! Prerequisite Courses | - |- ! Language of Instruction and Examinations | Greek |- !...') |
|||
Γραμμή 64: | Γραμμή 64: | ||
* Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems. | * Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems. | ||
After completing the course the student can handle: | After completing the course the student can handle: | ||
* theoretical documentation of problems | |||
* solving exercises | |||
* tracking applications | |||
which related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Unsolvability , to Computational Complexity and to NP-complete problems. | which related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Unsolvability , to Computational Complexity and to NP-complete problems. | ||
|- | |- | ||
Γραμμή 75: | Γραμμή 75: | ||
* Implementation- Consolidation | * Implementation- Consolidation | ||
|} | |} | ||
=== Syllabus === | === Syllabus === | ||
* Introductory concepts of Automata , Computability and Complexity as well as basic definitions, basic theorems and inductive proofs | * Introductory concepts of Automata , Computability and Complexity as well as basic definitions, basic theorems and inductive proofs |
Αναθεώρηση της 18:26, 29 Ιουνίου 2022
General
School |
School of Science |
---|---|
Academic Unit |
Department of Mathematics |
Level of Studies |
Undergraduate |
Course Code |
MAE745 |
Semester |
7 |
Course Title |
Automata Theory and Formal Languages |
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) | http://nlampp-lab.uoi.gr/lab/ |
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 are done:
After completing the course the student can handle:
which related to Finite Automata, Pushdown Automata, and Turing Machines as well as to Unsolvability , to Computational Complexity and to NP-complete problems. |
---|---|
General Competences |
|
Syllabus
- 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.
Teaching and Learning Methods - Evaluation
Delivery |
Face to face | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Use of Information and Communications Technology | Yes, use of Natural Language and Mathematical Problems Processing Laboratory | ||||||||||
Teaching Methods |
| ||||||||||
Student Performance Evaluation |
Final test |
Attached Bibliography
- Βιβλίο [11776]: Στοιχεία θεωρίας υπολογισμού (Elements of Computation Theory), Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
- Βιβλίο [257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (Introduction in Computation Theory), SIPSER MICHAEL