EuraStudy
Notizen/Informatik/INF-Th - Theoretische Informatik
Notizen · InformatikAT · Matura

INF-Th - Theoretische Informatik

Automaten, formale Sprachen, Berechenbarkeit und Komplexitätstheorie geben Antworten auf "Was ist berechenbar?" und "Was ist effizient berechenbar?".

3 Abschnitte·~9 Min Lesezeit·4 Kompetenzen·Niveau Standard 1 · Vertiefung 2·Stand 06/2026

T·0888 / 12
Prüfungsprofil
INF-Th-1 · Endliche Automaten und reguläre Sprachen unterscheidenINF-Th-2 · Kellerautomaten und kontextfreie Sprachen kennenINF-Th-3 · Berechenbarkeit und Halteproblem verstehenINF-Th-4 · P, NP und NP-vollständige Probleme einordnen
Tiefe

Lesetiefe: Vertiefung

Schrift

Schriftgröße: Standard

Inhalt · 3 Abschnitte▾
  1. INF-Th - Theoretische Informatik
    • 01Endliche Automaten und reguläre Sprachen◐
    • 02Berechenbarkeit und Halteproblem●
    • 03P, NP und NP-vollständige Probleme●
§ 01

Endliche Automaten und reguläre Sprachen#

●●○StandardLPINF-Th-1.1

Kernpunkte

Die theoretische Informatik fragt, was Maschinen überhaupt berechnen können - und beginnt beim einfachsten Modell, dem endlichen Automaten. Er besitzt nur endlich viele Zustände und keinen zusätzlichen Speicher; sein „Gedächtnis" ist allein der aktuelle Zustand ().

DFA für Sprache aller Bitfolgen mit gerader Anzahl Einsen

Start q0 q1 1 1 0 0 Akzeptierte Sprache L = { w in {0,1}* | w hat gerade Anzahl Einsen }
Abb. 1Zwei Zustände: q0 (gerade), q1 (ungerade); Akzeptanz in q0.
Ein DFA (deterministischer endlicher Automat) ist formal das Tupel M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_{0},F)M=(Q,Σ,δ,q0​,F): Zustände QQQ, Eingabealphabet Σ\SigmaΣ, Übergangsfunktion δ:Q×Σ→Q\delta: Q\times\Sigma \to Qδ:Q×Σ→Q, Startzustand q0q_{0}q0​ und Endzustände FFF. Er liest die Eingabe Zeichen für Zeichen, wechselt deterministisch den Zustand und akzeptiert, wenn er nach dem letzten Zeichen in einem Endzustand steht.
Ein NFA (nichtdeterministisch) darf zu einem Zeichen mehrere Folgezustände haben (und ε-Übergänge). Er ist trotzdem nicht mächtiger: Jeder NFA lässt sich per Potenzmengenkonstruktion in einen äquivalenten DFA übersetzen - NFAs sind nur oft kompakter zu entwerfen.
Reguläre Ausdrücke beschreiben dieselbe Sprachklasse algebraisch: Verkettung (`ab`), Alternative (`a|b`), Stern (`a`, beliebig oft) und Klammern. Der Satz von Kleene sichert die Gleichmächtigkeit zu: Eine Sprache ist genau dann regulär*, wenn ein endlicher Automat sie erkennt bzw. ein regulärer Ausdruck sie beschreibt (siehe Beispiel).
Endliche Automaten können nicht zählen, weil ihr Gedächtnis endlich ist. Die Sprache {anbn∣n≥0}\{a^{n}b^{n} \mid n \geq 0\}{anbn∣n≥0} (gleich viele a wie b) ist daher nicht regulär - man bräuchte einen Zähler, also einen Kellerautomaten mit Stack. Solche Nicht-Regularität beweist man mit dem Pumping-Lemma.
Anwendungen sind allgegenwärtig: der Lexer in Compilern, Suchmuster (grep) und Eingabevalidierung (etwa E-Mail-Format). Häufige Fehler: NFA und DFA gleichsetzen, die Akzeptanzbedingung vergessen (Endzustand erst nach der gesamten Eingabe), oder regex `a+` (mindestens eins) und `a*` (auch null) verwechseln.
M=(Q,Σ,δ,q0,F),δ:Q×Σ→QM = (Q,\Sigma,\delta,q_{0},F),\quad \delta: Q\times\Sigma \to QM=(Q,Σ,δ,q0​,F),δ:Q×Σ→Q

