02 Rekursive Regeln und Generationen

Einstieg in das Thema

Was brauchst du als Basiswissen?

Du kannst Rekursionsschritt und Abbruchbedingung an einem anschaulichen Muster unterscheiden.

Worum geht es?

Eine rekursive Beschreibung kann sehr kurz sein. Sie beschreibt eine große Struktur mithilfe einer kleineren Version derselben Struktur. Außerdem können feste Ersetzungsregeln aus einer kurzen Zeichenfolge mehrere Generationen erzeugen.

Was ist das Ziel?

Du kannst eine einfache rekursive Beschreibung auflösen, Regeln wiederholt ausführen und entstehende Generationen vergleichen.

Erarbeitung

Theorie

Aufgaben

Zuerst T(n) selbst auflösen. Das Zeichen □ steht für ein Quadrat. Es gilt:

T(0) = □ T(n) = □ gefolgt von T(n−1), wenn n mindestens 1 ist.
Aufgabe 1
Ergänze die Lücken:
T(4) = □ + T(...) = □ + □ + T(...) = □ + □ + □ + T(...) = □ + □ + □ + □ + T(...) = ...
Aufgabe 2
Was wird bei jedem Schritt kleiner?
Aufgabe 3
Welcher Grundfall beendet das Auflösen?
Aufgabe 4
Wie viele Quadrate enthält T(4)? Erkläre, warum es nicht vier sind.

Es gilt:

K(0) = ein Kreis K(n) = ein Kreis um K(n−1), falls n mindestens 1 ist.
Aufgabe 5
Löse K(3) und K(5) schrittweise auf.
Aufgabe 6
Zeichne beide Ergebnisse.
Aufgabe 7
Benenne Rekursionsschritt und Grundfall.
Aufgabe 8
Erkläre die Bedeutung von K(0).
Aufgabe 9
K(5) hat den Durchmesser 60 cm, K(4) 50 cm und K(3) 40 cm. Ergänze die Durchmesser bis zum Grundfall K(0).

Eine Treppenbeschreibung:

S(0) ist eine einzelne Stufe. S(n) ist eine Stufe vor S(n−1), wenn n mindestens 1 ist.
Aufgabe 10
Löse S(4) auf.
Aufgabe 11
Skizziere das Ergebnis.
Aufgabe 12
Formuliere die Beschreibung ohne Buchstaben und Klammern.
Aufgabe 13
Verändere den Grundfall so, dass S(0) aus zwei Stufen besteht. Wie wirkt sich dies auf S(4) aus?

Du sollst nun Zeichen ersetzen und damit "Wörter" bauen. Jetzt sind die Aufgaben also nicht mehr auflösend, sondern konstruierend.

Start: A Regeln: A → AB B → A
Aufgabe 14
Erzeuge sorgfältig:
- Generation 0: A - Generation 1: AB - Generation 2: ... - Generation 3: ... - Generation 4: ... - Generation 5: ...
Aufgabe 15
Markiere in Generation 3 jedes A und jedes B verschiedenfarbig. Ziehe von jedem Zeichen einen Pfeil zu seinem Ersatz in der nächsten Generation. So wird sichtbar, dass alle Zeichen ersetzt werden.
Aufgabe 16
Notiere die Länge jeder Generation.
Aufgabe 17
Wie viele A und wie viele B kommen jeweils vor?
Aufgabe 18
Vergleiche die Anzahlen einer Generation mit der Länge der vorherigen Generation. Was fällt auf?
Aufgabe 19
Sage die ersten drei Zeichen der nächsten Generation voraus, ohne sie vollständig aufzuschreiben.
Aufgabe 20
Erkläre mit eigenen Worten, wie die nächste Generation entsteht.

Hinweis: Wenn du auch in der Oberstufe Informatik wählst, wirst du Aufgaben ähnlicher Art wiedersehen.

System X: Start A, Regel A → AA System Y: Start A, Regel A → AB; für B gibt es keine Regel.
Aufgabe 21
Erzeuge für beide Systeme die Generationen 0 bis 4.
Aufgabe 22
Was geschieht mit einem Zeichen, für das keine Regel angegeben ist?
Aufgabe 23
Vergleiche die Längen.
Aufgabe 24
Welche Regel führt zu schnellerem Wachstum? Begründe anhand der erzeugten Generationen.

Erstelle nun eigene Ersetzungsregeln. Verwende höchstens die Zeichen A, B und C. Lege einen Start und für jedes verwendete Zeichen eine Regel fest.

Aufgabe 25
Erzeuge vier Generationen von Hand.
Aufgabe 26
Tausche nur Start und Regeln mit einer anderen Person (sofern möglich).
Aufgabe 27
Vergleicht anschließend eure Generationen.
Aufgabe 28
Falls sie verschieden sind: Findet die erste Stelle, an der eine Regel unterschiedlich angewendet wurde.

Rückblick und Ausblick

Was muss man wissen und können?

  • T(n−1) beschreibt eine kleinere Version derselben Struktur.
  • T(0) ist der Grundfall und Start der Folge.
  • Beim Auflösen arbeitet man sich von T(n) bis zum Grundfall zurück.
  • Beim Konstruieren liest man die Folge vom Grundfall aus vorwärts.
  • Generation 0 ist der Start.
  • Jede Regelanwendung erzeugt die nächste Generation.
  • Aus kurzen Regeln können schnell lange Zeichenketten entstehen.

Was folgt als Nächstes?

Nun untersuchen wir eine geometrische Struktur, die mit jeder Generation komplexer wird, obwohl ihre Regel sehr kurz bleibt.