Abschnittsübersicht

  • 11 B: Konzepte der theoretischen und technischen Informatik

    Alles einklappen Alles aufklappen

    • Kaffeeautomat, CC0Herzlich willkommen im Kurs Informatik 11 B zum Thema "Konzepte der theoretischen und technischen Informatik"!

      Dieser Kurs führt in die zustandsorientierte Modellierung ein und behandelt grundlegende Konzepte der theoretischen und technischen Informatik.

      Nachdem wir im ersten Themenfeld der Jahrgangsstufe 11 am Beispiel relationaler Datenbanksysteme einen praktischen Zugang zur Informatik kennengelernt haben, beschäftigen wir uns nun mit grundlegenden Modellen der Informatik. Zunächst untersuchen wir, wie sich Abläufe und Sprachen mithilfe von Automaten beschreiben lassen. Mit der Turingmaschine lernen wir anschließend ein Modell kennen, mit dem sich der Begriff der Berechenbarkeit untersuchen und auch dessen Grenzen beschreiben lassen.

      Im Bereich der technischen Informatik betrachten wir danach, wie ein realer Rechner grundsätzlich aufgebaut ist und Befehle verarbeitet. Dazu untersuchen wir das Modell des von-Neumann-Rechners.

      Stand: 14.03.2025 - Dieser Kurs wird aktuell nicht gepflegt.

    • Kommunikation im Kurssystem

      Neben der direkten Kommunikation mithilfe des Moodle-Mitteilungsdienstes, der auch auf der App funktioniert, und der E-Mail-Option, gibt es öffentliche Austausch- und Informationsmöglichkeiten in den Foren.

    • Ankündigungen Forum
    • Frage- und Diskussionsforum

    • Software im Themenfeld

      Der Großteil der im Unterricht eingesetzten Programmwerkzeuge ist Open-Source-Software oder kostenlos nutzbar. Für Hausaufgaben oder zum Nachvollziehen der Unterrichtsbeispiele kann der IoStick für die Sekundarstufe II benutzt werden. 

    • Software: Informatik on Stick (1 GB) Link/URL
    • FLACI: Webbasiertes Simulationsprogramm, Nachfolger von AtoCC Link/URL
    • Johnny 1: Offline-Version der Simulationssoftware für einen von-Neumann-Rechner Link/URL
    • Johnny 2: Online-Version der Simulationssoftware für einen von-Neumann-Rechner Link/URL
    • DSimWeb: Online-Version und Nachfolger von LogicSim Link/URL

    • Lehrbücher

    • Ergänzungsmaterial Automaten Link/URL

    • Quiz und Tests

    • Quiz 1 Link/URL

  • Mealy-Automat - Automat mit Ausgabe

    • Endliche Automaten mit Ausgabe

      Beginnen wir mit der Suche nach einem Modell für eine universelle Maschine. Das von-Neumann-Modell beschreibt den Computer als universell einsetzbare Maschine. Dies kennen wir bereits aus Klasse 10. Darüber hinaus begleitet uns das EVA(S)-Prinzip seit Klasse 5: Informatiksysteme nehmen Eingaben entgegen, verarbeiten sie und erzeugen Ausgaben.

      Gilt dies auch für Automaten? Sind Automaten ebenfalls universelle Maschinen?

      Automaten begegnen uns beispielsweise als Geldautomaten, Parkscheinautomaten oder Getränkeautomaten. Auch sie nehmen Eingaben entgegen, verarbeiten diese abhängig von ihrem aktuellen Zustand und erzeugen Ausgaben. Solche Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Es geht auf die 1955 veröffentlichte Arbeit "A Method for Synthesizing Sequential Circuits" des US-amerikanischen Mathematikers George H. Mealy zurück. 

      Definition des Mealy-Automat

      Ein Mealy-Automat MA = (X, Y, Z, δ, λ, z~0~) ist ein endlicher Automat mit Ausgabe. Dabei gilt:

      • X ... Eingabealphabet (nichtleere, endliche Menge)
      • Y ... Ausgabealphabet (nichtleere, endliche Menge)
      • Z ... Zustandsmenge (nichtleere, endliche Menge)
      • δ ... Überführungsfunktion, die jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
      • λ ... Ausgabefunktion, die jedem Paar (Eingabezeichen, Zustand) genau ein Ausgabezeichen zuordnet
      • z0 ∈ Z ist der Anfangszustand
      •  
      Aufbau eines Funktionsmodells

      Arbeitsweise des Funktionsmodells
      • SOLANGE noch ungelesene Zeichen auf dem Eingabeband vorhanden sind:
        • liest das aktuelle Zeichen vom Eingabeband
        • wechselt in Abhängigkeit vom aktuellen Zustand und vom gelesenen Zeichen in einen Folgezustand und schreibt ein Zeichen auf das Ausgabeband
        • bewege das Eingabe- und Ausgabeband um eine Zelle weiter
    • Beispiel: Blumenstraußautomat

      Ein Blumenstraußautomat bietet Blumensträuße für 4 EUR an. Der Kunde wirft 1- oder 2-Euro-Münzen ein und erhält die Blumen. Andere Münzwerte nimmt der Automat nicht an. Zu viel gezahltes Geld wird nicht erstattet.

      Der Blumenstraußautomat kann als Mealy-Automat MA = (X, Y, Z, δ, λ, q0) modelliert werden mit

      • X = {1_EUR, 2_EUR}
      • Y = {-, Blumen}
      • Z = {q0, q1, q2, q3}
      • δ, λ als Tabelle

        oder als Graph
      • q0

    • Aufgabe: primitiver Verschlüsselungsautomat

      Der Mealy-Automat MA = (X, Y, Z, δ , λ , q0) simuliert ein Verschlüsselungsverfahren, das nur mit Ziffern als Eingabezeichen arbeitet. Die Abbildung zeigt den Graph der Überführungsfunktion.

      .

      1. Geben Sie die Mengen X, Y und Z an.
      2. Verschlüsseln Sie die Zahlenfolge 0 - 8 - 1 - 5 und entschlüsseln Sie die Nachricht 18 - 24 - 12 - 14.
      3. Entwickeln Sie einen Automaten mit Ausgabe, der nach diesem Prinzip verschlüsselte Nachrichten entschlüsselt. Der Automat soll dabei die Eingabe ziffernweise entgegennehmen, also für obiges Beispiel statt 18 - 24 - 12 - 14 die Form 1 - 8 - 2 - 4 - ...
    • Übungen zum Mengenbegriff Aufgabe
    • Übungen zum Mealy-Automat Datei

  • Akzeptor und Sprache

    • Endliche Automaten ohne Ausgabe - Akzeptor

      Ein Safe öffnet sich nur dann, wenn die vierstellige Ziffernkombination korrekt eingegeben wurde. Ein Smartphone lässt sich nur dann bedienen, wenn eine PIN oder der Fingerabdruck korrekt sind. Beide Fälle lassen sich durch einen Automaten beschreiben. Eine Ausgabe nach jedem Schritt ist jedoch nicht mehr erforderlich. Erst am Ende der Eingabe muss entschieden werden, ob diese akzeptiert oder nicht akzeptiert wird. Solche Automaten nennt man Akzeptoren.

      Definition des Akzeptors - Automat ohne Ausgabe

      Ein Akzeptor A = (X, Z, δ, z0, ZE) ist ein endlicher Automat ohne Ausgabe. Dabei gilt:

        • X ... Eingabealphabet (nichtleere, endliche Menge)
        • Z ... Zustandsmenge (nichtleere, endliche Menge)
        • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
        • z0 ∈ Z ist der Anfangszustand
        • ZE ... Endzustandsmenge (endliche Teilmenge von Z)

      Aufbau eines Funktionsmodells


      Arbeitsweise
      • SOLANGE sich in der Zelle des Lesekopfs ein Zeichen befindet:
        • Lies mithilfe des Lesekopfs das Zeichen aus der aktuellen Zelle des Eingabebands
        • Wechsle in Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen in einen Folgezustand.
        • Bewege das Band eine Zelle weiter.
      • Nachdem das gesamte Eingabewort gelesen wurde, wird geprüft, ob sich der Automat in einem Endzustand befindet. Ist dies der Fall, wird das Wort akzeptiert.

      Wörter und Sprache
      • Ein Wort w ist eine endliche Folge von Zeichen aus einem Alphabet X.
      • Die Menge aller Wörter w über einem Alphabet X wird mit X* bezeichnet  und ist ist unendlich groß. Sie enthält auch das leere Wort. Das Zeichen ε bezeichnet das leere Wort, das aus keinem Zeichen besteht.
        Beispiel: Wenn X = {a, b}, dann ist die Menge aller Wörter X* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, ...}.
        Da Wörter beliebig lang sein können, enthält X* bei einem nichtleeren Alphabet unendlich viele Wörter.
      • Die Sprache eines Automaten L(A) ist die Menge aller Wörter über dem Alphabet X, die A nach vollständiger Abarbeitung von w in einen Endzustand überführen. 
      • Die Sprache kann verbal, durch die Angabe eines Musters, mathematisch oder durch Auflisten aller Wörter beschrieben werden, beispielsweise so:
        L(A) = {00, 000, 100, 0000, 0100, 1000, 1100, …} 
        L(A) ist die Menge aller Binärzahlen, deren letzte beiden Bits Null sind. 
        L(A) = {w | w ∈ X* und w endet auf 00}
        Interpretiert man diese Wörter als Binärzahlen, stellen sie Zahlen dar, die durch 4 teilbar sind.

      Beispiel: Safe mit vierstelligem Ziffernschloss

      Ein elektronischer Safe lässt sich nur dann öffnen, wenn die Ziffernkombination 0815 eingegeben wird. Alle anderen Eingaben sperren den Safe dauerhaft.

      Dies lässt sich als Akzeptor A = (X, Z, δ, q0, ZE) modellieren mit

          • X = {0, 1, ..., 9}
          • Z = {q0, q1, q2, q3, q4, q5}
          • δ als Tabelle

            oder als Graph
          • q0
          • ZE = {q4}

      Die Sprache L(A) des Automaten besteht einzig aus dem Wort w = 0815, L(A) = {0815}.

    • Zusammenfassung "Akzeptor und Sprache" und erste Übungen Datei
    • Übungen zum Akzeptor in Anwendungen Aufgabe
    • Übungen zum Akzeptor mit ab- bzw. 01-Sprachen Aufgabe

  • nur für LK: Kellerautomaten

    • Endliche Automaten ohne Ausgabe und mit Kellerspeicher - Kellerautomat

      Im Baumarkt gibt es einen Automaten, der Schrauben und die passende Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schrauben Muttern | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

      Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

      Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann nicht von einem endlichen Akzeptor erkannt werden. Wir benötigen dafür "irgendeinen" Speicher, der sich die Anzahl der Schrauben merken kann.


      Kellerautomat – Kellerspeicher

      Ein sehr simpler Speicher ist der sog. Kellerspeicher (Stapel, Stack). Wie in einem Keller können Objekte oben abgelegt (push) und von oben entnommen (pop) werden. Dabei gilt: das zuletzt abgelegte Objekt muss als erstes wieder entnommen werden. Dieses Prinzip bezeichnet man mit Last in – First out (LIFO). Dabei sind drei grundlegende Operationen möglich:

      • push: ein Zeichen oben auf den Keller legen,
      • pop: das oberste Zeichen aus dem Keller entfernen,
      • nop: den Kellerinhalt unverändert lassen.


      Funktionsmodell eines Kellerautomaten

      Der Automat besitzt einen Kellerspeicher zum Ablegen von Objekten. Der Kellerspeicher

      • ist nach oben offen, seine Größe ist nicht begrenzt.,

      • hat das Symbol # zur Anzeige des Kellerbodens.

      Zum Kellerautomaten gehören außerdem eine Steuereinheit und ein Eingabeband, dass die Eingabezeichen enthält, ein nach rechts bewegbarer Lesekopf sowie eine Lampe zur Anzeige des Akzeptierzustandes.


      Arbeitsweise
      • Initialisierung des Kellerautomaten: Keller ist leer, der Kellerlesekopf steht auf dem Kellerbodenzeichen #
      • SOLANGE ein Zustandsübergang möglich ist:
        • Lies mithilfe der Leseköpfe das Zeichen aus der aktuellen Zelle des Eingabebands sowie das oberste Zeichen aus dem Kellerspeicher
        • Führe in Abhängigkeit vom aktuellen Zustand, dem gelesenen Keller- und Bandzeichen eine Kelleroperation aus und wechsle in einen Folgezustand.
        • Bewege das Eingabeband eine Zelle weiter.
      • Falls der aktuelle Zustand ein Endzustand ist, das Eingabewort vollständig gelesen wurde und der Keller nur aus dem Kellerbodenzeichen # besteht, dann aktiviere die Akzeptanzanzeige.

      Definition des Kellerautomaten

      Ein deterministischer Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE) ist ein endlicher Automat ohne Ausgabe und mit Kellerspeicher. Dabei gilt:

        • X ... Eingabealphabet (nichtleere, endliche Menge)
        • Z ... Zustandsmenge (nichtleere, endliche Menge)
        • Γ ... Kelleralphabet (nichtleere, endliche Menge)
        • δ ... Überführungsfunktion. Sie legt in Abhängigkeit vom aktuellen Zustand, vom gelesenen Eingabezeichen und vom obersten Kellerzeichen den Folgezustand und die Kelleroperation fest. 
        • z0 ∈ Z ist der Anfangszustand
        • k0 ∈ Γ ist das Kellerbodenzeichen (manchmal auch Kellerleerzeichen) (#)
        • ZE ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)

      Bei einem nichtdeterministischen Kellerautomaten können für dieselbe Situation mehrere Zustandsübergänge möglich sein. Bei deterministischen Kellerautomaten darf für dieselbe Situation höchstens ein Zustandsübergang möglich sein.


      Beispiel: Kellerautomat für den Schrauben-Muttern-Automaten

      Die akzeptierte Sprache für den Automaten aus dem Eingangsbeispiel ist L = {Schrauben Muttern | n > 0}.

      Dafür lässt sich ein Kellerautomat KA = (X, Z, Γ, δ, z0, k0, ZE) konstruieren:

          • X = {Schraube, Mutter}
          • Z = {q0, q1, q2}
          • Γ = {#, S}
          • δ als Graph
          • q0
          • k0 = #
          • ZE = {q2}

      Die Beschriftung eines Übergangs ist wie folgt aufgebaut: (erwartetes Kellerzeichen, erwartetes Eingabezeichen): Kelleroperation.

        • Die Kelleroperation S# bedeutet dabei, dass das Zeichen S eingekellert werden soll, die Raute - die beim Lesen aus dem Keller entnommen wurde - jedoch davor wieder zurückgeschrieben werden muss.
        • Die Kelleroperation ε bedeutet dabei, dass kein Zeichen zurückgeschrieben werden muss.
        • Die Kelleroperation # bedeutet dabei, dass die Raute - die beim Lesen aus dem Keller entnommen wurde - wieder zurückgeschrieben werden muss.

      Der Übergang in den Endzustand q2 sieht eigenartig aus, bedeutet aber:
      Wenn der Keller leer ist und kein Zeichen mehr auf dem Band, dann setzte den Keller wieder leer und wechsle und den Endzustand.

      Das Symbol ε steht jeweils dafür, dass an dieser Stelle kein Zeichen verwendet wird:

        • als Eingabezeichen: Es wird kein Zeichen vom Eingabeband gelesen.
        • bei der Kelleroperation: Es wird kein Zeichen zurück in den Keller geschrieben.
    • 03 Zusammenfassung Kellerautomat und Übungen Datei
    • Anwendung Kellerautomat - Rangierproblem Datei
    • Übungszettel 5 "Kellerautomat" Datei
    • Datei für Aufgabe Kellerautomat
    • Determinismus und Nichtdeterminismus

      Die Aufgabe mit den Palindromen ist gar nicht so einfach. Unterscheiden wir nach drei Fällen:

      1. Palindrom mit Trennzeichen
      2. Palindrom ohne Trennzeichen und mit gerader Länge
      3. Palindrom ohne Trennzeichen und mit beliebiger Länge

      Die Aufgabe 1 ist mithilfe eines Kellerautomaten einfach. Das System muss bis zum Trennzeichen alles einkellern und danach - bei Gleichheit der Zeichen auf dem Band und im Keller - auskellern - fertig. Dies ist bestimmt und deterministisch. Für dieselbe Eingabe ist in jeder Situation eindeutig festgelegt, welcher Zustandsübergang ausgeführt wird. 

      In Aufgabe 2 haben wir kein Trennzeichen. Wir wissen also nicht, wo die Mitte ist. Wir können die Mitte auch nicht messen oder auf andere Art und Weise berechnen. Um das Palindrom zu erkennen, müssen wir also berechnen, wo die Mitte ist. Bei einem nichtdeterministischen Automaten können in derselben Situation mehrere Zustandsübergänge möglich sein. Man kann sich dies anschaulich so vorstellen, als würde der Automat mehrere Möglichkeiten ausprobieren. Ein Wort wird akzeptiert, wenn mindestens einer dieser möglichen Wege zu einer erfolgreichen Verarbeitung führt. Genau so etwas benötigen wir jetzt. Das System muss alles einkellern und an einer geeigneten Stelle mit dem Auskellern beginnen. Wenn wir Glück haben, war es die richtige, sonst muss das System eben neu probieren. 

      Nichtdeterminismus ist vor allem ein theoretisches Modell. Er erlaubt es, die Leistungsfähigkeit von Automaten und Algorithmen zu untersuchen und unterschiedliche Automatenmodelle miteinander zu vergleichen.

    • Aufgaben zum Kellerautomat

  • Turingmaschine als Akzeptor

    • Einleitungstext für den Grundkurs

      Im Baumarkt gibt es einen Automaten, der Schrauben und die passenden Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schrauben Muttern | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

      Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

      Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann also nicht von einem endlichen Akzeptor erkannt werden. 

      Einleitungstext für den Leistungskurs

      Unser Baumarkt erweitert sein Leistungsspektrum. Er bietet nun auch Schrauben, Unterlegscheiben und Muttern über den Automaten an (wow!). Die nachfolgende Generation soll zusätzlich auch Sprengringe (was das wohl ist) integrieren. In eine Sprache übersetzt also: L1 = {Schrauben Unterlegscheiben Muttern | n > 0} und L2 = {Schrauben Unterlegscheiben Sprengringn Muttern | n > 0}. Können wir einen Kellerautomat konstruieren, der diese Sprache erkennt und akzeptiert?

      Um es kurz zu machen: es wird uns nicht gelingen. Mit einem Kellerspeicher lässt sich beispielsweise die Anzahl zweier aufeinanderfolgender Zeichengruppen vergleichen. Für den Vergleich drei aufeinanderfolgender Zeichengruppen reicht ein einzelner Kellerspeicher jedoch nicht aus.

      Mit der Turingmaschine liegt jedoch ein Automatenmodell vor, welches unsere Probleme lösen kann. Die Änderungen im Vergleich zum Akzeptor sind

      • das Band wird beschreibbar und
      • der Lese-/Schreibkopf ist beidseitig bewegbar.

      Dadurch kann die Turingmaschine bereits gelesene Informationen auf dem Band verändern und später erneut verwenden.


      Alan Turing       entwickelte das mathematische Konzept einer universellen Maschine und stellt dies 1936 in seiner Arbeit "On Computable Numbers, with an Application to the 'Entscheidungsproblem'" vor. Diese Arbeit zählt zu den grundlegenden Beiträgen der theoretischen Informatik. Turing selbst war entscheidend in weitere Projekte eingebunden, die heute der Informatik zugeordnet werden. Eine genaue Beschäftigung mit dem Leben und Wirken Turings erfolgt im Unterricht.  

      Bildquelle: gemeinfrei von WikiCommons

      Aufbau eines Funktionsmodells


      Arbeitsweise
      • SOLANGE ein Zustandsübergang möglich ist:
        • Lies mithilfe des Lesekopfs das Zeichen aus der aktuellen Zelle des Eingabebands.
        • Schreibe in Abhängigkeit vom aktuellen Zustand und vom gelesenen Zeichen ein Zeichen auf das Band, bewege den Lese-/Schreibkopf gegebenenfalls nach links oder rechts und wechsle in einen Folgezustand.
      • Falls der aktuelle Zustand ein Endzustand ist, dann aktiviere die Akzeptanzanzeige. 
      • Hält die Maschine in einem Endzustand, wird das Eingabewort akzeptiert.

      Definition der Turingmaschine

      Eine Turingmaschine TM = (X, Z, Γ, δ, z0, $, ZE) ist ein endlicher Automat. Dabei gilt:

      • X ... Eingabealphabet (nichtleere, endliche Menge)
      • Z ... Zustandsmenge (nichtleere, endliche Menge)
      • Γ ... Bandalphabet (nichtleere, endliche Menge) und X ⊆ Γ
      • δ ... Überführungsfunktion, die in Abhängigkeit vom aktuellen Zustand und vom gelesenen Bandzeichen festlegt, welches Zeichen auf das Band geschrieben wird, wie sich der Lese-/Schreibkopf bewegt (L, N oder R) und in welchen Folgezustand die Maschine wechselt.
      • z0 ∈ Z ist der Anfangszustand
      • $ ... Bandvorbelegungszeichen, kennzeichnet eine zunächst unbeschriebene Zelle.
      • ZE ⊆ Z ... Endzustandsmenge (endliche Menge)

      Beispiel für das Grundkurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubenMuttern | n > 0}

      TM = (X, Z, Γ, δ, z0, $, ZE) mit

        • X ={Schraube, Mutter}
        • Z = {q0, q1, q2, q3, q4, q5}
        • Γ ={$, Schraube, Mutter}
        • q0 ∈ Z ist der Anfangszustand
        • ZE = {q5}
        • δ als Tabelle 

          oder als Graph

      Beispiel für das Leistungskurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubenUnterlegscheibenMuttern | n > 0}

      TM = (X, Z, Γ, δ, z0, $, ZE) mit

        • X ={Schraube, Unterlegscheibe, Mutter}
        • Z = {q0, ..., q8}
        • Γ ={$, Schraube, Unterlegscheibe, Mutter}
        • q0 ∈ Z ist der Anfangszustand
        • ZE = {q8}
        • δ als Tabelle 

          oder als Graph
    • Informationen über das Leben und Wirken von Alan Turing (ab Minute 8:50) Externes Tool
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Turingmaschine Datei
    • Übungen zur TM als Akzeptor Aufgabe

  • Turingmaschine als Rechner

    • Erarbeitung der neuen Qualität der Turingmaschine - Rechnen! Aufgabe

    • Die letzten Beispiele haben gezeigt, dass die Turingmaschine in der Lage ist Berechnungen auf Binärzahlen durchzuführen.

      Der Graph der hier gegebenen Turingmaschine teilt die auf dem Band stehende Binärzahl durch 2.

       

      Eine Funktion f heißt Turing-berechenbar, wenn es eine TM gibt, die f wie folgt berechnet:

      • im Startzustand mit dem Eingabewort w beginnend
      • durch definierte Zustandsübergänge in einem Endzustand hält und
      • das Wort v auf das Band geschrieben hat.


      Die Division einer Binärzahl durch 2 ist also Turing-berechenbar. Eine Berechnung ist eine schrittweise, nach bestimmten Regeln durchgeführte Manipulation der Zeichen auf dem Band. Die Zeichen können Codierungen von Zahlen oder Zeichen darstellen. Eine Turingmaschine kann einen Algorithmus modellieren. Führt sie eine Berechnung durch, bildet sie eine Eingabe auf eine Ausgabe ab und berechnet damit eine Funktion. 

    • Übungen zur rechnenden Turingmaschine Aufgabe

    • Church-Turing-These

      Alonzo Church und Alan Turing stellten eine These auf, die von den meisten Informatikern akzeptiert wird: 

      „Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“

      Das Modell der Turingmaschine mathematisiert damit die Begriffe Algorithmus und Berechenbarkeit.

      Die Church-Turing-These besagt vereinfacht: Alles, was sich überhaupt algorithmisch berechnen lässt, kann auch von einer Turingmaschine berechnet werden. Damit liefert die Turingmaschine ein grundlegendes Modell für die Begriffe Algorithmus und Berechenbarkeit. Somit wird aus der "Verarbeitungsvorschrift, die aus einer endlichen Folge von eindeutig ausführbaren Anweisungen besteht, mit der eine Vielzahl gleichartiger Aufgaben gelöst werden können und die Eigenschaften Endlichkeit, Ausführbarkeit, Terminiertheit, Eindeutigkeit und Allgemeingültigkeit hat" das mathematische Modell Turingmaschine, kurz: Programm = Algorithmus = Turingmaschine.

       

      nur für den LK: Verhältnis von berechenbaren Funktionen (Turingmaschinen/Algorithmen) zu definierbaren Funktionen 

      Wie viele Funktionen kann man eigentlich definieren und wie viele davon berechnen? Beide Mengen sind unendlich groß. Lasst uns da mal zuerst über Unendlichkeit reden.

       

      Man kann mithilfe des systematischen Durchzählens beweisen, dass die Menge der berechenbaren Funktionen - also der Turingmaschinen - abzählbar unendlich groß ist. Die Menge der definierbaren Funktionen ist beweisbar überabzählbar unendlich groß. Damit ergibt sich die Konsequenz, dass es definierbare Funktionen gibt, die nicht berechenbar sind und demzufolge sich nicht mit Hilfe einer Turingmaschine lösen lassen.

      Es gibt Probleme, für die kein Algorithmus existiert. 

      Vertiefung: 

    • Das Halteproblem

    • Rechnet er noch, ist er abgestürzt? Was macht er denn? Aufgabe

      Ein Programm (GK: Scratch, LK: Java/Python) sucht magische Quadrate der Größe 3×3 auf eine systematische, aber wenig effiziente Weise. Es probiert dazu alle Möglichkeiten aus. 

      1. Schätze spontan die Zeit bis zur Ausgabe einer ersten Lösung für deinen Computer. Probiere erst dann das Programm aus.
      2. Beschreibe die prinzipielle Arbeitsweise des Programms.
      3. GK/Scratch: 
        1. Füge den Baustein "zeige_Variablen" als 3. Block in das Ereignis "Wenn grüne Flagge angeklickt" ein und prüfe den Programmablauf.
        2. Füge an einer geeigneten Stelle des Programms den Block "zeige_Stoppuhr_und_warte" ein, um die Laufzeit bis zum vollständigen Durchlauf abzuschätzen.
      4. LK/Java/Python:
        1. Lasse Dir mithilfe der Systemzeit die Laufzeit für einen Block so ausgeben, dass du daraus auf die Laufzeit des gesamten Programms mathematisch schließen kannst.
      5. Schätze die Laufzeit eines gleichartigen Programms für 4x4-Quadrate.

    • Dass ein Programm sehr lange rechnet, bedeutet noch nicht, dass es niemals anhalten wird.

      Hält ein Algorithmus immer an?

      Lothar Collatz stellte 1937 folgendes Problem vor. Endet die Folge

      stets auf 1 für beliebige natürliche Zahlen a0?

      Beispiele:

      • a0 = 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
      • a0 = 49: 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
      • a0 = 75: 75, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1

      Aufgabe: Entwickeln Sie unter Verwendung des Struktogramms ein Programm zur Berechnung der Collatz-Folge für beliebige Startwerte. Untersuchen Sie, ob der Algorithmus für verschiedene Startwerte stoppt.

    • Collatz Vorgabe Java Datei

    • Stopp-Tester

      Die entwickelte Software untersucht letztlich stets eine endliche Menge von Eingaben und prüft, ob die Folge auf Eins endet. Bisher hat man dies für alle Zahlen bis 20·271 (lt. Springer 2025) positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen.

      Kann ein Algorithmus für ein beliebiges Programm P und eine beliebige Eingabe E entscheiden, ob P mit E nach endlich vielen Schritten anhält?

      Angenommen, es gäbe einen Stopp-Tester. Diesem übergeben wir ein beliebiges Programm und eine zugehörige Eingabe. Der Stopp-Tester soll stets nach endlich vielen Schritten entscheiden, ob dieses Programm mit dieser Eingabe anhält oder endlos weiterläuft.

      Da ein Programm als Zeichenfolge gespeichert werden kann, kann auch der Programmtext selbst eine Eingabe sein. Wir können einen Stopp-Tester deshalb insbesondere fragen, ob ein Programm anhält, wenn es seinen eigenen Programmtext als Eingabe erhält. Ein Programm nennen wir hier selbststoppend, wenn es anhält, sobald sein eigener Programmtext als Eingabe verwendet wird.

      Wie kann so ein Algorithmus aussehen?
      Sicherlich ist ein bestimmter Programmvorbau notwendig. Da jedoch zum Ende des Algorithmus die Ausgabe der Entscheidung ansteht, hat das - verbal beschrieben - Programm sicherlich folgende Gestalt, wobei stopp eine boolesche Variable ist, die vorher berechnet wurde.

      BEGIN
        {...}
        IF (stopp)
        THEN Ausgabe: "Das Programm ist selbststoppend."
        ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
      END.


      Wenn dieses Programm existiert, dann könnte ein Programmierer den Quelltext aber auch ändern und so das Programm SELTSAM erschaffen:

      BEGIN
        {...}
        IF (stopp)
        THEN ...
             WHILE (true) DO //nichts
        ELSE ...
      END.

      Ist Seltsam selbststoppend oder nicht?

      Fall 1: Der Stopp-Tester sagt voraus, dass SELTSAM anhält.

      Dann führt SELTSAM absichtlich eine Endlosschleife aus. Es hält also nicht. Die Vorhersage ist falsch.

      Fall 2: Der Stopp-Tester sagt voraus, dass SELTSAM nicht anhält.

      Dann beendet sich SELTSAM. Es hält also doch. Auch diese Vorhersage ist falsch.

      In beiden Fällen entsteht ein Widerspruch. Der Fehler kann nicht in der Konstruktion von SELTSAM liegen, sondern nur in unserer ursprünglichen Annahme: Ein Stopp-Tester, der für jedes beliebige Programm und jede beliebige Eingabe korrekt entscheidet, ob das Programm anhält, kann nicht existieren.

      Resümee:

      Es gibt keinen Algorithmus, der für jedes beliebige Programm und jede beliebige Eingabe entscheiden kann, ob das Programm nach endlich vielen Schritten anhält. Das Halteproblem ist damit algorithmisch nicht entscheidbar. Es zeigt eine prinzipielle Grenze der Berechenbarkeit und damit auch der Turingmaschine. Damit haben wir ein Problem gefunden, das grundsätzlich nicht durch einen Algorithmus für alle möglichen Eingaben gelöst werden kann.

      Vertiefung/Visualisierung: 

       

  • Formale Sprache und Grammatik

    • Mit Akzeptor, Kellerautomat und Turingmaschine haben wir Automatenmodelle kennengelernt, die formale Sprachen erkennen können. Nun betrachten wir die andere Richtung: Formale Sprachen können auch mithilfe von Regeln erzeugt werden. Solche Regelsysteme heißen Grammatiken. Am Ende werden wir untersuchen, welcher Grammatiktyp zu welchem Automatenmodell gehört.

      In Klasse 10 haben wir natürliche und künstliche Sprachen miteinander verglichen. Dabei spielten bereits die Begriffe Alphabet, Syntax, Semantik und Grammatik eine Rolle. Für formale Sprachen konzentrieren wir uns nun auf die Syntax: Welche Zeichenfolgen gehören zu einer Sprache und durch welche Regeln können sie erzeugt werden?

    • Aufgabe zum Syntaxdiagramm (Tafelwerk?)

      Prüfe ob Befehl korrekt ist -> Akzeptorrolle

      Gib einen Befehl an, der ... -> Generatorrolle

    • Verschiedene Möglichkeiten zur Beschreibung einer Syntax

      Die Syntax einer formalen Sprache kann auf unterschiedliche Weise beschrieben werden. Aus dem Umgang mit SQL kennen wir bereits Syntaxdiagramme. Beispielsweise findet sich eine Beschreibung des SELECT-Befehl in der SQLite-Dokumentation auszugsweise wie folgt:

      SELECT-Syntax

    • ÜBERARBEITUNG notwendig!!!

      1. Produktionsregeln als alternative Beschreibung mit Grammatikbeispiel und Baum
      2. Theorie Definition G = (T, N, P, S) und Ableitungsbaum
      3. Anwendung: Grammatiken entwickeln und untersuchen
      4. unterschiedliche Einschränkungen der Produktionsregeln --> Chomsky-Hierarchie
      5. Zusammenführung mit den bekannten Automaten

    • Formale Sprache

      Im Zusammenhang mit Automaten haben wir bereits festgelegt:

      • Ein Alphabet ist eine endliche Menge von Zeichen.
      • Ein Wort ist eine endliche Folge von Zeichen eines Alphabets.
      • X* bezeichnet die Menge aller Wörter über dem Alphabet X.
      • Eine formale Sprache L über X ist eine Teilmenge von X*.


      Sprachklassifikation

      Natürliche Sprachen wie Deutsch sind historisch entstanden und besitzen häufig Mehrdeutigkeiten.

      Künstliche Sprachen wurden gezielt geschaffen. Dazu gehören beispielsweise Plansprachen und Programmiersprachen.

      Formale Sprachen sind Sprachen, deren syntaktisch gültige Wörter bzw. Ausdrücke eindeutig nach festgelegten Regeln bestimmt werden können. Programmiersprachen sind wichtige Anwendungen formaler Sprachen. Formale Sprachen besitzen eine eindeutig festgelegte Syntax. Sie kann beispielsweise durch Grammatiken, Syntaxdiagramme oder andere Sprachbeschreibungen angegeben werden. Die Untersuchung formaler Sprachen begann in den 1950er-Jahren durch Noam Chomsky.

      Bild: Σ, retouched by Wugapodes and Jonnmann, CC BY-SA 4.0 via Wikimedia Commons

    • Übungen zum Syntaxdiagramm für SQL Aufgabe
    • Syntaxdiagramm und Produktionsregeln Datei
    • Übung aus dem Informatik-Abitur 2012 Datei
    • Anlage Datei
    • Präsentation "Turingmaschine und Chomsky-Hierarchie" Datei
    • Grammatik Link/URL
    • Chomsky-Hierarchie Link/URL
    • Übung: Grammatiktyp bestimmen Aufgabe
    • Übung: Bestimmung der generierten Sprache Aufgabe
    • Aufgaben zur Grammatik

  • Von-Neumann-Rechner

    • John von NeumannMit der Turingmaschine haben wir ein abstraktes Modell kennengelernt, mit dem sich algorithmische Berechnungen und die Grenzen der Berechenbarkeit untersuchen lassen. Für den Bau realer Computer waren jedoch konkrete technische Konzepte erforderlich. In den 1930er- und 1940er-Jahren entstanden verschiedene elektromechanische und elektronische Rechenmaschinen. Aus diesen Entwicklungen ging schließlich auch das Architekturmodell hervor, das wir heute als von-Neumann-Architektur bezeichnen.

      Im Mai 1941 stellte Konrad Zuse in Berlin die Z3 fertig. Sie gilt als erster funktionsfähiger programmgesteuerter Digitalrechner. Kriegsbedingt erfuhr die Welt jedoch nichts von dieser revolutionären Erfindung. In anderen Ländern arbeiteten Forscher ebenfalls an der Entwicklung von "rechnenden Elektronengehirnen".

      John von Neumann kam 1944 mit der Entwicklung des EDVAC in Berührung. 1945 beschrieb er im First Draft of a Report on the EDVAC grundlegende Prinzipien eines speicherprogrammierten Rechners. Viele dieser Prinzipien prägen Rechnerarchitekturen bis heute.

      Bildquelle: WikiCommons (https://commons.wikimedia.org/wiki/File:JohnvonNeumann-LosAlamos.jpg)
      Unless otherwise indicated, this information has been authored by an employee or employees of the Los Alamos National Security, LLC (LANS), operator of the Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396 with the U.S. Department of Energy. The U.S. Government has rights to use, reproduce, and distribute this information. The public may copy and use this information without charge, provided that this Notice and any statement of authorship are reproduced on all copies. Neither the Government nor LANS makes any warranty, express or implied, or assumes any liability or responsibility for the use of this information.

    • Video aus Medienstelle (FWU/Hagemann):

      • Meilensteine der Kommunikation: Zuse, Babbage und der Computer
      • Geschichte der Computer
    • Geschichte der Computer - Abschnitt: Die ersten Computer der Welt Externes Tool
      Nicht verfügbar, außer: Sie sind in einer Gruppe

    • Exkurs: Vorstellung historischer Hardware

      • Rechnersysteme: Abakus, Addiator, LC 80, Poly 880, Z 1013, Mainboards
      • Speichermedien: Lochkarte/-streifen, Magnetband, Disketten, Festplatten, Exoten
    • Erarbeitung von-Neumann-Architektur Aufgabe

      Erarbeiten Sie unter Verwendung der Lehrbücher Informatik 2 Schöningh S. 234ff. und Oldenbourg S. 88ff. sowie des Arbeitsblattes den Aufbau und die Prinzipien der von-Neumann-Architektur.

    • 01 AB von Neumann Vorgabe Datei

    • Die von-Neumann-Architektur mit Johnny begreifen

    • SOL Johnny Vorgabe Datei
    • Online-Version des Johnny-Simulators Link/URL
    • Johnny-Dateien
    • Befehlssatz Johnny Datei
    • Video 1: Lineare Programme Link/URL
    • Video 2: Programme mit Verzweigungen Link/URL
    • Video 3: Programme mit Wiederholungen Link/URL
    • Video 4: John-von-Neumann-Zyklus Link/URL

    • Übungen aus Abituren

    • Übungen zu Johnny (aus Abituraufgaben) Datei
    • Dateien zu den Übungen Verzeichnis

    • Exkurs für Freaks: Maschinennahe Programmierung am LC80

    • 05 LC 80 Maschinensprache Datei
    • Reales Beispiel: ggt für LC 80 Datei

    • Architekturnachteil und Alternative

    • Von-Neumann-Flaschenhals Aufgabe

      Eine Kritik am von-Neumann-Konzept wurde 1977 von Turing-Award-Preisträger John W. Backus geübt: 

      „Sicherlich muss es auf eine weniger primitive Art möglich sein, große Änderungen auf dem Speicher durchzuführen, als riesige Mengen von Datenwörtern vor und zurück durch den Von-Neumann-Flaschenhals zu schieben. Diese Röhre bildet nicht nur einen wörtlichen Flaschenhals für den Datenverkehr eines Problems [...], es ist ein intellektueller Flaschenhals, der uns an ein Denken „ein Datenwort auf einmal“ gebunden hat, anstatt uns zu ermutigen, in den Begriffen der größeren konzeptuellen Einheiten der vorliegenden Aufgabe zu denken.“

      Ermitteln Sie mithilfe eines der bereits analysierten MOPS- oder Johnny-Programme, was mit dem Begriff "von-Neumann-Flaschenhals" gemeint ist. Recherchieren Sie Möglichkeiten, das Problem des Flaschenhalses zu reduzieren.


    • Der Prozessor fordert während der Abarbeitung des Programms die Programmbefehle aus dem Speicher über den Datenbus an, muss aber auch die zu verarbeitenden Daten vom Speicher holen und wieder im Speicher ablegen. Teilweise müssen Operanden aus dem Speicher in den Prozessor nachgeladen werden. Das Rechenwerk ist also zum Warten verdammt. 

      Wie man damit leicht einsieht, ist das Verbindungssystem zwischen dem Prozessor und dem Speicher ein Engpass, der auch als von-Neumann-Flaschenhals bezeichnet wird.


      Illustration des Flaschenhalses am Polycomputer 880 im Einzelschrittbetrieb.

      Da insbesondere der Hauptspeicher und die Ein-/Ausgabegeräte meist deutlich langsamer arbeiten als der Prozessor, entstehen zusätzliche Wartezeiten..

      Eine wichtige Gegenmaßnahme sind schnelle Cache-Speicher zwischen Prozessor und Hauptspeicher. Sie halten häufig oder voraussichtlich benötigte Daten und Befehle möglichst nahe am Prozessor bereit.

      Das klassische von-Neumann-Modell beschreibt die Befehlsverarbeitung grundsätzlich als Folge einzelner Verarbeitungsschritte. Backus kritisierte, dass dieses Modell dadurch auch das Denken über Programme stark auf die schrittweise Verarbeitung einzelner Datenwerte ausrichtet.

    • Hardvard-Architektur: Vergleich, Vor- und Nachteile (nur im LK) Link/URL

      Ermitteln Sie mithilfe der angegebenen Website Gemeinsamkeiten und Unterschiede in der Architektur. Leiten Sie jeweils Vor- und Nachteile ab.

  • nur im LK: Speichern, Rechnen und Vergleichen mit Logikgatter

    • George BoolDass das Binärsystem für Rechenautomaten besonders günstig ist, erkannten Konrad Zuse (Deutschland) und George Stibitz (USA) in den 1930er Jahren. Die mathematischen Grundlagen dafür gehen auf den britischen Mathematiker George Boole zurück, der Mitte des 19. Jahrhunderts die nach ihm benannte Boolesche Algebra entwickelte.

      Versuchen wir nun, Elemente aus dem theoretische Modell der von-Neumann-Architektur mithilfe der (booleschen) Grundbausteine digitaler Systeme - der sog. Logikgatter - zu entwickeln.

      Bildquelle: George Boole, See page for author, Public domain, via Wikimedia Commons

    • Tafelwerkergänzung Gatter Datei

    • Grundlagen Logikgatter entdecken

      (in Abhängigkeit vom Wissensstand aus Klasse 10)

    • Grundgatter AND/OR/NOT/XOR: Kapitel 1.1 bis 1.8 Link/URL
    • 01 AB Gatter Wiederholung 10 Datei
    • Vorgaben für LogicSim und DSimWeb Verzeichnis
    • Übungen zu Gattern Aufgabe

    • Elemente der von-Neumann-Architektur mit Logikgatter entwickeln

    • Intermezzo: Rechnen mit Binärzahlen Aufgabe
    • Halb- und Volladierer Aufgabe

    • Probleme beim Rechnen

    • Übungen zu Gattern zur Umsetzung der von-Neumann-Architektur Aufgabe

      Durch das Zusammenschalten von Logikgattern ist es uns gelungen, Elemente der von-Neumann-Architektur hardwarenah zu entwickeln. Schauen wir, ob es vielleicht irgendwo Probleme geben könnte.

      1. Geben Sie die Elemente der von-Neumann-Architektur an, die wir hardwarenah aus Grundgattern entwickeln könnten.
      2. Im Rechenwerk finden Berechnungen und Vergleiche mithilfe des Binärsystems statt.
        1. Informieren Sie sich über die Codierung positiver und negativer ganzer Zahlen. Erläutern Sie die Begriffe Einer- und Zweierkomplement.
        2. Begründen Sie, dass Computer bei der Additionen zweier positiver ganzer Zahlen eine negative Zahl erhalten können.
        3. Übertragen Sie das Java-Programm main.java in den Online-Java-Editor und testen Sie die Funktionalität für die Zahlen 0, 30, -4234 und 2147483645.
          Begründen Sie das Verhalten des Programms.
        4. Entwickeln Sie in DSimWeb je eine Schaltung für die Bildung des Einerkomplements und des Zweierkomplements einer 4-Bit breiten Binärzahl. 
          Analysieren Sie die Schaltung A.json. Ermitteln Sie, was diese Schaltung leistet.
        5. Johnny verfügt über den Befehl TST. Wiederholden Sie, worauf der Test erfolgt.
          Entwickeln Sie in DSimWeb je eine Schaltung für Testung eines Bits bzw. eines Bytes wie in Johnny. 
          Analysieren Sie die Schaltung B.json. Ermitteln Sie, was diese Schaltung leistet.
    • Lösungen der Aufgaben Textseite
    • Präsentation Computerzahlen Datei
    • Übungsdateien Verzeichnis

    • Computer müssen auch negative ganze Zahlen darstellen können. 

      Eine Idee besteht darin, die Bitfolgen der natürlichen Zahl zu negieren (Einerkomplement). Wenn beispielsweise 6d = 0110b gilt, dann wäre im Einerkomplement -6d = 1001b.
      Allerdings gibt es dann zur Zahl 0 eine "negative" Null: 0d = 0000b, -0d = 1111b. Die Null ist aber einmalig, zur ihr darf es kein "Gegenstück" geben.

      Daher verwendet man das sog. Zweierkomplement. Die negierte Binärzahl wird einfach inkrementiert; aus 6d = 0110b wird -6d = 1010b. Addiert man beide Binärzahlen, so erhält man  sinnvollerweise Null.

      Im Zweierkomplement sind alle Binärzahlen, bei denen das höchste Bit den Wert 1 hat, negativ. Mit vier Bit lassen sich nun die Zahlen von -8d = 1111b bis 7d = 0111b bilden. Inkrementiert man die Binärdarstellung von 7d = 0111b, so erhält man 1000b = -8. Der Zahlbereich der ganzen Zahlen ist somit als Zahlenkreis darstellbar. Dies erklärt den Fehler im Java-Programm. Der Programmierer muss also stets auf den Wertebereich des Datentyps achten, um keine fehlerhaften Berechnungen durch Überlauf zu erzeugen.

      Die Abbildung reeller Zahlen auf dem Computer ist defacto unmöglich. Man nutzt ein Hilfskonstrukt, die Gleitkommadarstellung. Diese ist lässt jedoch nur eine endlich und diskret Menge an Zahlen zu, d. h. zwischen zwei Zahlen ist eine Lücke. Die Differenz zu nächst möglichen Gleitkommazahl ist ein Fehler, der sich bei umfangreichen Rechnungen auch sehr schnell summieren und dann zu ernsthaften Konsequenzen führen kann. 

      Zum Ausprobieren: Addiert in Java/Python einfach mal 0.1 und 0.2.