Informatik · Grundlagen · Logik, Automaten, Sprachen, Berechenbarkeit und Komplexität

Theoretische Informatik

Von Aussagen- und Prädikatenlogik über Automaten, Grammatiken und Turing-Maschinen bis zu P = NP, Petri-Netzen und Anwendungen in Compilerbau, Verifikation und Kryptologie – ein zusammenhängender Lernweg in 8 Bereichen und 32 Einheiten.

Aussagenlogik

Formeln aus Elementaraussagen und Operatoren: ihre Syntax, ihre Bedeutung, Normalformen und Kalküle, mit denen man Folgerungen mechanisch beweist.

(A⇒B)≡(¬A∨B)(A \Rightarrow B) \equiv (\lnot A \lor B)
  1. 1.1Grundbegriffe der AussagenlogikElementaraussagen, Operatoren und Wahrheitstabellen – und die Aussagenlogik als formale Sprache mit Grammatik und Syntaxbaum.Interaktiv0/15
  2. 1.2Rechenregeln und NormalformenUmformungsregeln, DNF und KNF – und der Schritt vom Umformen zum Kalkül, in dem Beweise reine Symbolmanipulation sind.Interaktiv0/12
  3. 1.3Interpretation und ErfüllbarkeitEine Interpretation belegt die Variablen mit Wahrheitswerten. Wie viele Belegungen eine Formel wahr machen, teilt Formeln in vier Klassen.Interaktiv0/6
  4. 1.4Indirekter Beweis und ResolutionDen Widerspruch mechanisch suchen: Klauseln verschmelzen, bis die leere Klausel entsteht.Interaktiv0/7
  5. 1.5Korrektheit und VollständigkeitBeweist ein Kalkül nur Wahres – und alles Wahre? Für die Aussagenlogik lautet die Antwort zweimal ja.Interaktiv0/6

Prädikatenlogik

Logik mit Objekten, Eigenschaften und Quantoren – bis zu Gödels Grenzen der Beweisbarkeit und zur Logik-Programmierung mit Prolog.

∀x ∃y: P(x,y)\forall x\, \exists y:\ P(x, y)
  1. 2.1Grundbegriffe der PrädikatenlogikTerme, Prädikate und Quantoren über einem Universum – die Sprache, in der auch Datenbankabfragen formuliert sind.Interaktiv0/12
  2. 2.2Resolution in der PrädikatenlogikBevor zwei Literale sich aufheben können, müssen ihre Terme passend gemacht werden – durch Unifikation.Interaktiv0/6
  3. 2.3Vollständigkeit und UnvollständigkeitHilberts Traum einer vollständig beweisbaren Mathematik – und Gödels Nachweis, dass er sich nicht erfüllen lässt.Interaktiv0/8
  4. 2.4Logik-Programmierung mit PrologProgrammieren durch Beschreiben: Fakten und Regeln aufschreiben, Anfragen stellen – die Suche übernimmt Prolog.Interaktiv0/10

Endliche Automaten und reguläre Ausdrücke

Maschinen mit endlichem Gedächtnis, die Wörter lesen und akzeptieren – und die Mustersprache der regulären Ausdrücke, die genau dasselbe kann.

L(DFA)=L(NFA)=LregL(\mathrm{DFA}) = L(\mathrm{NFA}) = L_{\mathrm{reg}}
  1. 3.1Grundbegriffe endlicher AutomatenZustände, Übergänge, Start und Ziel: deterministische und nichtdeterministische Automaten, Akzeptoren und Transduktoren.Interaktiv0/11
  2. 3.2Reguläre Ausdrücke und SprachenMuster aus Alternative, Verkettung und Wiederholung – genauso mächtig wie endliche Automaten, und mit klaren Grenzen.Interaktiv0/9
  3. 3.3PraxisanwendungenWo Automaten und reguläre Ausdrücke täglich arbeiten: in Suchfunktionen, Eingabefiltern, Compilern und Schaltungen.Interaktiv0/5

Formale Sprachen und Grammatiken

Grammatiken erzeugen Sprachen. Nach der Form ihrer Regeln ordnet die Chomsky-Hierarchie sie in vier Stufen – mit sehr unterschiedlicher Entscheidbarkeit.

