EuraStudy
Notizen/Informatik/INF-Th - Theoretische Informatik
AT · 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·~11 Min Lesezeit·4 Kompetenzen·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 · Zeilenabstand: Kompakt

Medien immer laden: aus

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

3 Abschnitte · 15 Merksätze · 2 Formeln · 15 Fehlerwarnungen

§ 01
§ 01

Endliche Automaten und reguläre Sprachen#

~4 Min Lesezeit●●○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.
Abb. 1 ↓
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.

Vokabeln

→ Kartei
  • deterministischer AutomatAutomat mit genau einem Folgezustand je Zeichen.
  • nichtdeterministischer AutomatAutomat mit mehreren möglichen Folgezuständen.
  • reguläre SpracheSprache, die von einem endlichen Automaten erkannt wird.
  • PotenzmengenkonstruktionVerfahren zur Umwandlung eines NFA in einen äquivalenten DFA.
  • regulärer AusdruckKompakte Beschreibung einer regulären Sprache.
  • Pumping-LemmaNotwendige Eigenschaft regulärer Sprachen; dient dem Nachweis der Nicht-Regularität.

Definition eines deterministischen endlichen Automaten

M=(Q,Σ,δ,q0,F),δ:Q×Σ→QM = (Q,\Sigma,\delta,q_{0},F),\quad \delta: Q\times\Sigma \to QM=(Q,Σ,δ,q0​,F),δ:Q×Σ→Q

QQQ ist die Zustandsmenge, Σ\SigmaΣ das Eingabealphabet, δ\deltaδ die Übergangsfunktion, q0q_{0}q0​ der Start- und FFF die Menge der Endzustände. Dass δ\deltaδ eine FUNKTION ist, macht den Automaten deterministisch - je Zustand und Zeichen gibt es genau einen Folgezustand.

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

  • Konstruiere einen deterministischen Automaten für eine einfache Sprache und beschrifte Startzustand, Übergänge und Endzustände vollständig.
  • Skizziere die Potenzmengenkonstruktion, mit der sich jeder nichtdeterministische Automat in einen deterministischen überführen lässt.
  • Prüfe die Akzeptanz vollständig: Das Wort ist akzeptiert, wenn nach der GESAMTEN Eingabe ein Endzustand erreicht ist.
  • Trenne die Quantoren regulärer Ausdrücke: a∗a^{*}a∗ erlaubt null Vorkommen, a+a^{+}a+ verlangt mindestens eines.
  • Nenne das Pumping-Lemma als Werkzeug, um die NICHT-Regularität einer Sprache zu zeigen.

Typische Fehler

  • Nichtdeterministische und deterministische Automaten werden gleichgesetzt; im DFA gibt es je Zeichen genau einen Folgezustand.
  • Die Akzeptanzbedingung wird verkürzt; ein zwischenzeitlich erreichter Endzustand genügt nicht.
  • a∗a^{*}a∗ und a+a^{+}a+ werden vertauscht.
  • Das Pumping-Lemma wird zum Beweis der Regularität verwendet; es taugt nur zur Widerlegung.
  • Der Fehlerzustand wird weggelassen, obwohl der DFA für jedes Zeichen einen Übergang braucht.

§ 01

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema→

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

§ 02
§ 02

Berechenbarkeit und Halteproblem#

~3 Min Lesezeit●●●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.
Abb. 2 ↓
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.

Vokabeln

→ Kartei
  • TuringmaschineFormales Rechenmodell; Maßstab des Berechenbarkeitsbegriffs.
  • entscheidbarEs gibt ein Verfahren, das für jede Eingabe mit Ja oder Nein terminiert.
  • semi-entscheidbarNur die Ja-Fälle terminieren sicher.
  • HalteproblemUnentscheidbare Frage, ob ein Programm bei gegebener Eingabe hält.
  • DiagonalisierungBeweistechnik über die Selbstanwendung; Grundlage des Halteproblembeweises.
  • Church-Turing-TheseAnnahme, dass alles intuitiv Berechenbare turingberechenbar ist.
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

  • Skizziere den Widerspruchsbeweis zum Halteproblem über die Selbstanwendung eines hypothetischen Halte-Entscheiders.
  • Unterscheide entscheidbar, semi-entscheidbar und unentscheidbar an je einem Beispiel.
  • Ordne die Church-Turing-These richtig ein: Sie ist eine These über den Begriff der Berechenbarkeit, kein beweisbarer Satz.
  • Halte fest, dass Unentscheidbarkeit sprachunabhängig ist - kein Programm in keiner Sprache kann das Halteproblem lösen.
  • Trenne Berechenbarkeit von Effizienz: Ein Problem kann berechenbar und dennoch praktisch unlösbar sein.

