260.169 UE Ubungen zu¨ Einfuhrung in das funktionale¨ und ...cms.mpi.univie.ac.at/mitten/angaben.pdf · 4. UBUNGSZEITEN¨ Seite 5 4 Ubungszeiten¨ Die Ubungen ﬁnden im¨ Computerpraktikum

260.169 UEUbungen zu

Einfuhrung in das funktionaleund symbolische Programmieren

mit Mathematica

Florian MITTENDORFER

16. Marz 2010

Seite 1

Inhaltsverzeichnis

A UBUNGSMODUS 3

1 Beurteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Durchfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Ausarbeitung/Abgabe der Beispiele . . . . . . . . . . . . . . . . . . .. . . . 4

4 Ubungszeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5 Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5.1 Aufbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5.2 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

6 Fragen/Informationen/... . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 7

B BEISPIELE 8

1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.1 Komplexe Funktionen: Riemann Flachen (10 Pkte) . . . . . .. . . . . 8

2 Regelbasierendes Programmieren . . . . . . . . . . . . . . . . . . . . .. . . 9

2.0.1 One-Liners (4x5 Pkte) . . . . . . . . . . . . . . . . . . . . . 9

2.0.2 Damenspiel (20 Pkte) . . . . . . . . . . . . . . . . . . . . . 10

3 Funktionales Programmieren . . . . . . . . . . . . . . . . . . . . . . . . .. . 11

3.1 Chaos Game (10 Pkte) . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.1.1 Deterministisches Chaos (max. 30 Pkte) . . . . . . . . . . . 13

3.1.2 Fraktale (max. 35 Pkte) . . . . . . . . . . . . . . . . . . . . 18

4 Matrizen und Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Ubungsunterlagen 1. Marz 2010

INHALTSVERZEICHNIS Seite 2

4.1 Kristallgitter (20 Pkte) . . . . . . . . . . . . . . . . . . . . . . . . . .21

4.2 1-dimensionale Quasikristalle (25 Pkte) . . . . . . . . . . . .. . . . . 21

4.3 Random Walk (20 Pkte) . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.4 Skalierungsverhalten (20 Pkte) . . . . . . . . . . . . . . . . . . . .. . 25

4.5 Spins am Gitter (20 Pkte) . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Neue Methoden: Genetische Algorithmen . . . . . . . . . . . . . . . .. . . . 29

5.1 Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.2 Losung eines dreidimensionalen Packungsproblems mitHilfe von ge-netischen Algorithmen (25 Pkte) . . . . . . . . . . . . . . . . . . . . . 30

5.3 Erweiterung: Komplexeres 2D Packungsproblem (20 Pkte). . . . . . . 30

C Package.m - Ubersicht 32

1. Marz 2010

Seite 3

A UBUNGSMODUS

Fur dieUbung260169 UE Ubungen zu Einf uhrung in das funktionale und symbolischeProgrammieren mit Mathematica gilt im SS2010 der folgendeUbungsmodus:

1 Beurteilung

1. Es gibt eine vorgegebene Sammlung von UE-Beispielen (siehe Abschnitt B), aus denensich jede/jeder eine Anzahl von Beispielen aussuchen kann.

2. Fur einepositiveNote mussen mindestens 40 Punkte erreicht werden, wobei zumindest je10 Punkte in der Kategorie ’2:Funktionales Programmieren’und ’3: Matrizen und Gitter’erreicht werden mussen.

3. Fur jedes Beispiel gibt es eine maximal erreichbare Punkteanzahl (siehe auch TabelleC.1).

4. Jede/jeder gibt bis Semesterende eine beliebige Anzahl von gelosten (oder teilweise gelosten)und ausprogrammierten Beispiele ab.

5. Die Punkte aller abgegebenen Beispiele werden aufsummiert.

6. Die erreichten Punkte bestimmen dann nach folgendem Schlussel die Note:

(Randbedingung: In Kategorie 2 und 3 wurden zumindest 10 Punkte erreicht.)

Punkte Note

≤ 40 5

40 - 49 4

50 - 60 3

60 - 70 2

≥ 70 1

Tabelle A.1: Notenschlussel


2. DURCHFUHRUNG Seite 4

2 Durchfuhrung

• Die physische Anwesenheit wahrend derUbung istnicht erforderlich.

• Die Ubungen konnen auch zu Hause oder auf anderen Ihnen zur Verfugung stehendenComputern absolviert werden.

• Da die Platze wahrend derUbungszeiten beschrankt sind mogen jene, die auf die wahrendder Ubungszeiten zur Verfugung stehenden Gerate angewiesensind, sich rechtzeitig an-melden. Die Vergabe der Platze erfolgt nach demfirst come. . . first servePrinzip!

• Die Anmeldungzu denUbungen istimmer(d.h. auch wenn dieUbungen extern absolviertwerden)erforderlich. Anmeldeschlußist am 31.Marz 2010.

• Die Anmeldung zu denUbungen ist bis 31. Marz 2010 durch folgende Moglichkeitengegeben:

1. Email an:[email protected]

2. Auf Listen wahrend der Vorlesung.

3 Ausarbeitung/Abgabe der Beispiele

• Jedes Beispiel ist alsMathematica -File (∗.m) auszuarbeiten. Es kann pro Beispiel nurdieses eine File abgegeben werden. Bei der Namensvergabe ist sich an die vorgegebenenNamenPackage.m entsprechend der UE-Angabe zu halten.

• Fur jedes PackagePackage.m muß es eineMessage Package::usage geben, die al-le exportierten Funktionen auflistet. Jede dieser Funktionen muß wiederum ihre eigene::usage Message besitzen.

• Ein kurzerUberblick, wie packages aufgebaut sind ist in Abschnitt 5 gegeben.

