Pascalzahlen, Sierpinsky-Dreiecke und zelluläre Automaten

Letztmalig dran rumgefummelt: 13.06.08 19:06:19

	Es gibt wohl kaum einen Schüler, dem nicht früher oder später die Sogenannten Pascalzahlen begegnen, um Gelegenheit für mancherlei mathematische Entdeckungen zu bieten. Ihre Anordnung zum „arithmetischen Dreieck" war in arabischen und fernöstlichen Ländern Jahrhunderte vor Pascal bekannt; in Europa tauchen die Zahlen im 16. Jahrhundert auf, und erste Anwendungen auf die Kombinatorik und den binomischen Lehrsatz sind auf Anfang des 17. Jahrhunderts zu datieren.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Betrachtungen 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren das hat auch viel mit Problemlösungsstrategien zu tun Logo für die Pascal-Zahlen begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 48 ff.
	Blaise Pascal

1. Problembeschreibung

	Pascals eigenständiger Beitrag besteht in einer systematischen Analyse der Struktur des arithmetischen Dreiecks und im klar gehandhabten Beweisverfahren der vollständigen Induktion. Seit Pascals Zeiten hat das Dreieck nicht an Reiz verloren; noch immer finden sich neue und überraschende Anwendungen.
	Bild 1 Bildungsvorschrift für die Pascal-Zahlen Schnell begreifen die Schüler das einfache Bildungsgesetz: P(n,k)=P(n-1,k-1)+P(n-1,k) und alsbald wird munter drauflos gerechnet. Doch schon nach wenigen Zeilen wachsen die Zahlen ins Gigantische, vor denen der beste menschliche Rechner kapitulieren muss, und auch der Computer kann nur wenige Zeilen weiterrechnen. Wir helfen uns dadurch, dass wir etwas Information verschenken, indem wir die Pascalzahlen durch eine feste Zahl p teilen und lediglich die Reste aufschreiben. Das Bildungsgesetz gilt nach wie vor, so dass die Rechnung sehr einfach bleibt bzw. noch einfacher wird. Im Fall p=2 kommt es also nur darauf an, ob eine Pascalzahl gerade oder ungerade ist: Rechnet man „modulo 2", besteht das Dreieck lediglich aus Nullen und Einsen, und es gelten die Rechenregeln: 0+0=0 1+0=0+1=1 1+1=0 Wir bekommen das folgende Dreieck (vgl. Bild 2). Der Computer zeichnet die einprägsame Struktur von Bild 2. Ähnlich reizvolle, leicht abgewandelte Dreiecksstrukturen ergeben sich, wenn p die Werte 3, 5,7,... annimmt.
	Antivalenz-Logik Bild 3 Pascal-Dreieck mit Biärrechnung Pascal-Dreieck als DigCad 4.0-Datei
	Bild 3 Pascal-Dreieck Pascal-Dreieck als DigCad 4.0-Datei
	Bild 4 Pascal-Dreieck Pascal-Dreieck als DigCad 4.0-Datei

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.
	Aufgabe 1: Man schreibe ein Programm, welches arithmetische Dreiecke modulo p zeichnet. Dabei soll die Null durch jeweils eine Leerstelle dargestellt werden. Es liegt nahe, die arithmetischen Dreiecke (genauer: ihre Grenzwerte für wachsende Zeilenzahl) geometrisch nachzukonstruieren. Der Fall p=2 führt auf eine Figur, die nach dem polnischen Mathematiker W Sierpinsky benannt ist, der im Jahr 1916 eine Arbeit über Kurven publiziert hat, die man heute als Fraktale bezeichnen würde (siehe unten). Wir beginnen mit einem gleichseitigen Dreieck Δ0 und zerlegen es in vier kongruente Teildreicke. Nach Wegnahme des mittleren Teildreiecks erhalten wir die Figur Al. Die drei Teildreicke von Δ1 werden wieder in vier Teildreiecke zerlegt, das mittlere Dreieck wird jeweils weggenommen, woraus Δ2 entsteht, und so geht es weiter (vgl. Bild 3). Wird der Vorgang beliebig wiederholt, entsteht die Grenzfigur Δ∞. Eine leichte Rechnung zeigt, dass ihr Flächeninhalt null, der Umfang aller ihrer Dreiecke dagegen unendlich ist. Die Figur Δ1 ist also „mehr als eindimensional" und „weniger als zweidimensional" (Henn, 1989). Für jede Figur S dieser Dreiecksfolge gilt: Wird S durch eine Ähnlichkeitsabbildung mit Streckfaktor 2 zu S' vergrößert, so kann S' in drei kongruente Kopien von S zerlegt werden. Das Maß von S' ist y(S')=3y(S)=2,u (S), woraus D=log3/log2 =1,585 folgt. Die Zahl D heißt „Ähnlichkeitsdimension" von S. Die zur Definition dieses Dimensionsbegriffs verwendete „Selbstähnlichkeit" lässt sich wie folgt veranschaulichen: Wir fotografieren S mit ständig wachsender Vergrößerung; jedoch - wie weit die Vergrößerung auch getrieben wird - stets zeigt sich das gleiche Bild. Geometrische Gebilde mit dieser Eigenschaft heißen nach B. Mandelbrot „Fraktale". Wir stellen fest: Der Grenzwert des arithmetischen Dreiecks modulo 2 bzw. sein geometrisches Pendant, das Sierpinsky-Dreieck, sind Fraktale. Die Erzeugungsregeln für Pascalzahlen modulo p lassen sich beträchtlich verallgemeinern, wenn man diese als Zustände „linearer zellulärer Automaten" auffasst. Wie bereits erläutert, besteht ein linearer zellulärer Automat aus einem beliebig langen Streifen von Feldern (Zellen), die ihren Zustand nach gewissen Regeln ändern. Ein solcher Automat wird durch zwei natürliche Zahlen p und r sowie endlich viele Übergangsregeln spezifiziert. Die Zahlen 0, 1, 2, ..., p-1 sind die möglichen Zustände einer Zelle; die Zahl r ist der sogenannte Nachbarschaftsradius, der angibt, wie viele Nachbarzellen auf jeder Seite einer Zelle deren nächsten Zustand bestimmen. Betrachten wir das Beispiel p=2, r=1. Das heißt: Jede Zelle kann zwei Zustände 0 und 1 annehmen, die Übergangsregeln beziehen neben der Zelle selbst je r=1 Nachbarn links und rechts dieser Zelle ein. Die Übergangsregeln notieren wir wie folgt: 111 110 101 100 011010 001000 0 1 0 1 1 0 1 0 Abkürzend können wir 01011010=90 schreiben, wenn wir die untere Zustandsfolge als Dualzahl auffassen und ihr dezimales Äquivalent bilden. Die „Regel 90" liefert das arithmetische Dreieck modulo 2, wenn von genau einer Zelle im Zu stand 1 ausgegangen wird (vgl. Bild 2). Mit Hilfe der Regel 10010110=150 bekommen wir dagegen die Figur im Bild 4. Interessante Strukturen liefern auch die Regeln 18, 22, 126, 146, 182 und 218. Aufgabe 2: Man verallgemeinere das Programm von Aufgabe 1 so, dass es die Evolution eines gegebenen linearen zellulären Automaten auf dem Bildschirm ausgibt. Ferner konstruiere man das geometrische Pendant zu Regel 150 und beweise, dass seine Ähnlichkeitsdimension kg,1 +)/'log-' =1,694 ist.
	Binärzahlen und binär codierte Dezimalzahlen grafische Veranschaulichung der Bitzuordnungen für die ersten 256 Hexadezimalzahlen grafische Veranschaulichung der Bitzuordnungen für die ersten 256 Hexadezimalzahlen

