Theoretical Informatics I

Course Information
TitleΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ I / Theoretical Informatics I
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CoordinatorGeorgios Rachonis
Course ID40000480

Programme of Study: UPS of School of Mathematics (2014-today)

Registered students: 431
OrientationAttendance TypeSemesterYearECTS
CoreCompulsory Course215.5

Class Information
Academic Year2017 – 2018
Class PeriodSpring
Faculty Instructors
Weekly Hours3
Class ID
Course Type 2016-2020
  • Background
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
Language of Instruction
  • Greek (Instruction, Examination)
Learning Outcomes
Theoretical Computer Science is a synchronous field of Mathematics which contributes to the strict foundations of Computer Science. The purpose of this course is that the students will understand the mathematical modeling of algorithms with the help of finite automata, and the important results obtained from this procedure.
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 self-critical
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
Reading Assigment1234.1
Student Assessment
Student Assessment methods
  • Written Exam with Short Answer Questions (Summative)
  • Written Exam with Problem Solving (Summative)
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού των Η. Lewis και Χ. Παπαδημητρίου. - Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser.
Additional bibliography for study
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 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, Prentice-Hall Inc., 2nd edition 1998. - Grzegorz Rozenberg, Arto Salomaa eds., Handbook of Formal Languages, volumes 1-3, Springer-Verlag, Berlin, 1997.
Last Update