# 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 Winter Coordinator Anastasios Ntelopoulos Common No Status Active Course ID 600000997

### Programme of Study: Merikī Foítīsī - PPS Īlektrológōn Mīchanikṓn kai Mīchanikṓn Ypologistṓn (2016 - sīmera)

Registered students: 0
OrientationAttendance TypeSemesterYearECTS
ĪLEKTRIKĪS ENERGEIASElective Courses744
ĪLEKTRONIKĪS KAI YPOLOGISTŌNElective Courses744
TĪLEPIKOINŌNIŌNElective Courses744

### Programme of Study: Electrical and Computer Engineering

Registered students: 81
OrientationAttendance TypeSemesterYearECTS
ELECTRICAL ENERGYElective Courses744
ELECTRONICS AND COMPUTER ENGINEERINGElective Courses744
TELECOMMUNICATIONSElective Courses744

 Academic Year 2019 – 2020 Class Period Winter Faculty Instructors Class ID 600144673

### Class Schedule

 Building Πολυτεχνείο - πτέρυγα Γ (ΤΗΜΜΥ & Τοπογράφων Μηχ.) Floor Όροφος 1 Hall Α2 (3) Calendar Τετάρτη 15:00 έως 17:00 Building Πολυτεχνείο - πτέρυγα Γ (ΤΗΜΜΥ & Τοπογράφων Μηχ.) Floor Όροφος 1 Hall Α7 (4) Calendar Δευτέρα 18:00 έως 20:00
Course Type 2016-2020
• Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
• Face to face
Digital Course Content
Language of Instruction
• Greek (Instruction, Examination)
• English (Examination)
Learning Outcomes
1. To understand the hierarchy of problems and the associated hierarchy of algorithms. 2. 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) 3. 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).
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