THEORY OF COMPUTATION

Course Information
TitleΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ / THEORY OF COMPUTATION
CodeNCO-02-05
FacultySciences
SchoolInformatics
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CoordinatorPanagiotis Katsaros
CommonNo
StatusActive
Course ID40002922

Programme of Study: PPS-Tmīma Plīroforikīs (2019-sīmera)

Registered students: 273
OrientationAttendance TypeSemesterYearECTS
GENIKĪ KATEUTHYNSĪCompulsory Course216

Class Information
Academic Year2017 – 2018
Class PeriodSpring
Faculty Instructors
Weekly Hours5
Class ID
600104709
Type of the Course
  • Scientific Area
Course Category
Specific Foundation / Core
Mode of Delivery
  • Face to face
Digital Course Content
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
Prerequisites
General Prerequisites
Some basic knowledge of Discrete Mathematics (set theory, relations, functions, proof techniques) is desirable. This basic knowledge is covered briefly in the introduction of the course.
Learning Outcomes
The students who will attend the course are expected to • understand the notion of computation and the capabilities of our computing machines • know the principles and the foundations of the Computer Science • digest material upon which other subjects are founded, such as the Theory of Programming Languages and the Algorithmics • cultivate the ability to develop formal and mathematically rigorous reasoning • know open problems and applications of the Theory of Computation in the science and the technology
General Competences
  • Apply knowledge in practice
  • Adapt to new situations
  • Make decisions
  • Work autonomously
  • Be critical and self-critical
  • Advance free, creative and causative thinking
Course Content (Syllabus)
Introduction, Regular Languages: Regular Expressions and Finite Automata, Context-Free Languages: Grammars and Pushdown Automata, Turing Machines, Undecidability
Keywords
Languages, Grammars, Automata, Undecidability
Educational Material Types
  • Slide presentations
  • Interactive excersises
  • Book
Use of Information and Communication Technologies
Use of ICT
  • Use of ICT in Course Teaching
  • Use of ICT in Communication with Students
Description
The course material is offered in Internet through the (moodle) software e-learning platform, which is also used for communicating with the students. The lectures take place by audiovisual teaching aids (electronic slides).
Course Organization
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures52
Reading Assigment112
Tutorial13
Exams3
Total180
Student Assessment
Description
The students are evaluated based on their answers to a mandatory interactive test (10 %) and their performance in the final written exam (90 %). Their study is successful if the weighted average is a promotable grade (5). The evaluation criteria, the mid-term exam and the results for the students' performance will be announced in the (moodle) software e-learning platform.
Student Assessment methods
  • Written Exam with Multiple Choice Questions (Formative, Summative)
  • Written Exam with Short Answer Questions (Formative, Summative)
  • Written Exam with Problem Solving (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
1. H.R. Lewis, Χ. Παπαδημητρίου, "Στοιχεία θεωρίας υπολογισμού", 1η έκδοση/2005, Εκδόσεις Κριτική, ISBN: 978-960-218-397-7 Κωδικός Βιβλίου στον Εύδοξο: 11776 2. M. Sipser, "Εισαγωγή στη Θεωρία Υπολογισμού", 1η έκδοση/2009, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN: 978-960-524-243-5 Κωδικός Βιβλίου στον Εύδοξο: 257
Additional bibliography for study
1. Π. Κατσαρός, "Θεωρία Υπολογισμού και Εφαρμογές", 2015, Αποθετήριο Κάλλιπος, https://repository.kallipos.gr/handle/11419/5744 2. E. Rich, "Automata, Computability and Complexity: Theory and Applications", 1st edition/2007, Prentice Hall, ISBN: 978-0132288064 3. J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation", 3rd edition/2006, Prentice Hall, ISBN: 978-0321455369
Last Update
13-06-2016