• Die Ubertragung geschieht uber e-mail, Programmlistings undanderepaperwarewerdennicht akzeptiert!

• Derspateste Abgabeterminist am 1. Juli 2010.

1. Marz 2010

4. UBUNGSZEITEN Seite 5

4 Ubungszeiten

Die Ubungen finden imComputerpraktikum (Godel HS) statt.

Mittwoch, von 15.30 - 16.15 Uhr (Gruppe 1)Mittwoch, von 16.15 - 17.00 Uhr (Gruppe 2)

Beginn der Ubungen: Mittwoch, den 17.Marz 2010.

Ende der Ubungen: Mittwoch, den 23. Juni 2010.

5 Packages

Ein guter Programmierstil zeichnet sich dadurch aus, dass der Programmcode (oder Teile davon)fur spatere Projekte weiterverwendbar ist. Daher benutzen “gute” Programmierer stets einenmodularen Aufbau fur ihre Programme. Es werden kleine Einheiten verwendet, die uber wohldefinierte Schnittstellen miteinander kommunizieren und nach ihren Funktionen in Gruppengespeichert werden. Diese Gruppen werden fur gewohnlichModulegenannt, die UntereinheitenUnterroutinen.

AuchMathematicaunterstutzt modulare Programmierung, verwendet aber andere Bezeichnun-gen fur die Untereinheiten.

Eine Package ist eine abgeschlossene funktionale Einheit, innerhalb derer Variablen, Funk-tionen und Parameter definiert und verwendet werden konnen, die dann auch nach außen hinunsichtbar bleiben. Zur Kommunikation mit der Außenwelt muss eine Schnittstelle definiertsein.

Die Beschreibung des Packages und diehelp messagesind optional, helfen aber dem Anwender(und Programmierer) den Code und dessen Anwendung zu verstehen.

5.1 Aufbau

Ein Package besteht aus einem header, einem Hauptteil und einem Schluss. Ein kleines Beispielsoll das verdeutlichen.

1. Head:

BeginPackage["NameOfPackage‘"]NameOfPackage::usage = "Description"

1. Marz 2010

5. PACKAGES Seite 6

2. Body

Begin["‘Private‘"]

3. Tail

End[]EndPackage[]

5.2 Beispiel

Name des packages :Q2R:

Head

BeginPackage["Q2R‘"]

Q2R::usage = "\nIsingmodell (sehr vereinfacht)\n\nAufruf: Q2R[Zeit,Groesze,Spinausrichtung]\n\nVoreingestellte Werte: Zeit=10,Groesze=5,Spinausric htung=0.65\n\nEingabebeispiele: Q2R[] liefert die Ergebnisse fuer die Voreinstellungen\n Q2R[10,5,.72]\n\nAutoren: Gruppe mma04\n"

Body

Begin["‘Private‘"]

