Hempel: Informatik 11 GK/LK - B Konzepte der theoretischen und technischen Informatik
Kursthemen
-
-
Herzlich 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: 06.03.2023 - Dieser Kurs wird aktuell nicht gepflegt.
-
-
-
Endliche Automaten mit Ausgabe
Beginnen wir mit der Suche nach dem Modell für eine universelle Maschine. Modell bedeutet, eine möglichst exakte, allgemeingültige Beschreibung nebst einem Funktionsbild für eine programmierbare Rechenmaschine zu finden. Die grundlegenden Komponenten kennen wir bereits seit Klasse 5/6 als EVA-Prinzip.
Beginnen wir die Suche mit elementaren Geräten - Computer sind da viel zu komplex. Wie wäre es mit einem Automaten? Reale Automaten sind ebenfalls Maschinen, die sich mit EVA beschreiben lassen. Sie finden sich z. B. in Form von Geldautomaten, Parkscheinautomaten, Getränkeautomaten oder Bonbon-Automaten.
Reale Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Das Modell 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: Blumenautomat
Ein Blumenautomat 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 Blumenautomat 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
-
Der durch nachfolgenden Graph gegebene Mealy-Automat mit Ausgabe MA = (X, Y, Z, δ , λ , q0) simuliert ein Verschlüsselungsverfahren, das nur mit Ziffern als Eingabezeichen arbeitet.
- Geben Sie die Mengen X, Y und Z an.
- Verschlüsseln Sie die Zahlenfolge 0 - 8 - 1 - 5 und entschlüsseln Sie die Nachricht 18 - 24 - 12 - 14.
- 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ösungen zur Aufgabe Mealy-Automat Textseite
-
Lösung Klingelton Datei
-
Lösung Kaffeeautomat Datei
-
-
-
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
- Der Automat liest ein Zeichen vom Eingabeband.
- In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen wechselt der Automat in einen Folgezustand. Anschließend wird das Band um eine Zelle weiter bewegt.
- Der Vorgang beginnt von vorn, solange noch ungelesene Zeichen auf dem Eingabeband sind.
- Befindet sich der Automat nach Lesen aller Eingabezeichen im Endzustand, so ist die Eingabe akzeptiert.
Sprache L(A) eines Akzeptors A
- Die Sprache eines Automaten L(A) ist die Menge aller von ihm akzeptierten Wörter, die man aus dem Eingabealphabet X bilden kann.
- Die Sprache kann verbal, durch die Angabe eines Musters oder aller Wörter beschrieben werden.
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}.
-
-
Lösungen zu den Aufgaben aus der Zusammenfassung "Akzeptor und Sprache" Textseite
-
Lösungen Akzeptor in Anwendungen Textseite
-
Lösungen Akzeptor mit ab- bzw. 01-Sprachen Textseite
-
-
-
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 #
- Einlesen des Eingabezeichens vom Eingabeband und Entnahme des aktuelle Kellerzeichen
- Zustandsübergang und Kelleroperation (push, pop, nop) in Abhängigkeit vom aktuellen Zustand, dem Eingabezeichen und dem Kellerzeichen
- Vorrücken des Bandlesekopfs um ein Zeichen
- ggf. Wiederholung der Schritte 2 bis 4
Der Kellerautomat akzeptiert eine Eingabe, wenn das Eingabewort vollständig eingelesen wurde, der aktuelle Zustand eine Endzustand ist und der Inhalt des Kellers leer ist.
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}
wobei die Beschriftung eines Übergangs wie folgt aufgebaut ist: (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
-
Lösungen Rangierproblem Textseite
-
Lösungen Übungszettel Textseite
-
Determinismus und Nichtdeterminismus
Die Aufgabe mit den Palindromen ist gar nicht so einfach. Unterscheiden wir nach drei Fällen:
- Palindrom mit Trennzeichen
- Palindrom ohne Trennzeichen und mit gerader Länge
- 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).
-
Lösungen Textseite
-
-
-
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
- Der Automat liest ein Zeichen vom Eingabeband.
- In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen schreibt der Automat ein Zeichen auf das Band, wechselt in einen Folgezustand und bewegt den Lese-/Schreibkopf nach links/rechts oder gar nicht.
- Der Vorgang beginnt von vorn, solange noch Verarbeitungsschritte möglich sein.
- Stoppt der Automat und befindet sich dann im Endzustand, so ist die Eingabe akzeptiert.
Definition des Akzeptors - Automat ohne Ausgabe
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 -
Lösung zur Aufgabe S. 8 Textseite
-
Lösung der Übungsaufgaben zur TM Textseite
-
-
-
Mit dem Akzeptor haben wir nun ein Automatenmodell kennengelernt, das (formale) Sprache erkennen kann. Im Folgenden frischen wir diese Erkenntnisse aus Klasse 10 auf und erweitern sie um eine visuelle Beschreibung für die Erzeugung von Sprache.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 natürlicher Sprachen (Esperanto, Klingonisch, Morsen, Blindenschrift) analysierten wir und versuchten uns in PROLOG.
-
Sollten Sie Probleme im Kreuzworträtsel gehabt haben, dann arbeiten Sie die Begriffe mithilfe von Inf-Schule: Sprache als Zeichensystem nach.
-
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 mit/ohne Bedeutung - Zeichenfolge
Aneinanderreihung einzelner Zeichen mit/ohne Bedeutung - Alphabet
Gesamtheit aller Zeichen der Sprache - 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.
- Zeichen
-
Die Definition einer formalen Grammatik lässt sich mithilfe von Syntaxdiagrammen visualisieren. Wir kennen diese Syntaxdiagramme bereits von der Sprache SQL, als wir den SELECT-Befehl verwendet haben. Hier der Auszug aus der SQLite-Dokumentation:
-
-
-
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.
-
Lösungen Verzeichnis
-
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.
- Schätze spontan die Zeit bis zur Ausgabe einer ersten Lösung für deinen Computer. Probiere erst dann das Programm aus.
- Beschreibe die prinzipielle Arbeitsweise des Programms.
- GK/Scratch:
- Füge den Baustein "zeige_Variablen" als 3. Block in das Ereignis "Wenn grüne Flagge angeklickt" ein und prüfe den Programmablauf.
- 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.
- LK/Java/Python:
- 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.
- Schätze die Laufzeit eines gleichartigen Programms für 4x4-Quadrate.
-
Beispiel für eine nicht berechenbare Funktion - das Halteproblem
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.
-
-
Mit 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. -
Geschichte der Computer - Abschnitt: Die ersten Computer der Welt Externes Tool -
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.
-
AB Johnny Lösungen Datei
-
Lösung 4_3a-c Datei
-
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.
-
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.
-
-
-
Dass 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
-
Lösungen Verzeichnis
-
Lösungen Verzeichnis
-
Lösungen Verzeichnis
-
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.
- Geben Sie die Elemente der von-Neumann-Architektur an, die wir hardwarenah aus Grundgattern entwickeln könnten.
- Im Rechenwerk finden Berechnungen und Vergleiche mithilfe des Binärsystems statt.
- Informieren Sie sich im Lehrbuch über die Codierung positiver und negativer ganzer Zahlen.
- Erläutern Sie die Begriffe Einer- und Zweierkomplement.
- Begründen Sie, dass Computer bei der Additionen zweier positiver Zahlen eine negative Zahl erhalten können.
- 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.
- Gruppe A:
- Entwickeln Sie in LogicSim je eine Schaltung für die Bildung des Einerkomplements und des Zweierkomplements einer 4-Bit breiten Binärzahl.
- Analysieren Sie die Schaltung GruppeA.lsim. Ermitteln Sie, was diese Schaltung leistet.
- Gruppe B:
- Johnny verfügt über den Befehl TST. Ermitteln Sie, worauf der Test erfolgt.
- Entwickeln Sie in LogicSim je eine Schaltung für Testung eines Bits bzw. eines Bytes wie in Johnny.
- 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.
-
