Theoritical Informatics II

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

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

Registered students: 192
OrientationAttendance TypeSemesterYearECTS
CoreElective Courses belonging to the selected specializationSpring-5.5

Class Information
Academic Year2019 – 2020
Class PeriodSpring
Instructors from Other Categories
Weekly Hours3
Class ID
Course Type 2016-2020
  • Background
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
Required Courses
  • 0401 Theoretical Informatics I
General Prerequisites
Knowledge and ability to handle basic concepts of the theory of formal language and automata theory.
Learning Outcomes
Upon successful completion of the course, students will be able to:     1. Understand the function of context-free grammars and pushdown automata through their theoretical description and use this description in theoretical exercises. They will also be able to understand the mathematical nature of these models and prove their properties using classical algebraic and logical proof techniques.     2. In conjunction with the prerequisite knowledge of the course "Theoretical Informatics I", students will be able to understand the concept of hierarchy of classes of typical languages in terms of their structural complexity.     3. In addition, they will be able to understand how to study a class of typical language e.g. determine closure properties of the class, and also how to study the properties of the theoretical models that define the languages ​​of the class, e.g. their distinction in machines that produce languages and machines that recognize languages, their ability to be minimized in order to improve their performance in potential applications.     4. Finally, students will be able to understand the utility of mathematical modeling and study of processes and phenomena that we encounter in Computer Science.
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 teams
  • Work in an international context
  • Work in an interdisciplinary team
  • Generate new research ideas
  • Be critical and self-critical
  • Advance free, creative and causative thinking
Course Content (Syllabus)
Complete minimization of finite automata. Context-free grammars. Syntactic trees. Context-free languages. Properties of context-free languages. Relation among recognizable and context-free languages. Pushdown automata.
Grammars, Context-free languages
Educational Material Types
  • Notes
  • Book
Course Organization
Reading Assigment1234.1
Student Assessment
Student Assessment methods
  • Written Exam with Short Answer Questions (Formative)
  • Written Exam with Problem Solving (Formative, Summative)
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού, H.Lewis, Χ.Παπαδημητρίου, Κριτική, 2005, Αθήνα. - Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Παν/κές Εκδόσεις Κρήτης, 2007 έδοση 2009.
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