t.BA.IT.THIN.19HS (Theory of Computation) 
Module: Theory of Computation
This information was generated on: 20 April 2024
No.
t.BA.IT.THIN.19HS
Title
Theory of Computation
Organised by
T CAI
Credits
4

Description

Version: 3.0 start 01 February 2022
 

Short description

 Students learn the basic terms and concepts used in theoretical computer science. They will also understand how to build models for assessing the performance of current and future computer systems: formal languages, automata theory and computational complexity

Module coordinator

 Olaf Stern, strf

Learning objectives (competencies)
Objectives Competences Taxonomy levels
(1) They will acquire knowledge relating to the formal languages/grammatical systems, the types of automatas which use these and the relationships between them. They will be able to design automatas for given formal languages which will accept or define these languages, as well as design languages which given automatas can recognise and define.    
(2) The students will be familiar with the major approaches used to formalise concepts of computability and those used to develop algorithms. They will be aware of the equivalences between these various approaches. They will know the concepts of decidable and semidecidable problems and will be aware of the relationship between these two types of problems.    
(3) The students will know the most important classes of complexity – particularly P and NP – as well as the simple notations used to describe them (o notation and omega notation). They will understand the question of whether P=NP and be aware of its significance. They will be familiar with the polynomial reduction method and be able to apply it to comparatively simple examples.    

Module contents

 Motivation applicable to theoretical computer science:
  • formal calculation models
  • ability to recognise fundamental principles, irrespective of the hardware or software being used
  • the limits applicable to automatic calculations
Formal languages / machine theory:
  • fundamental definitions of formal languages
  • regular languages, finite-state machines (DFSM, NFSM, e-NFSM)
  • context-independent languages, pushdown automata
  • (recursive languages), Turing machines (TM)
  • Chomsky hierarchy
Computability and algorithm concept:
  • computable functions. Church’s thesis
  • Equivalence of TMs and computers
  • Computability and programming languages: GOTO, while and loop programmes
  • The algorithm concept
  • Primitive recursion
  • Non-decidability and decidability: Ld diagonal language, Rice’s theorem, busy beavers
  • Semi-decidable problems: halting problem, game of life, (Collatz numbers ?)
  • Reduction
Complexity theory
  • the complexity of algorithms
  • O-notation (omega-notation)
  • Polynomial and exponential functions
  • P class, NP class
  • NP-complete, NP-hard
  • Polynomial time reduction

Teaching materials

 - Ausführlicher Foliensatz, Ergänzungsunterlagen, Aufgabenserien mit Musterlösungen
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit bzw. Introduction to Automata Theory, Languages, and Computation, Pearson Studium, Addison-Wesley Verlag, (auch als Taschenbuch und e-Book verfügbar), 2011 / 2013

Supplementary literature

 - Detailed set of slides, supplementary documents, task series with sample solutions
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit bzw. Introduction to Automata Theory, Languages, and Computation, Pearson Studium, Addison-Wesley Verlag, (also available as paperback book and e-Book), 2011 / 2013

Prerequisites

 none

Teaching language

 (X) German ( ) English

Part of International Profile

 ( ) Yes (X) No

Module structure

 Type 2a
  For more details please click on this link: T_CL_Modulauspraegungen_SM2025

Exams
Description Type Form Scope Grade Weighting
Graded assignments during teaching semester excercises written about 9 task series points 20%
End-of-semester exam exam written grades grading 80%

Remarks

  

Legal basis

 The module description is part of the legal basis in addition to the general academic regulations. It is binding. During the first week of the semester a written and communicated supplement can specify the module description in more detail.

Note

Course: Theoretische Informatik - Vorlesung
No.
t.BA.IT.THIN.19HS.V
Title
Theoretische Informatik - Vorlesung

Note

  • No module description is available in the system for the cut-off date of 01 August 2099.