Frank Fischer · Institut für Informatik · frank.fischer@uni-mainz.de

Angewandte Mathematik am Rechner 1SOMMERSEMESTER 2018

Kapitel 4

Algebra

WiederholungKapitel 3

Funktionen

InformatikAlgorithmus / Berechnung

Mathematik„Wohldefinierte“ Zuordnung

Arithmetische Ausdrücke

Operator ∗

Operator +

Operator /

Operator ∗

“ ”3 ⋅ 𝑥 +4 ⋅ 𝑦

5

3 ⋅ 𝑥 +4 ⋅ 𝑦

5

3 𝑥

4 𝑦

5

Halteproblem

Unentscheidbar: Halteproblem

▪ Gegeben

▪ ein Algorithmus (z.B. Python Programm)

▪ und seine Eingabe (Eingabedaten)

▪ Frage

▪ Hält der Algorithmus jemals an?

▪ Also: Stürzt das Programm mit dieser Eingabe nicht ab?

WiderspruchWiderspruch

▪ Annahme: Haltetest(Algorithmus, Eingabe)

▪ Problemalg. mit Eingabe (Problemalg., Problemalg.)

Simulation

Simulation

Simulation

Simulationuniverselle TM

Simulation

Simulation

Ergänzungen Kapitel 3

Emergente Komplexität

Mandelbrot-

Menge

Iteration𝑧 → 𝑧2 + 𝑐𝑧, 𝑐 ∈ ℂ

Farbe = Zahl Iterationen bis Ergebnis > 2

re 𝑐 →

im𝑐

→

[Quelle: Wikipedia Contrib.„Simpsons contributor“]

Emergente Komplexität

Penrose Tilings

Prinzip

▪ Kacheln aneinanderfügen

▪ Gesamte 2D Ebene gefüllt

▪ Global aperiodisch(keine Wiederholungen)

Turing mächtig → Programmieren durch Design von (anderen) Kacheln

[WP contrib.Geometry Guy]

[WP contrib. Inductiveload]Bilder:Wikipedia

Emergente Komplexität

Conway‘s „Game of Life“

▪ Lebende Zellen mit <2 Nachbarn sterben

▪ Lebenden Zellen mit 2 oder 3 Nachbarn leben weiter

▪ Lebende Zellen mit >3 Nachbarn sterben

▪ Tote Zellen mit genau 3 Nachbarn werden zum Leben erweckt.

Das „Spiel“ ist Turing mächtigVideo: [Wikipedia user Kieff, CC-SA3]

Kapitel 4: Algebra

Algebra

Mathematische Sprache

▪ Ausdrücke als Bäume

▪ Allgemeine Typen (Boolsche Typen, Funktionen, etc.)

▪ Quantoren

Abstraktion

▪ Mathematische Strukturen

▪ Informatik: Polymorphie / generischer Code

Algebra

Mathematische Sprache

▪ Ausdrücke als Bäume

▪ Allgemeine Typen (Boolsche Typen, Funktionen, etc.)

▪ Quantoren

Arithmetische Ausdrücke

Operator ∗

Operator +

Operator /

Operator ∗

“ ”3 ⋅ 𝑥 +4 ⋅ 𝑦

5

3 ⋅ 𝑥 +4 ⋅ 𝑦

5

3 𝑥

4 𝑦

5

ℝ ℝ

Operator +

ℝ

ℝ ℝ

Operator ∗

ℝ

ℝ ℝ≠0

Operator /

ℝ

ℝ ℝ

Operator ∗

ℝ

Konstante 5

ℝ

Variable y

ℝ

Konstante 4

ℝ

Variable x

ℝ

Konstante 3

ℝ

Operatorenbaum, typisiert

Variable x Variable y

Ausgabe

ℝ ℝ

Operator +

ℝ

ℝ ℝ

Operator ∗

ℝ

ℝ ℝ≠0

Operator /

ℝ

ℝ ℝ

Operator ∗

ℝ

Konstante 5

ℝ

Variable y

ℝ

Konstante 4

ℝ

Variable x

ℝ

Konstante 3

ℝ

Operatorenbaum als Modul

Algebra

Mathematische Sprache

▪ Ausdrücke als Bäume

▪ Allgemeine Typen (Wahrheitswerte, Funktionen, etc.)

▪ Quantoren

Allgemeine Typen

Mathematische „Typen“ (Mengen)

▪ Wahrheitswerte

▪ Funktionen (→ higher-order functions)

▪ Mengen

