Title  ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ I / Theoretical Informatics I 
Code  0401 
Faculty  Sciences 
School  Mathematics 
Cycle / Level  1st / Undergraduate 
Teaching Period  Spring 
Common  No 
Status  Active 
Course ID  40000480 
Programme of Study: UPS of School of Mathematics (2014today)
Registered students: 573
Orientation  Attendance Type  Semester  Year  ECTS 

Core  Compulsory Course  2  1  5.5 
Academic Year  2019 – 2020 
Class Period  Spring 
Instructors from Other Categories 

Weekly Hours  3 
Class ID  600147690

Type of the Course
 Background
 Scientific Area
Course Category
Specific Foundation / Core
Mode of Delivery
 Face to face
Digital Course Content
 eStudy Guide https://qa.auth.gr/en/class/1/600147690
 Other: http://users.auth.gr/grahonis/TCS.html
Language of Instruction
 Greek (Instruction, Examination)
Learning Outcomes
 Understanding of strict mathematical modeling for algorithms via automata.
 Learning of finite automata, recognizable languages and rational languages.
 Minimization of algorithms which are described by automata.
 Discrimination among recognizable and nonrecognizable languages.
General Competences
 Apply knowledge in practice
 Retrieve, analyse and synthesise data and information, with the use of necessary technologies
 Adapt to new situations
 Make decisions
 Work autonomously
 Work in an international context
 Work in an interdisciplinary team
 Generate new research ideas
 Be critical and selfcritical
Course Content (Syllabus)
Preliminaries: Sets, relations, algorithms. Growth of functions. Alphabets and formal languages. Finite automata: complete, deterministic, nondeterministic and their equivalence. Recognizable languages. Pumping lemma. Rational languages. Algorithms for the minimization of finite automata. Decidability results.
Educational Material Types
 Notes
 Book
Course Organization
Activities  Workload  ECTS  Individual  Teamwork  Erasmus 

Lectures  39  1.3  ✓  
Reading Assigment  123  4.1  
Exams  3  0.1  
Total  165  5.5 
Student Assessment
Student Assessment methods
 Written Exam with Short Answer Questions (Summative)
 Written Exam with Problem Solving (Summative)
Bibliography
Course Bibliography (Eudoxus)
 Στοιχεία Θεωρίας Υπολογισμού των Η. Lewis και Χ. Παπαδημητρίου.
 Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser.
Additional bibliography for study
 John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, AddisonWesley, 3rd edition 2007.
 Juraj Hromkovic, Theoretical Computer Science, Texts in Theoretical Computer Science, EATCS Series, Springer, 2004.
 Harry Lewis, Christos Papadimitriou, Elements of the Theory of Computation, PrenticeHall Inc., 2nd edition 1998.
 Grzegorz Rozenberg, Arto Salomaa eds., Handbook of Formal Languages, volumes 13, SpringerVerlag, Berlin, 1997.
Last Update
21042020