Informatiktheorie

Einleitung

Informatiktheorie bezeichnet den theoretischen Kern der Informatik. Sie untersucht nicht zuerst konkrete Geräte, Programme oder Apps, sondern die grundlegenden Fragen hinter allem Rechnen: Was kann überhaupt berechnet werden? Wie lässt sich ein Algorithmus präzise beschreiben? Welche Probleme sind leicht, schwer oder vielleicht praktisch unlösbar? Welche Rolle spielen Logik, Sprache, Automat und Beweis beim Verstehen von Informationsverarbeitung?

Die Informatiktheorie verbindet Ideen aus Mathematik, Logik, Sprachwissenschaft, Ingenieurwissenschaft und Philosophie. Sie hilft Dir, Computer nicht nur als Werkzeuge zu benutzen, sondern ihre Möglichkeiten und Grenzen zu verstehen. Besonders wichtig sind dabei die Teilgebiete Automatentheorie, formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie, Algorithmentheorie und Logik in der Informatik. Diese Gebiete zeigen, warum manche Aufgaben automatisch lösbar sind, warum andere Aufgaben sehr viel Zeit benötigen und warum manche Fragen prinzipiell nicht durch ein Programm entschieden werden können.

Lernziele

Nach diesem aiMOOC kannst Du erklären, was die Informatiktheorie untersucht, warum sie für Softwareentwicklung, Künstliche Intelligenz, Kryptographie, Datenbank, Compilerbau und Netzwerke wichtig ist und wie zentrale theoretische Modelle funktionieren. Du lernst, endliche Automaten, Turingmaschinen, formale Grammatiken, Algorithmen, Entscheidungsprobleme und Komplexitätsklassen als Denkwerkzeuge zu nutzen. Außerdem übst Du, informatische Aussagen zu begründen, einfache Modelle zu entwerfen und theoretische Grenzen des Rechnens auf reale Probleme zu übertragen.

Grundlagen der Informatiktheorie

Gegenstand und zentrale Leitfragen

Die Informatiktheorie fragt nach den allgemeinen Strukturen des Rechnens. Ein einzelner Computer kann schneller oder langsamer sein, mehr oder weniger Speicher haben und mit unterschiedlichen Programmiersprachen arbeiten. Die theoretische Informatik abstrahiert davon und fragt: Welche Eigenschaften bleiben gleich, wenn man von der konkreten Maschine absieht?

Wichtige Leitfragen sind: Was ist ein Algorithmus? Was bedeutet Berechenbarkeit? Welche Probleme lassen sich mit einem Programm lösen? Welche Probleme sind zwar lösbar, benötigen aber so viele Ressourcen, dass sie praktisch nicht berechenbar erscheinen? Wie lassen sich Sprachen, Programme, Protokolle und Datenstrukturen formal beschreiben? Wie kann man beweisen, dass ein Verfahren korrekt ist?

Diese Fragen sind nicht nur theoretisch. Sie bestimmen, ob eine Suchmaschine effizient arbeiten kann, ob eine Verschlüsselung sicher ist, ob ein Compiler Quellcode korrekt übersetzt, ob ein Datenbankmanagementsystem Anfragen optimiert und ob ein KI-System zuverlässig überprüft werden kann.

Abstraktion als Methode

Eine zentrale Methode der Informatiktheorie ist die Abstraktion. Dabei werden konkrete Einzelheiten weggelassen, um das Wesentliche sichtbar zu machen. Ein Automat muss nicht aus Metall bestehen. Er kann als mathematisches Modell aus Zuständen, Eingabealphabet, Übergangsfunktion, Startzustand und akzeptierenden Zuständen beschrieben werden. Eine Turingmaschine ist kein moderner Computer, sondern ein Modell, mit dem man die grundsätzliche Leistungsfähigkeit von Berechnung untersuchen kann.

Durch Abstraktion entstehen Modelle, die auf viele technische Situationen anwendbar sind. Ein endlicher Automat kann zum Beispiel einen Fahrkartenautomaten, ein Drehkreuz, ein einfaches Kommunikationsprotokoll oder die Erkennung bestimmter Textmuster beschreiben. Eine formale Grammatik kann natürliche Sprachen teilweise modellieren, Programmiersprachen definieren oder Datenformate wie XML und JSON strukturieren.

Beweisen statt nur Ausprobieren

