Theory of Computation and Algorithms
| Title | Θεωρία Υπολογισμών και Αλγορίθμων / Theory of Computation and Algorithms |
| Code | 048 |
| Faculty | Engineering |
| School | Electrical and Computer Engineering |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Spring |
| Coordinator | Anastasios Ntelopoulos |
| Common | No |
| Status | Active |
| Course ID | 600000997 |
Programme of Study: Electrical and Computer Engineering
Registered students: 0
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| ELECTRICAL ENERGY | Elective Courses | 8 | 4 | 4 |
| ELECTRONICS AND COMPUTER ENGINEERING | Elective Courses | 8 | 4 | 4 |
| TELECOMMUNICATIONS | Elective Courses | 8 | 4 | 4 |
| Academic Year | 2026 – 2027 |
| Class Period | Spring |
| Faculty Instructors | |
| Weekly Hours | 4 |
| Class ID | 600309793
|
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/600309793
- eLearning: https://elearning.auth.gr/course/view.php?id=11968
Language of Instruction
- Greek (Instruction, Examination)
Learning Outcomes
To understand the hierarchy of problems and the associated hierarchy of algorithms.
To learn how algorithms correspond to formal computing machines (finite automata, pushdown automata, Turing machines) while problems correspond to formal languages (regular, context free, recursive)
To be able to study the computational complexity of various key algorithms and classify problems on the basis of their algorithmic complexity (classes P, NP, NP complete, EXP).
To study the issues of undecidability.
General Competences
- Retrieve, analyse and synthesise data and information, with the use of necessary technologies
Course Content (Syllabus)
1. Relations, alphabets, strings, languages.
2. Computational complexity.
3. Regular expressions and languages.
4. Finite automata.
5. Context free grammars and languages.
6. Pushdown automata.
7. Turing machines.
8. Recursive languages.
9. Decidability.
10. P, NP, NP complete, EXP problems.
Educational Material Types
- Slide presentations
- Book
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 104 | 3.5 | ✓ | ||
| Exams | 16 | 0.5 | ✓ | ||
| Total | 120 | 4 |
Student Assessment
Description
Evaluation is based on the final examination
Bibliography
Course Bibliography (Eudoxus)
1. Εισαγωγή στη Θεωρία Υπολογισμού
Κωδικός Βιβλίου στον Εύδοξο: 257
Έκδοση: 1η έκδ./2009
Συγγραφείς: Sipser Michael
ISBN: 978-960-524-243-5
Διαθέτης (Εκδότης): Ιδρυμα Τεχνολογίας και ΄Ερευνας –Παν/κές Εκδόσεις.
2. Στοιχεία Θεωρίας Υπολογισμού
Κωδικός Βιβλίου στον Εύδοξο: 11776
Έκδοση: 1η /2005
Συγγραφείς: Θεοχάρης Lewis Harry R., Παπαδημητρίου Χρίστος.
ISBN: 978-960-218-397-7
Διαθέτης (Εκδότης): Κριτική Α.Ε.
Additional bibliography for study
Εκτός από την επιλογή των βιβλίων που προτείνονται, το μάθημα υποστηρίζεται από συνοπτικές σημειώσεις.
Last Update
14-09-2023