Definition eines deterministischen endlichen Automaten

Musterbeispiel

Regulärer Ausdruck und Sprache

Beschreibe die Sprache des regulären Ausdrucks `(0|1)*1` und gib einen DFA an.

  1. 01Sprache interpretieren

    (0∣1)∗(0|1)^{*}(0∣1)∗ steht für beliebig viele 0/1; das angehängte 1 erzwingt, dass das letzte Zeichen 1 ist.

  2. 02Beispiele

    "1", "01", "11", "001", "10101" gehören dazu; "10", "0", "100" nicht.

  3. 03DFA-Zustände

    q0 = "letzter Buchstabe = 0 oder leer" (nicht akzeptierend), q1 = "letzter Buchstabe = 1" (akzeptierend).

  4. 04Übergänge

    q0 --0--> q0, q0 --1--> q1; q1 --0--> q0, q1 --1--> q1. Startzustand q0, F = {q1}.

Ergebnis: Sprache aller Bitstrings, die mit 1 enden. Reguläre Sprachen entsprechen genau den DFA-akzeptierten Sprachen (Satz von Kleene).

Schritt-für-Schritt Erklärung3 Schritte
  1. 1

    Endliche Automaten sind das einfachste Berechnungsmodell - sie merken sich nur einen Zustand.

    DFA für Sprache aller Bitfolgen mit gerader Anzahl Einsen

    Start q0 q1 1 1 0 0 Akzeptierte Sprache L = { w in {0,1}* | w hat gerade Anzahl Einsen }
    Abb.Zwei Zustände: q0 (gerade), q1 (ungerade); Akzeptanz in q0.
  2. 2

    Reguläre Ausdrücke sind dieselbe Macht wie endliche Automaten - das ist der Satz von Kleene.

  3. 3

    Sobald du zählen musst (z.B. Klammern), reicht ein DFA nicht mehr - du brauchst einen Kellerautomaten.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre den Begriff "endlicher Automat". Konstruiere einen DFA für die Sprache aller Binärstrings mit gerader Anzahl Einsen.

Maturafokus

  • DFA für einfache Sprachen konstruieren (gerade Anzahl 0en, endet auf 1).
  • NFA in DFA umwandeln (Potenzmengenkonstruktion) skizzieren.
  • Pumping-Lemma als Werkzeug zur Nicht-Regularitaet kennen.

Typische Fehler

  • NFA mit DFA gleichgesetzt und immer mehrere Folgezustände erlaubt.
  • Akzeptanzbedingung vergessen (Endzustand nach kompletter Eingabe).
  • Regex `a+` und `a` verwechselt (+ = mindestens 1, = mindestens 0).

Aktive Wiederholung

Konstruiere einen DFA, der genau die Strings akzeptiert, die mit "ab" beginnen und mit "ba" enden (Alphabet {a,b}).

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Sipser: Introduction to the Theory of Computation (Cengage)

§ 02

Berechenbarkeit und Halteproblem#

●●●VertiefungLPINF-Th-3.1

Kernpunkte

Manche Probleme sind nicht nur teuer, sondern grundsätzlich unlösbar - kein Algorithmus kann sie für alle Eingaben korrekt entscheiden. Die Berechenbarkeitstheorie zieht genau diese Grenze des überhaupt Machbaren.
Eine Funktion heißt berechenbar, wenn es einen Algorithmus (formalisiert als Turingmaschine) gibt, der sie für jede Eingabe in endlich vielen Schritten berechnet. Bei Entscheidungsproblemen (Ja/Nein-Fragen) spricht man von entscheidbar.
Die Church-Turing-These behauptet, dass alles intuitiv „Berechenbare" genau dem Turing-Berechenbaren entspricht - ob man Turingmaschinen, λ-Kalkül oder reale Programmiersprachen nimmt, sie alle erfassen dieselbe Klasse. Sie ist eine These (nicht beweisbar, aber bislang unwiderlegt).
Man unterscheidet drei Stufen (): entscheidbar (der Algorithmus hält immer mit ja/nein), semi-entscheidbar (er hält bei „ja", läuft bei „nein" aber eventuell ewig) und unentscheidbar (kein Algorithmus bewältigt alle Eingaben).

