Das Monte-Carlo-Verfahren

Letztmalig dran rumgefummelt: 27.04.15 17:17:55

	Der Mathematiker Stanislaus M. Ulam (1909-1984) hat die Wissenschaft nicht nur um wichtige mathematische Sätze und Methoden - wie z. B. den Satz von Borsuk-Ulam und die Monte-Carlo-Methode, d. h. die Simulation mittels Zufallszahlen, sondern auch um interessante Aufgaben, die in Zahlentheorie bzw. Unterhaltungsmathematik fallen, bereichert. Im Jahr 1963 musste Ulam, der damals am Los Alamos Scientific Laboratory arbeitete, einen (seiner Meinung nach) sehr langweiligen Vortrag anhören. Um sich die Zeit zu vertreiben, kritzelte er ein schachbrettartiges Gitternetz aufs Papier und nummerierte die einzelnen Felder gemäß einer - dem Uhrzeigersinn entgegengesetzten - Spirale. Ohne besondere Absicht kreiste er die Primzahlen ein - und stellte dabei zu seiner Überraschung fest, dass diese offenbar die Neigung besitzen, sich diagonal oder horizontal auf Geraden anzuordnen
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für das Monte Carlo-Verfahren begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 130/2004 Seite 70

1. Problembeschreibung

	Diese zufällige Entdeckung inspirierte Ulam, das Gleiche auch mit anderen quadratischen Spiralen zu versuchen. Im Rechenzentrum von Los Alamos waren die ersten 90 Millionen Primzahlen auf Magnetband gespeichert, und zudem verfügte der Computer MANIAC II sogar über eine grafische Ausgabe - damals noch eine Seltenheit. Zusammen mit den Kollegen Mark Wells und Myron Stein programmierte er den Computer so, dass die Vermutung an den Primzahlen zwischen 1 und 65 000 visuell überprüft werden konnte.
	Aufgabe: Es soll ein Programm geschrieben werden, das ein endliches Stück der Ulamspirale abbildet! Das Auge nimmt zuerst die diagonal verlaufenden Geraden wahr, die durch aneinander grenzende Felder ungerader Zahlen entstehen; es lässt sich aber auch deutlich eine Tendenz der Primzahlen zur Anordnung in horizontalen und vertikalen Geraden feststellen. Eine Gerade beliebiger Richtung trägt Zahlen, die sich durch ein quadratisches Polynom darstellen lassen; beispielsweise beschreibt 4x2 + 10x + 5 die Folge 5,19, 41, 71 für x = 0, 1, 2,3 (siehe Bild 1). Beginnt die Spirale nicht mit 1, sondern beispielsweise mit 17, werden die Diagonalen durch andere quadratische Polynome dargestellt; etwa im Fall n =17 durch das Polynom x2 + x + 17, das für x = 0, ..., 15 Primzahlen liefert. Eulers bekanntestes primzahlwertiges Poynom x2 + x + 41 kann auf ähnliche Art in einem Gitter dargestellt werden, wenn die Spirale mit 41 beginnt; es erzeugt 40 auf der Hauptdiagonale gelegene Primzahlen. Schon lange ist bekannt, dass von den ersten 2398 Zahlen, die durch dieses Polynom erzeugt werden, genau die Hälfte Primzahlen sind.
	Primzahlen auf der Ulam-Spirale

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

3. Lösungsalgorithmus

4. Programmvorschläge

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

8. 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 Rost am 18. Februar 2008