Tracetabelle


Programmstrukturen mit welchen der Wert von Variablen verändert wird, nennt man Algorithmen.

Mit Hilfe von Algorithmen werden:

  • Berechnungen mit Daten durchgeführt,
  • Daten sortiert,
  • Daten mit besonderen Eigenschaften gesucht,
  • Daten verschlüsselt und entschlüsselt
  • ...

Damit man versteht, was ein Algorithmus mit Daten macht, ist es hilfreich, wenn man den Wert von Variablen, in denen Daten gespeichert sind, während der Ausführung eines Algorithmus beobachten kann.

Die tabellarische Auflistung von Daten, die in Variablen gespeichert sind und die man während des Ablaufs eines Algorithmus notiert, nennt man eine Tracetabelle.


Tracetabelle für eine Schleife

  • Starten Sie das Programm Blockly-Trace-Editor oder löschen Sie das aktuelle Programm durch einen Klick auf "Programm löschen", wenn der Blockly-Trace-Editor noch geöffnet ist.

  • Bauen Sie folgendes Programm und erzeugen Sie die vollständige Tracetabelle:

Bei solchen einfachen Veränderung von "a" kann unser Gehirn noch mitdenken. Bei komplizierteren Algorithmen ist es hilfreich, wenn man sieht, bei welcher Wiederholung, die Variable "a" einen bestimmten Wert hatte. Dazu verwendet man den Schleifenblock "zähle ... von ... bis" bei welchem eine Zählvariable verwendet wird, die ihren Wert bei jedem Durchlauf der Schleife verändert.

Damit beide Variablen in der Trace-Tabelle angezeigt werden, muss der Block "Trace-Eintrag dazu" mit der Variablen "i" ergänzt werden.

  • Klicken Sie auf das Zahnradsymbol im Block "Trace-Eintrag dazu" und schieben Sie von der linken Spalte einen Block "Element" innerhalb von "verbinden".

  • Ergänzen Sie den Block mit der Variablen "i", so dass folgende Trace-Tabelle erzeugt wird, wenn Sie wiederholt auf "nächster Schritt" klicken:

Wenn man im Block "Trace-Eintrag dazu" eine Variable andockt, die noch keinen Wert hat, dann wird in der Trace-Tabelle nichts angezeigt.

  • Wenn etwas nicht klappt, können Sie das Programm auch laden: Schleife.

Übung 1: Fibonacci

Die Fibonacci-Zahlenfolge ist eine berühmte Folge von Zahlen:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …

Sie entsteht, indem ab der dritten Zahl eine neue Zahl in der Zahlenfolge die Summe der beiden letzten bereits vorhandenen Zahlen ist:

2 = 1 + 1; 3 = 2 + 1; 5 = 3 + 2; 8 = 5 + 3; ...

Ein Algorithmus, um diese Zahlenfolge zu erzeugen, kann wie folgt beschrieben werden:

  • Lege drei Variablen "neueZahl = 1", "v1 = 0", "v2 = 1" fest
  • Wiederhole von i = 2 bis 15:
    • neueZahl = v1 + v2
    • v1 = v2
    • v2 = neue Zahl

Erstellen Sie ein Block- oder Text-Programm, das diesen Algorithmus auführen kann und erzeugen Sie eine Trace-Tabelle mit den ersten 15 Zahlen der Fibonacci-Folge.


Listen zur Speicherung von Daten

In vielen Situationen ist es notwendig, vorliegende Daten anhand bestimmter Kriterien zu sortieren. Bei Zahlen ist eine der einfachsten Sortierungen die Sortierung nach deren Größe. In diesem Kapitel lernen Sie einen Sortier-Algorithmus kennen, mit welchem man eine Menge von Zahlen der Größe nach sortieren kann.

Bevor eine Menge von Zahlen durch den Computer sortiert werden kann, muss diese gespeichert werden. Man könnte für jede Zahl eine eigene Variable anlegen, aber ein Programm würde dadurch sehr unübersichtlich werden. Sinnvoller ist es, die Menge von Zahlen in einer einzigen Variablen zu speichern.

Datenstruktur "Liste"

Auf die Elemente einer Liste kann über den Index der Liste zugegriffen werden.

Der Index einer Liste beginnt bei 0.

Für die im Beispiel angelegte Liste mit den Elementen 3, 9, 7, 1, 4 gilt also:

  • Element bei Index 0 ist 3
  • Element bei Index 1 ist 9
  • Element bei Index 2 ist 7
  • Element bei Index 3 ist 1
  • Element bei Index 4 ist 4

Beim Entwickeln eines Algorithmus mit Listen muss also genau beachtet werden, wie man den Zugriff auf Elemente einer Liste über den Index programmiert.

Inhalte einer Liste entnehmen

  • Menschen nummerieren eine Menge von Zahlen beginnend bei 1.
  • Informatiker*innen beginnen bei der Nummerierung von Listen bei 0.
Inhalte in einer Liste mit neuen Inhalten ersetzen


Zwei Zahlen sortieren

In einer Liste kann eine Menge von Zahlen gespeichert werden. Diese Menge von Zahlen kann mit Hilfe von Algorithmen bearbeitet werden. Beispielsweise kann die Liste von Zahlen nach der Größe sortiert werden.

Das folgende Beispiel funktioniert wie folgt:

  • Zuerst wird eine Liste mit zwei Zufallszahlen erzeugt.
  • Dann wird mit einer Falls-Abfrage geprüft, ob die Zahl beim Index 0 größer ist als die Zahl beim Index 1.
  • Wenn ja:
    • der Inhalt von Index 1 wird in eine Hilfsvariable namens "temp" gespeichert,
    • in Index 0 wird der Inhalt von Index 1 gespeichert,
    • in Index 1 wird der Inhalt von "temp" gespeichert.
  • Wenn nein:
    • dann wird nichts gemacht


Fünf Zahlen sortieren

Das folgende Beispiel funktioniert wie folgt:

  • Zuerst wird eine Liste mit fünf Zufallszahlen erzeugt.
  • Mit Hilfe von zwei Wiederholungsschleifen werden die Zahlen solange durchlaufen, bis sie der Größe nach sortiert sind.
  • Dazu wird mit einer Falls-Abfrage geprüft, ob die Zahl beim Index 0 größer ist als die Zahl beim Index 1.
  • Wenn ja:
    • der Inhalt von Index 1 wird in eine Hilfsvariable namens "temp" gespeichert,
    • in Index 0 wird der Inhalt von Index 1 gespeichert,
    • in Index 1 wird der Inhalt von "temp" gespeichert.
  • Wenn nein:
    • dann wird nichts gemacht


Optimierung des Algorithmus

Der erste Sortieralgorithmus benötigt bei \(n\) Zahlen \(n^2\) Schleifen-Wiederholungen. Das kann bei großen Zahlenmengen, die sortiert werden sollen, schnell sehr viel werden.

Der Algorithmus soll so umgebaut werden, dass erkannt wird, wann die Zahlen sortiert sind und der Algorithmus früher gestoppt wird.

Der erste Sortieralgorithmus benötigt bei \(n\) Zahlen \(n^2\) Schleifen-Wiederholungen. Das kann bei großen Zahlenmengen, die sortiert werden sollen, schnell sehr viel werden.

Der folgende Algorithmus soll so umgebaut werden, dass erkannt wird, wann die Zahlen sortiert sind und der Algorithmus früher gestoppt wird.