Main content

CS 460L — Theoretical Computer Science for Pre-Service-Teachers
(dt. Theoretische Informatik für Lehramt an Gymnasien-Studierende)

Level, degree of commitment Advanced module, required module
Forms of teaching and learning,
workload		 Lecture (4 SWS), recitation classen and seminar (2 SWS),
270 hours (attendance in den Lehrveranstaltungen 90 h, preparation and follow-up inklusive Studienleistungen 150 h, Vorbereitung and Ablegen von Prüfungsleistungen 30 h)
Credit points,
formal requirements		 9 CP
Course requirement(s): A) with seminar: 1) Weekly exercises 2) Presentation of at least two exercises 3) Presentation, approx. 30 minutes in the seminar on school-related topics of the lecture with regard to the implementation in the senior high school level in the seminar or B) with 'Schnittstellenübungen': 1) Weekly exercises 2) Presentation of at least two exercises 3) Exercises in the interface exercises 4) Presentation of at least one exercise in the 'Schnittstellenübung': If a seminar A) is completed, the successful completion of at least 40 % of the exercises in coursework 1), otherwise B) the successful completion of at least 50 % of the exercises in the 'Schnittstellenübung' in coursework 1) and 3) is a prerequisite for admission to the module examination.
Examination type: Written examination (120 min.)
Language,
Grading		 German,
The grading is done with 0 to 15 points according to the examination regulations for the degree program LAaG Computer Science. In the event of failure, a total of 4 attempts are available for the examination.
Duration,
frequency		 One semester,
each winter semester
Person in charge of the module's outline Prof. Dr. Christian Komusiewicz

Contents

  • Automata theory and formal languages: grammars and the Chomsky hierarchy, finite automata and regular expressions, context-free grammars and push-down automata, closure properties of formal languages, decidability questions
  • Computability: models of computability: Turing, Loop and While-computability, primitive recursion and μ-recursion, Church-Turing thesis; decidability, enumerability, undecidable problems
  • Complexity theory: complexity measures; P and NP; reductions and NP-complete problems

Qualification Goals

Basic knowledge in core areas of theoretical computer science, in detail:

  • Dealing with regular expressions, finite automata and grammars. Recognizing the possibilities and limitations,
  • Understanding formal models of computing,
  • Principal limits of algorithmic computing,
  • Limits of efficient problem solving,
  • Training of oral communication skills in the exercises by practicing free speech in front of an audience and during discussion.

Prerequisites

None. The competences taught in the following modules are recommended: Basic Linear Algebra or Basic Real Analysis.


Applicability

The module can be attended at FB12 in study program(s)

  • LAaG Computer Science

When studying LAaG Computer Science, this module must be completed in the study area Advanced Modules.


Recommended Reading

(not specified)



Please note:

This page describes a module according to the latest valid module guide in Winter semester 2023/24. Most rules valid for a module are not covered by the examination regulations and can therefore be updated on a semesterly basis. The following versions are available in the online module guide:

The module guide contains all modules, independent of the current event offer. Please compare the current course catalogue in Marvin.

The information in this online module guide was created automatically. Legally binding is only the information in the examination regulations (Prüfungsordnung). If you notice any discrepancies or errors, we would be grateful for any advice.