In der praktischen Programmierung testest Du ein Programm mit Beispielen. In der Informatiktheorie geht es zusätzlich darum, Aussagen allgemein zu beweisen. Ein Test kann zeigen, dass ein Programm für bestimmte Eingaben funktioniert. Ein Beweis kann zeigen, dass ein Algorithmus für alle erlaubten Eingaben korrekt ist.

Dabei nutzt man unter anderem direkte Beweise, Widerspruchsbeweise, vollständige Induktion, Invarianten und Reduktionen. Besonders wichtig ist die Reduktion: Man zeigt, dass ein Problem mindestens so schwer ist wie ein anderes Problem, indem man Lösungen des einen Problems systematisch in Lösungen des anderen Problems übersetzt. Dieses Verfahren ist grundlegend für die Komplexitätstheorie und für den Nachweis von Unentscheidbarkeit.

Formale Sprachen und Grammatiken

Alphabet, Wort und Sprache

In der Informatiktheorie ist ein Alphabet eine endliche Menge von Zeichen. Ein Wort ist eine endliche Folge von Zeichen aus einem Alphabet. Eine formale Sprache ist eine Menge von Wörtern. Diese einfachen Begriffe sind erstaunlich mächtig. Sie ermöglichen es, Programmiersprachen, Datenformate, Suchmuster, Netzwerkprotokolle und Befehlssprachen mathematisch zu beschreiben.

Ein Beispiel: Über dem Alphabet {0, 1} kann man die Sprache aller Wörter betrachten, die mit 1 beginnen und mit 0 enden. Ebenso kann man die Sprache aller gültigen E-Mail-Adressen, aller korrekt geklammerten Ausdrücke oder aller syntaktisch richtigen Programme einer Programmiersprache untersuchen. In der Praxis erkennt man solche Sprachen häufig mit Parsern, Compilern oder regulären Ausdrücken.

Grammatik und Chomsky-Hierarchie

Eine formale Grammatik beschreibt, wie Wörter einer Sprache erzeugt werden können. Sie besteht aus Symbolen und Regeln. Besonders bekannt ist die Chomsky-Hierarchie, die formale Sprachen nach der Art ihrer Grammatiken ordnet. Sie unterscheidet unter anderem reguläre Sprachen, kontextfreie Sprachen, kontextsensitive Sprachen und rekursiv aufzählbare Sprachen.

Diese Einteilung ist nicht nur historisch wichtig. Sie zeigt, welche Art von Automat eine Sprache erkennen kann. Reguläre Sprachen werden von endlichen Automaten erkannt. Kontextfreie Sprachen werden von Kellerautomaten erkannt und sind wichtig für die Struktur von Programmiersprachen. Komplexere Sprachklassen benötigen leistungsfähigere Modelle wie die Turingmaschine.

Bedeutung für Programmiersprachen

Jede Programmiersprache braucht eine klare Syntax. Die Syntax legt fest, welche Zeichenfolgen gültige Programme bilden. Formale Grammatiken helfen dabei, diese Syntax eindeutig zu beschreiben. Ein Compiler oder Interpreter kann dann prüfen, ob ein Programm syntaktisch korrekt ist, und daraus interne Strukturen wie einen Syntaxbaum erzeugen.

Dabei zeigt sich eine wichtige Idee der Informatiktheorie: Sprache ist nicht nur Kommunikation zwischen Menschen, sondern auch ein präzises Werkzeug für Maschinen. Wenn die Regeln unklar sind, kann ein Computer sie nicht zuverlässig anwenden. Deshalb sind formale Sprachen eine Brücke zwischen menschlichem Denken und maschineller Verarbeitung.

Automatenmodelle

Endliche Automaten

Ein endlicher Automat ist ein Modell mit endlich vielen Zuständen. Er liest ein Eingabewort Zeichen für Zeichen und wechselt abhängig vom aktuellen Zustand und vom gelesenen Zeichen in einen neuen Zustand. Am Ende entscheidet der Automat, ob das Wort akzeptiert oder verworfen wird.

Endliche Automaten eignen sich für Aufgaben mit begrenztem Gedächtnis. Sie können zum Beispiel einfache Mustererkennung, Ampelsteuerungen, Türsysteme oder Zustände in einem Computerspiel modellieren. Sie können aber nicht beliebig tief verschachtelte Strukturen zählen, weil ihnen dafür ein unbegrenzter Speicher fehlt. Diese Grenze macht deutlich, warum unterschiedliche Rechenmodelle unterschiedliche Fähigkeiten besitzen.

