Glanz: aiMOOC über GPT aiMOOC Action erstellt

2026-06-17T18:47:33Z

aiMOOC über GPT aiMOOC Action erstellt

Neue Seite

{{T}}

{{BR}}
= Informatiktheorie =

{{BR}}
== 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 Sprache|formale Sprachen]], [[Berechenbarkeitstheorie]], [[Komplexitätstheorie]], [[Algorithmus|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.

{{BR}}
== Lernziele ==

Nach diesem aiMOOC kannst Du erklären, was die [[Informatiktheorie]] untersucht, warum sie für [[Softwareentwicklung]], [[Künstliche Intelligenz]], [[Kryptographie]], [[Datenbank]], [[Compilerbau]] und [[Netzwerk]]e wichtig ist und wie zentrale theoretische Modelle funktionieren. Du lernst, [[endlicher Automat|endliche Automaten]], [[Turingmaschine]]n, [[formale Grammatik]]en, [[Algorithmus|Algorithmen]], [[Entscheidungsproblem]]e und [[Komplexitätsklasse]]n 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.

{{BR}}
= Grundlagen der Informatiktheorie =

{{BR}}
== 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 [[Programmiersprache]]n 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 [[Sprache]]n, [[Programm]]e, [[Protokoll]]e und [[Datenstruktur]]en 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.

{{BR}}
== 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 [[Zustand|Zuständen]], [[Eingabealphabet]], [[Übergangsfunktion]], [[Startzustand]] und [[Endzustand|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.

{{BR}}
== 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 [[direkter Beweis|direkte Beweise]], [[Widerspruchsbeweis]]e, [[vollständige Induktion]], [[Invariante]]n und [[Reduktion]]en. 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]].

{{BR}}
= Formale Sprachen und Grammatiken =

{{BR}}
== 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, [[Programmiersprache]]n, [[Datenformat]]e, [[Suchmuster]], [[Netzwerkprotokoll]]e und [[Befehlssprache]]n 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 [[Parser]]n, [[Compiler]]n oder [[regulärer Ausdruck|regulären Ausdrücken]].

{{BR}}
== 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 Sprache]]n, [[kontextfreie Sprache]]n, [[kontextsensitive Sprache]]n und [[rekursiv aufzählbare Sprache]]n.

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

{{BR}}
== Bedeutung für Programmiersprachen ==

Jede [[Programmiersprache]] braucht eine klare [[Syntax]]. Die Syntax legt fest, welche Zeichenfolgen gültige Programme bilden. [[Formale Grammatik]]en 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.

{{BR}}
= Automatenmodelle =

{{BR}}
== 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.

{{BR}}
== 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 Sprache]]n. Viele Grundstrukturen von [[Programmiersprache]]n 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.

{{BR}}
== 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.

{{BR}}
= Berechenbarkeitstheorie =

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
== 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.

{{BR}}
= Komplexitätstheorie =

{{BR}}
== 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.

{{BR}}
== O-Notation ==

Die [[Landau-Notation|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]], [[Datenbank]]en und [[Simulation]]en ist diese Einsicht besonders wichtig.

{{BR}}
== 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ändigkeit|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.

{{BR}}
= Logik, Beweise und Korrektheit =

{{BR}}
== 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-Anweisung]]en, [[Datenbankabfrage]]n, [[Schaltkreis]]en, [[Spezifikation]]en, [[Verifikation]] und [[Künstliche Intelligenz]]. Wer logische Strukturen versteht, kann Programme klarer entwerfen und Fehler systematischer finden.

{{BR}}
== 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 [[Invariante]]n 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.

{{BR}}
== 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]], [[Verkehrssystem]]en und [[Industrieanlage]]n. 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.

{{BR}}
= Anwendungen und Bedeutung =

{{BR}}
== Compilerbau und Programmiersprachen ==

Im [[Compilerbau]] werden [[formale Sprache]]n, [[Grammatik]]en, [[Automat]]en 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.

{{BR}}
== Kryptographie und Sicherheit ==

Die [[Kryptographie]] nutzt [[Algorithmus|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.

{{BR}}
== 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 Sprache]]n spielen außerdem in Wissensrepräsentation, automatischem Schließen und Verarbeitung natürlicher Sprache eine Rolle.

{{BR}}
== 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]], [[digitale Sicherheit|digitaler Sicherheit]], [[Algorithmische Entscheidung|algorithmischen Entscheidungen]] und [[Künstliche Intelligenz|KI-Systemen]] hilft theoretisches Wissen, Möglichkeiten und Grenzen sachlich einzuschätzen.

{{BR}}
= Lernraum: Medien und OER-Hinweise =

{{BR}}
== 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.

# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=Turing+machine&title=Special:MediaSearch&type=image Wikimedia-Commons-Suche zu Turing machine]
# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=finite+state+machine&title=Special:MediaSearch&type=image Wikimedia-Commons-Suche zu finite state machine]
# [[Wikimedia Commons]]: [https://commons.wikimedia.org/w/index.php?search=formal+language+automata&title=Special:MediaSearch&type=image Wikimedia-Commons-Suche zu formal language automata]

{{BR}}
== Wikipedia und weitere OER ==

