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

Core  Elective Courses belonging to the selected specialization  Spring    5.5 
Academic Year  2019 – 2020 
Class Period  Spring 
Instructors from Other Categories 

Weekly Hours  3 
Class ID  600147694

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/600147694
 eLearning (Moodle): https://elearning.auth.gr/course/view.php?id=12922
 Other: http://users.auth.gr/grahonis/TCS_II.html
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
 Greek (Instruction, Examination)
Prerequisites
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 contextfree 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 selfcritical
 Advance free, creative and causative thinking
Course Content (Syllabus)
Complete minimization of finite automata. Contextfree grammars. Syntactic trees. Contextfree languages. Properties of contextfree languages. Relation among recognizable and contextfree languages. Pushdown automata.
Keywords
Grammars, Contextfree languages
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 (Formative)
 Written Exam with Problem Solving (Formative, Summative)
Bibliography
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, 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
15032020