Kellerautomaten

Ein Kellerautomat erweitert den endlichen Automaten um einen Stapelspeicher, den sogenannten Keller. Auf diesen Speicher kann nur nach dem Last-in-first-out-Prinzip zugegriffen werden: Was zuletzt abgelegt wurde, wird zuerst wieder gelesen. Dadurch kann ein Kellerautomat verschachtelte Strukturen erkennen, etwa korrekt gesetzte Klammern.

Kellerautomaten sind wichtig für kontextfreie Sprachen. Viele Grundstrukturen von Programmiersprachen lassen sich kontextfrei beschreiben. Wenn ein Compiler prüft, ob Klammern, Blöcke oder Ausdrücke richtig geschachtelt sind, steckt dahinter eine Idee, die mit Kellerautomaten verwandt ist.

Turingmaschinen

Die Turingmaschine ist eines der wichtigsten Modelle der Informatiktheorie. Sie besteht aus einem unendlich gedachten Band, einem Schreib-Lese-Kopf, endlich vielen Zuständen und Übergangsregeln. Sie kann Zeichen lesen, schreiben, den Kopf bewegen und ihren Zustand ändern. Obwohl dieses Modell einfach wirkt, beschreibt es nach der Church-Turing-These genau das, was im intuitiven Sinn algorithmisch berechenbar ist.

Die Turingmaschine hilft, die Grenzen des Rechnens zu untersuchen. Sie zeigt nicht nur, was berechnet werden kann, sondern auch, was nicht berechnet werden kann. Ein berühmtes Beispiel ist das Halteproblem: Es gibt kein allgemeines Programm, das für jedes beliebige Programm und jede beliebige Eingabe korrekt entscheidet, ob dieses Programm irgendwann anhält oder endlos weiterläuft.

Berechenbarkeitstheorie

Entscheidungsprobleme

Ein Entscheidungsproblem ist eine Frage, die für jede Eingabe mit Ja oder Nein beantwortet werden soll. Beispiele sind: Ist eine Zahl prim? Enthält ein Graph einen bestimmten Weg? Ist ein Wort Teil einer bestimmten formalen Sprache? Hält ein gegebenes Programm bei einer gegebenen Eingabe?

Die Berechenbarkeitstheorie untersucht, ob solche Probleme prinzipiell durch einen Algorithmus gelöst werden können. Dabei geht es nicht zuerst darum, wie schnell ein Algorithmus ist. Entscheidend ist, ob überhaupt ein Verfahren existiert, das nach endlich vielen Schritten immer die richtige Antwort liefert.

Entscheidbarkeit und Unentscheidbarkeit

Ein Problem heißt entscheidbar, wenn es einen Algorithmus gibt, der für jede Eingabe anhält und korrekt mit Ja oder Nein antwortet. Ein Problem heißt unentscheidbar, wenn ein solcher Algorithmus nicht existiert. Die Existenz unentscheidbarer Probleme ist eine der tiefsten Einsichten der Informatiktheorie.

Das Halteproblem ist das klassische Beispiel für ein unentscheidbares Problem. Es zeigt, dass es grundsätzliche Grenzen automatischer Analyse gibt. Kein Programm kann jedes andere Programm vollständig daraufhin überprüfen, ob es für jede mögliche Eingabe anhält. Diese Erkenntnis ist für Softwareverifikation, Programmanalyse, Sicherheit und Künstliche Intelligenz bedeutsam.

Berechenbar heißt nicht immer praktisch lösbar

Wenn ein Problem berechenbar ist, bedeutet das noch nicht, dass es praktisch gut lösbar ist. Ein Algorithmus kann theoretisch existieren, aber mehr Zeit oder Speicher benötigen, als im Universum realistisch verfügbar ist. Hier beginnt die Komplexitätstheorie. Sie fragt nicht nur, ob ein Problem lösbar ist, sondern wie viele Ressourcen eine Lösung benötigt.

Diese Unterscheidung ist besonders wichtig. Die Berechenbarkeitstheorie beantwortet die Frage nach dem prinzipiellen Können. Die Komplexitätstheorie untersucht die Frage nach dem effizienten Können.

Komplexitätstheorie

Zeit- und Speicherkomplexität