▪ Generische / abstrakte Typen (mehr dazu später)

Beispiele

Beispiele

▪ Prädikat: 𝑎 ∈ ℕ ist eine gerade Zahl

▪ Aussage: Wenn 𝑎 ∈ ℕ gerade ist, ist (𝑎 + 1) ungerade

▪ Prädikat: 𝑎 ∈ ℕ ist eine Primzahl

Beispiele

Beispiele

▪ Prädikat: 𝑎 ∈ ℕ ist eine gerade Zahl

▪ Aussage: Wenn 𝑎 ∈ ℕ gerade ist, ist (𝑎 + 1) ungerade

▪ Prädikat: 𝑎 ∈ ℕ ist eine Primzahl

𝑎 mod 2 = 0

𝑎 mod 2 = 0 ⇒ 𝑎 + 1 mod 2 = 0

𝑝𝑟𝑖𝑚 𝑎 = ∀𝑏 = 2… 𝑎 − 1 : 𝑎 𝑚𝑜𝑑 𝑏 = 0

Algebra

Mathematische Sprache

▪ Ausdrücke als Bäume

▪ Allgemeine Typen (Wahrheitswerte, Funktionen, etc.)

▪ Quantoren

„Schleifen über Mengen“

Boolsche Quantoren

▪ ∀ – „für alle“

▪ ∃ – „es gibt ein“

Arithmetik

▪ ∑ – „Summe“

▪ ∏ – „Produkt“

Mengen

▪ ⋃ – „Vereinigung“

▪ ⋂ – „Summe“

Menge

Operator ∀boolescheFunktion

bool

Menge 𝑀

Menge

Parameter

∗

𝑀 ∗

Prädikat

bool

noch mehr…

∗

„und“ Verknüpfung

∀𝑚 ∈ 𝑀: 𝑝𝑟𝑒𝑑(𝑚)

„Schleifen über Mengen“

Quantoren / Summenzeichen / etc.

▪ Verknüpfung vieler Funktionsauswertungen

▪ Iteration über Mengen

▪ Unendliche Mengen erlaubt

▪ Nicht immer berechenbar

Menge

„Schleife“

Typ 2

Typ 1

Menge 𝑀

Menge

𝑀 Typ 3

Funktion

Typ 2

Umsetzung in Python/JAVA

Objektorientierte Umsetzung

▪ Funktionsobjekte: Baumknoten▪ Echte Funktionen (komposit)

▪ Konstanten (Blattknoten)

▪ Variablen (Rolle als Eingaben des ganzen Baumes)

▪ Typcheck▪ Kompositobjekte

▪ Quantoren (Iteration)▪ Binden Variablen im Unterbaum (Mechanismus)

▪ Funktionskonstruktion▪ Binden von Variablen

▪ Rekursion (Zyklen im Baum)

vorauss.nicht in der

Aufgabe

Abstrakte Algebra

Mathematische Polymorphie

Generische Definitionen, Sätze, Beweise

▪ Strukturelle Ähnlichkeiten (z.B. ℕ ↔ ℤ, ℝ ↔ ℤmod 𝑝)

▪ Theorie nicht immer wieder neu aufbauen

▪ Typparameter für Definitionen, Sätze Beweise

Generische Algorithmen

▪ Gleiche Algorithmen für ähnliche Typen

▪ Bespiel: Euklidischer Algorithmus

▪ ggT von zwei natürlichen Zahlen

▪ Genauso auf Polynome anwendbar

▪ Keine doppelte Arbeit…

Polymorphie

Informatik

▪ Wir kennen das Problem (zur Genüge!)

▪ Ähnliche Algorithmen für verschiedene Datenstrukturen

Lösung

▪ Typparameter

▪ Explizit: Generics, Templates, etc.„Parametrische Polymorphie“

▪ Implizit: Vererbung / virtuelle Methoden„Subtyping“

Mathematische Polymorphie

Mathematischer Typ

▪ „algebraische Struktur“

▪ Menge + Operationen (z.B.: ℤ,+ )

Abstrakter Datentyp

▪ Mengen (Menge von „Daten“) selbst egal

▪ Betrachte Operationen („Zugriffsfunktionen“)

Benennung essentieller Voraussetzungen

▪ Eigenschaften der Operationen

▪ Definieren Menge von Typen implizit

Mathematik vs. Informatik

Definition mathematischer Strukturen

▪ Liste von Eigenschaften

▪ Text bzw. formal: Boolsche Ausdrücke (Aussagen)

