@mutetella: Ich glaube, ich habe dich mit zu vielen unterschiedlichen Konzepten auf einmal zugeschüttet, ohne wirklich zu erklären, wie eines auf dem anderen aufbaut, und was unten und was oben ist. Ich versuche es nochmal anders und fange ganz von vorne an, wobei ich der Vollständigkeit halber auch Sachen beschreiben werde, die du schon kennst.
Beim Lesen solltest du immer im Hinterkopf behalten, was John v. Neumann einem Studenten sagte, der sich beklagte, weil er etwas nicht verstand: "Junger Mann, man versteht die Sachen in der Mathematik nicht, man gewöhnt sich nur an sie". Tatsächlich ist das u.s. bloß der Aufbau einer Struktur aus Begriffen bzw. Konzepten, mit denen man über mathematische Gegenstände sprechen kann, aber keine komplizierten Formeln oder Berechnungen.
Die angesprochen Konzepte stammen aus der
abstrakten Algebra. Der typische Mathematikunterricht in der Schule benutzt zwar deren Konzepte, aber nur zur Darstellung im Rahmen dessen, was er tatsächlich ist: Rechenunterricht. Abstrakte Algebra beschreibt die
Strukturen, innerhalb derer man rechnen kann, und zwar auf so allgemeine Weise, dass es den Schulunterricht sprengen würde. Man kann zB. eine Algebra für reguläre Ausdrücke angeben, und völlig zu Recht das Zerlegen von Strings mittels regulärer Ausdrücke "Rechnen" nennen. Im Englischen ist das viel offensichtlicher, denn das englische Wort für Rechnen ist Computing. Das ist das, was Programmierer ihre "Rechner" tun lassen. Die Konzepte der abstrakten Algebra gehören deswegen zum Fundament der theoretischen Informatik, und alle anderen Bereiche wie Zahlentheorie, Berechenbarkeitstheorie, Automatentheorie usw. lassen sich algebraisch darstellen.
Das grundlegendste Konzept ist das der
Menge. Eine Menge ist eine ungeordnete Ansammlung von beliebig vielen "Dingen", wobei jedes einzelne Ding höchstens einmal in einer Menge vorkommt. Sie werden durch Aufzählung in geschweiften Klammern dargestellt, zB. {Adam, Eva}, {Tick, Trick, Track}, {2, 3, 5, 7}.
Ungeordnet bedeutet einfach, dass die Reihenfolge der Aufzählung keine Rolle spielt. Die Menge {Adam, Eva} ist dieselbe, wie die Menge {Eva, Adam}.
Mengen kann man Namen geben, zB. Z, die Menge aller ganzen Zahlen, oder Q, die Menge aller rationalen Zahlen, oder Str, die Menge aller Strings, usw.
Die Dinge in einer Menge nennt man
Elemente. Wenn ein Element x in einer Menge M enthalten ist, dann schreibt man oft auch kurz: "x ist in M", oder "x in M".
Man kann Mengen auch durch die sog.
Komprehension darstellen: {x | x in Z, x > 5}, d.i. alle ganzen Zahlen größer als 5, oder {x | x war mit Henry VIII. verheiratet}, was dieselbe Menge ist wie {Katharina von Aragón, Anne Boleyn, Jane Seymour, Anna von Kleve, Catherine Howard, Catherine Parr}, oder {(x, y) | x in Z, y in Str} was bedeutet: die Menge aller geordneten Paare mit einer ganzen Zahl an erster und einem String an zweiter Stelle: (1, 'Brezel'), (7, 'sieben'), (123, 'Garmisch-Partenkirchen'), ... Die Komprehension sollte einem Pythonista bekannt vorkommen, wg. List Comprehensions, und ab Python 2.7 gibt es sogar Set Comprehensions: {x for x in some_numbers if x > 5}. Das ist praktisch eine 1:1-Übersetzung des ersten Beispiels.
Das | spricht man gewöhnlich aus als "wobei" oder "so dass". Es wird weiter unten in anderem Kontext wieder auftauchen.
Das nächste Konzept ist das der
Funktion. Eine Funktion ist eine eindeutige Zuordnung zwischen den Elementen von Mengen. Angenommen die Mengen S={1, 2, 3, 4} und T={2, 4, 6, 8}, dann kann man zB. folgende Zuordnung wählen:
Man könnte auch statt dieser Tabelle eine Rechenregel verwenden:
Oder in Python-Syntax:
Code: Alles auswählen
def f(x):
if 1 <= x <= 4:
return x * 2
else:
raise ValueError('f is not defined for values smaller than 1 or greater than 4!')
Der wichtige Punkt ist, dass die Funktion, mathematisch gesehen, durch die Mengen und die Zuordnung zwischen den Elementen schon vollständig definiert ist.
Eindeutig bedeutet, dass jedem Wert der ersten Menge genau ein Wert der zweiten Menge zugeordnet wird. zB. kann die Anzahl der Kilometer des kürzesten Weges zwischen Köln und x nicht zwei oder mehr Zahlen sein, da entweder beide Wege gleich lang sind und deswegen dieselbe Anzahl an Kilometern besitzen, oder einer von beiden kürzer ist, so dass dieser auch eine geringere Anzahl von Kilometern hat, wodurch der andere eben kein kürzester Weg mehr wäre.
Es könnte jedoch zwei Orte A und B geben, die gleich weit von Köln entfernt sind. Dann wäre die Anzahl der Kilometer des kürzesten Weges von Köln nach A dieselbe, wie die von Köln nach B. Die Funktion wäre dann immer noch eindeutig, weil dafür ja nur gefordert wird, dass es keine zwei unterschiedlich langen kürzesten Wege gibt, die
beide von Köln nach A, oder
beide von Köln nach B gehen.
Eine andere Funktion wäre zB. g x: y | y ist mit x verheiratet. Wenn Anton mit Emily, Bernd mit Franziska und Christian mit Dorothea verheiratet ist, dann könnte man das in Python so formulieren:
Code: Alles auswählen
married_with = {
'Anton': 'Emily',
'Bernd': 'Franziska',
'Christian': 'Dorothea'
}
g = married_with.__getitem__
assert g('Bernd') == 'Franziska'
Man würde wohl einen besseren Namen als
g verwenden, zB.
wife_of, aber mathematisch gesehen wäre es immer noch dieselbe Funktion, weil zwei Funktionen genau dann gleich sind, wenn sie dieselben Zuordnungen vornehmen. Diese Zuordnungen lassen sich auch als Wertepaare darstellen, zB. in Pyhon:
Code: Alles auswählen
assert set((('Anton', 'Emily'), ('Bernd', 'Franziska'), ('Christian', 'Dorothea'))) == set(married_with.items())
Die Definitionsmenge (engl. Domain) einer Funktion ist die Menge der ersten Elemente der Wertepaare, die Wertemenge (engl. Codomain) ist die Menge zweiten Elemente. In Python:
Code: Alles auswählen
domain = set([x for x, y in married_with.items()])
codomain = set([y for x, y in married_with.items()])
#oder:
domain = set(married_with.keys())
codomain = set(married_with.values())
assert domain == set(('Anton', 'Bernd', 'Christian'))
assert codomain == set(('Dorothea', 'Emily', 'Franziska'))
Funktionen können auch mehr als ein Argument haben, zB.
f(x, y): der Abstand zwischen x und y, oder
g(a, b, c): das Dreieck mit den Koordinaten a, b und c, oder
h(n, x): die in höchstens n Schritten erreichbaren Straßen von da aus gezählt, wo x wohnt.
Funktionen besitzen eine sog.
Signatur. Das ist ein Ausdruck, der beschreibt, welche Mengen bei der Zuordnung involviert sind. zB. hat eine Funktion, die eine ganze Zahl einer anderen zuordnet, wie
f x: x * 2, die Signatur Z --> Z. Die Funktion wife_of oben hat die Signatur Man --> Woman, oder Husband --> Wife. Die Funktion mit den Dreieckskoordinaten oben hätte die Signatur Coor x Coor x Coor --> Triangle, wobei Coor die Menge der Koordinaten, Triangle die Menge der Dreiecke und x das Kreuzprodukt ist.
Endofunktionen sind Funktionen, bei denen alle Argumente und auch der Wert, der ihnen durch die Funktion zugeordnet wird, Elemente derselben Menge sind. Ihre Signatur ist dann T^n --> T für die Menge T über der sie Endofunktionen sind. Das caret soll "hoch" heißen, wie in 3² == 9. T³ --> T ist dann dasselbe wie T x T x T --> T.
Man sagt übrigens meist "für ... nimmt die Funktion den Wert --- an" oder "... wird abgebildet auf ---" statt "... wird --- zugeordnet".
Das nächte Konzept ist das einer
Algebra. Das ist eine Struktur mit bestimmten Eigenschaften. Sie besteht aus einer Menge M von Elementen (Zahlen, Strings, ...) und wenigstens einer 2-stelligen
Operation. Operation ist in diesem Kontext nur ein anderes Wort für Endofunktion. Diese erzeugt also aus je zwei Elementen der Menge wieder ein drittes derselben, dh. sie hat die Signatur M² --> M. zB:
Code: Alles auswählen
3 + 4 == 7
2 * 5 == 10
'hallo' + 'welt' == 'hallowelt'
[1, 2] + [3, 4] == [1, 2, 3, 4]
set([1, 2, 3]) | set([3, 4, 5]) == set([1, 2, 3, 4, 5])
Diese Beispiele sollen im Speziellen etwas verdeutlichen, was im Allgemeinen gilt. Eine Algebra besteht nicht aus genau den Zahlen 3 und 4 und der Addition, oder den Strings 'hallo' und 'welt' und der Konkatenation, sondern aus
allen ganzen Zahlen mit der Addition und
allen Strings mit der Konkatenation. Die konkreten Beispiele sollen nur das allgemeine Schema anhand eines Einzelfalles illustrieren.
Eine Algebra stellt man üblicherweise durch Aufzählung in spitzen Klammern dar. Erst kommt die Menge der Elemente, um die es geht, die sog.
Trägermenge, und danach Operationen und Konstanten:
<M, op1, op2, ..., k1, k2, ...>. Diese Form der Darstellung nennt man die
Signatur einer Algebra.
Die einfachste Form einer Algebra nennt man
Magma: zB. <Z, ->, das sind die ganzen Zahlen zusammen mit der Subtraktion, oder <Q\0, />, das sind die Rationalen Zahlen ohne 0 zusammen mit der Division.
Ein Magma, dessen Operation
assoziativ ist, nennt man
Halbgruppe. Angenommen eine Menge M und eine Operation ° über deren Elementen, also eine Algebra mit der Signatur <M, °>. Dann bedeutet "assoziativ", dass für alle Elemente a, b und c in M gilt, dass (a ° b) ° c == a ° (b ° c) ist. Für die Algebren aus dem letzten Absatz gilt das offensichtlich nicht, da zB. (7 - 5) - 2 != 7 - (5 - 2) und (12.4 / 3.1) / 2.0 != 12.4 / (3.1 / 2.0) ist. Ein Beispiel für eine Halbgruppe wäre die Menge aller nicht-leeren Strings
NLStr und die Konkatenation +: <NLStr, +>, weil die Konkatenation assoziativ ist:
Code: Alles auswählen
('ich' + 'mach') + 'brotzeit' == 'ich' + ('mach' + 'brotzeit')
'ichmach' + 'brotzeit' == 'ich' + 'machbrotzeit'
'ichmachbrotzeit' == 'ichmachbrotzeit'
Wenn die Trägermenge einer Halbgruppe ein
Identitätselement bezüglich der Operation enthält, dann erhält man ein
Monoid. Das Identitätselement ist das Element der Trägermenge, dass sich in Bezug auf die Operation
neutral verhält. Die allgemeine Signatur hat dann die Form <M, °, I>, wobei M die Trägermenge, ° die Operation und I das Identitätselement ist. Beispielsweise <N, +, 0>, d.i. die Menge der natürlichen Zahlen, zusammen mit der Addition und der 0, oder <N\0, *, 1>, also die natürlichen Zahlen ohne 0 zusammen mit der Multiplikation und der 1, oder <Str, +, ''>, d.h. Strings zusammen mit der Konkatenation und dem Leerstring. Oder, sofern 1-Endo-T die Menge der 1-stelligen Endofunktionen über der Menge T, * die Funktionskomposition und
identity(x): x | x in T die Identitätsfunktion ist, <1-Endo-T, *, identity>. Das war das Beispiel aus meinem anderen Artikel, wo ich einen Decorator zur Funktionskomposition gezeigt hatte. Funktionskomposition hört sich kompliziert an, ist aber tatsächlich sehr einfach. Wenn man lauter 1-stellige Endofunktionen hat, dann kann man entweder so rechnen:
Oder einfacher:
Bei der Funktionskomposition "kettet" nun man einfach Funktionen aneinander:
f * g * h bedeutet also einfach: wende erst f auf einen Wert an, wende auf dessen Ergebnis g an und auf dessen Ergebnis wiederum h. Das funktioniert, weil die Werte, die jede dieser Funktionen annehmen kann, alles Elemente derselben Menge sind. Generell kann man zwei Funktionen komponieren, wenn die Wertemenge der ersten Funktion gleich der Definitionsmenge der zweiten ist, zB. in Python
chr und
str.lower, das erste wandelt eine Zahl in einen String um, und das zweite einen String in Kleinbuchstaben, also wieder einen String. zB. chr(70) == 'F' und str.lower('F') == 'f'. Also ist (chr * str.lower)(70) == 'f'.
Was aber, wenn das nicht der Fall ist? Wenn man zB. eine Menge von Funktionen hat, die alle dieselben Definitions- und Wertemengen haben, aber diese nicht kompatibel zueinander sind? Also zB. wenn alle die Signatur Z --> (Z, Str) haben, dh. wenn jede dieser Funktionen eine ganze Zahl auf eine ganze Zahl und einen String abbildet? Kann man dann etwas der Funktionskomposition vergleichbares trotzdem konstruieren?
Das bringt uns zum nachsten Konzept, der
Monade. Diese stammt nicht aus der abstrakten Algebra, sondern aus der
Kategorientheorie, auf die ich nicht weiter eingehen werde, weil ich selber gerade erst angefangen habe, das zu lernen.
Tatsächlich möchte ich hier auch die Monaden nicht nochmal erklären, weil es schon spät ist. Sobald dir die hier beschriebenen Konzepte klar sind, wirst du auch die Erklärung der Monaden aus meinem vorhergehenden Posting verstehen.
Ich möchte nur noch erwähnen, dass es in der abstrakten Algebra noch weitere Arten von Strukturen gibt. Für Informatiker interessant sind zB.
Verbände und
Scott-Domains. Letztere verwendet man, um die Semantik von Programmiersprachen zu beschreiben. Für's tägliche Programmiergeschäft braucht man sie aber nicht.
In specifications, Murphy's Law supersedes Ohm's.
)