Die Komplexitätstheorie untersucht den Aufwand von Algorithmen. Besonders wichtig sind Zeitkomplexität und Speicherkomplexität. Die Zeitkomplexität beschreibt, wie die Anzahl der Rechenschritte mit der Größe der Eingabe wächst. Die Speicherkomplexität beschreibt, wie viel Speicher benötigt wird.

Dabei interessiert man sich meist nicht für die genaue Laufzeit auf einem bestimmten Computer. Entscheidend ist das Wachstum. Ein Algorithmus mit linearer Laufzeit wächst ungefähr proportional zur Eingabegröße. Ein quadratischer Algorithmus wächst deutlich schneller. Ein exponentieller Algorithmus kann schon bei relativ kleinen Eingaben praktisch unbrauchbar werden.

O-Notation

Die O-Notation beschreibt das asymptotische Wachstum von Funktionen. Sie ermöglicht es, Algorithmen unabhängig von konkreter Hardware zu vergleichen. Wenn ein Sortierverfahren im schlechtesten Fall eine Laufzeit von O(n²) hat und ein anderes O(n log n), dann wächst das zweite Verfahren bei großen Eingaben in der Regel deutlich langsamer.

Die O-Notation ist eine Sprache für Effizienz. Sie zeigt Dir, warum ein Programm bei kleinen Testdaten gut funktionieren kann, bei großen Datenmengen aber scheitert. In Datenanalyse, Künstliche Intelligenz, Datenbanken und Simulationen ist diese Einsicht besonders wichtig.

P, NP und NP-Vollständigkeit

Die Komplexitätsklasse P enthält Probleme, die sich in polynomieller Zeit lösen lassen. Die Klasse NP enthält Probleme, bei denen eine vorgeschlagene Lösung in polynomieller Zeit überprüft werden kann. Die offene Frage, ob P = NP gilt, gehört zu den berühmtesten ungelösten Problemen der Informatik und Mathematik.

Ein Problem heißt NP-vollständig, wenn es in NP liegt und jedes Problem aus NP effizient auf dieses Problem zurückgeführt werden kann. Wenn man für ein NP-vollständiges Problem einen effizienten Algorithmus fände, hätte man damit effiziente Algorithmen für alle Probleme in NP. Beispiele, die häufig in diesem Zusammenhang behandelt werden, sind das Erfüllbarkeitsproblem der Aussagenlogik, das Rucksackproblem und das Problem des Handlungsreisenden in bestimmten Entscheidungsvarianten.

Logik, Beweise und Korrektheit

Aussagenlogik und Prädikatenlogik

Logik ist eine Grundlage der Informatiktheorie. In der Aussagenlogik werden Aussagen mit Operatoren wie und, oder, nicht und wenn-dann verknüpft. In der Prädikatenlogik kommen Variablen, Quantoren und Prädikate hinzu. Diese Formen der Logik helfen, Bedingungen, Programmeigenschaften und Datenbankanfragen präzise zu formulieren.

In der Informatik begegnet Dir Logik überall: in if-Anweisungen, Datenbankabfragen, Schaltkreisen, Spezifikationen, Verifikation und Künstliche Intelligenz. Wer logische Strukturen versteht, kann Programme klarer entwerfen und Fehler systematischer finden.

Korrektheit von Algorithmen

Ein Algorithmus ist korrekt, wenn er für alle zulässigen Eingaben das geforderte Ergebnis liefert. Um das zu zeigen, reicht Ausprobieren nicht aus. Man braucht eine Begründung. Häufig werden Invarianten verwendet. Eine Invariante ist eine Aussage, die während der Ausführung eines Algorithmus an bestimmten Stellen immer wahr bleibt.

Ein einfaches Beispiel ist eine Schleife, die eine Liste durchsucht. Eine passende Invariante kann lauten: Alle bisher geprüften Elemente erfüllen nicht die gesuchte Eigenschaft. Wenn diese Aussage am Anfang gilt, durch jeden Schleifendurchlauf erhalten bleibt und am Ende zur gewünschten Schlussfolgerung führt, entsteht ein Korrektheitsbeweis.

Verifikation und Grenzen automatischer Prüfung

Softwareverifikation versucht, die Korrektheit von Software systematisch nachzuweisen. Das ist in sicherheitskritischen Bereichen wichtig, etwa bei Medizintechnik, Luftfahrt, Kryptographie, Verkehrssystemen und Industrieanlagen. Theoretische Grenzen wie das Halteproblem zeigen jedoch, dass automatische Verifikation nicht für alle denkbaren Programme vollständig möglich ist.