Entscheidbarkeitsklassen

EntscheidbarkeitsklassenTabelle mit 3 Spalten und 3 Zeilen, Daten: Klasse · Eigenschaft · Beispiel; entscheidbar · hält stets mit ja/nein · Primzahltest, Sortiertheit; semi-entscheidbar · hält bei „ja", sonst nie · Akzeptanz einer TM; unentscheidbar · kein Algorithmus möglich · Halteproblem, ÄquivalenzKLASSEEIGENSCHAFTBEISPIELentscheidbarhält stets mit ja/neinPrimzahltest, Sortiertheitsemi-entscheidbarhält bei „ja", sonst nieAkzeptanz einer TMunentscheidbarkein Algorithmus möglichHalteproblem, Äquivalenz
Abb. 2Probleme lassen sich nach der Stärke des möglichen Algorithmus einordnen.
Das berühmteste unentscheidbare Problem ist das Halteproblem: Kein Programm kann für jedes Programm PPP und jede Eingabe xxx entscheiden, ob PPP bei xxx hält. Der Beweis per Diagonalisierung (Turing 1936) nimmt einen solchen Entscheider an und baut daraus ein Programm, das sich selbst widerspricht (siehe Beispiel). Nach dem Satz von Rice sind auch Programmäquivalenz und „erreicht Zeile X je?" unentscheidbar.
Praktische Folge: Kein Werkzeug kann jeden Bug oder jede Endlosschleife finden - aber statische Analyse, Linter und Typsysteme entscheiden viele Fälle korrekt (konservativ, mit Fehlalarmen). Häufige Fehler: Unentscheidbarkeit für „zu schwer für heutige Rechner" halten (sie ist prinzipiell, keine Frage der Leistung), das Halteproblem auf eine einzelne Sprache beziehen, oder Berechenbarkeit mit Effizienz verwechseln.
Musterbeispiel

Halteproblem - Beweisidee

Skizziere den Beweis (Diagonalisierung), dass das Halteproblem unentscheidbar ist.

  1. 01Annahme

    Es gibt ein Programm H(P, x), das für jedes Programm P und Eingabe x in endlicher Zeit ja/nein liefert, ob P bei x hält.

  2. 02Konstruktion D

    Definiere D(P): wenn H(P, P) = "hält" -> Endlosschleife; sonst -> halten.

  3. 03Anwenden auf D selbst

    Was sagt H(D, D)?

  4. 04Widerspruch

    Wenn H(D,D) = "hält": dann macht D bei Eingabe D Endlosschleife - Widerspruch. Wenn H(D,D) = "hält nicht": dann hält D bei D - Widerspruch.

Ergebnis: Beide Fälle führen zum Widerspruch. Folglich existiert H nicht. Das Halteproblem ist unentscheidbar (Turing 1936).

Schritt-für-Schritt Erklärung3 Schritte
  1. 1

    Berechenbarkeit fragt: lässt sich etwas überhaupt berechnen? Komplexität fragt: wie schnell?

  2. 2

    Das Halteproblem ist das berühmteste Beispiel eines unlösbaren Problems.

  3. 3

    Die Diagonalargumentation von Turing ist eine der elegantesten Beweisideen der Informatik.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erläutere die Begriffe Berechenbarkeit und Entscheidbarkeit. Skizziere den Beweis, dass das Halteproblem unentscheidbar ist, und nenne praktische Konsequenzen.

Maturafokus

  • Halteproblem-Beweis (Diagonalisierung) skizzieren können.
  • Unterschied entscheidbar / semi-entscheidbar / unentscheidbar erklären.
  • Church-Turing-These einordnen (philosophisch, nicht beweisbar).

Typische Fehler

  • Unentscheidbarkeit wird als "zu schwer für heutige Computer" missverstanden.
  • Halteproblem nur in einer Sprache (z.B. nur Python) angenommen.
  • Berechenbarkeit mit Effizienz verwechselt.

Aktive Wiederholung

Erkläre die Konsequenzen der Unentscheidbarkeit des Halteproblems für die Softwareentwicklung. Warum gibt es trotzdem statische Codeanalyse?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Turing: On Computable Numbers (1936) (Proc. London Math. Soc.)

