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: 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

Class Information
Academic Year2019 – 2020
Class PeriodWinter
Faculty Instructors
Class ID
600144673
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
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures104
Exams16
Total120
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
10-12-2015