Trotzdem ist die Informatiktheorie hier sehr nützlich. Sie hilft zu unterscheiden, welche Eigenschaften automatisch überprüfbar sind, welche nur teilweise überprüfbar sind und wo menschliche Modellierung, formale Spezifikation und begrenzte Analyse nötig bleiben.

Anwendungen und Bedeutung

Compilerbau und Programmiersprachen

Im Compilerbau werden formale Sprachen, Grammatiken, Automaten und Parser praktisch eingesetzt. Ein Compiler liest Quellcode, prüft seine Struktur, erzeugt Zwischenrepräsentationen und übersetzt ihn in ausführbaren Code. Ohne theoretische Grundlagen wäre es schwer, Programmiersprachen zuverlässig und eindeutig zu definieren.

Kryptographie und Sicherheit

Die Kryptographie nutzt Algorithmen, Komplexitätstheorie und Zahlentheorie. Viele Verschlüsselungsverfahren beruhen darauf, dass bestimmte Probleme praktisch schwer zu lösen sind. Sicherheit bedeutet hier oft nicht, dass ein Angriff logisch unmöglich ist, sondern dass er mit bekannten Verfahren und verfügbaren Ressourcen unrealistisch aufwendig wäre.

Künstliche Intelligenz und Datenanalyse

Auch Künstliche Intelligenz und Datenanalyse brauchen theoretische Grundlagen. Lernverfahren müssen mit großen Datenmengen umgehen. Such- und Optimierungsprobleme können sehr komplex werden. Die Komplexitätstheorie hilft, realistische Erwartungen an Verfahren zu entwickeln. Logik und formale Sprachen spielen außerdem in Wissensrepräsentation, automatischem Schließen und Verarbeitung natürlicher Sprache eine Rolle.

Gesellschaftliche Relevanz

Die Informatiktheorie wirkt auf gesellschaftliche Fragen. Wenn automatisierte Systeme Entscheidungen unterstützen, ist es wichtig zu verstehen, was berechenbar, überprüfbar und erklärbar ist. Bei Datenschutz, digitaler Sicherheit, algorithmischen Entscheidungen und KI-Systemen hilft theoretisches Wissen, Möglichkeiten und Grenzen sachlich einzuschätzen.

Lernraum: Medien und OER-Hinweise

Wikimedia Commons

Da hier keine unsicheren oder frei geratenen Mediendateien eingebunden werden sollen, nutzt dieser Lernraum sichere Such- und OER-Hinweise. Für passende freie Abbildungen kannst Du gezielt in Wikimedia Commons recherchieren und die Lizenzhinweise prüfen.

Wikipedia und weitere OER

Wikipedia: Wikipedia-Artikel Theoretische Informatik
Wikipedia: Wikipedia-Artikel Turingmaschine
Wikiversity: Wikiversity-Suche zu Theoretische Informatik
Serlo und andere freie Lernplattformen: Nutze Suchbegriffe wie Informatik, Algorithmus, Logik, Automat und Komplexität, und prüfe jeweils Lizenz, Niveau und fachliche Passung.

Lernvideos und Suchhinweise

Prüfe vor dem Einsatz eines Videos im Unterricht immer fachliche Richtigkeit, Werbeumfeld, Altersangemessenheit, Barrierefreiheit und Lizenzhinweise.

Interaktive Aufgaben

Quiz: Teste Dein Wissen

Was untersucht die Informatiktheorie besonders grundlegend? (Möglichkeiten und Grenzen des Rechnens) (!Farben von Computergehäusen) (!Geschwindigkeit einzelner Drucker) (!Geschichte eines bestimmten Smartphones)

Was ist ein Alphabet in der formalen Sprachtheorie? (Eine endliche Menge von Zeichen) (!Eine Liste aller Programmiersprachen) (!Ein Betriebssystem für Textverarbeitung) (!Eine zufällige Sammlung von Dateien)

Welche Aussage beschreibt eine formale Sprache am besten? (Eine Menge von Wörtern über einem Alphabet) (!Ein Gespräch zwischen zwei Menschen) (!Eine Sammlung beliebiger Computerbilder) (!Ein einzelner Prozessorbefehl)

Welches Modell erkennt reguläre Sprachen? (Endlicher Automat) (!Tabellenkalkulation) (!Grafikkarte) (!Datenkabel)