§ 03

P, NP und NP-vollständige Probleme#

●●●VertiefungLPINF-Th-4.1

Kernpunkte

Während die Berechenbarkeit fragt „überhaupt lösbar?", fragt die Komplexitätstheorie „effizient lösbar?". Die zentrale Trennlinie verläuft zwischen den Klassen P und NP ().

Komplexitätshierarchie P, NP, NP-vollständig, NP-schwer

NP P NP-vollst. SAT, TSP Offene Frage: gilt P = NP? Bisher ungelöst.
Abb. 3P ⊆ NP; NP-vollständige Probleme bilden den schwierigsten Teil von NP.
P ist die Klasse der Entscheidungsprobleme, die sich in polynomieller Zeit lösen lassen (O(nk)O(n^{k})O(nk)). „Polynomiell" gilt als praktisch handhabbar - Sortieren, kürzeste Wege und der Primzahltest liegen in P.
NP ist die Klasse der Probleme, deren Lösung sich in polynomieller Zeit verifizieren lässt, auch wenn das Finden schwer scheint. NP steht für „nichtdeterministisch polynomiell", nicht für „nicht polynomiell" - ein verbreitetes Missverständnis. Eine erfüllende SAT-Belegung zu prüfen ist leicht, sie zu finden vermutlich schwer (siehe Beispiel).
Offensichtlich gilt P⊆NPP \subseteq NPP⊆NP (was man lösen kann, kann man auch verifizieren). Ob umgekehrt NP⊆PNP \subseteq PNP⊆P, also P = NP, ist seit 1971 offen und eines der mit je 1 Mio. Dollar dotierten Millennium-Probleme; die meisten Fachleute vermuten P≠NPP \neq NPP=NP.
Ein Problem ist NP-vollständig, wenn es (a) in NP liegt und (b) sich jedes andere NP-Problem in polynomieller Zeit darauf reduzieren lässt - es ist also „mindestens so schwer" wie alle NP-Probleme. SAT war das erste (Satz von Cook-Levin); weitere Klassiker sind 3-SAT, TSP (Travelling Salesman), Subset Sum und das Cliquen-Problem. Die Tragweite: Fände man für ein NP-vollständiges Problem einen Polynomialalgorithmus, wäre sofort P=NPP=NPP=NP.
Solange P≠NPP \neq NPP=NP gilt, behilft man sich bei NP-schweren Problemen mit Approximationsalgorithmen, Heuristiken und leistungsfähigen SAT-Solvern, die viele reale Instanzen schnell lösen. Häufige Fehler: NP als „nicht polynomiell" deuten, NP-vollständig mit unentscheidbar gleichsetzen (NP-Probleme sind lösbar, nur evtl. langsam), oder eine Approximation für die exakte Lösung halten.
P⊆NP⊆EXPTIMEP \subseteq NP \subseteq EXPTIMEP⊆NP⊆EXPTIME

Hierarchie der Komplexitätsklassen

Musterbeispiel

Eine SAT-Belegung verifizieren (Zertifikat)

Prüfe, ob die Belegung x1=1, x2=0, x3=1x_{1}=1,\ x_{2}=0,\ x_{3}=1x1​=1, x2​=0, x3​=1 die Formel (x1∨¬x2)∧(¬x1∨x3)∧(x2∨x3)(x_{1} \lor \lnot x_{2}) \land (\lnot x_{1} \lor x_{3}) \land (x_{2} \lor x_{3})(x1​∨¬x2​)∧(¬x1​∨x3​)∧(x2​∨x3​) erfüllt.

  1. 01Klausel 1

    (x1∨¬x2)=(1∨¬0)=(1∨1)=1(x_{1} \lor \lnot x_{2}) = (1 \lor \lnot 0) = (1 \lor 1) = 1(x1​∨¬x2​)=(1∨¬0)=(1∨1)=1.

  2. 02Klausel 2

    (¬x1∨x3)=(¬1∨1)=(0∨1)=1(\lnot x_{1} \lor x_{3}) = (\lnot 1 \lor 1) = (0 \lor 1) = 1(¬x1​∨x3​)=(¬1∨1)=(0∨1)=1.

  3. 03Klausel 3

    (x2∨x3)=(0∨1)=1(x_{2} \lor x_{3}) = (0 \lor 1) = 1(x2​∨x3​)=(0∨1)=1.

  4. 04Konjunktion

    Alle Klauseln sind erfüllt: 1∧1∧1=11 \land 1 \land 1 = 11∧1∧1=1 - die Belegung erfüllt die Formel.

  5. 05Bedeutung

    Das Prüfen einer gegebenen Belegung kostet nur O(Anzahl Klauseln)O(\text{Anzahl Klauseln})O(Anzahl Klauseln) - deshalb liegt SAT in NP. Eine erfüllende Belegung zu finden erfordert im Worst Case das Durchsuchen von 2n2^{n}2n Kombinationen.

