108.036 Theoretical Computer Science
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021S, VO, 2.0h, 3.0EC
TUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Distance Learning

Learning outcomes

After successful completion of the course, students are able to...

The intended learning outcome of this course is to understand the contents of the course. Among other effects, this understanding forms the basis for the capability to correctly reproduce the statements and notions covered in the course as well as for the ability to explain and apply the proof techniques used in the course.

Subject of course

The lecture starts with an introduction to the theory of finite automata and formal languages. We get to know the classes of regular and context-free languages, as well as various formalisms for defining such languages, in particular finite automata and formal grammars. In the second part, after a significant leap in expressivity, we will deal with computability theory, i.e., the question which functions are computable in principle. We use the operator representation of partial recursive functions as well as Turing-machines. We discuss the Church-Turing thesis and prove the foundational results of computability theory. In the third part we consider computational complexity theory which is obtained from computability theory by restricting the resources which are available to a computation, e.g. to polynomial time. The P vs. NP -problem belongs to this subject and will form the centre of our discussion of computational complexity.

Teaching methods

reading of lecture notes, discussion on contents

Mode of examination

Oral

Additional information

For further information please consult the TUWEL-page of this course.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri13:00 - 14:0005.03.2021 Zoom (LIVE)Vorbesprechung

Examination modalities

Positive Absolvierung einer mündlichen Prüfung.

Course registration

Begin End Deregistration end
12.02.2021 00:00

Registration modalities:

Melden Sie sich bitte zu dieser LVA an um auf den zugehörigen TUWEL-Kurs zugreifen zu können.

Curricula

Literature

Lecture notes for this course are available.

Accompanying courses

Language

if required in English