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: 422
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| Core | Compulsory Course | 2 | 1 | 5.5 |
| Academic Year | 2017 – 2018 |
| Class Period | Spring |
| Faculty Instructors |
|
| Weekly Hours | 3 |
| Class ID | 600099206
|
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/600099206
- Other: http://users.auth.gr/grahonis/TCS.html
Language of Instruction
- Greek (Instruction, Examination)
Learning Outcomes
Theoretical Computer Science is a synchronous field of Mathematics which contributes to the strict foundations of Computer Science.
The purpose of this course is that the students will understand the mathematical modeling of algorithms with the help of finite automata, and the important results obtained from this procedure.
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
05-05-2017