L3⊂L2⊂L1⊂L0L_3 \subset L_2 \subset L_1 \subset L_0
  1. 4.1Grundbegriffe formaler SprachenAlphabet, Wort, Sprache und Grammatik – und die vier Fragen, die man einer Sprache stellen kann.Interaktiv0/5
  2. 4.2Die Chomsky-HierarchieVier Grammatiktypen, vier Sprachklassen, echt ineinander verschachtelt.Interaktiv0/8
  3. 4.3Kontextfreie GrammatikenDie Grammatiken der Programmiersprachen: Ableitungsbäume, Mehrdeutigkeit, BNF und ihre eigene Version des Pumping-Lemmas.Interaktiv0/10
  4. 4.4Kontextsensitive GrammatikenRegeln, die nur in einer bestimmten Umgebung greifen – mächtiger, aber kaum noch entscheidbar.Interaktiv0/5

Berechenbarkeit und Turing-Maschinen

Was kann ein Computer überhaupt berechnen? Turing-Maschinen und gleich mächtige Modelle – und Probleme wie das Halteproblem, die kein Programm lösen kann.

(z,b)→(z′,b′,v)(z, b) \to (z', b', v)
  1. 5.1Modelle der BerechenbarkeitTuring-Maschine und Lambda-Kalkül beschreiben dasselbe – die Church-Turing-These macht daraus den Begriff „berechenbar“.0/4
  2. 5.2Turing-MaschinenEin Band, ein Kopf und eine Tabelle von Anweisungen – das einfachste Modell eines Computers.0/9
  3. 5.3Weitere BerechnungsmodelleLoop, While, Goto und rekursive Funktionen: Welche Sprachmittel braucht man für volle Berechnungsstärke?0/10
  4. 5.4Berechenbarkeit, Entscheidbarkeit und das HalteproblemManche Ja-Nein-Fragen über Programme kann kein Programm beantworten – das Halteproblem ist die berühmteste.0/15

Komplexitätstheorie

Nicht nur ob, sondern wie schnell: Wachstumsklassen, Zeit- und Platzbedarf und die offene Frage P = NP.

P=?NP\mathrm P \overset{?}{=} \mathrm{NP}
  1. 6.1Landausche O-NotationWie schnell wächst der Aufwand mit der Eingabegröße? Die O-Notation vergleicht Funktionen, ohne sich um Konstanten zu kümmern.0/7
  2. 6.2Grundbegriffe der KomplexitätstheorieZeit und Speicher als Ressourcen – gemessen an Algorithmen und an ganzen Aufgaben, mit Sortieren als Paradebeispiel.0/7
  3. 6.3P = NP?Ist Finden so leicht wie Prüfen? Die wichtigste offene Frage der Informatik – und was Quantencomputer daran ändern.0/11
  4. 6.4NP-vollständige ProblemeVon Logik über Packprobleme bis zu Graphen: ein Katalog harter Probleme, die alle aneinander hängen.0/7

Petri-Netze

Ein grafisches Modell für nebenläufige Systeme: Marken wandern durch ein Netz aus Plätzen und Transitionen – mit Werkzeugen für Verklemmungen, Erreichbarkeit und Invarianten.

s [t⟩ s′s \,[t\rangle\, s'
  1. 7.1Graphen und Petri-NetzeBipartite Graphen aus Plätzen und Transitionen, Marken als Zustand und das Schalten als einziger Rechenschritt.0/10
  2. 7.2Eigenschaften nebenläufiger SystemeLebendigkeit, Beschränktheit und Verklemmungsfreiheit – modelliert am Beispiel der speisenden Philosophen.0/8
  3. 7.3Erreichbarkeit in Petri-NetzenWelche Zustände kann ein Netz überhaupt annehmen? Der Erreichbarkeitsgraph beantwortet das – solange er endlich bleibt.0/8
  4. 7.4Invarianten von Petri-NetzenLineare Algebra für Netze: Schalten als Vektoraddition, und Invarianten als Größen, die sich beim Schalten nie ändern.0/9

Anwendungen der Logik und der theoretischen Informatik

Wo die Theorie Praxis wird: im Compiler, bei der Verifikation von Programmen, in der künstlichen Intelligenz und in der Kryptologie.

{P} S {Q}\{P\}\ S\ \{Q\}
  1. 8.1CompilerAutomaten, Grammatiken und Typregeln im Zusammenspiel: der Weg vom Quelltext zum Maschinencode.0/6
  2. 8.2ProgrammkorrektheitTut ein Programm, was es soll? Spezifikationen, Hoare-Logik und Schleifeninvarianten als Werkzeuge für Beweise über Programme.0/8
  3. 8.3Künstliche IntelligenzVon regelbasierten Expertensystemen bis zur datengetriebenen KI – und was formale Sprachen mit Sprachverarbeitung zu tun haben.0/4
  4. 8.4KryptologieSicherheit aus Komplexität: Einwegfunktionen, RSA, Diffie-Hellman und die Bedrohung durch Quantencomputer.0/10