Kurs-Icon

Theoretische Informatik 2: Berechenbarkeit und Komplexität

Beschreibung

Formale Sprachen und Automaten bilden die Grundlage, um Eingaben von NutzerInnen zu analysieren, angefangen bei Adressen in Web-Formularen bis hin zu komplexem Quelltext in Java. Diese dreiteilige Kursreihe liefert das theoretische Fundament. Er zeigt auch die Grenzen von Maschinenmodellen und von Berechenbarkeit im Allgemeinen. Dieser dritte Kurs widmet sich speziell dem Konzept von Turing-Maschinen und Fragen der Komplexität und der Berechenbarkeit.

Lernziele

Mit der Hilfe dieses Kurses sollen diese Lernziele ermöglicht werden:

  • Du kannst das grundlegende Prinzip von Turingmaschinen erklären.
  • Du kannst das Problem der Unentscheidbarkeit darlegen und mehrere Beispiele nennen.
  • Du kannst semi-entscheidbare Probleme von unentscheidbaren Problemen abgrenzen.
  • Du kannst die Gedanken hinter den Zeitkomplexitätsklassen P und NP beschreiben.

Kursaufbau

  1. Organisation
  2. Turing-Maschinen
  3. Unentscheidbare Probleme
  4. Semi-entscheidbare Probleme
  5. Zeitkomplexität

Ähnliche Lernangebote

Kurs-Icon

Theoretische Informatik 1: Reguläre Sprachen und Endliche Automaten

Formale Sprachen und Automaten bilden die Grundlage, um Eingaben von NutzerInnen zu analysieren, angefangen bei Adressen in Web-Formularen bis hin zu komplexem Quelltext in Java. Diese dreiteilige...

location_on Online
signal_cellular_alt Grundlagen
language Deutsch
Kurs-Icon

Digitale Gesellschaft – KI als Schlüssel zu gesellschaftlichen Herausforderungen

Künstliche Intelligenz (KI) ist spätestens seit ChatGPT ein allgegenwärtiges Thema. Die Auswirkungen dieser Technologie betreffen mit großer Wahrscheinlichkeit schon jetzt und oft unbemerkt...

location_on Online
signal_cellular_alt Grundlagen
language Deutsch
Kurs-Icon

KI – Der Weg zur Anwendung

Künstliche Intelligenz wird gelegentlich als die silberne Kugel für alle Probleme und Herausforderungen in Zusammenhang mit der Digitalisierung dargestellt. Tatsächlich steckt hinter dem...

location_on Online
signal_cellular_alt Grundlagen
language Deutsch