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 |- !...')
 
Χωρίς σύνοψη επεξεργασίας
 
(14 ενδιάμεσες αναθεωρήσεις από τον ίδιο χρήστη δεν εμφανίζεται)
Γραμμή 1: Γραμμή 1:
* [[Θεωρία Υπολογισμού (MAE745)|Ελληνική Έκδοση]]
{{Course-UnderGraduate-Top-EN}}
{{Menu-OnAllPages-EN}}
=== General ===
=== General ===
{| class="wikitable"
{| class="wikitable"
Γραμμή 24: Γραμμή 28:
! Course Title
! Course Title
|
|
Automata Theory and Formal Languages
Theory of Computation
|-
|-
! Independent Teaching Activities
! Independent Teaching Activities
Γραμμή 46: Γραμμή 50:
|-
|-
! Course Website (URL)
! Course Website (URL)
| http://nlampp-lab.uoi.gr/lab/
| See [https://ecourse.uoi.gr/ eCourse], the Learning Management System maintained by the University of Ioannina.
|}
|}


Γραμμή 55: Γραμμή 59:
! 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:
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:
* 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
Γραμμή 63: Γραμμή 66:
* Introduction of Turing Machines. Standard TM, useful  techniques for TM constructions. Modification of TM. TM as procedure.  
* 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.
* 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:
Upon completion of the course, the students will be able to:
theoretical documentation of problems
* understand theoretical documentation of mathematical problems
• solving  exercises
* solve exercises
• tracking applications
* track further 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 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
! General Competences
Γραμμή 75: Γραμμή 78:
* Implementation- Consolidation
* Implementation- Consolidation
|}
|}
=== Syllabus ===
=== 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
* Introduction and related concepts.
* 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.
* Finite automata and regular expressions, regular languages, closure properties, pumping lemma, algorithms.
* 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.
* Determinism, non-determinism.  
* Introduction of Turing Machines. Standard TM, useful  techniques for TM constructions. Modification of TM. TM as procedure.  
* Pushdown automata and context-free grammars, context-free languages, closure properties, pumping lemma, algorithms.  
* Unsolvability. The Church-Turing Thesis. The Universal TM. The Halting Problem for TM. Computational Complexity. NP-complete problems.
* 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 ===
=== Teaching and Learning Methods - Evaluation ===
{| class="wikitable"
{| class="wikitable"
Γραμμή 90: Γραμμή 100:
|-
|-
! Use of Information and Communications Technology
! Use of Information and Communications Technology
| Yes, use of Natural Language and Mathematical Problems Processing Laboratory
|
* 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
! Teaching Methods
Γραμμή 113: Γραμμή 127:
! Student Performance Evaluation
! Student Performance Evaluation
|
|
Final test
Final test
|}
|}
=== Attached Bibliography ===
=== Attached Bibliography ===
* Βιβλίο [11776]: Στοιχεία θεωρίας υπολογισμού (Elements of Computation Theory), Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
 
* Βιβλίο [257]: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ (Introduction in Computation Theory), SIPSER MICHAEL
<!-- In order to edit the bibliography, visit the webpage -->
<!-- https://wiki.math.uoi.gr/index.php/%CE%A0%CF%81%CF%8C%CF%84%CF%85%CF%80%CE%BF:MAE745-Biblio -->
 
See the official [https://service.eudoxus.gr/public/departments#20 Eudoxus site] or the [https://cloud.math.uoi.gr/index.php/s/62t8WPCwEXJK7oL local repository] of Eudoxus lists per academic year, which is maintained by the Department of Mathematics. Books and other resources, not provided by Eudoxus:
 
{{MAE745-Biblio}}

Τελευταία αναθεώρηση της 12:36, 15 Ιουνίου 2023

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 are 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

Attached Bibliography

See the official Eudoxus site or the local repository of Eudoxus lists per academic year, which is maintained by the Department of Mathematics. Books and other resources, not provided by Eudoxus:

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