Theoritical Informatics II
| Title | ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ ΙΙ / Theoritical Informatics II |
| Code | 0432 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Spring |
| Coordinator | Georgios Rachonis |
| Common | Yes |
| Status | Active |
| Course ID | 40000484 |
Programme of Study: UPS of School of Mathematics (2014-today)
Registered students: 122
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| Core | Elective Courses belonging to the selected specialization | Spring | - | 5.5 |
| Academic Year | 2018 – 2019 |
| Class Period | Spring |
| Faculty Instructors |
|
| Weekly Hours | 3 |
| Class ID | 600121496
|
Course Type 2016-2020
- Background
- Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600121496
- Other: http://users.auth.gr/grahonis/TCS_II.html
Language of Instruction
- Greek (Instruction, Examination)
Prerequisites
Required Courses
- 0401 Theoretical Informatics I
Learning Outcomes
This course is a continuation of the course Theoretical Computer Science I. The students are introduced to further minimization algorithms of finite automata. Furthermore, they study the class of context-free languages, i.e., the mathematical model of programming languages generated by context-free grammars. They also study pushdown automata and they are introduced to the practical use of these models to syntactical analysis as well as the main compilers' properties.
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.
Keywords
Grammars, Context-free 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, 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
25-09-2018