▪ Wenn erfüllt, dann besteht die Struktur

Informatik

▪ Mehr Varianten (templates, generics, traits,type classes, subtyping, mix-ins, multiple-inheritance…)

▪ Technische Erfordernisse

▪ Effizienz, Code-Generierung/Bindung, Compilerchecks, etc.

Beispiel: „Gruppen“

Gruppe

Gruppen Axiome

▪ Abgeschlossen: Set 𝐺, “∘ ”: 𝐺, 𝐺 → 𝐺

▪ Assoziativ: 𝑔1 ∘ 𝑔2 ∘ 𝑔3 = 𝑔1 ∘ 𝑔2 ∘ 𝑔3

▪ ∃ neutrales Element 𝑖𝑑 ∈ 𝐺: 𝑖𝑑 ∘ 𝑔 = 𝑔 ∘ 𝑖𝑑 = 𝑔

▪ ∀ 𝑔 ∈ 𝐺: ∃ inverses Element 𝑔−1 ∈ 𝐺:𝑔 ∘ 𝑔−1 = 𝑔−1 ∘ 𝑔 = 𝑖𝑑

Gruppe

template <set T, operator ○>

T operator”○”(T, T)

Axiome: abgeschlossen, assoziativ, neutrales Element, InversionFunkt. ○

Pseudo-Code: schematisch:

Abelsche Gruppen

Abelsche („kommutative“) Gruppe

▪ Zusätzlich kommutativ

▪ Kommutativität: 𝑔1 ∘ 𝑔2 = 𝑔2 ∘ 𝑔1

Funktion ○

Was drücken die Axiome aus?

Abgeschlossene Operation

Verknüpfungen sind immer möglich

∀𝑎, 𝑏 ∈ 𝐺: 𝑎 ∘ 𝑏 ∈ 𝐺

a

b1

b2

b3

Was drücken die Axiome aus?

Neutrales Element

(eindeutige) Operation,

die nichts bewirkt

∀𝑎 ∈ 𝐺: 𝑎 ∘ 𝑖𝑑 = 𝑎

aid

Inverses

alle Operationen reversibel

∀𝑎 ∈ 𝐺: 𝑎 ∘ 𝑎−1 = 𝑖𝑑

kein Informationsverlust!

a

a-1

Was drücken die Axiome aus?

Assoziativität

Operationen können Konsistent

zusammengefaßt werden:

∀𝑎, 𝑏, 𝑐 ∈ 𝐺: ( 𝑎 ∘ 𝑏) ∘ 𝑐 = 𝑎 ∘ (𝑏 ∘ 𝑐)

Alternative Erklärung

⋅ ∘ 𝑔 : 𝐺 → 𝐺 ist eine Operation (Transformation)

„∘“ führt Operationen

hintereinander aus

a

b c

( 𝑎 ∘ 𝑏)

(𝑏 ∘ 𝑐)

Was drücken die Axiome aus?

Kommutativität

Intuition: Gitter / Flache Struktur

∀𝑎, 𝑏 ∈ 𝐺: 𝑎 ∘ 𝑏 = 𝑏 ∘ 𝑎

a

b

ab

Gekrümmte Räume…

b

a a

b

„Flacher “ Raum

(Euklidische Geometrie)

nicht

flach

a

b

ab

(Verallgemeinerung:

Manigfaltigkeit)

Zusammengefaßt

Mathematische Struktur

▪ Ein oder mehrere Mengen 𝑀1, … ,𝑀𝑛

▪ Funktionen 𝑓1, … 𝑓𝑘, die zwischen 𝑀1, … ,𝑀𝑛 abbilden

▪ Typischerweise als Operatoren geschrieben: „+“, „∗“, „-“, „/“

▪ Axiome: Eigenschaften dieser Funktionen

Die Axiome definieren die Struktur

▪ Mengen nicht explizit konstruiert

▪ Funktionen nicht explizit konstruiert

Anwendung

▪ Beweis, daß konkrete Strukturen die Axiome erfüllen

Zusammengefaßt

Abstrakte Datentypen in der Informatik

▪ Ein oder mehrere Datentypen 𝑀1, … ,𝑀𝑛

▪ Operationen 𝑓1, … 𝑓𝑘, die mit Werten aus 𝑀1, … ,𝑀𝑛 arbeiten

▪ Notation je nach Programmiersprache

▪ Eigenschaften dieser Funktionen meistens implizit

Generischer Code

