IMIT13 - Informatik

Ein Akzeptor ist ein erkennender Automat

In der theoretischen Informatik steht der Begriff Alphabet für eine Menge mit einer festen Anzahl eindeutig unterscheidbarer Symbole. Mit dem Begriff Alphabet ist in der Informatik also nicht nur das "normale" Alphabet von A-Z gemeint

Attribute beschreiben den Zustand eines Objekts

Das Ausgabealphabet ist das Alphabet, das von einem Automaten zur Ausgabe benutzt wird

Der Begriff Automat stammt vom griechischen automatos ("sich selbst bewegend, von selbst tun"). Gemeint ist damit im allgemeinen Sprachgebrauch entweder eine Apparat, der gegen Bezahlung eine Leistung vollbringt oder eine Ware herausgibt, oder eine Maschine, die nach einem vorgegebenen "Programm" eine Tätigkeit selbstständig ausführt.

Die Church-Turing-These lautet stark vereinfacht:

Alles, was überhaupt berechenbar ist, ist schon mit der Turing-Maschine berechenbar.

deterministischer endlicher Automat

Bei einem deterministischen Automaten ist das Verhalten vorhersagbar. Er kann von einem Zustand nur auf einem Weg zu einem anderen Zustand wechseln

Im dynamischen Modell der UML wird vor allem das Verhalten eines Systems beschrieben

Das Eingabealphabet ist das Alphabet, das von einem Automaten als Eingabe akzeptiert wird beziehungsweise als Eingabe verwendet wird

ELIZA ist ein Computerprogramm von Joseph Weizenbaum. Er entwickelte es 1966 und setzte es zur Simulation einer Sitzung bei einem Psychotherapeuten ein.

Ein endlicher Automat ist ein Automat, der nur endliche Zustände annehmen kann. Ausserdem hat er ein endliches Eingabealphabet und ein endliches Ausgabealphabet

Ein erkennender Automat stellt sicher, dass eine Eingabe korrekt ist beziehungsweise dass die Eingabe zum Eingabealphabet des Automaten gehört

FIFO steht für First in, first out  (frei übersetzt: "Was zuerst kommt, geht zuerst wieder raus")

Beim Halte-Problem soll durch einen Computer berechnet werden, ob ein Programm bei einer bestimmten Eingabe beendet wird oder nicht

Das Halte-Problem ist nicht entscheidbar

Eine Kante ist eine Linie in einem Diagramm

Ein Kellerautomat kann Eingabe speichern. Die Speicherung erfolgt nach dem LIFO-Prinzip

Ein Mealy-Automat ist ein Automat mit Ausgabe. Die Ausgabe hängt sowohl von der Eingabe als auch vom Zustand ab.

Methoden beschreiben das Verhalten eines Objekts

Ein Modell stellt abstrahiert charakteristische Merkmale eines System aus einem bestimmten Blickwinkel dar.

Der Begriff Modell kann auch für das genaue Gegenteil stehen - also nicht für eine Abbildung der Realität unter einem bestimmten Blickwinkel, sondern für eine Vorlage aus der Realität, die abgebildet wird.

Ein Moore-Automat ist ein Automat mit Ausgabe. Er liefert für einen bestimmten Zustand eine bestimmte Ausgabe

nicht-deterministischer endlicher Automat

Bei einem nicht-deterministischen Automaten ist das Verhalten nicht vorhersagbar. Er kann von einem Zustand auf mehreren Wegen zu einem anderen Zustand wechseln

Beim Problem des Handlungsreisenden geht es darum, für einen Handlungsreisenden einen optimalen Weg zwischen den Stationen seiner Reise zu berechnen. Diese Aufgabe ist für einen Computer zwar prinzipiell lösbar, doch ist der Aufwand so hoch, dass eine Lösung nur theoretisch gefunden werden kann.

Eine Registermaschine ist ein Modell, dass einem "echten" Rechner sehr nahe kommt. Eine Registermaschine besteht aus einem Akkumulator und unendlich vielen Speicherzellen, die fortlaufend nummeriert sind.

Die Verarbeitung der Daten erfolgt durch spezielle Befehle

Der Startzustand ist der Zustand, den ein Automat zu Beginn hat

State Chart Diagramm ist eine andere Bezeichnung für ein Zustands-Diagramm der UML

Im statischen Modell der UML wird vor allem die Struktur eines Systems dargestellt

Ein Transduktor ist ein Automat, der eine Ausgabe erzeugt

Eine Transition ist der Übergang von einem Zustand in einen anderen

Ein Transitionssystem ist ein Automat ohne Ausgabe

Die Turing-Maschine geht auf den englischen Mathematiker Alan Turing zurück. Er entwickelte 193 ein Modell einer Maschine, die in der Lage ist, Rechenoperationen durchzuführen. Die Maschine besteht dabei lediglich aus einigen wenigen Komponenten und kann auch nur wenige Operationen ausführen.

Was eine Turing-Maschine machen soll, wird durch ein Programm festgelegt.

Grundsätzlich gilt: Alles was nicht mit der Turing-Maschine berechenbar ist, ist gar nicht berechenbar.

DerTuring-Test soll feststellen, ob Computer eine ähnliche Intelligenz wie Menschen haben. Dazu "unterhält" sich eine Testperson - ohne es zu wissen - mit einem Computer. Bis heute hat noch keine Maschine den Test bestanden

Unified Modeling Language

Die Unified Modeling Language ist eine objektorientierte Modellierungssprache für Software-Systeme

In einem Zustands-Diagramm werden die Zustände eines Automaten als Kreise dargestellt. Die Linien zwischen den Kreisen stellen die Übergänge zwischen den Zuständen dar.

Im Zustands-Diagramm der UML werden nur die Zustände und Zustandsübergänge dargestellt, die für das Problem auch wirklich von Bedeutung sind. Dazu werden bestimmte Symbole und Kennzeichnungen verwendet

Die Zustandsmenge ist die Menge der Zustände, die ein Automat annehmen kann