-i
erreichen (z.B. python -i meinSkript.py
). In PyCharm können Sie Ihren Code markieren Ctrl+A
und dann per „Execute Selection in Console“ in die interaktive Konsole laden.[15 Punkte]
Als erstes definieren wir die Mengenklasse selbst (selbstverständlich ohne die Standardklasse set
aus Python zu verwenden!).
Set
(Python unterscheidet Groß- und Kleinschreibung; daher können wir die so nennen). Ihr Konstruktor soll dabei eine Liste von beliebigen Python-Objekten als Argument enthalten, die die (unterschiedlichen!) Elemente der Menge enthalten. Speichern Sie diese Liste intern ab.__str__(self)
, die (grundsätzlich für Python-Objekte) eine Repräsentation als Zeichenkette (String) zu einem Objekt der Klasse ausgeben soll. Verwenden Sie dabei die übliche Mengennotation (z.B. \(\{a,b,c\}\)), wobei die leere Menge durch ein gesondertes Symbol (üblicherweise \(\emptyset\)) gekennzeichnet wird. Durch Sie können Sie ihre Menge einfach ausgeben lassen, wie etwa mit: A = Set(["hund","katze","maus"])
print(A)
# {hund, katze, maus}
union(A,B)
oder alternativ __add__
oder __or__
(Vereinigung \(A \cup B\)),intersect(A,B)
oder __and__
(Schnitt \(A\cap B\)),complement(A,B)
oder alternativ __sub__
(Komplement \(A\setminus B\)). Achten Sie dabei darauf, dass jedes Element nur einmal in einer Menge enthalten sein darf.subset(self,auswahl)
, die, basierend auf der aktuellen Mengeninstanz, mithilfe einer gegebenen Auswahlfunktion eine Teilmenge auswählt. In mathematischer Notation würde man hierfür \[\texttt{A.subset(f)} = \{a\in A\, |\, \texttt{auswahl(a) ist wahr}\}\] schreiben.true
bzw. false
zurückgibt. A = Set(["hund","katze","maus"])
# Lambda-Kalkül: Teilmenge aller Wörter mit vier Buchstaben
print(A.subset(lambda x: len(x)==4))
# "normal" definierte Funktion: Teilmenge aller Wörter, die ein 'a' enthalten
def mitA(s):
return "a" in s
print(A.subset(mitA))
__iter__(self)
),e
in Ihrer Menge enthalten ist (__contains__(self,e)
),__len__(self)
)__getitem__(self,i)
).
A = Set(["hund","katze","maus"])
# subset
print(A.subset(lambda x: len(x)==4))
# __iter__
for i in A:
print(i)
# __contains__
if "hund" in A:
print("wau")
# __len__
print(len(A))
# _getitem_
print(A[2])
[15 Punkte]
Wir benutzen unsere neue Mengenklasse nun, um einige Anwendungen zu realisieren. Wir beginnen mit einem eher abstrakten Gedankenspiel:
powerset(self)
). Das Ergebnis dieser Methode sollte dabei selbst auch eine Instanz von Set
sein, d.h. die Ausgabe und die restlichen definierten Methoden sollten auch auf der Potenzmenge funktionieren. **
-Operator überladen (__pow__(a,b)
). binomialCoefficients(num)
, die alle Zahlen \(\binom{n}{k}, 0\le k\le n\), ausgibt und verwenden Sie zur Berechnung das Ergebnis der soeben definierte Methode zur Bestimmung der Potenzmenge. [10 Punkte]
Mengen definieren keine Ordnung ihrer Elemente. Um Anordnungen von Elementen, bei denen jede Position eine andere Semantik hat, zu konstruieren, benötigen wir das Konzept des kartesischen Produktes (Menge aller Paare zweier Mengen):
\[A \times B:= \left\{ (a, b) \mid a \in A, b \in B \right\}\]subset
-Funktion. a = (1,2)
)product(self,otherSet)
hinzu, um kartesische Produkte bequem erstellen zu können. *
-Operator überladen (__mul__(a,b)
)....schauen wir uns Funktionen und Relationen an. Diese kann man rein mit Hilfe von Mengen konstruieren, und das möchten wir hier machen. Dabei ist es grundsätzlich möglich, Funktionen durch Relationen auszudrücken und umgekehrt.
Aufgrund des Umfangs des Aufgabenblattes und da wir später nochmals auf Relationen zurückgreifen werden, haben wir den Teil mit den Funktionen gestrichen.CartesianProduct
zu definieren (sofern Sie eine erstellt haben).subset
-Methode auch angibt, wann ein Element Teil der Struktur ist und wann nicht. call
-Operator. Sie können dies erreichen, indem Sie eine Methode __call__(self,a)
anfügen, die zu jedem \(a\) das entsprechende \(b\) zurückgibt. Die Funktion können Sie dann wie gewöhnliche Python-Methoden auch aufrufen.
A = Set(["hund","katze","maus"])
F = ...
# Aufruf (als Werte sind jedoch nur Elemente aus A erlaubt!)
F(A[1])
Set
erbt, können Sie die Funktion selbst als Menge ausgeben lassen.A
auf die andere Menge B
abbilden? [20 Punkte]
Relationen sind Verallgemeinerungen von Funktionen (bzw. Funktionen sind spezielle Relationen). Eine Funktion ordnet jedem Element einer Definitionsmenge \(A\) ein Element der Wertemenge \(B\) zu. Relationen verallgemeinern dies: Wir können jedem Element aus der Definitionsmenge beliebig viele Elemente der Wertemenge zuordnen (weiterhin kann jedes Element von \(A\) auch vielen verschiedenen Elementen aus \(B\) zugeordnet werden). Anders gesagt: Wir merken uns lediglich für jedes Paar \((a,b), a \in A, b \in B\), ob es in der Relation enthalten ist oder nicht. Relationen sind also Strukturen, die auf dem kartesischen Produkt zweier Mengen agieren (etwa \(A\times B\)).
Wie der Name schon sagt, bringen Sie die Elemente dieser beiden Mengen zu einander in „Relation“:
Die Mengenrelation zwischen den Mengen \(A\) und \(B\) legt für alle Paare \((a,b)\) fest, ob die Elementrelation zwischen Elementen \(a\) und \(b\) entweder besteht oder nicht besteht. Man kann eine Relation also als Teilmenge des kartesischen Produktes definieren, \(R \subseteq A \times B\).
Alternativ kann man dies auch als Funktion \(R: A \times B \rightarrow \{0,1\}\) beschreiben.
Warum ist das so? Erklären Sie dies in der Vorstellung Ihrer Lösung!
(Ganz nebenbei: Durch rekursive Anwendung des kartesischen Produktes, \(A\times (B\times C)\), können auch Relationen auf mehr als zwei Mengen definiert werden; hier schauen wir uns aber nur Relationen zwischen zwei Mengen an.)
Beispiel (einfache Relationen): Sei \(A\) die Menge der in Mainz wohnenden Studenten und \(B\) die Menge der aus Wiesbaden anreisenden Studenten. Wir sagen \(a\in A\) und \(b\in B\) stehen genau dann zu einander in Relation, wenn sie sich kennen.
Relationen helfen uns dabei, komplexere Strukturen zu definieren. Hierzu hat man in der Mathematik Relationen charakterisiert, die in vielen Anwendungen immer wieder auftauchen. Interessant sind dabei oft homogene Relationen \(R\) auf \(A^2 = A\times A\):
Äquivalenzrelation: Ein wichtiges Konzept ist das einer Äquivalenzrelation. Hiermit definieren wir einen vergröberten Gleichheitsoperator „\(=\)“ (auch gerne als „\(\equiv\)“ geschrieben), der die folgenden Eigenschaften erfüllt:
Erfüllt eine Relation diese drei Eigenschaften spricht man von einer Äquivalenzrelation.
Das besondere dabei ist, dass man alle Elemente der Grundmenge so in Teilmengen aufteilen kann, dass alle Elemente jeweils in Relation zu einander stehen, jedoch nicht zu den Elementen der anderen Mengen. Diese Mengen nennen wir (Äquivalenz-)Klassen.
Da die Äquivalenzrelation die Klassenelemente eindeutig zuordnet, stellt man eine Klasse häufig (um Schreibarbeit zu sparen) nur durch einen einzigen (beliebigen, aber eindeutig bestimmten) Repräsentanten dar (siehe Beispiel).
Restklassen werden als Beispiel für Äquivalenzklassen in der nächsten Aufgabe an einem konkreten Beispiel erklärt.
In Programmiersprachen, in denen man Gleichheitsoperatoren selbst definieren kann (wie z.B. Python oder C++) geht man fast immer implizit davon aus, dass diese die Eigenschaften einer Äquivalenzrelation haben. So gehören in Python z.B. alle Integer-Zahlen, die den gleichen Wert kodieren, zur gleichen Äquivalenzklasse, auch wenn es sich um verschiedene Objekte handelt, die an unterschiedlichen Speicherstellen liegen. Das heißt, diese „umdefinierte“ Gleichheit vergröbert die Gleichheit, die nur die Objektidentitäten überprüft.
Algorithmische Umsetzung des Findens von Äquivalenzklassen: Programmatisch würde man so vorgehen, dass man mit einem Element startet und es als neue Klasse definiert. Für alle neuen Elemente der Basismenge \(A\) prüft man nun, ob das Element mit dem ersten(!, beliebig aber festen) Element einer der existierenden Klassen in Relation steht. (Warum reicht es aus nur ein Element der Klasse mit dem neuen Element auf Relation zu prüfen?) Falls ja, fügt man das Element der Klasse an, falls es keine passende Klasse gibt, bildet das Element eine neue Klasse.
Ordnungsrelationen auf Mengen (Verallgemeinerung von \(\le\)): Die natürlichen Zahlen sind geordnet, d.h. zu jedem Paar von Zahlen kann man sagen welche Zahl größer (oder gleich) ist. Ordnungsrelationen sind eine (abstrakte) Klasse von Relationen, die einer (bislang ungeordneten) Menge \(A\) eine Reihenfolge gibt. Eine abstrakte Ordnungsrelation muss immer folgende Eigenschaften erfüllen:
Beispiel Beziehungen: Auf der Menge der Personen \(\{\text{Alice},\text{Bob},\text{Charles},\text{Denise}, \text{Eric}\}\) definieren wir eine Relation: X mag Y. (Überlegen Sie sich an dieser Stelle, wer wen mag).
Beispiel Ordnungen: Sei \(N\) eine Menge von Zahlen. Wir definieren die Relation durch \((a,b) \in R_1 \Leftrightarrow a\le b\). Für dieselbe Menge definieren wir zwei weitere Relationen durch \((a,b) \in R_2 \Leftrightarrow a < b\) und \((a,b) \in R_3 \Leftrightarrow a = b\).
Beispiel Restklassen: Sei \(N\) eine Menge von Zahlen und \(m \in N\) eine Zahl (z.B. 5). Wir definieren die Relation durch \((a,b) \in R_1 \Leftrightarrow a - b \text{ ganzzahlig Teilbar durch } m\). Als Repräsentant \(r\) der Restklasse wählen wir stets die kleinste Zahl der Klasse und schreiben die Klasse dann als \([r]\).
subset
-Methode, die das Relations-Objekt von der Set
-Klasse erbt) und prüfen Sie diese darauf, ob es sich um Äquivalenzrelationen handelt.[10 Punkte]
Nun können wir uns endlich dem widmen, was wir zu Beginn versprochen haben — der Implementierung der Kongruenzrechnung, basierend auf der von uns implementierten Arithmetik.
Der Restklassenring \(\mathbb{Z}/n\mathbb{Z}\) ist eine Menge mit einer besonderen mathematische Struktur, deren Elemente nämlich wieder Mengen sind (hier genannt Klassen). Ziel dieser mathematischen Struktur ist es, die üblichen Rechenoperationen \(+\), \(-\), \(\cdot\) so zu definieren, dass das Ergebnis immer zwischen \(0\) und \(n-1\) liegt, aber sonst die üblichen Regeln gelten (z.B. Klammersetzung, Vertauschen von Summanden und Faktoren, ...).
In der Mathematik wünscht man sich in sich abgeschlossene Strukturen (Gruppen, Ringe, Körper). Abgeschlossen bedeutet, dass das Ergebnis der ausgezeichnete Operationen stets wieder ein Element der Struktur ist. Das Problem an den üblichen Rechenoperationen auf den ganzen Zahlen ist, dass das Ergebnis von etwa \(a+b\) nicht mehr unbedingt zwischen \(0\) und \(n-1\) liegt, z.B. für \(a=3\), \(b=4\) und \(n=6\) ist \(a+b=7\). Wir können die ganzen Zahlen und ihre Rechenoperationen also nicht direkt verwenden, sondern müssen noch ein wenig zusätzlich arbeiten.
Der Restklassenring umgeht dies, indem die Elemente der Struktur in Wirklichkeit selbst eine Menge ist, die jedoch nach ihrem kleinsten Element benannt wird. Als Beispiel sind die Elemente von \(\mathbb{Z}/5\mathbb{Z}\): \[
\begin{aligned}
\overline{0} &:= \{ 0, 5, 10, 15, 20, \dots \}\\
\overline{1} &:= \{ 1, 6, 11, 16, 21, \dots \}\\
\overline{2} &:= \{ 2, 7, 12, 17, 22, \dots \}\\
\overline{3} &:= \{ 3, 8, 13, 18, 23, \dots \}\\
\overline{4} &:= \{ 4, 9, 14, 19, 24, \dots \}
\end{aligned}
\] Die Symbole mit einem Strich \(\overline{a}\) sind dabei nur Namen für die Menge. (Manchmal schreibt man statt \(\overline{\cdot}\) auch \([\cdot]\).) Wir hätten stattdessen auch andere Namen (a.k.a Repräsentanten) für die Mengen, etwa \[
\begin{aligned}
\overline{5} &:= \{ 0, 5, 10, 15, 20, \dots \}\\
\overline{16} &:= \{ 1, 6, 11, 16, 21, \dots \}\\
\overline{22} &:= \{ 2, 7, 12, 17, 22, \dots \}\\
\overline{3} &:= \{ 3, 8, 13, 18, 23, \dots \}\\
\overline{9} &:= \{ 4, 9, 14, 19, 24, \dots \},
\end{aligned}
\] wählen können. Grund hierfür ist die Eindeutigkeit der Mengen unter der Relation \[
a \text{ ist in Relation zu } b \Leftrightarrow a - b = k\cdot n, \text{ für ein beliebiges } k
\] wobei \(n\) für die Relation fest ist. (Im Beispiel eben wäre \(n=5\)).
Übrigens ist dies dieselbe Relation, wie das dritte Beispiel aus der vorhergehenden Aufgabe.
Die Eigenschaft in welcher Klasse ein Element ist bleibt konsistent (wohldefiniert) unter den Operationen \(+\) und \(\cdot\), wenn wir erst die herkömmlichen Additions- und Multiplikationsoperationen auf beliebige Repräsentanten anwenden und dann wieder einen Repräsentanten wählen: \[ \begin{aligned} \left[ a \right] + [ b ] &:= [ a + b ]\\ [ a ] \cdot [ b ] &:= [ a \cdot b ]. \end{aligned} \] Dies liegt an der folgenden leicht zu zeigenden Eigenschaft:
Sei \([a_1] = [b_1]\) und \([a_2] = [b_2]\), dann gilt \[ \begin{aligned} \left[ a_1 + a_2 \right] &= [ b_1 + b_2 ],\quad \text{ und }\\ [ a_1 \cdot a_2 ] &= [ b_1 \cdot b_2 ]. \end{aligned} \]
Um dies noch einmal Zusammenzufassen:
Dieses mathematische Konstrukt ist in der Lage Multiplikationen und Additionen durchzuführen und dabei „automatisch“ das Ergebnis „modulo \(n\)“ zu rechnen. Wir erreichen dies, indem wir zwei ganze Zahlen, die sich um ein Vielfaches von \(n\) unterscheiden (also \(a\) und \(b\) mit \(a - b = k \cdot n\) für eine ganze Zahl \(k \in \mathbb{Z}\)), mit einander identifizieren, also als „äquivalent“ betrachten.
Nun zur eigentlichen Aufgabe:
add
und mult
, welche die Summe bzw. das Produkt zweier Äquivalenzklassen im Sinne dieser Arithmetik bestimmen.Hinweis: Um besser mit den Äquivalenzklassen arbeiten zu können, empfehlen wir Ihnen eine neue Klasse zu erstellen (z.B. EquivalenceClass
), die von Set
erbt und lediglich die __str__
-Methode überschreibt, um nur einen Repräsentanten auszugeben statt der ganzen Menge.
Sofern Sie möchten können sie auch eine statische Variable einführen, die die Ausgabe steuert, um bei Bedarf doch alle Elemente zu inspizieren.
Abbildung 3.1: Verschiedene Zoom-Stufen des „Apfelmännchens“. (In den beiden Reihen sind jeweils andere Colorschemes in Verwendung.)
In dieser Aufgabe wollen wir das berühmte „Apfelmännchen“ implementieren.
Dies ist ein Beispiel dafür, wie mit wenigen, sehr einfachen arithmetischen Operationen eine sehr vielfältige und komplexe Struktur entstehen kann. Man nennt dieses Phänomen im Allgemeinen Fall emergente Komplexität — es ist nicht nötig besonders komplexe Regeln zu definieren, um mit diesen sehr komplexe Resultate zu erhalten. Die Turing-mächtige Maschine ist der Extremfall — sie ist universell und kann, mit einem geeigneten Programm, alles erzeugen.
Mandelbrotmengen sind keine Turing-Maschinen; dennoch entsteht eine sehr interessante Struktur aus einer harmlos und simpel erscheinenden Rechenvorschrift.
Bevor wir uns der Mandelbrotmenge selbst widmen, sollen an dieser Stelle nochmals die komplexen Zahlen wiederholt werden.
Die komplexen Zahlen sind die Menge \[\mathbb{C} := \mathbb{R} + i\cdot \mathbb{R} := \{a+ib \,|\, a,b\in \mathbb{R}\},\] die mit der folgenden Struktur versehen sind: Eine komplexe Zahl \(z = a+ib\) besteht damit aus zwei reellen Zahlen \(a,b\) und der imaginären Einheit \(i\), die die Eigenschaft \(i^2=-1\) besitzt. Aus dieser Eigenschaft und der herkömmlichen Multiplikation und Addition auf reellen Zahlen folgen die Rechenregeln: \[\begin{aligned}
\text{Addition:}\quad &(a+ib)+(c+id) &= \quad &\, (a+c) + i(b+d)\\
\text{Multiplikation:}\quad &(a+ib)\cdot(c+id) &= \quad &\, (ac-bd) + i(bc+ad)\\
\text{Absolutbetrag (entspr. Länge im } \mathbb{R}^2\text{):} \quad &|(a+ib)| &= \quad &\, \sqrt{a^2 + b^2}
\end{aligned}\] Komplexe Zahlen sind glücklicherweise bereits fest in Python und Numpy implementiert. Es unterscheidet sich lediglich das Symbol der komplexen Einheit \(i\): Für Python ist diese nämlich durch j
gekennzeichnet.
Wir beginnen mit einer beliebigen komplexen Zahl \(c\in \mathbb{C}\) und definieren die Folge
\[\begin{aligned} z_0 &= 0\\ z_{n+1} &= z_n^2 + c, \quad \text{ für } n\ge 0. \end{aligned}\]Die Mandelbrotmenge \(M\) ist die Menge, für die der Absolutbetrag dieser Folge nach oben hin beschränkt ist, mathematisch ausgedrückt:
\[c \in M \Leftrightarrow \limsup_{n\rightarrow \infty} |z_n| \le 2. \][30 Punkte]
Nun werden wir die Mandelbrotmenge darstellen.
Wichtig: An dieser Stelle der Hinweis, dass die Berechnung der Darstellung mit reinem Python nur langsam von statten gehen würde.
Daher sind die Aufgaben so formuliert, dass Sie Numpy verwenden sollten, damit die „Interaktion“ noch Sinn macht. Andernfalls macht der Teil mit dem „Zoomen“ wenig Spaß.
Hinweis: Verwenden Sie dennoch eine geringere Auflösung, damit die Berechnungen noch schneller sind.
MousePressEvent
verwenden. (Siehe Skript: e.X(),e.Y()
liefert Ihnen die Koordinaten in Ihrem selbstdefinierten Gitter. # importieren Sie zu Beginn Ihres Codes das Matplotlib-Paket
import matplotlib.pyplot as plt
# ... in ihrer update- bzw. draw-Methode ...
# Normalisieren von count (Werte zwischen 0 und 1)
max = np.max(count)
min = np.min(count)
if max==0:
max = 1
count = (count - min) / max
# für große n können die Farbübergänge zu stark sein. Dies kann z.B. mit
# count = count**0.25
# umgewichtet werden
# Farbschema anwenden
# (eine Auswahl finden Sie unter: http://matplotlib.org/users/colormaps.html )
colormap = plt.cm.RdYlBu # z.B. in Ihrer GUI Auswählbar
colfloat = colormap(count)
# Qt erwartet Werte zwischen 0 und 255 für RGB-Bilder
colint = np.asarray(colfloat*255, dtype=np.uint8)
# Konvertieren in ein QImage & Anzeigen
img = QImage(colint.data, self.width, self.height, QImage.Format_RGBA8888)
pixmap = QPixmap.fromImage(img)
self.display.setPixmap(pixmap)