Wozu dient ein Kellerautomat hauptsächlich? (Zum Erkennen kontextfreier Sprachen) (!Zum Drucken von Quellcode) (!Zum Speichern von Bildern auf Papier) (!Zum Beschleunigen eines Monitors)

Was zeigt das Halteproblem? (Es gibt unentscheidbare Probleme) (!Jedes Programm hält immer an) (!Alle Probleme sind leicht lösbar) (!Computer können keine Zahlen verarbeiten)

Was beschreibt die Zeitkomplexität eines Algorithmus? (Das Wachstum der Rechenschritte mit der Eingabegröße) (!Die Farbe der Benutzeroberfläche) (!Die Anzahl der Tasten auf einer Tastatur) (!Die Lautstärke eines Computers)

Welche Klasse enthält Probleme, deren Lösungen in polynomieller Zeit überprüft werden können? (NP) (!HTML) (!USB) (!RGB)

Welche Methode zeigt oft, dass ein Problem mindestens so schwer ist wie ein anderes? (Reduktion) (!Formatierung) (!Komprimierung des Bildschirms) (!Austausch des Netzteils)

Warum sind formale Grammatiken im Compilerbau wichtig? (Sie beschreiben die Syntax von Programmiersprachen) (!Sie erhöhen die Bildschirmhelligkeit) (!Sie ersetzen alle Algorithmen) (!Sie löschen automatisch fehlerhafte Dateien)

Memory

Alphabet	Zeichenmenge
Wort	Zeichenfolge
Sprache	Wortmenge
Endlicher Automat	Zustandsmodell
Kellerautomat	Stapelspeicher
Turingmaschine	Berechnungsmodell
Halteproblem	Unentscheidbarkeit
O-Notation	Wachstumsordnung

Drag and Drop

Ordne die richtigen Begriffe zu.	Thema
Endlicher Automat	Reguläre Sprache
Kellerautomat	Kontextfreie Sprache
Turingmaschine	Berechenbarkeit
O-Notation	Laufzeitwachstum
Reduktion	Schwierigkeitsvergleich
Grammatik	Spracherzeugung

...

Kreuzworträtsel

Turingmaschine	Welches theoretische Modell nutzt ein Band und einen Schreib-Lese-Kopf?
Automat	Wie heißt ein Modell mit Zuständen und Übergängen?
Algorithmus	Wie heißt eine eindeutige Schrittfolge zur Lösung eines Problems?
Grammatik	Wie heißt ein Regelsystem zur Erzeugung formaler Sprachen?
Komplexitaet	Welcher Begriff beschreibt den Ressourcenaufwand von Algorithmen?
Reduktion	Welche Methode vergleicht die Schwierigkeit zweier Probleme?

LearningApps

Lückentext

Die

untersucht die grundlegenden Möglichkeiten und Grenzen des Rechnens. Ein

ist in der formalen Sprachtheorie eine endliche Menge von Zeichen. Eine formale

ist eine Menge von Wörtern über einem Alphabet. Ein endlicher

arbeitet mit Zuständen und Übergängen. Ein

besitzt zusätzlich einen Stapelspeicher. Die

ist ein zentrales Modell zur Untersuchung von Berechenbarkeit. Das

zeigt, dass es unentscheidbare Probleme gibt. Die

untersucht den Aufwand von Algorithmen. Die

beschreibt das Wachstum einer Laufzeitfunktion. Eine

kann zeigen, dass ein Problem mindestens so schwer ist wie ein anderes.

Offene Aufgaben

Leicht

Begriffskarte: Erstelle eine Begriffskarte zu Informatiktheorie mit den Begriffen Algorithmus, Automat, Sprache, Berechenbarkeit und Komplexität.
Alltagsautomat: Beschreibe einen Automaten aus Deinem Alltag, zum Beispiel eine Ampel, einen Getränkeautomaten oder ein Drehkreuz, und notiere mögliche Zustände.
Formale Sprache: Erfinde ein kleines Alphabet und beschreibe eine Sprache aus Wörtern, die nach einer klaren Regel gebildet werden.
Erklärtext: Schreibe einen kurzen Text, der einer jüngeren Lerngruppe erklärt, warum nicht jedes Problem automatisch lösbar ist.

Standard

