|Title||ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ ΙΙ / Theoritical Informatics II|
|Cycle / Level||1st / Undergraduate|
Programme of Study: UPS of School of Mathematics (2014-today)
Registered students: 191
|Core||Elective Courses belonging to the selected specialization||Spring||-||5.5|
|Academic Year||2019 – 2020|
|Instructors from Other Categories|| |
|Class ID|| |
Type of the Course
- Scientific Area
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600147694
- eLearning (Moodle): https://elearning.auth.gr/course/view.php?id=12922
- Other: http://users.auth.gr/grahonis/TCS_II.html
The course is also offered to exchange programme students.
Language of Instruction
- Greek (Instruction, Examination)
- 0401 Theoretical Informatics I
Knowledge and ability to handle basic concepts of the theory of formal language and automata theory.
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.
- 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
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.