Q2R[t_Integer:10,L_Integer:4,p_:.65]:=(

. . . Program

Tail

End[]EndPackage[]

1. Marz 2010

6. FRAGEN/INFORMATIONEN/... Seite 7

Das ersteEnd[] schließt diePrivate Umgebung, das zweiteEndPackage[] das Package (unddamit den Gultigkeitsbereich der Variablen. Der Name vor dem Schlusselwortusage spezifi-ziert die Schnittstelle, sodass der Name des Packages dann innerhalb derMathematicasessionbekannt ist.

6 Fragen/Informationen/...

Sollten Unklarheiten oder Fragen bezuglich der Durchfuhrung derUbungen oder denUE-Beispielenbestehen oder sonstige Probleme auftreten, wenden Sie sichbitte an:

• Email an:[email protected]

• Es kannjeder(insbesondere auch jene, die dieUbungen extern absolvieren) wahrend derUbungszeiten am Mittwoch Nachmittag von 15.30 - 17:00 Uhr vorbeischauen und Fragenbesprechen (Probleme/Fragen beim Ausprogrammieren derUbungsbeispiele).

Zusatzliche Informationen sind auf der Homepage der Arbeitsgruppe unter

http://cmp.univie.ac.at/

zu finden. Dort ist auch dieseUbungsanleitung als pdf beziehbar sowie alle Informationen nach-lesbar.

Wien, am 1. Marz 2010

Florian Mittendorfer

1. Marz 2010

Seite 8

B BEISPIELE

1 Einfuhrung

1.1 Komplexe Funktionen: Riemann Flachen (10 Pkte)

Viele komplexe Funktionen, wie zB. der Logarithmus, sind inder komplexen Ebene nicht ein-deutig definiert, da ihre inverse Funktion - die Exponentialfunktion - im komplexen mehr alseinen Funktionswert hat. Die Funktionen lassen sich allerdings geometrisch als eine Verknpfungvon mehreren Blattern in der komplexen Zahlenebenen (BildB.1) darstellen.

Schreiben Sie einPackageRiemann.m , das die Riemannsche Flache fur wahlweise den Real-bzw. Imaginarteil einer beliebigen komplexen Funktion darstellt und stellen Sie mit diesemPackage die Riemannflachen der folgenden Funktionen dar:

• Log[z]

• Sqrt[z]

• 1/Sqrt[z]

• ArcCos[z]

Abbildung B.1: Riemann’sche Flache fur den Logarithmus in der komplexen Zahlenebene.


2. REGELBASIERENDES PROGRAMMIEREN Seite 9

2 Regelbasierendes Programmieren

2.0.1 One-Liners (4x5 Pkte)

Versuchen Sie die folgenden Probleme mit Hilfe von Ersetzungsregeln als ’Einzeiler’ zu losen:

Maxima Schreiben Sie eine FunktionMaxima[] , die diejenigen Elemente einer Liste ausge-ben soll, die großer als alle Vorganger sind.

In[1]:= Maxima[{2,5,3,6,4,8,1}]Out[1]:= {2,5,6,8}

Conway Folge Schreiben Sie eine Funktion, die dasn-te Element der Conway-Folge

3, 13, 1113, 3113, 132113, 1113122113, ...

berechnet.

Run length encoding Schreiben Sie eine FunktionRunEncode[] , die das sogenannterunlength encodingeiner beliebigen Liste von Integern berechnet.

In[1]:= RunEncode[{3,3,2,2,2,2,1,4,4,3}]Out[2]:= { {3,2},{2,4},{1,1},{4,2},{3,1} }}

Das run length encodingliefert eine Liste von geordneten Paaren{n, cnt } von denenn dieInteger der ursprunglichen Liste, undcnt die Anzahl von direkt aufeinanderfolgendenns be-stimmt.

0-1 Folgen Schreiben Sie eine FunktionSequences[n] , die alle moglichen Folgen der Ele-mente 0 und 1 der Langen ausgibt:

In[1]:= Sequences[3]Out[1]:= {{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1 ,0,1},{1,1,0},{1,1,1}}

1. Marz 2010

2. REGELBASIERENDES PROGRAMMIEREN Seite 10

2.0.2 Damenspiel (20 Pkte)

Furn≥ 4 kann man auf einemn×n Schachbrett jeweilsn Damen so plazieren, daß keine Dameeine andere schlagen kann.

Schreiben Sie ein PackageQueens.m , das zu einem gegebenenn mogliche Konfigurationenfindet und entsprechend darstellt. Bestimmen Sie zwei Losungen furn = 6, die nicht durchDrehung ineinander uberfuhrbar sind.

Hinweis: Um die Anzahl der zu untersuchenden Stellungen gering zu halten, empfiehlt es sichschon bei der Erzeugung der moglichen Stellungen die Schachregeln zu berucksichtigen. Einesolche Konfiguration ist in Abbildung B.2 dargestellt.

Abbildung B.2: Eine Losung desn-Damen Problems furn = 6.

1. Marz 2010

3. FUNKTIONALES PROGRAMMIEREN Seite 11

3 Funktionales Programmieren

3.1 Chaos Game (10 Pkte)

Als Beispiel fur ein sogenanntesIterated Function System(IFS) wollen wir dasChaos Gamebetrachten:

Gegeben sei ein gleichseitiges Dreieck in der Ebene —d.h.das Dreieck mit den Punkten(0,0),(1,0), und(0.5,

√3/2) — wobei wir die drei Vertices mit 1,2, und 3 bezeichnen wollen. Dann

wahlen wir einenbeliebigenPunktP0 in der Ebene und definieren eine Folge von Punkten{Pn}wie folgt: Starte mitP0; dann wahle zufallig einen der drei Dreiecks Vertices undbezeichne mitP1 den Mittelpunkt der Strecke zwischenP0 und dem gewahlten Vertex; wahle wieder zufalligeinen der drei Dreiecks Vertices und bezeichne mitP2 den Mittelpunkt der Strecke zwischenP1

und dem gewahlten Vertex. Durch kontinuierliches fortsetzten wird die Folge der Punkte{Pn}erzeugt.

Dieser Prozeß wirdChaos Gamegenannt, vor allem wegen der offensichtlich vollig unre-gelmaßigen Bewegung der Punkte, zumindest wenn man die ersten 10-20 Punkte der Folgebetrachtet (Abbildung B.3).

Betrachtete man aber Abbildung B.4 mit 8000 Punkten, so ist ein klares Muster — das soge-nannte”Sierpinsky Dreieck”— erkennbar. Tatsachlich konvergiert die Folge{Pn} fur jedenbeliebigen StartwertP0 gegen das”Sierpinsky Dreieck”.

Schreiben Sie ein PackageChaosGame.m, das die Folge{Pn} fur einen beliebig vorgegbenenStartpunktP0 undn Iterationen graphisch darstellt.

1. Marz 2010


0.25 0.5 0.75 1

0.25

0.5

0.75

Abbildung B.3: Die ersten 15 Punkte der Folge{Pn} des Chaos Gamesvom Startpunkt(0.2,0.7) und der Verwendung des gleichseitigen Dreieckes(0,0),(1,0), und(0.5,

√3/2).

0.25 0.5 0.75 1

0.25

0.5

0.75

Abbildung B.4: Eine Folge desChaos Gamesvom Startpunkt(0.2,0.7) und 8000 Schritte unterVerwendung des gleichseitigen Dreieckes(0,0),(1,0), und(0.5,

√3/2).

1. Marz 2010


3.1.1 Deterministisches Chaos (max. 30 Pkte)

Wir betrachten als Beispiel eineiterative Abbildung auf dem Einheitsintervall, d.h. eine Abbil-dung der Klasse

xt+1 = f (r,xt), x∈ [0,1] , (B.1)

wobei die Funktionf in x stetig (in der Regel sogar differenzierbar) sein soll.

Solche einfachen, streng deterministischen Gleichungen durchlaufen ein breites Spektrum anmoglichen dynamischen Verhalten.

Logistische Gleichung (20 Pkte) Ein Beispiel von (B.1) ist dieLogistische Gleichung

xt+1 = r xt (1−xt) , x∈ [0,1] , r ∈ (1,4] . (B.2)

Studiert man dieses System als Funktion des ”Kontrollparameters” r so zeigt es eine reicheStruktur. Furr < 3 konvergiert die sukzessive Iterationx1 → x2 → x3 → . . . → x zu dem Fix-punktx (x = f (r, x)). Furr > 3 wird der Fixpunkt ¯x(r) instabil und es tritt Periodenverdopplungauf, d.h. stabile Fixpunkte erfullen die Bedingung ¯x = f (r, f (r, x)). Bei r = 1+

√6 tritt aber-

mals Periodenverdopplung auf, sodaß man jetzt vier stabileFixpunkte besitzt. Fur die Funktionf bedeutet dies, daß diese fur die Iteration furt → ∞ diese vier Punkte in einer ganz bestimmtenSequenz immer wieder durchlauft. Dieser Prozeß der Periodenverdopplung setzt sich kaskaden-artig fort bis zu einem Haufungspunkt, der beim Wert

r∞ = 3.56994. . . (B.3)

liegt (numerisch bestimmt).

Fur Werter > r∞ tritt ein strukturell neues Verhalten auf, daß in den Abbildung B.5-AbbildungB.9 zu verfolgen ist. Aus den Bildern erkennt man, daß jenseits von r∞ (B.3) Bereiche vonChaos auftreten, die aber immer wieder von Bandern mit periodischen Attraktoren unterbrochenwerden. Im Gegensatz zum Bereich< r∞, wo nur Perioden vom Typus 2n vorkommen, tretenin diesen Zwischenbereichen auch Reihen von Perioden

p ·2n, p ·3n, p ·5n, mit p = 3,5,6, . . . (B.4)

auf.

Schreiben Sie ein PackageLogistic.m , das den Attraktor (B.2) fur beliebiger- undx-Bereichegraphisch darstellt.

1. Marz 2010


Funktion f (r,xt) r xt(1−xt) xt exp[r(1−xt)] axt ;a(1−xt)

Fixpunkt wird instabil bei 3.0000 2.0000 1.0000

”Chaotic regions” beginnen 3.5699 2.6924 1.0000

Zyklus mit ungerader Periode star-tet

3.6768 2.8332 1.4142

”Chaotic regions” enden 4.000 ∞ 2.0000

Periodische Attraktoren in”Chao-tic regions”

Ja Ja Nein

Tabelle B.1: Zusammenfassung der Funktionen vom Typ (B.1) und deren unterschiedlichesdynamisches Verhalten in verschiedenen chaotischen Bereichen.

Hinweise: x0 = 12 ist ein guter Startwert. Bei den Abbildungen sollen eine Folge von iterierten

Wertenxt fur t > tn aufgetragen werden, wotn so hoch gewahlt ist, daß die Einschwingvorgangebereits abgeklungen sind. Ein guter Wert zum Testen isttn = 100.

Deterministisches Chaos (30 Pkte) Die Gleichung

xt+1 = xt exp[r(1−xt)] (B.5)

als auch

xt =

r xt , xt < 12

r (1−xt), xt > 12

, x∈ [0,1] (B.6)

sind weitere Beispiele fur Gleichungen vom Typ (B.1).

Implementieren Sie ein PackageDetChaos.m , das beliebige Gleichungen vom Typ (B.1) suk-zessive iteriert und fur verschiedener- und x-Bereiche graphische darstellt. Testen Sie IhreImplementation, indem Sie explizit die drei vorgestelltenGleichungen darstellen.UberprufenSie die Eigenschaften aus Tabelle B.1 und betrachten Sie dieGleichung in verschiedenen Bi-furkationsbereichen.

Hinweise: Wahlen Sie einen passenden Startwertx0. Bei den Abbildungen sollen eine Fol-ge von iterierten Wertenxt fur t > tn aufgetragen werden, wotn so hoch gewahlt ist, daß dieEinschwingvorgange bereits abgeklungen sind. Ein guter Wert zum Testen isttn = 100.

Wichtig: Bei der Losung der PackagesLogistic.m undDetChaos.m ergibt sich einemaximalePunkteanzahl von 30 Punkten!

1. Marz 2010


2.8 3.2 3.4 3.6 3.8 4

0.2

0.4

0.6

0.8

1

Abbildung B.5: DieLogistische Gleichungfur 2.8< r < 4. Der Bereich, wo der Fixpunkt insta-bil wird, die Periodenverdopplungen bis zu 24, sowie das Fenster der Periode 3 sind besondersgut zu erkennen.

3.735 3.74 3.745 3.75 3.755

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Abbildung B.6: Im gedehnten Bereich 3.73< r < 3.76 ist das Fenster mit der Periode 5 gut zuerkennen.

1. Marz 2010


3.736 3.738 3.74 3.742 3.744

0.425

0.45

0.475

0.5

0.525

0.55

0.575

Abbildung B.7: Ein Ausschnitt aus Abbildung B.6 mit 0.4 < xt < 0.6 und 3.735< r < 3.745.

3.741 3.742 3.743 3.744 3.745

0.47

0.48

0.49

0.5

0.51

0.52

0.53

Abbildung B.8: Ein Ausschnitt aus Abbildung B.7 mit 0.47< xt < 0.53 und 3.740< r < 3.745.Vergleiche mit Abbildung B.5: In einem Teilfenster des ganzen Diagrammes wiederholt sich imKleinen das Muster, welches das Gesamtbild pragt.

1. Marz 2010


3.74402 3.74405 3.74407 3.7441 3.74413 3.74415 3.74418 3.7442

0.47

0.48

0.49

0.5

0.51

0.52

0.53

Abbildung B.9: Eine Vergroßerung des periodischen Fensters von Abbildung B.8. Das gezeigteFenster ist 0.47< xt < 0.53 und 3.7440< r < 3.7442.

1. Marz 2010


3.1.2 Fraktale (max. 35 Pkte)

Koch-Kurve (10 Pkte) Die Koch-Kurve (Koch snowflake) wird durch einen iterativen Prozeßerzeugt. Ein Liniensegment der Langel (vgl. Abbildung B.10a) wird in der angegebenen Weise(Abb. B.10b) durch 4 Segmente der Langel/3 ersetzt. Nach 3 solchen Iterationen erhalt mandann die Abbildung B.10c.

Schreiben Sie ein PackageKoch.m , das aus einer beliebig vorgegebenen Linie die Koch-Kurveerzeugt und graphisch darstellt.

Abbildung B.10: Erzeugung der Koch-Kurve. (a) Das Ausgangs-Liniensegment. (b) Das Seg-ment wird durch 4 gleichlange Teile der Lange 1/3 ersetzt. (c) Die Koch-Kurve nach 3 Iteratio-nen.

Random Midpoint Displacement (20 Pkte) Man kann sogenannte Zufallsfraktale (randomfractals) erzeugen, indem – ahnlich wie bei der Koch-Kurve – ein gegebenes SegmentP1P2

durch zwei SegmenteP1M′ undM′P2 ersetzt, wobei die Koordinaten des TeilungspunktesM′ =(r,θ) mit Hilfe einer (Pseudo-) Zufallszahl gleichformig aus 0≤ r ≤ p, bzw. 0≤ θ ≤ 2π gewahltwerden. Siehe dazu auch Abbildung B.11.

Die vorgegebene Konstantep bestimmt dabei nicht nur das Aussehen des Fraktals (gestrecktoder zackig), sondern auch die fraktale (Ahnlichkeits-) DimensionD.

D =logN

log 1R

. (B.7)

Dabei istN die Anzahl der gleichlangen Teile, in die das ursprungliche Segment geteilt wird,und R ist die (relative) Lange eines dieser Teile. Fur die Koch-Kurve galte dementsprechend

1. Marz 2010


Abbildung B.11: Die Erzeugung eines Fraktals durch dasrandom midpoint displacement. (a)Einfachesmidpoint displacement, in dem rein deterministisch substituiert wird. (b)randommidpoint displacement: Der MittelpunktM′ wird beliebig innerhalb der Scheibep gewahlt undbestimmt so die beiden neuen SegmenteP1M′ undM′P2.

N = 4 undR= 13, und damit alsoD = 1.262. Bei dem hier betrachteten stochastischen Prozeß

muß allerdingsRdurch den ErwartungswertE des SegmentsP1M′ ersetzt werden, der sich wiefolgt schreiben laßt

E =

Z p

0dr

Z 2π

0dθ

2rp2

12π

(14

+ r2 + r cosθ)1/2

. (B.8)

Schreiben Sie ein PackageMidPoint.m , das diesen Fraktal fur verschiedene Werte vonp er-zeugt und graphisch darstellt, und berechnen Sie uber (B.7) mit Hilfe von (B.8) seine fraktaleDimension.

Hinweise: Fur p = 0.35 ergibt sichD = 1.09607. Dasr-Integral in (B.8) kann analytisch aus-gewertet werden. In Abbildung B.12 ist ein solcherart produzierter Fraktal dargestellt.

Iterative Fraktale (35 Pkte) Implementieren Sie ein PackageFractals.m , das beliebige 2-dimensionale Fraktale, die analog zur Koch-Kurve oder zum Verfahren desrandom midpointdisplacmentiterativ durch Substitution erzeugt werden konnen, generiert. Testen Sie die Imple-mentation, indem Sie explizit die Koch-Kurve und denrandom midpoint displacement-Fraktaldarstellen.

Hinweis: Uberlegen Sie sich ein entsprechend allgemeines Konzept einesGenerators, der dieverschiedenen Fraktale bestimmen soll.

NOTE: Bei der Losung des PackagesFractals.m ergeben sich fur die PackagesKoch.m undMidPoint.m keine Punkte!

1. Marz 2010


Abbildung B.12: Ein Fraktal, der durch das Verfahren desrandom midpoint displacementerzeugt worden ist. Maximales Displacementp = 0.35, 7 Iterationen; fraktale DimensionD = 1.09607.

1. Marz 2010

4. MATRIZEN UND GITTER Seite 21

4 Matrizen und Gitter

4.1 Kristallgitter (20 Pkte)

Nachste-Nachbar-Tabellen In der Festkorperphysik kennt man drei kubische Systeme:

• primitiv kubisch (simple cubic (sc): die Atome sitzen an den Eckpunkten eines Wurfels)

• kubisch raumzentriert (body-centered cubic (bcc)die Atome sitzen an den Eckpunktenund am Schnittpunkt der Raumdiagonalen eines Wurfels)

• kubisch flachenzentriert (face-centered cubic (fcc): die Atome sitzen an den Eckpunktenund an den Schnittpunkten der Flachendiagonalen)

Bestimmen Sie die Anzahl der Atome mit gleichem Abstand von einem Ausgangsatom fur diese3 Systeme (die sogenannten Nachbarschalen: Schale= Kugeloberflache mit einem bestimmtenRadius auf denen die Mittelpunkte der Atome zu liegen kommen). Ausgehend von einem Star-tatom wird zuerst die Anzahl der nachsten Nachbarn (= jene Punkte mit dem kleinsten Abstandvom Startpunkt), dann die Anzahl der ubernachsten Nachbarn usw. berechnet.

Schreiben Sie ein PackageNachbar.m , dessen Input der Typ des kubischen Systems und dieAnzahl der zu berechnenden Nachbarschalen ist und das als Output die Anzahl der Atome inden einzelnen Schalen als Liste ausgibt.

Diese Nachbartabellen finden ihre Anwendung in den Tight-Binding Methoden der theoreti-schen Festkorperphysik.

4.2 1-dimensionale Quasikristalle (25 Pkte)

Der folgende Algorithmus erzeugt 1-dimensionale Quasikristalle (siehe dazu auch AbbildungB.13):

1. Erzeuge ein regelmaßiges 2-dimensionales Punktgitter(z.B. quadratisch).

2. Lege durch dieses Gitter zwei parallele Geraden, die durch zwei benachbarte Gitterpunktegehen, die mit derx-Achse einen Winkelα einschließen. Der Bereich zwischen diesenGeraden soll Akzeptanz-Domane (acceptance domain) heißen.

3. Bestimme alle Gitterpunkte, die innerhalb der Akzeptanz-Domane liegen.

4. Projiziere die so gefundenen Gitterpunkte auf eine der beiden Geraden.

Die Folge dieser Projektionen bildet genau dann einen 1-dimensionalen Quasikristall, wenntanα eine irrationale Zahl ist. Fur tanα = 1

τ , τ = 12(1+

√5) (Goldene Schnitt), erhalt man dann

die sogenannte Fibonacci-Kette.

1. Marz 2010


Schreiben Sie ein PackageQuasi1d.m , das den obigen Algorithmus fur beliebigesα fur einquadratisches Gitter implementiert, und erzeugen Sie damit die Fibonacci-Kette.

2 4 6 8 10 12

-2

-1

0

1

2

3

4

5

6

7

Abbildung B.13: Graphische Darstellung der Erzeugung eines 1-dimensionalen Quasikristalls.Man beachte das zugrundeliegende regelmaßige (quadratische) Gitter, die Akzeptanz-Domane(acceptance domain) zwischen den beiden Geraden, die darin liegenden Gitterpunkte und denauf die obere Gerade projizierten (und gedrehten) 1d Quasikristall. Durch die Wahl des Gera-denwinkels (mit derx-Achse) vonθ = arctan(1/τ), τ = 1

2(1+√

5) entsteht hier die Fibonacci-Kette.

1. Marz 2010


4.3 Random Walk (20 Pkte)

Beschreiben Sie den Zufallsweg (Random walk) eines Teilchens auf einem Gitter mit Fehlstel-len. Ein einfaches Modell kann mit folgendem Algorithmus beschrieben werden :

1. Erzeuge ein quadratisches Gitter, dessen Gitterplatzemit einer Wahrscheinlichkeitp be-setzt sind.

2. Wahle einen beliebigen Punkt des Gitters (besetzt oder unbesetzt) als Startpunkt.

3. Wahle zufallig einen der 4 unmittelbaren Nachbarpunkte (NSWO).

4. Wenn dieser Punkt besetzt ist, wechsle dorthin. Andernfalls bleibe auf dem jetzigen Punktstehen.

5. Falls noch nicht genug Schritte, gehe zu Punkt (3). Sonst Ende.

Die Modellierung dieses Prozesses ist in der Physik unter dem Namen Perkolationstheorie be-kannt Ist die Besetzungswahrscheinlichkeit unter einem kritischen Wertp< pc = 0.593, gibt esnur kleine zusammenhangende Cluster von besetzten Gitterpunkten, sodaß der obige Algorith-mus nur innerhalb dieses abgeschlossenen Clusters bleibt.Ubersteigtp jedoch die Percolations-Schwellepc, tritt praktisch immer (d.h. mit Wahrscheinlichkeit 1) eingroßer verbundener Clu-ster auf, sodaß die Bewegung auf den besetzten Gitterplatzen das ganze Gitter uberstreicht.

Schreiben Sie ein PackagePerkolation.m , das den obigen Algorithmus fur beliebig großequadratische Gitter bei beliebiger Besetzungswahrscheinlichkeit p implementiert, und stellenSie mehrere solcherwalksgraphisch dar.

Hinweis: Verwenden Sie periodische Randbedingungen oder ein entsprechend großes Gitter,um zu vermeiden, daß sie uber den Rand des Gitters hinaus marschieren.

1. Marz 2010


Abbildung B.14: Percolation auf einem quadratischen Gitter mit N = 50 bei einer Besetzungs-wahrscheinlichkeitp = 0.5. Dargestellt ist einwalk nach 200 Schritten.

1. Marz 2010


4.4 Skalierungsverhalten (20 Pkte)

In vielen Bereichen der Physik trifft man auf ein Skalierungsproblem: Wird z.B. eine physika-lische Große anstelle der ursprnglichen Messgenauigkeitp′ mit der empfindlicheren Messungp gemessen, so kann diese Renormierungstransformation mathematisch als

p′ = f2(p) , (B.9)

beschrieben werden.

Als einfaches Beispiel betrachten wir nochmals ein zweidimensionales, quadratisches Gittermit einer Kantenlange vonb = 2n. Unsere physikalische Große sei die Wahrscheinlichkeitp,daß ein Gitterpunkt des Gitters von einem ”Atom” besetzt ist.

Unsere Renormierungsvorschrift ist nun, daß wir ein Untergitter von 2×2 Gitterpunkten be-trachten, das wir als virtuelles Gitter bezeichnen wollen.Dieses 2× 2 Gitter vergrobert dasursprungliche Gitter und fuhrt damit zu einer Reduzierung der Gesamtgitterplatze. Das neueGitter bezeichnen wir auch als Super-Gitter und die 2×2 Gitterzellen als Block (siehe Abbil-dung B.15).

Treffen wir 4 Atome ein einem Block an, so wird der zugehorige Gitterplatz imSuper-Gitter besetzt. Falls nur 3 Gitterplatze besetzt sind, so wird der Platz imSuper-Gitter ebenfalls besetzt. Sind im Block nur 2 oder 1 Atom enthalten, bleibtder entsprechende Platz im Super-Gitter leer.

Damit laßt sich die Wahrscheinlichkeit, daß ein Gitterplatz im Super-Gitter besetzt wird, nie-derschreiben als

p′ = f2(p) = p4 +4p3(1− p) . (B.10)

Der kritische Punktpc fur das 2×2 Gitter ist der Punkt, der invariant unter der Transformationf2 ist. Dieser ergibt sich aus (B.10) zupc = 0.768 und ist etwas großer alspc = 0.593, der ausComputersimulationen erhalten wird (stimmt aber gut mit Experimenten uberein).

Schreiben Sie ein PackageRenorm.m , das die angegebene Renormierung (2×2 Block) fur eingegebenesb×b,b = 2n Gitter, dessen Gitterplatze mit einer Wahrscheinlichkeit p besetzt sind,t-mal durchfuhrt und die erhaltenen Super-Gitter graphisch darstellt.

1. Marz 2010


Abbildung B.15: Renormierungsschritt mit einem 2×2 Block.

1. Marz 2010


Abbildung B.16: Renormierung eines 8×8 Gitters, mitp=0.7, und die daraus erhaltenen Super-Gitter.

1. Marz 2010


4.5 Ising Modell (20 Pkte)

Betrachten wir ein quadratischesL∗L Gitter, dessen Gitterplatze zwei Zustande (”Spins”) besit-zen konnen (S= 1 ”Spin up” oderS=−1 ”Spin down”). Am Beginn der Simulation (t=0) sinddie Spins zufallig verteilt, danach wird der Spin am Gitterplatzx,y zur Zeitt +1 als Funktionfder umliegenden Gitterplatze berechnet

Sx,y(t +1) = f [Sx−1,y(t),Sx+1,y(t),Sx,y−1(t),Sx,y+1L(t)] . (B.11)

Fur unser Ising Modell verwenden wir eine einfache Funktion f :

Ein Spin wird dann und nur dann gedreht,wenn dieser gleich viele ”up” wie ”down” Nachbarn hat.

Hiebei wird das Gitter der Reihe nach abgegangen (i.e. linksoben→ rechts unten) und fur jedenGitterplatz uberpruft, ob er gleich viele ”up” wie ”down”Nachbarn hat. Wenn ja, wird der Spinumgedreht. Ausgangspunkt ist eine zufallige Verteilung der Spins auf dem Gitter, wobei jederGitterplatz mit einer Wahrscheinlichkeit von 1− p mit einemSpin ”up” (Sx,y = 1) und mit derWahrscheinlichkeit vonp mit einemSpin ”down” (Sx,y = −1) besetzt wird. EineZeitschrittistbeendet, nachdem so viele Durchlaufe wie Spins im Gitter vorhanden sind gemacht wurden.

Die gesamte Magnetisierung des Systems ist gegeben durch:

Mt =1L2

L2

∑k=1

Sk(t) . (B.12)

Schreiben Sie ein PackageIsing.m , das die MagnetisierungMt fur dieses Ising Modell aufeinemL ∗ L Gitter mit derSpin ”down” Wahrscheinlichkeit vonp fur t Zeitschritte simuliertund die Konfiguration der Spins graphisch ausgibt.

Hinweis: Testen Sie die Funktionsfahigkeit Ihres Scripts fur kleineL, t Werte (≈ 10) und ver-suchen Sie keinewirklichen Simulationen, die die Zeitressourcen bei weitem uberschreitenwurden.

1. Marz 2010

5. NEUE METHODEN: GENETISCHE ALGORITHMEN Seite 29

5 Neue Methoden: Genetische Algorithmen

5.1 Problemstellung

Genetische Algorithmen sind eine Methode zur Losung “unl¨osbarer” Aufgaben. “Unlosbar”soll hier so verstanden werden, daß ein konventioneller, deterministischer Ansatz wenig Erfolghatte, da das Berechnen der Losung fur alle praktischen Probleme zuviel Zeit und/oder ma-teriellen Aufwand (Speicher, Geld) in Anspruch nahme. In dieser Kategorie befindet sich dassogenannte“travelling salesman”–Problem, bei dem es darum geht, die kurzeste Wegstreckezu wahlen, um eine bestimmte Anzahl von vorgegebenen Stadten zu besuchen; oder um andereOptimierungsaufgaben.

Die Methode der genetischen Algorithmen wurde von John H. Holland als ein Losungsansatzfur “komplexe” Problemstellungen entwickelt [?, ?]. Sie wird heute in vielen Anwendungenimplementiert [?, ?], von der Computerwissenschaft, derOkonomie und Spieltheorie bis hin zutechnischen Bereichen wie der Berechnung von Fachwerkkonstruktionen in der Statik.

Genetische Algorithmen basieren auf der Entwicklung von “Arten” oder Losungsvarianten, mitnachheriger Bewertung und der Bildung neuer Arten durch bloße Mutation und Kreuzung. Diedabei auftretenden Zustande und Prozesse sind nicht unahnlich der heutigen Vorstellungen vonder Entstehung des Lebens auf der Erde, was durch den Terminus “genetisch” angedeutet wird.

Im Detail sieht die Methode der genetischen Algorithmen folgende Schritte bei der Losungeines konkreten Problems vor:

• Im ersten Schritt wird ein Satz (Pool) von moglichen Losungen erzeugt. Diese Losungenkonnen am Anfang zufallig erzeugt werden. Fur die folgenden Beispiele kann jede Teillosungzb. eine binare (0/1) Liste mit den Koordinaten der Objektesein.

• Im zweiten Schritt werden aus dem bestehenden Losungsset neue Losungen erzeugt. Da-bei kommen zwei Mechanismen zu tragen:

– “Kreuzung” (englisch “crossover”): eine bestehende Losung wird mit einer anderenLosung gekreuzt, d.h. ihrer jeweiligen binaren (0-1) Folgen ab einer bestimmten,zufallig gewahlten Position dieser Folge ausgetauscht:

Eltern

A: 00101000101001000111110001B: 11101010111001111110101011

Kreuzung:

A′: 00101000101... + ...001111110101011 =00101000101001111110101011

– “Mutation” aller Losungen durch zufalligen Austausch von 0 und 1 bzw. 1 und 0 anbeliebigen Positionen mit geringer Wahrscheinlichkeit (normalerweise 1:100);

1. Marz 2010


• Im dritten Schritt werden die neu erzeugten Losungen mit einer Bewertungsfunktion (Fit-nessfunktion) bewertet. Falls die neu erzeugte Teillosung besser als ist als seine Elternwird die schlechtere Losungen (Eltern) ersetzt.

5.2 Losung eines dreidimensionalen Packungsproblems mit Hilfevon ge-netischen Algorithmen (25 Pkte)

Losen Sie ein einfaches Packungsproblem mit Hilfe von genetischen Algorithmen. Ordnen Siedazu in einen Einheitswurfel der Kantenlange 1 mN Punkte so an, daß die Summe aller (eu-klid’schen) Abstande der Punkte voneinander maximal wird.

Fur einen typischen Losungsvektor kann der Standort derN Objekte durchN Vektoren

X = {~x1,~x2,~x3, . . . ,~xN−1,~xN}

angegeben werden. Die binare Codierung jedes Vektors~x j = (x1 j ,x2 j) kann unter anderemdurch binare Darstellung der einzelnen Komponenten bis zueiner Tiefe vonn bits erfolgen. Diebeiden Bitsequenzen konnen dann hintereinander geschrieben werden und ergeben so einenCode der Lange 2n fur~x j ; dh.,

~x j = (x1 j ,x2 j) ∼= b1,1, jb2,1, j · · ·bn−1,1, jbn,1, j︸︷︷︸

x1 j

b1,2, jb2,2, j · · ·bn−1,2, jbn,2, j︸︷︷︸

x2 j

.

Fur die Bewertungsfunktion verwenden Sie die Summe aller Abstande der Punkte:

B(X) =N

∑i=1

∑j<i

|~xi −~x j | ,

Schreiben Sie ein PackageGenet3D.m , das die Punktpositionen zur obigen Aufgabenstellungerrechnet. Um die Losungen zu veranschaulichen, stelle man die Losungskonfigurationen furN = 3,4,5 eingeschrieben in den Einheitswurfel dar.

5.3 Erweiterung: Komplexeres 2D Packungsproblem (20 Pkte)

In dieser Erweiterung zum vorherigen Beispiel soll die Anordnung von identischen (Punkt-)Objekten auf einer vorgegebenen Flache studiert werden. Diese Flache soll beliebig wahlbarsein und hier in Form von geschlossenen Polygonzugen vorliegen.

Die GrundflacheG sei durch eine Menge vonK zweidimensionalen Vektoren

G≡ {~v1,~v2,~v3, . . . ,~vK−1,~vK}

definiert, welche einen geschlossenen Polygonzug darstellen. Die einzelnenK Seiten

S≡ {s1,2,s2,3, . . . ,sK−1,K,sK,1}

1. Marz 2010


des geschlossenen Polygons sind gegeben durch Gerade

si, j = {~x |~x =~vi +α(~v j −~vi), α ∈ R},

wobei oben genannte Punktmenge die Schnittpunkte aller Geraden ist; d.h.,~vi = si−1,i ∩ si,i+1

(imodK).

Als weitere Forderung an die Position der Objekte wollen wirstellen, daß sie sich uberhauptin der Grundflache befinden. Dies kann man zum Beispiel erreichen, indem man eine Bewer-tungsfunktionB einfuhrt, die verschwindet, falls ein Objekt außerhalb der Grundflache liegt;d.h.,

B(X)

6= 0 wennxi ∈ G fur allexi , i = 1, . . . ,N

= 0 sonst

Schreiben Sie ein PackageGenet2D.m mit folgender Eigenschaft:

N Objekte sollen nun auf einer vorgegebenen GrundflacheG so angeordnet werden, daß diesel-ben in moglichst großem Abstand zueinander und zur Flachenbegrenzung liegen. Als Bewer-tungsfunktionB(X) kann hier die Summe der Euklid’schen Abstande von jeweils zwei Objektenzueinander und die jeweils kleinsten Entfernung zur Flachengrenze dienen; d.h.,

B(X) =N

∑i=1

∑j<i

|~xi −~x j |+N

∑k=1

minsi, j∈S

dist(xk,si, j).

1. Marz 2010

Seite 32

C Package.m - Ubersicht

Kategorie Package.m Punkte

0 Riemann 10

1 One-liners 4x5

1 Queens.m 20

2 ChaosGame.m 10

2 Logistic.m 20

2 DetChaos.m 30

2 Koch.m 10

2 MidPoint.m 20

2 Fractals.m 35

3 Nachbar.m 20

3 Quasi1d.m 20

3 Perkolation.m 20

3 Renorm.m 20

3 Ising.m 20

4 Genet3D.m 25

4 Genet2D.m 20

Tabelle C.1: Maximale Punkteanzahl fur jedesPackage.m .


Documents

260.169 UE Ubungen zu¨ Einfuhrung in das funktionale¨ und ...cms.mpi.univie.ac.at/mitten/angaben.pdf · 4. UBUNGSZEITEN¨ Seite 5 4 Ubungszeiten¨ Die Ubungen ﬁnden im¨ Computerpraktikum