Automatenmodell: Entwirf einen endlichen Automaten, der Wörter über dem Alphabet {0, 1} akzeptiert, die mit 1 beginnen und mit 0 enden.
Grammatikentwurf: Formuliere einfache Regeln für korrekt geklammerte Ausdrücke und erkläre, warum ein Stapelspeicher hilfreich sein kann.
Laufzeitanalyse: Vergleiche zwei Suchverfahren in einer Liste und beschreibe, wie sich ihre Laufzeit bei wachsender Eingabegröße verändert.
Halteproblem: Erstelle eine Präsentationsfolie, die die Idee des Halteproblems ohne Programmcode erklärt.

Schwer

Reduktion: Recherchiere ein klassisches Beispiel einer Reduktion und erkläre, was dabei von einem Problem in ein anderes übersetzt wird.
P-NP-Problem: Schreibe einen argumentativen Text darüber, warum die Frage P = NP für Kryptographie, Optimierung und Künstliche Intelligenz bedeutsam ist.
Compilerbau: Analysiere an einer einfachen Programmiersprache, welche Rolle Token, Parser, Grammatik und Syntaxbaum spielen.
Projekt Informatiktheorie: Entwickle ein kleines Lernvideo oder eine Animation, die endlicher Automat, Kellerautomat und Turingmaschine vergleicht.

type=create break=no preload=CHAT GPT TEXT HIER EINFÜGEN default= width=30 placeholder= Dein MOOC Titel buttonlabel=MOOC erstellen </inputbox>

Lernkontrolle

Transfer Automat: Entwickle für ein reales System Deiner Wahl ein Zustandsmodell und begründe, welche Informationen der Automat speichern muss und welche nicht.
Transfer Sprache: Vergleiche eine natürliche Sprache mit einer formalen Sprache und erkläre, warum Computer eindeutige Regeln benötigen.
Transfer Berechenbarkeit: Erkläre anhand eines selbst gewählten Beispiels, warum die Aussage berechenbar nicht dasselbe bedeutet wie praktisch effizient lösbar.
Transfer Komplexität: Beurteile, warum ein Algorithmus mit exponentiellem Wachstum bei kleinen Eingaben funktionieren kann, bei großen Eingaben aber unbrauchbar wird.
Transfer Sicherheit: Erkläre, wie die Schwierigkeit bestimmter Probleme zur Sicherheit in der Kryptographie beitragen kann.
Transfer Verantwortung: Diskutiere, warum theoretisches Wissen über Grenzen automatischer Prüfung für den verantwortungsvollen Einsatz von KI-Systemen wichtig ist.

Lernnachweis

Der Lernnachweis zur Informatiktheorie prüft nicht nur auswendig gelerntes Faktenwissen, sondern Dein Verständnis für Modelle, Zusammenhänge und Grenzen des Rechnens. Er kann als Portfolio, Projektpräsentation, mündliche Prüfung oder schriftliche Ausarbeitung durchgeführt werden.

Portfolio: Sammle mindestens drei eigene Ergebnisse aus diesem aiMOOC, zum Beispiel ein Automatenmodell, eine Laufzeitanalyse und eine Erklärung zum Halteproblem.
Modellierung: Erkläre an einem selbst gewählten Beispiel, warum ein abstraktes Modell in der Informatiktheorie nützlich ist.
Argumentation: Begründe, warum Berechenbarkeit und Komplexität unterschiedliche Fragen beantworten.
Transferleistung: Übertrage die Idee der Reduktion auf ein neues Problem und beschreibe, was dabei erhalten bleiben muss.
Reflexion: Beurteile, warum theoretisches Wissen für verantwortungsvolle Softwareentwicklung und Künstliche Intelligenz wichtig ist.

OERs zum Thema

Links

Informatiktheorie

aiMOOC-Projekte

Schulfach+