Ergebnis: Die Belegung x1=1,x2=0,x3=1x_{1}=1, x_{2}=0, x_{3}=1x1​=1,x2​=0,x3​=1 ist ein „Zertifikat", das die Erfüllbarkeit in linearer Zeit nachweist. Verifizieren ist leicht (NP), Finden ist schwer - SAT ist NP-vollständig (Cook-Levin).

Schritt-für-Schritt Erklärung3 Schritte
  1. 1

    P und NP sind die zwei wichtigsten Komplexitätsklassen - sie definieren, was praktisch lösbar ist.

    Komplexitätshierarchie P, NP, NP-vollständig, NP-schwer

    NP P NP-vollst. SAT, TSP Offene Frage: gilt P = NP? Bisher ungelöst.
    Abb.P ⊆ NP; NP-vollständige Probleme bilden den schwierigsten Teil von NP.
  2. 2

    NP-vollständig heisst: ist eines davon effizient lösbar, sind sie alle effizient lösbar.

  3. 3

    Solange P != NP gilt, vertrauen wir auf approximative Lösungen, Heuristiken und SAT-Solver.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre die Komplexitätsklassen P und NP. Was bedeutet NP-vollständig? Diskutiere die Bedeutung der offenen Frage P = NP an einem Beispiel.

Maturafokus

  • P/NP/NPC im Mengenbild zeichnen.
  • Begriff polynomielle Reduktion erklären.
  • TSP/SAT als Beispiele und ihre praktischen Auswirkungen (Approximationen, Heuristiken) nennen.

Typische Fehler

  • NP wird als "nicht polynomiell" interpretiert (richtig: "nichtdeterministisch polynomiell").
  • NP-vollständig wird mit "unentscheidbar" gleichgesetzt.
  • Approximationsalgorithmen werden mit exakter Lösung verwechselt.

Aktive Wiederholung

Erkläre, warum SAT NP-vollständig ist (Satz von Cook-Levin). Welche praktischen Strategien wendet man auf NP-schwere Probleme an?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Cook: The Complexity of Theorem-Proving Procedures (STOC 1971) · Clay Mathematics Institute - P vs NP Problem (CMI)

Inhalt

Abschnitt -- / 03

    • 01Endliche Automaten und reguläre Sprachen◐
    • 02Berechenbarkeit und Halteproblem●
    • 03P, NP und NP-vollständige Probleme●

0/3 Gelesen

Aus den Notizen ins Training

INF-Th - Theoretische Informatik

Festige dieses Thema an passenden Aufgaben aus der Fragenbank.

~9
Min
4
Kompetenzen
Üben
Beispielfrage

Erkläre den Begriff "endlicher Automat". Konstruiere einen DFA für die Sprache aller Binärstrings mit gerader Anzahl Einsen.

7 BE · 2022

Zur Fragenbank

Belege & Quellen

Quellen

Cengage

  • Sipser: Introduction to the Theory of Computation

Proc. London Math. Soc.

  • Turing: On Computable Numbers (1936)

STOC 1971

  • Cook: The Complexity of Theorem-Proving Procedures

CMI

  • Clay Mathematics Institute - P vs NP Problem

Vorheriges Thema

INF-OS - Betriebssysteme und Hardware

Nächstes Thema

INF-WebSE - Webentwicklung und Software Engineering

EuraStudy·Notizen T·08·MMXXVI

Weiter mit dem nächsten Thema — der Lernpfad bleibt erhalten.