Theoretical Informatics I
| Title | ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ I / Theoretical Informatics I |
| Code | 0401 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 1st / Undergraduate |
| Teaching Period | Spring |
| Coordinator | Georgios Rachonis |
| Common | No |
| Status | Active |
| Course ID | 40000480 |
Programme of Study: UPS of School of Mathematics (2014-today)
Registered students: 510
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| Core | Compulsory Course | 2 | 1 | 5.5 |
| Academic Year | 2018 – 2019 |
| Class Period | Spring |
| Faculty Instructors |
|
| Weekly Hours | 3 |
| Class ID | 600121492
|
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/600121492
- Other: http://users.auth.gr/grahonis/TCS.html
Language of Instruction
- Greek (Instruction, Examination)
Learning Outcomes
- Understanding of strict mathematical modeling for algorithms via automata.
- Learning of finite automata, recognizable languages and rational languages.
- Minimization of algorithms which are described by automata.
- Discrimination among recognizable and non-recognizable languages.
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 an international context
- Work in an interdisciplinary team
- Generate new research ideas
- Be critical and self-critical
Course Content (Syllabus)
Preliminaries: Sets, relations, algorithms. Growth of functions. Alphabets and formal languages. Finite automata: complete, deterministic, nondeterministic and their equivalence. Recognizable languages. Pumping lemma. Rational languages. Algorithms for the minimization of finite automata. Decidability results.
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 (Summative)
- Written Exam with Problem Solving (Summative)
Bibliography
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού των Η. Lewis και Χ. Παπαδημητρίου.
- Εισαγωγή στη Θεωρία Υπολογισμού του M. Sipser.
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
10-05-2019