# [[Wikipedia]]: [https://de.m.wikipedia.org/wiki/Theoretische_Informatik Wikipedia-Artikel Theoretische Informatik]
# [[Wikipedia]]: [https://de.m.wikipedia.org/wiki/Turingmaschine Wikipedia-Artikel Turingmaschine]
# [[Wikiversity]]: [https://de.wikiversity.org/w/index.php?search=Theoretische+Informatik 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.

{{BR}}
== Lernvideos und Suchhinweise ==

# [[Lernvideo]]: [https://www.youtube.com/results?search_query=Theoretische+Informatik+Automaten+Berechenbarkeit+Komplexit%C3%A4t YouTube-Suche Theoretische Informatik Automaten Berechenbarkeit Komplexität]
# [[Lernvideo]]: [https://www.youtube.com/results?search_query=Turingmaschine+einfach+erkl%C3%A4rt YouTube-Suche Turingmaschine einfach erklärt]
# [[Lernvideo]]: [https://www.youtube.com/results?search_query=P+NP+Problem+einfach+erkl%C3%A4rt YouTube-Suche P NP Problem einfach erklärt]

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

{{BR}}
= Interaktive Aufgaben =

{{BR}}
== Quiz: Teste Dein Wissen ==

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{BR}}
== Memory ==

<div class="memo-quiz">
{|
|-
| Alphabet || Zeichenmenge
|-
| Wort || Zeichenfolge
|-
| Sprache || Wortmenge
|-
| Endlicher Automat || Zustandsmodell
|-
| Kellerautomat || Stapelspeicher
|-
| Turingmaschine || Berechnungsmodell
|-
| Halteproblem || Unentscheidbarkeit
|-
| O-Notation || Wachstumsordnung
|}
{{E}}
<br>

{{BR}}
== Drag and Drop ==

<div class="lueckentext-quiz">

{| class="wikitable"
! Ordne die richtigen Begriffe zu.
! Thema
|-
| '''Endlicher Automat'''
| Reguläre Sprache
|-
| '''Kellerautomat'''
| Kontextfreie Sprache
|-
| '''Turingmaschine'''
| Berechenbarkeit
|-
| '''O-Notation'''
| Laufzeitwachstum
|-
| '''Reduktion'''
| Schwierigkeitsvergleich
|-
| '''Grammatik'''
| Spracherzeugung

|}
{{E}}

<br>
...
<br />

{{BR}}
== Kreuzworträtsel ==

<div class="kreuzwort-quiz">
{|
|-
| 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?
|}
{{E}}
<br>

{{BR}}
== LearningApps ==

<iframe> https://learningapps.org/index.php?s=Informatiktheorie </iframe>

{{BR}}
== Lückentext ==

<quiz display=simple>
{'''Vervollständige den Text.'''<br>
|type="{}"}
Die { Informatiktheorie } untersucht die grundlegenden Möglichkeiten und Grenzen des Rechnens. Ein { Alphabet } ist in der formalen Sprachtheorie eine endliche Menge von Zeichen. Eine formale { Sprache } ist eine Menge von Wörtern über einem Alphabet. Ein endlicher { Automat } arbeitet mit Zuständen und Übergängen. Ein { Kellerautomat } besitzt zusätzlich einen Stapelspeicher. Die { Turingmaschine } ist ein zentrales Modell zur Untersuchung von Berechenbarkeit. Das { Halteproblem } zeigt, dass es unentscheidbare Probleme gibt. Die { Komplexitätstheorie } untersucht den Aufwand von Algorithmen. Die { O-Notation } beschreibt das Wachstum einer Laufzeitfunktion. Eine { Reduktion } kann zeigen, dass ein Problem mindestens so schwer ist wie ein anderes.
</quiz>

<br>

{{BR}}
= Offene Aufgaben =

{{BR}}
=== 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.

{{BR}}
=== Standard ===

# [[Automatenmodell]]: Entwirf einen [[endlicher Automat|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 [[Halteproblem]]s ohne Programmcode erklärt.

{{BR}}
=== 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.

{{:Offene Aufgabe - MOOC erstellen}}

{{BR}}
= 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 [[formale Sprache|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 [[Künstliche Intelligenz|KI-Systemen]] wichtig ist.

{{BR}}
= 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.

<br>
<br>
{{BR}}
= OERs zum Thema =

<iframe> https://de.m.wikipedia.org/wiki/Theoretische_Informatik </iframe>

<br>

{{BR}}
= Links =

{| align=center
{{:D-Tab}}
'''[[Informatiktheorie]]'''
# [[Theoretische Informatik]]
# [[Formale Sprache]]
# [[Chomsky-Hierarchie]]
# [[Automatentheorie]]
# [[Endlicher Automat]]
# [[Kellerautomat]]
# [[Turingmaschine]]
# [[Berechenbarkeitstheorie]]
# [[Halteproblem]]
# [[Komplexitätstheorie]]
# [[P-NP-Problem]]
# [[Algorithmus]]
# [[Logik]]
# [[Compilerbau]]
|}

[[Kategorie:Informatik]]
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Mathematik]]
[[Kategorie:Medienbildung]]
[[Kategorie:Digitale Bildung]]
[[Kategorie:Sekundarstufe II]]
[[Kategorie:Studium]]
[[Kategorie:Schule]]

{{BR}}
= aiMOOC-Projekte =

[[Kategorie:AI_MOOC]] [[Kategorie:GPT aiMOOC]]
{{MT}}

Informatiktheorie - Versionsgeschichte

Glanz: aiMOOC über GPT aiMOOC Action erstellt