Typische Fehler

  • Unentscheidbarkeit wird als „für heutige Rechner zu schwer" gedeutet; sie ist prinzipiell.
  • Das Halteproblem wird als Eigenheit einer bestimmten Programmiersprache dargestellt.
  • Berechenbarkeit und Effizienz werden verwechselt.
  • Semi-entscheidbar wird als „manchmal entscheidbar" beschrieben; gemeint ist, dass nur die Ja-Fälle sicher terminieren.
  • Aus der Unentscheidbarkeit wird geschlossen, es gebe keine nützlichen Teillösungen; statische Analysewerkzeuge arbeiten genau dort.

§ 02

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema→

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

§ 03
§ 03

P, NP und NP-vollständige Probleme#

~4 Min Lesezeit●●●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.
Abb. 3 ↓
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.

Vokabeln

→ Kartei
  • Komplexitätsklasse PIn polynomieller Zeit lösbare Entscheidungsprobleme.
  • Komplexitätsklasse NPProbleme, deren Lösung in polynomieller Zeit prüfbar ist.
  • NP-vollständigSchwerste Probleme in NP; jedes NP-Problem lässt sich darauf reduzieren.
  • polynomielle ReduktionEffiziente Übersetzung eines Problems in ein anderes.
  • SATErfüllbarkeitsproblem der Aussagenlogik; erstes bewiesen NP-vollständiges Problem.
  • HeuristikVerfahren ohne Optimalitätsgarantie, aber mit brauchbarer Laufzeit.

Hierarchie der Komplexitätsklassen

P⊆NP⊆EXPTIMEP \subseteq NP \subseteq EXPTIMEP⊆NP⊆EXPTIME

Ob die Inklusionen echt sind, ist offen: P=NPP=NPP=NP ist eines der großen ungelösten Probleme. Bewiesen ist lediglich, dass PPP eine echte Teilmenge von EXPTIME ist.

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. Klausel 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. Klausel 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. Klausel 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 heißt: 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

  • Zeichne das Mengenbild mit P innerhalb von NP und den NP-vollständigen Problemen am oberen Rand.
  • Löse NP richtig auf: nichtdeterministisch polynomiell - eine Lösung lässt sich in polynomieller Zeit PRÜFEN.
  • Erkläre die polynomielle Reduktion als Werkzeug, mit dem sich die Schwierigkeit eines Problems auf ein anderes überträgt.
  • Nenne SAT und das Rundreiseproblem als Standardbeispiele samt praktischer Folge - man arbeitet mit Heuristiken und Näherungsverfahren.
  • Betone die Offenheit der Frage P=NPP=NPP=NP und was ihre Beantwortung praktisch bedeuten würde.

Typische Fehler

  • NP wird als „nicht polynomiell" gelesen.
  • NP-vollständig wird mit unentscheidbar gleichgesetzt; NP-vollständige Probleme sind sehr wohl lösbar, nur aufwendig.
  • Näherungsverfahren werden mit exakten Lösungen verwechselt.
  • Aus der Zugehörigkeit zu NP wird auf praktische Unlösbarkeit geschlossen; P ist eine Teilmenge von NP.
  • Die Reduktionsrichtung wird vertauscht; reduziert wird das SCHWERE auf das zu untersuchende Problem.

§ 03

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema→

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)

Stand 06/2026 · Vollständige Fassung über den Tiefenregler — gleiche Stelle, gleiche Anker

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.

~11
Min
4
Kompetenzen
50
Fragen
Ü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
Wiederholung planen

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

Siehe auch

  • INF-Alg - Algorithmen, Programmierung und KomplexitätDie Komplexitätsklassen ordnen die dort behandelten Verfahren ein.
  • INF-Modell - Boolesche Logik, UML und ModellierungAutomaten und Aussagenlogik teilen dieselbe formale Sprache.
  • INF-DS - DatenstrukturenUntere Schranken wie $\Omega(n\log n)$ begrenzen, was eine Struktur leisten kann.

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.