3. Lösungsalgorithmus

Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Vom Informatikkurs der Jahrgangsstufe 12 des Schuljahres 2007/08 wurden per Projektarbeit einige solcher Algorithmen erstellt und werden hier nun zusammengefasst sowie präsentiert. Besonders interessante Lösungen kamen aus dieser Gruppe oftmals von Johannes, Eric aber auch von André.
	Version 1.0 (schnellste Berechnung, bis 7 Stellen akzeptabel): Das Programm kann Narziss-Zahlen ausrechnen, allerdings nur bis 9 Stellen, da 10 Stellen bereits Delphis Variablen sprengen. Außerdem muss man den Rechner nach der Berechnung noch an lassen, da die Werte nur in eine ListBox geschrieben werden.   Programm zur Ermittlung der Narziss-Zahlen Programm zur Ermittlung der Narziss-Zahlen   Programm zur Ermittlung der Narziss-Zahlen
	Erics Version: Programm zur Ermittlung auch großer PASCAL-Dreiecks-Zahlen Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex Programm zur Ermittlung auch großer Narziss-Zahlen - extrem laufzeitkomplex

5. Zusammenfassung

6. Weiterführende Betrachtungen

	Die grundlegende Idee lautet, dass man die nun mit jeder geometrischen Grundstruktur einschließlich Kreisen als mathematische und/oder rekursive Struktur behandeln kann. Ab einer Zahl von neun dürfte das aber sehr unübersichtlich sein - deshalb also unser Ansatz bis neun ;-)
	Sierpinsky-Quadrate Sierpinsky-Geometrie für Quadrate Sierpinsky-Geometrie für Quadrate Sierpinsky-Pentagramm als DigCad 4.0-Datei Sierpinsky-Pentagramm als DigCad 4.0-Datei
	Sierpinsky-Pentagramme Sierpinsky-Geometrie für Pentagramme hab' ich noch nicht gefunden ;-) Sierpinsky-Pentagramm als DigCad 4.0-Date diese also auch nicht ;-)
	Sierpinsky-Sechsecke Sierpinsky-Geometrie für Sechsecke Sierpinsky-Geometrie für Sechsecke Sierpinsky-Sechseck als DigCad 4.0-Datei Sierpinsky-Sechseck als DigCad 4.0-Datei

7. Weiterführende Informationen

	War 'ne tolle Sache (zumindest für mich als Lehrer), einmal ein Schuljahr lang mit Schülern über doch die Grenzen von Programmiersprachen tangierende Probleme zu diskutieren, diese auszuloten, Algorithmen zu finden und wieder wegzuwerfen. Dümmer geworden ist dabei wahrscheinlich keine der betroffenen Seiten, die Schüler werden's teilweise einige Monate später an Universitäten bemerken ;-) Alles war im Rahmen des Möglichen: es anstrengend (was es ja sein soll), aber machbar - unten kann man einige Ergebnisse einsehen. Alles, was präsentiert wird, ist Wissensstand  Juni 2008 ;-)
	die Primzahl-Zwillingssuche der Kaprekar Algorithmus das 153-Problem - Narziß-Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Ulam-Spirale die befreundeten Zahlen die Polynomzahlen die Goldbach-Vermutung das Palindrom Spiegelsummen-Problem die Perfect Numbers
	die Zahlenteiler GGT KGV   die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-) die Pseudoprimzahlen Quersummenermittlung Primzahlfaktorisierung

8. Links zum Thema

	http://ams.astro.univie.ac.at/~nendwich/Diverses/Fraktale/

9. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Ros am 28. Februar 2008