Theoretical Informatics I

Course Information
TitleΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ I / Theoretical Informatics I
Code0401
FacultySciences
SchoolMathematics
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CommonNo
StatusActive
Course ID40000480

Programme of Study: UPS of School of Mathematics (2014-today)

Registered students: 373
OrientationAttendance TypeSemesterYearECTS
CoreCompulsory Course215.5

Class Information
Academic Year2015 – 2016
Class PeriodSpring
Faculty Instructors
Weekly Hours3
Class ID
600004805
Type of the Course
  • Background
  • Scientific Area
Course Category
Specific Foundation / Core
Mode of Delivery
  • Face to face
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
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures391.3
Total391.3
Student Assessment
Student Assessment methods
  • Written Exam with Short Answer Questions (Formative)
  • Written Exam with Problem Solving (Formative, 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
15-09-2013