Theory of Computation and Algorithms

Course Information
TitleΘεωρία Υπολογισμών και Αλγορίθμων / Theory of Computation and Algorithms
Code048
FacultyEngineering
SchoolElectrical and Computer Engineering
Cycle / Level1st / Undergraduate
Teaching PeriodWinter
CoordinatorAnastasios Ntelopoulos
CommonNo
StatusActive
Course ID600000997

Programme of Study: Electrical and Computer Engineering

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

Class Information
Academic Year2021 – 2022
Class PeriodWinter
Faculty Instructors
Weekly Hours4
Class ID
600196777
Course Type 2016-2020
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
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
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures1043.5
Exams160.5
Total1204
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
06-10-2021