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: 196
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| Core | Elective Courses belonging to the selected specialization | Spring | - | 5.5 |
| Academic Year | 2020 – 2021 |
| Class Period | Spring |
| Instructors from Other Categories |
|
| Weekly Hours | 3 |
| Class ID | 600166770
|
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/600166770
- 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 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.
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
15-03-2020
