Theory of Computing III: Computability and Complexity

Автори / авторки: Prof. Dr. Andreas Schäfer
Пропонований університет: Technische Hochschule Lübeck
Мова курсу: Англійська
Галузь знань: Wirtschaftsinformatik Безкоштовно
Середнє навантаження: 50 Години Безкоштовно Рекомендований лист
Поділіться
твітнути
Поділіться
Поділіться
Поділіться
Поділіться

Що очікує Вас на даному курсі?

Formal Languages and Automata provide the basis for analyzing user input from addresses in web forms to complex Java code. This 3-part course provides the basics of the theory. It also shows the limits of each machine model and finally the limits of computability in general.

This course, building on the previous two, discusses Turing machines and problems of decidability and complexity.

Чого можна навчитися на цьому курсі?

With the help of this course, we want you to achieve the following learning outcomes:

  • You can describe basic principles of Turing machines.
  • You can discuss the problem of undecidability and name multiple examples.
  • You can distinguish between undecidable and semi-decidable problems.
  • You can describe the idea of the time complexity classes P and NP.
  • You can elaborate on the basic idea of space complexity.

Структура

  • Organization
  • Turing machines
  • Undecidable Problems
  • Semi-decidable Problems
  • Time Complexity
  • Space Complexity

Автори / авторки

Prof. Dr. Andreas Schäfer

Andreas Schäfer received his PhD 2007 from the Carl von Ossietzky University in Oldenburg, Germany. 

He then worked at the European Patent Office for 5 years. Since 2012 he is Professor of Computer 

Science at the Technische Hochschule Lübeck. His interests include Automata Theory, Logic and Formal Methods. 


Ліцензія

Creative Commons