Prüfungsliteratur 2026
Bundesland	Bücher	Kurzbeschreibung
Baden-Württemberg	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck Mittlere Reife Der Markisenmann - Jan Weiler oder Als die Welt uns gehörte - Liz Kessler Ein Schatten wie ein Leopard - Myron Levoy oder Pampa Blues - Rolf Lappert	Abitur Dorfrichter-Komödie über Wahrheit/Schuld; Roman über einen Ort und deutsche Geschichte. Mittlere Reife Wahllektüren (Roadtrip-Vater-Sohn / Jugendroman im NS-Kontext / Coming-of-age / Provinzroman).
Bayern	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Lustspiel über Machtmissbrauch und Recht; Roman als Zeitschnitt deutscher Geschichte an einem Haus/Grundstück.
Berlin/Brandenburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Der Biberpelz - Gerhart Hauptmann Heimsuchung - Jenny Erpenbeck	Abitur Gerichtskomödie; soziales Drama um Ausbeutung/Armut; Komödie/Satire um Diebstahl und Obrigkeit; Roman über Erinnerungsräume und Umbrüche.
Bremen	Abitur Nach Mitternacht - Irmgard Keun Mario und der Zauberer - Thomas Mann Emilia Galotti - Gotthold Ephraim Lessing oder Miss Sara Sampson - Gotthold Ephraim Lessing	Abitur Roman in der NS-Zeit (Alltag, Anpassung, Angst); Novelle über Verführung/Massenpsychologie; bürgerliche Trauerspiele (Moral, Macht, Stand).
Hamburg	Abitur Der zerbrochne Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun	Abitur Justiz-/Machtkritik als Komödie; Großstadtroman der Weimarer Zeit (Rollenbilder, Aufstiegsträume, soziale Realität).
Hessen	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Heimsuchung - Jenny Erpenbeck Der Prozess - Franz Kafka	Abitur Gerichtskomödie; Fragmentdrama über Gewalt/Entmenschlichung; Erinnerungsroman über deutsche Brüche; moderner Roman über Schuld, Macht und Bürokratie.
Niedersachsen	Abitur Der zerbrochene Krug - Heinrich von Kleist Das kunstseidene Mädchen - Irmgard Keun Die Marquise von O. - Heinrich von Kleist Über das Marionettentheater - Heinrich von Kleist	Abitur Schwerpunkt auf Drama/Roman sowie Kleist-Prosatext und Essay (Ehre, Gewalt, Unschuld; Ästhetik/„Anmut“).
Nordrhein-Westfalen	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Komödie über Wahrheit und Autorität; Roman als literarische „Geschichtsschichtung“ an einem Ort.
Saarland	Abitur Heimsuchung - Jenny Erpenbeck Furor - Lutz Hübner und Sarah Nemitz Bahnwärter Thiel - Gerhart Hauptmann	Abitur Erinnerungsroman an einem Ort; zeitgenössisches Drama über Eskalation/Populismus; naturalistische Novelle (Pflicht/Überforderung/Abgrund).
Sachsen (berufliches Gymnasium)	Abitur Der zerbrochne Krug - Heinrich von Kleist Woyzeck - Georg Büchner Irrungen, Wirrungen - Theodor Fontane Der gute Mensch von Sezuan - Bertolt Brecht Heimsuchung - Jenny Erpenbeck Der Trafikant - Robert Seethaler	Abitur Mischung aus Klassiker-Drama, sozialem Drama, realistischem Roman, epischem Theater und Gegenwarts-/Erinnerungsroman; zusätzlich Coming-of-age im historischen Kontext.
Sachsen-Anhalt	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Themenfelder)	Abitur Schwerpunktsetzung über Themenfelder (u. a. Literatur um 1900; Sprache in politisch-gesellschaftlichen Kontexten), ohne feste Einzeltitel.
Schleswig-Holstein	Abitur Der zerbrochne Krug - Heinrich von Kleist Heimsuchung - Jenny Erpenbeck	Abitur Recht/Gerechtigkeit und historische Tiefenschichten eines Ortes – umgesetzt über Drama und Gegenwartsroman.
Thüringen	Abitur (keine fest benannte landesweite Pflichtlektüre veröffentlicht; Orientierung am gemeinsamen Aufgabenpool)	Abitur In der Praxis häufig Orientierung am gemeinsamen Aufgabenpool; landesweite Einzeltitel je nach Vorgabe/Handreichung nicht einheitlich ausgewiesen.
Mecklenburg-Vorpommern	Abitur (Quelle aktuell technisch nicht abrufbar; Beteiligung am gemeinsamen Aufgabenpool bekannt)	Abitur Land beteiligt sich am länderübergreifenden Aufgabenpool; konkrete, veröffentlichte Einzeltitel konnten hier nicht ausgelesen werden.
Rheinland-Pfalz	Abitur (keine landesweit einheitliche Pflichtlektüre; schulische Auswahl)	Abitur Keine landesweite Einheitsliste; Auswahl kann schul-/kursbezogen erfolgen.