THEORY OF COMPUTATION
| Title | ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ / THEORY OF COMPUTATION |
| Code | NCO-02-05 |
| Faculty | Sciences |
| School | Informatics |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Spring |
| Coordinator | Panagiotis Katsaros |
| Common | No |
| Status | Active |
| Course ID | 40002922 |
Programme of Study: PPS-Tmīma Plīroforikīs (2019-sīmera)
Registered students: 463
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| GENIKĪ KATEUTHYNSĪ | Compulsory Course | 2 | 1 | 6 |
| Academic Year | 2020 – 2021 |
| Class Period | Spring |
| Faculty Instructors |
|
| Weekly Hours | 5 |
| Class ID | 600180146
|
Course Type 2016-2020
- Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600180146
- eLearning (Moodle): https://elearning.auth.gr/course/view.php?id=8083
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
- Greek (Instruction, Examination)
Prerequisites
General Prerequisites
Some basic knowledge of Discrete Mathematics (set theory, relations, functions, proof techniques) is desirable. This basic knowledge is covered briefly in the introduction of the course.
Learning Outcomes
Cognitive: The main aim of the course is the students to know the foundations and principles of computer science and to understand the notion of computation and the capabilities/limitations of our computing machines.
Skills: Students are expected to be able to develop formally defined and mathematically substantiated reasoning, for the equivalence of mathematical models of computation and for algorithms to compute formal languages of diverse complexity classes and for problems that are not computable.
General Competences
- Apply knowledge in practice
- Adapt to new situations
- Make decisions
- Work autonomously
- Be critical and self-critical
- Advance free, creative and causative thinking
Course Content (Syllabus)
Introduction, Regular Languages: Regular Expressions and Finite Automata, Context-Free Languages: Grammars and Pushdown Automata, Turing Machines, Undecidability
Keywords
Languages, Grammars, Automata, Undecidability
Educational Material Types
- Slide presentations
- Interactive excersises
- Book
Use of Information and Communication Technologies
Use of ICT
- Use of ICT in Course Teaching
- Use of ICT in Communication with Students
Description
The course material is offered in Internet through the (moodle) software e-learning platform, which is also used for communicating with the students. The lectures take place by audiovisual teaching aids (electronic slides).
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 52 | ✓ | ✓ | ||
| Reading Assigment | 112 | ✓ | |||
| Tutorial | 13 | ✓ | ✓ | ||
| Exams | 3 | ✓ | ✓ | ||
| Total | 180 |
Student Assessment
Description
The students are evaluated based on their answers to a mandatory interactive test (10 %) and their performance in the final written exam (90 %). Their study is successful if the weighted average is a promotable grade (5). The evaluation criteria, the mid-term exam and the results for the students' performance will be announced in the (moodle) software e-learning platform.
Student Assessment methods
- Written Exam with Multiple Choice Questions (Formative, Summative)
- Written Exam with Short Answer Questions (Formative, Summative)
- Written Exam with Problem Solving (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
1. H.R. Lewis, Χ. Παπαδημητρίου, "Στοιχεία θεωρίας υπολογισμού", 1η έκδοση/2005, Εκδόσεις Κριτική, ISBN: 978-960-218-397-7
Κωδικός Βιβλίου στον Εύδοξο: 11776
2. M. Sipser, "Εισαγωγή στη Θεωρία Υπολογισμού", 1η έκδοση/2009, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN: 978-960-524-243-5
Κωδικός Βιβλίου στον Εύδοξο: 257
Additional bibliography for study
1. Π. Κατσαρός, "Θεωρία Υπολογισμού και Εφαρμογές", 2015, Αποθετήριο Κάλλιπος, https://repository.kallipos.gr/handle/11419/5744
2. E. Rich, "Automata, Computability and Complexity: Theory and Applications", 1st edition/2007, Prentice Hall, ISBN: 978-0132288064
3. J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation", 3rd edition/2006, Prentice Hall, ISBN: 978-0321455369
Last Update
12-10-2020
