Theory of Computation and Algorithms
| Title | ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΩΝ ΚΑΙ ΑΛΓΟΡΙΘΜΩΝ / Theory of Computation and Algorithms |
| Code | ΗΥ2802 |
| Faculty | Engineering |
| School | Electrical and Computer Engineering |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Winter |
| Coordinator | Anastasios Ntelopoulos |
| Common | No |
| Status | Active |
| Course ID | 20000603 |
| Academic Year | 2018 – 2019 |
| Class Period | Winter |
| Faculty Instructors | |
| Weekly Hours | 4 |
| Class ID | 600130526
|
Class Schedule
| Building | Πολυτεχνείο - πτέρυγα Γ (ΤΗΜΜΥ & Τοπογράφων Μηχ.) |
| Floor | Όροφος 1 |
| Hall | Α7 (4) |
| Calendar | Δευτέρα 18:00 έως 20:00 |
| Building | Πολυτεχνείο - πτέρυγα Γ (ΤΗΜΜΥ & Τοπογράφων Μηχ.) |
| Floor | Όροφος 1 |
| Hall | Α2 (3) |
| Calendar | Τετάρτη 15:00 έως 17:00 |
Course Type 2016-2020
- Background
- 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/600130526
- At the Website of the School: http://alexander.ee.auth.gr:8083/eTHMMY/
Language of Instruction
- Greek (Instruction, Examination)
- English (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 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
- Apply knowledge in practice
- Adapt to new situations
- Work in an interdisciplinary team
- Generate new research ideas
- Be critical and self-critical
- Advance free, creative and causative thinking
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.
Keywords
algorithms, problems, automata, computing machines, Turing machines, computational complexity
Educational Material Types
- Notes
- Book
Use of Information and Communication Technologies
Use of ICT
- Use of ICT in Course Teaching
- Use of ICT in Communication with Students
Description
e-notes
communication via eTHMMY platform
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 52 | ✓ | |||
| Total | 52 |
Student Assessment
Description
Evaluation is based on the final examination
Student Assessment methods
- Written Exam with Short Answer Questions (Summative)
- Written Exam with Problem Solving (Summative)
Bibliography
Course Bibliography (Eudoxus)
1. Τίτλος: ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ
Έκδοση: 1η/2009Συγγραφείς: SIPSER MICHAEL
ISBN: 978-960-524-243-5
Διαθέτης (Εκδότης): ΙΔΡΥΜΑ ΤΕΧΝΟΛΟΓΙΑΣ & ΕΡΕΥΝΑΣ-ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΗΡΑΚΛΕΙΟ - ΚΡΗΤΗΣ
Κωδικός Βιβλίου στον Εύδοξο: 257
2. Τίτλος: ΣΤΟΙΧΕΙΑ ΘΕΩΡΙΑΣ ΥΠΟΛΟΓΙΣΜΟΥ
Έκδοση: 1η έκδ./2005
Συγγραφείς: Lewis Harry R.,Παπαδημητρίου Χρίστος Χ.
ISBN: 978-960-218-397-7
Διαθέτης (Εκδότης): ΕΚΔΟΣΕΙΣ ΚΡΙΤΙΚΗ ΑΕ
Κωδικός Βιβλίου στον Εύδοξο: 11776
Additional bibliography for study
Σημειώσεις του διδάσκοντα
Last Update
04-08-2013
