Abschnittsübersicht

  • Einklappen Ausklappen

    11 B: Formale Sprachen, endliche Automaten und John-von-Neumann-Rechner

    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 Aspekte aus der theoretischen und der technischen Informatik.

      Nachdem wir im ersten Abschnitt der Jahrgangsstufe 11 einen praktischen Zugang zur Wissenschaft Informatik am Beispiel der Modellierung von Datenbanken erfahren haben, wollen wir nun einen Schritt weiter gehen und den Computer als universelle Maschine hinterfragen. Ziel ist es, ein/das Modell für eine universelle Maschine zu entwickeln, die in der Lage ist, Probleme durch Programmierung zu lösen. Uns interessiert das Modell und seine Grenzen. Natürlich wollen wir aus dem Modell dann auch einen Computer entwickeln - naja, zumindest versuchen wir das mal.

      Der Moodle-Kurs begleitet den Unterricht. Sie finden hier alle Tafelbilder, Aufgaben, Dateien, Arbeitsblätter sowie Lösungen. Die Unterlagen werden nach der Behandlung in der Stunde veröffentlicht. Darüber hinaus werden Sie Aktivitäten im Kurs ausführen müssen. 

      Stand: 19.11.2024 - Dieser Kurs wird aktuell 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 als Open Source oder Freeware deklariert. 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
    • AtoCC: Simulationssoftware AutoEdit und GrammarEditor Link/URL
    • FLACI: Webbasiertes Simulationsprogramm, Nachfolger von AtoCC Link/URL
    • Johnny: Offline-Version der Simulationssoftware für einen von-Neumann-Rechner Link/URL
    • Johnny: Online-Version der Simulationssoftware für einen von-Neumann-Rechner Link/URL
    • LogicSim 2 Link/URL
    • DSimWeb: Online-Version und Nachfolger von LogicSim Link/URL

    • Lehrbücher

    • Ergänzungsmaterial Automaten Link/URL
  • Einklappen Ausklappen

    Selbststudium 10.12.2024

    • Aufgaben
      Nicht verfügbar, außer: Sie sind in LK_11
    • Gründung beider deutscher Staaten Externes Tool
      Nicht verfügbar, außer: Ihr Profilfeld Nachname ist Hempel
  • Einklappen Ausklappen

    Mealy-Automat - Automat mit Ausgabe

    • Endliche Automaten mit Ausgabe

      Beginnen wir mit der Suche nach dem Modell für eine universelle Maschine. Das von-Neumann-Modell beschreibt den Computer als universelle Maschine. Dies wissen wir aus Klasse 10. Darüber hinaus kennen wir das EVA(S)-Prinzip bereits seit Klasse 5.

      Sind Automaten auch universelle Maschinen? Wir finden sie z. B. in Form von Geldautomaten, Parkscheinautomaten, Getränkeautomaten oder Bonbon-Automaten. Solche Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Es geht auf die 1955 veröffentliche Arbeit "A Method for Synthesizing Sequential Circuits" des US-amerikanischer Mathematiker George H. Mealy zurück.

      Definition des Mealy-Automat

      Ein Mealy-Automat MA = (X, Y, Z, δ, λ, z0) 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, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
        • λ ... Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) genau ein Ausgabezeichen zuordnet
        • z0 ∈ Z ist der Anfangszustand
      Aufbau eines Funktionsmodells

      Arbeitsweise
      • Der Automat liest ein Zeichen vom Eingabeband.
      • In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen wechselt der Automat in einen Folgezustand und gibt auf dem Ausgabeband ein Zeichen aus. Anschließend werden beide Bänder um eine Zelle weiter bewegt.
      • Der Vorgang beginnt von vorn, solange noch ungelesene Zeichen auf dem Eingabeband sind.
    • 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 akzeptiert der Automat nicht. 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 entgegen nehmen, also für obiges Beispiel statt 18 - 24 - 12 - 14 die Form 1 - 8 - 2 - 4 - ...
    • Lösung zur Aufgabe "Primitiver Verschlüsselungsautomat" Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Übungen zum Mengenbegriff Aufgabe
    • Übungen zum Mealy-Automat Datei
  • Einklappen Ausklappen

    Akzeptor und Sprache

    • Endliche Automaten ohne Ausgabe - Akzeptor

      Ein Safe öffnet sich nur dann, wenn die vierstellige Ziffernkombination korrekt eingegeben wurde. Eine 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 (nichtleere, 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 Eingabeband
        • Wechsle in Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen in einen Folgezustand.
        • Bewege das Band eine Zelle weiter.
      • Falls der aktuelle Zustand ein Endzustand ist, dann aktiviere die Akzeptanzanzeige.

      Wörter und Sprache
      • Ein Wort w ist eine Kombination von Zeichen aus einem Alphabet X.
      • Die Menge aller Wörter über einem Alphabet X ist unendlich groß.
        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, ...}.
      • Die Sprache eines Automaten L(A) ist die Menge aller Wörter über dem Alphabet X, die A 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 alle Binärzahlen, deren letzten beiden Bits Null sind. 
        L(A) ist die Menge aller durch 4 teilbaren Binärzahlen.
        L(A) = {w | w ∈ X* und w endet auf 00}

      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
    • Lösungen zu den Aufgaben aus der Zusammenfassung "Akzeptor und Sprache" Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Übungen zum Akzeptor in Anwendungen Aufgabe
    • Lösungen Akzeptor in Anwendungen Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Übungen zum Akzeptor mit ab- bzw. 01-Sprachen Aufgabe
    • Lösungen Akzeptor mit ab- bzw. 01-Sprachen Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
  • Einklappen Ausklappen

    nur für LK: Kellerautomaten

    • Endliche Automaten ohne Ausgabe und mit Kellerspeicher - Kellerautomat

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


      Funktionsmodell eines Kellerautomaten

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

      • ist nach oben offen, also unendlich groß,

      • hat das Symbol # zur Anzeige des leeren Kellers.

      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 Kellerleerzeichen #
      • SOLANGE ein Zustandsübergang möglich ist:
        • Lies mithilfe der Leseköpfe das Zeichen aus der aktuellen Zelle des Eingabeband 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 Kellerleerzeichen 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, die dem aktuellem Zustand in Abhängigkeit vom jeweils aktuellen (ggf. leerem) Eingabezeichen und Kellerzeichen höchstens eine Kelleroperation und einen Folgezustand zuordnet
        • z0 ∈ Z ist der Anfangszustand
        • k0 ∈ Γ ist das Kellerleerzeichen (#)
        • ZE ... Endzustandsmenge (nichtleere, endliche Teilmenge von Z)

      Bei einem nichtdeterministischer Kellerautomaten müssen die Zustandsübergänge nicht eindeutig 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: (erwünschtes Kellerzeichen, erwünschtes Eingabezeichen): zu realisierende 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.

      ε hat also eine Mehrfachbedeutung: 

        • als Kelleroperation: nichts zurückschreiben
        • als "virtuelles" Eingabezeichen - nichts vom Band lesen
    • 03 Zusammenfassung Kellerautomat und Übungen Datei
    • Anwendung Kellerautomat - Rangierproblem Datei
    • Lösungen Rangierproblem Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Übungszettel 5 "Kellerautomat" Datei
    • Datei für Aufgabe Kellerautomat
    • Lösungen Übungszettel Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • 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 die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen. 

      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 raten, wo die Mitte ist. Ein Algorithmus oder ein Automat, der eine Lösung rät oder für die gleiche Eingabe bei identischer Startvorgabe verschiedene Lösungen ausgibt, wird nichtdeterministisch genannt. Genau so etwas benötigen wir jetzt. Das System muss alles einkellern und an einer zu ratenden Stelle mit dem Auskellern beginnen. Wenn wir Glück haben, war es die richtige, sonst muss das System eben neu raten. 

      So unsinnig uns der Nichtdeterminismus für Computer auch erscheinen mag, er findet trotzdem seine Anwendung in der Welt der Informatik (Randomisierte Algorithmen, Quicksort). 

    • Aufgaben zum Kellerautomat
    • Lösungen Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
  • Einklappen Ausklappen

    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 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. Der Kellerautomat kann zwei Mengen vergleichen, versagt aber bei drei Mengen.

      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.


      Alan Turing       entwickelte das mathematische Konzept einer universellen Maschine und stellt dies 1936 in der Arbeit "On Computable Numbers, with an Application to the 'Entscheidungsproblem'" vor. Dieser Beitrag gilt als die Geburtsurkunde der Wissenschaft 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: https://commons.wikimedia.org/w/index.php?title=File:Alan_Turing_az_1930-as_%C3%A9vekben.jpg&oldid=450320260

      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 dem gelesenen Zeichen Automat ein Zeichen auf das Band, führe eine Lese-/Schreibkopfoperation (keine, eine Bewegung nach links/rechts) durch und wechsle dann in einen Folgezustand.
      • Falls der aktuelle Zustand ein Endzustand ist, dann aktiviere die Akzeptanzanzeige.

      Definition der Turingmaschine

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

      • X ... Eingabealphabet (nichtleere, endliche Menge)
      • Z ... Zustandsmenge (nichtleere, endliche Menge)
      • Γ ... Bandalphabet (nichtleere, endliche Menge)
      • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) höchstens eine Ausgabe, eine Kopfbewegung (L, N, R) und einen Folgezustand zuordnet
      • z0 ∈ Z ist der Anfangszustand
      • $ ... Bandvorbelegungszeichen
      • ZE ⊆ Z ... Endzustandsmenge (nichtleere, 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
    • Lösung zur Aufgabe S. 8 Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
    • Übungen zur TM als Akzeptor Aufgabe
    • Lösung der Übungsaufgaben zur TM Textseite
      Nicht verfügbar, außer: Sie sind in einer Gruppe
  • Einklappen Ausklappen

    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 Manipulationen der Zeichen auf dem Band. Die Zeichen können Codierungen von Zahlen oder Zeichen darstellen. Damit beschreibt eine Turingmaschine eine Funktion = Programm = Algorithmus, die nach bestimmten Regeln Eingaben auf dem Band in Ausgaben auf das Band abbildet. 

    • Übungen zur rechnenden Turingmaschine Aufgabe
    • Lösungen Verzeichnis
      Nicht verfügbar, außer: Sie sind in einer Gruppe

    • 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.

      Ein Algorithmus ist nicht anderes als eine intuitiv berechenbare Funktion und somit eine Turingmaschine. 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.


      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 definierbare Funktionen, die nicht algorithmisch lösbar sind. 

      Vertiefung: 

      Haben Sie mal ein Beispiel für so eine Funktion? 😀

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

      Ein Programm (GK: Scratch, LK: Java/Python) sucht magische Quadrate von Typ 3x3 auf eine logische, aber nicht sehr effektive Art. Es probiert einfach alle Varianten 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.

    • 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·258 (lt. Spiegel 2011) positiv beantworten können. Dennoch könnte schon die nächste Zahl das Programm in eine Endlosschleife führen. Sinnvoll wäre ein Programm, mit dessen Hilfe man für jedes beliebige Programm entscheiden kann, ob es mit jeder beliebigen Eingabe nach endlich vielen Schritten abbricht oder nicht?

      Dies dürfte kein Problem sein, da jedes Programm als eine Zeichenkette dargestellt werden kann und damit als Eingabe für das Stopp-Test-Programm dienen kann. Man könnte sogar für Testzwecke das Stopp-Programm selbst als Eingabe nutzen. Die Informatiker nennen dies "Selbstanwendbarkeitsproblem".

      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 Ausgabe: "Das Programm ist selbststoppend."
             WHILE (true) DO //nichts
        ELSE Ausgabe: "Das Programm ist nicht selbststoppend."
      END.

      Ist Seltsam selbststoppend oder nicht?

      Angenommen es ist selbststoppend. Startet man nun das Programm SELTSAM und gibt ihm seinen Quelltext als Eingabe, so wird der gleiche Algorithmus abgearbeitet, wie beim Stopp-Test und damit die Variable stopp auf true gesetzt. Das Programm gibt nun aus, dass es selbststoppend ist, bleibt aber dann in der Endlosschleife hängen, ist also nicht selbststoppend. Damit steht es im Widerspruch zur Annahme.

      Angenommen es ist nicht selbststoppend. Auch hier wird das Programm SELTSAM wie oben beschrieben abgearbeitet und die Variable stopp erhält den Wert false. Der Algorithmus gibt nun aus "Das Programm ist nicht selbststoppend", hält aber anschließend. Damit ist aber wieder ein Widerspruch zur Annahme vorhanden.

      Da SELTSAM weder die Eigenschaft "selbststoppend" noch deren logische Negation besitzt, kann es nach den Gesetzen der Logik nicht existieren. Da es formal aus dem ersten Programm entwickelt wurde, kann es aber auch kein Programm Stopp-Tester geben.

      Resümee:

      Es ist nicht möglich von einem beliebigen Programm zu sagen, ob es nach endlich vielen Schritten stoppt oder nicht! Damit wurde (beweisbar) ein Problem gefunden, dass nicht mit Hilfe des Computers gelöst werden kann.

      Vertiefung/Visualisierung: 

       

  • Einklappen Ausklappen

    Formale Sprache und Grammatik

    • Mit Akzeptor, Kellerautomat und Turingmaschine haben wir Automatenmodelle kennengelernt, die (formale) Sprachen erkennen können. Im Folgenden frischen wir diese Erkenntnisse zu Sprache und Grammatik aus Klasse 10 auf. 

      In der Jahrgangsstufe 10 haben wir bereits natürliche und künstliche Sprachen analysiert und verglichen. Mithilfe der Begriffe Zeichen, Zeichenfolge, Wort, Satz, Alphabet, Grammatik, Sprache, Syntax und Semantik waren wir in der Lage, Eigenschaften von Sprache, wie etwa Mehrdeutigkeit, Fehlerfreundlichkeit, Universalität und Flexibilität zu untersuchen. Hilfssysteme für natürliche Sprachen (Esperanto, Klingonisch, Morsen, Blindenschrift) haben wir analysiert. 

    • Sprache

      Schriftliche Sprache definieren wir als Zeichensystem zum Zweck der Kommunikation. Im weitesten Sinn werden neben den so genannten natürlichen Sprachen auch künstliche Sprachen (wie beispielsweise Welthilfssprachen oder Programmiersprachen in der EDV) sowie die Kommunikationsmittel der Tiere dazu gerechnet.

      Elemente einer Sprache

      Die (schriftliche) Sprache besteht aus

      • Zeichen
        kleinstes Element einer Sprache
      • Alphabet
        Gesamtheit aller Zeichen der Sprache
      • Zeichenfolge
        Aneinanderreihung einzelner Zeichen mit/ohne Bedeutung
      • Wort
        Aneinanderreihung einzelner Zeichen (Morphologie) mit einer Bedeutung (Wortsemantik)
      • Satz
        kleinste sprachliche vollständige Einheit mit einer Bedeutung (Satzsemantik), die nach festen Regeln (Syntax) aufgebaut ist
      • Grammatik
        Regelwerk zur Wort- (Morphologie) und Satzbildung (Syntax), Form der systematischen Sprachbeschreibung
      • Semantik
        Bedeutung der Zeichen, Worte und Sätze


      Sprachklassifikation

      Natürliche Sprachen ist die von Menschen gesprochene Sprache, die aus einer historischen Entwicklung entstanden ist. Künstliche Sprachen (Plansprache, Geheimsprache, ...) sind vom Menschen geschaffene Hilfssysteme und dienen der Codierung von Sprache z. B. für einen alternativen Übertragungsweg. 

      Natürliche Sprachen besitzen eine komplizierte Grammatik und eine mehrdeutige Semantik. Dies kann sich über die Hilfssysteme auch auf die künstlichen Sprachen übertragen.

      Formale Sprachen (z. B. Programmiersprachen) vermeiden diese strukturellen und semantischen Uneindeutigkeiten. Sie werden durch eine formale Grammatiken erzeugt. Die Untersuchung formaler Sprachen begann in den 1950er-Jahren durch Noam Chomsky.


      Formale Grammatik

      Eine formale Grammatik lässt sich mithilfe von Syntaxdiagrammen darstellen und wählen daher diesen Zugang, da wir ihn bereits von der Sprache SQL kennen. Beispielsweise findet sich eine Beschreibung des SELECT-Befehl in der SQLite-Dokumentation auszugsweise wie folgt:

    • Ü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
  • Einklappen Ausklappen

    Von-Neumann-Rechner

    Hervorgehoben

    • John von NeumannMit der Turingmaschine haben wir nun eine mathematisches Modell für eine universelle Maschine, die in der Lage ist, eine Vielzahl von Problemen durch eine Programmierung zu lösen. Turings Idee in ein reales Gerät zu verwandeln, war dann aber noch eine weitere Herausforderung.

      Im Mai 1941 gelang dies dem Berliner Ingenieur Konrad Zuse mit der Z3, dem ersten funktionsfähigem Digitalrechner der Welt. 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 erfuhr zufällig von der amerikanischen Entwicklung und erkannte den Nutzen für ein Projekt, in das er involviert war - dem Manhattan-Projekt. Im Nachgang abstrahierte er alle ihm bekannten Entwicklungen und beschrieb 1945 in First Draft of a Report on the EDVAC die bis heute gültige prinzipiellen Architektur eines Computers.

      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 LK_12

    • 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 acht 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
    • AB Johnny Lösungen Datei
      Nicht verfügbar, außer: Sie sind in LK_12
    • Lösung 4_3a-c Datei
      Nicht verfügbar, außer: Sie sind in LK_12
    • 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 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 zusätzlich die Geschwindigkeit der peripheren Elemente (Speicher, I/O-Einheit) heutzutage deutlich kleiner ist als die Verarbeitungsgeschwindigkeit des Prozessors, kommt es immer wieder zu unnötigen Wartezeiten des Prozessors.

      In der Praxis versucht man diesen Effekt abzuschwächen. Eine Möglichkeit ist der Einsatz von Zwischenspeichern (Cache) im Prozessor (L1) oder vor dem Prozessor (L2). Diese können die Daten aus dem Speicher schon vorsorglich einlesen. 

      Die Kritik von Backus zielt aber noch in eine weitere Richtung. Aufgrund der strukturellen Vorgabe kann ein von-Neumann-Rechner stets nur eins nach dem anderen tun. Dies ist aus Backus Sicht eine Einschränkung auch des Denkens.

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

      Einer der ersten Computer, der Mark I, wurde in Kooperation zwischen IBM und der Harvard-Universität entwickelt und 1944 in Betrieb genommen wurde. Er verwendete eine Rechnerarchitektur die sich von der von-Neumann-Architektur unterscheidet.

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


  • Einklappen Ausklappen

    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 Mathematik dafür wurde von George Boole (USA) in der Mitte des 18. Jahrhunderts entwickelt. 

      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 10 Datei
    • Vorgaben für LogicSim Verzeichnis
    • Lösungen Verzeichnis
      Nicht verfügbar, außer: Sie sind in LK_12
    • Kleine Übungen zu Gattern (Selbststudium) Aufgabe
    • Lösungen Verzeichnis
      Nicht verfügbar, außer: Sie sind in LK_12

    • Elemente der von-Neumann-Architektur mit Logikgatter entwickeln

    • 02 Intermezzo: Binäres Rechnen Datei
    • Halbaddierer/Volladierer: Kapitel 3.4 und 3.5 Link/URL
    • Flip-Flop als binärer Speicher: Kapitel 6.1, 6.2, 6.4 und 6.5 Link/URL
    • 01 AB Gatter für von-Neumann Datei
    • Vorgabe und Module für LogicSim Verzeichnis
    • Lösungen Verzeichnis
      Nicht verfügbar, außer: Sie sind in LK_12

    • 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 im Lehrbuch über die Codierung positiver und negativer ganzer Zahlen.
        2. Erläutern Sie die Begriffe Einer- und Zweierkomplement.
        3. Begründen Sie, dass Computer bei der Additionen zweier positiver Zahlen eine negative Zahl erhalten können.
        4. Starten Sie das Java-Programm Zahlen.java im Java-Editor und testen Sie die Funktionalität für die Zahlen 0, 30, -4, 120, -120. Begründen Sie das Verhalten des Programms.
        5. Gruppe A:
          1. Entwickeln Sie in LogicSim je eine Schaltung für die Bildung des Einerkomplements und des Zweierkomplements einer 4-Bit breiten Binärzahl.
          2. Analysieren Sie die Schaltung GruppeA.lsim. Ermitteln Sie, was diese Schaltung leistet.
        6. Gruppe B:
          1. Johnny verfügt über den Befehl TST. Ermitteln Sie, worauf der Test erfolgt.
          2. Entwickeln Sie in LogicSim je eine Schaltung für Testung eines Bits bzw. eines Bytes wie in Johnny. 
          3. Analysieren Sie die Schaltung GruppeB.lsim. Ermitteln Sie, was diese Schaltung leistet.

    • 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.