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: 339
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| GENIKĪ KATEUTHYNSĪ | Compulsory Course | 2 | 1 | 6 |
| Academic Year | 2017 – 2018 |
| Class Period | Spring |
| Faculty Instructors |
|
| Weekly Hours | 5 |
| Class ID | 600104709
|
Class Schedule
| Building | Φυσικομαθηματική (Δ) |
| Floor | Ισόγειο |
| Hall | ΑΙΘΟΥΣΑ Δ22 (190) |
| Calendar | Παρασκευή 09:00 έως 12:00 |
| Building | Φυσικομαθηματική (Δ) |
| Floor | Όροφος 1 |
| Hall | ΑΜΦΙΘΕΑΤΡΟ Α31 "ΟΙΚΟΝΟΜΟΥ" (195) |
| Calendar | Δευτέρα 13:00 έως 15:00 |
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/600104709
- At the Website of the School: 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
The students who will attend the course are expected to
• understand the notion of computation and the capabilities of our computing machines
• know the principles and the foundations of the Computer Science
• digest material upon which other subjects are founded, such as the Theory of Programming Languages and the Algorithmics
• cultivate the ability to develop formal and mathematically rigorous reasoning
• know open problems and applications of the Theory of Computation in the science and the technology
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
13-06-2016
