Theoretical Informatics I

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

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

Registered students: 419
OrientationAttendance TypeSemesterYearECTS
CoreCompulsory Course215.5

Class Information
Academic Year2020 – 2021
Class PeriodSpring
Faculty Instructors
Weekly Hours3
Class ID
1. ΤΜΗΜΑ ΑGeorgios Rachonis
2. ΤΜΗΜΑ ΒGeorgios Rachonis
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
- 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 non-recognizable 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 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