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.

2024S, VO, 2.0h, 3.0EC

Course evaluation

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VO Lecture
  • Format: Presence

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

Lecture

Mode of examination

Oral

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Fri14:00 - 16:0008.03.2024 - 28.06.2024Sem.R. DA grün 06A Vorlesung
Theoretical Computer Science - Single appointments
DayDateTimeLocationDescription
Fri08.03.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri15.03.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri22.03.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri12.04.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri19.04.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri26.04.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri03.05.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri17.05.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri24.05.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri31.05.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri07.06.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri14.06.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri21.06.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung
Fri28.06.202414:00 - 16:00Sem.R. DA grün 06A Vorlesung

Examination modalities

Positive Absolvierung einer mündlichen Prüfung.

Course registration

Not necessary

Curricula

Study CodeObligationSemesterPrecon.Info
033 201 Technical Mathematics Mandatory elective
860 GW Optional Courses - Technical Mathematics Not specified

Literature

No lecture notes are available.

Accompanying courses

Language

if required in English