▪ Kann auf verschiedenen Daten arbeiten

▪ Funktionszeiger (o.ä.) als Abstraktion

Anwendung

▪ Konkrete Typen definieren, mit generischem Code binden

Beispiele:

Polymorphie in Programmiersprachen

Technische Umsetzung

Programmiersprachen

▪ Zusätzlich erforderlich:

▪ Codegenerierung / Flußkontrolle

▪ Fehlerprüfung durch Interpreter/Compiler

▪ Effizienz: Übersetzung

▪ Effizienz: Ausführung

▪ Typsysteme

▪ Definition von abstrakten Strukturen

▪ Teilweises Prüfen von Annahmen

Typsysteme

Typsystem in der Informatik

▪ Verbindung von: Datentypen, Operationen, Annahmen

Prüfung von Annahmen

▪ Allgemeine Annahmen nicht möglich

▪ Korrektheitsbeweise unentscheidbar

Daher eingeschränkte Typsysteme

▪ Kein Zugriff auf „falschen“ / „leeren“ Speicher

▪ Sehr einfache zusätzliche Annahmen

▪ Polymorphie (Wiederverwendung)

Polymorphie

Polymorphie in der Mathematik

▪ „Angenommen, G sei eine Gruppe, die auch noch folgende drei Eigenschaften hat…“

▪ Formalisierte Sprache?

Herausforderungen

▪ Effizient umsetzbar?

▪ Annahmen prüfbar (Laufzeit / Compile-time)?

▪ Flexibel?

▪ Zur Laufzeit instantiieren oder neu übersezten?

Beispiel: Vererbung

Vererbung („Subtyping“)

▪ Abstrakte Oberklassen

▪ Machen Annahmen, die für alle Subtypen gelten müssen

▪ Abgeleitete Klassen

▪ Neue, spezifischere Annahmen („is-a“-relation)

▪ (Partielle) Implementation

– Code für Funktionen/Methoden

– Datenfelder

Beispiel: Vererbung

Vererbung („Subtyping“)

Python

# Assumptions for MyClassclass MyClass:

def OperationA(x, y):pass

def OperationB(z):pass

# Extra Assumptionsclass MySubClass(MyClass):

pass

JAVA

// Assumptions for MyClassabstract class MyClass {

abstract int OperationA(MyClass x, MyClass y);

abstract MyClass OperationB(MyClass z);

}

// Extra assumptionsclass MySubClass extends MyClass{…}

Vererbung

Einschränkung

▪ Ein impliziter Typparameter pro Datenelement wählt Funktion aus

▪ Problematisches Beispiel:

– Multiplikation von Matrizen mit Vektoren

– Verschiedene Matrizen und verschiedene Vektoren

– Auswahl von „Operator∗(Matrix, Vektor)“

▪ Rein hierarchische Verfeinerung

▪ Komplexere Typbeziehungen nicht darstellbar

Vorteil

▪ Einfach, effizient, dynamisch; oft „good enough“

Beispiel: Generischer Code

Generischer Code in C++ (JAVA ähnlich)

▪ Typparameter für Code und Daten

▪ Instanziierung: „Duck-typing“

int n = myFunction<int, MyClass>(MyClass(23))

▪ Code wird bei Instantiierung neu übersetzt

▪ Wenn der entstandene Code richtig ist, klappt es

▪ Wenn falsch: (verwirrende) Fehlermeldungen

template <typename T1, typename T2>T1 myFunction(T2 a) {

T1 b = a.calcStuff(42);return b;

}

Templates / Generics

Vorteile

▪ Sehr flexibel

▪ Generischer Code + Daten (hier nicht gezeigt)

▪ Compiler prüft syntaktische Korrektheitbei Instantiierung (Compile-time)

Nachteile

▪ Alle Annahmen implizit

▪ Compiler prüft bei Instantiierung (Compile-time)

▪ Komplexere Annahmen ungeprüft

▪ Statisch (Instantiierung beim Übersetzen)

Python

Dynamisch typisiert

▪ Jede Variable ist ein „Objekt“

▪ Anwesenheit von Methoden + Datenfeldern wirdgrundsätzlich zur Laufzeit geprüft

▪ Late-binding (Objekte dynamisch an Code gebunden)

Ähnlichkeit zu C++ Templates

▪ Python macht im Prinzip das gleiche…

▪ …aber zur Laufzeit!

▪ Vorteil: sehr flexibel (alles dynamisch)

▪ Nachteil: Fehler fallen erst zur Laufzeit auf