Vorlage:Navigationsleiste/Algorithmen und Datenstrukturen

Funktionsdefinition und Signatur

In diesem Kapitel wird die Funktionsdefinition und Signatur von funktionalen Algorithmen behandelt.

Funktionsdefinition

Eine Funktion f ist eine Relation zwischen einer Eingabemenge X und einer Ausgabemenge $Y (f \subseteq X * Y)$ mit der Eigenschaft:

Für alle x ∈ X, y,y‘ ∈ Y mit (x,y),(x,y‘) ∈ f gilt y=y‘

Wir schreiben dann üblicherweise f(x)=y anstatt(x,y)∈ f und deklarieren eine Funktion durch $f : X \to Y$ . Ist $f : X \to Y$ eine Funktion so heißt X Eingabemenge und Y Ausgabemenge. In der funktionalen Programmierung sind Ein‐ und Ausgabemengen üblicherweise Terme eines bestimmten Typs.

Termdefinition

Sei T ein Typ, $V_{T}$ eine Menge von Variablen vom Typ T und $C_{T}$ eine Menge von Konstanten vom Typ T. Dann ist jedes $X \in V_{T}$ ist ein Term vom Typ T, jedes $a \in C_{T}$ ein Term vom Typ T und ist $f : T^{k} \to T$ eine Funktion und $t_{1}, . . ., t_{k}$ sind Terme vom Typ T, so ist $f (t_{1}, . . ., t_{k})$ ein Term vom Typ T.

Beispiel Terme natürlicher Zahlen

Sei int der Typ der natürlichen Zahlen, $V_{i n t}$ eine Menge von Variablen vom Typ $T_{i n t}$ und $C_{i n t} = ℕ = 1, 2, 3 . . .$ . Mögliche Funktionen auf natürliche Zahlen sind

$+ : i n t$ x $i n t \to i n t$
$* : i n t$ x $i n t \to i n t$

3+4, (8+9)*10, X*4+1 sind dann Terme natürlicher Zahlen.

Beispiel Bool´sche Terme

Sei bool der Typ der Bool´sche Terme, $V_{b o o l}$ eine Menge von Variablen vom Typ $T_{b o o l}$ und $C_{b o o l} = t r u e, f a l s e$ . Mögliche Funktionen auf Bool´sche Termes sind

$⋀ : b o o l$ x $b o o l \to b o o l$
$\neg : b o o l \to b o o l$

true $⋀$ und $\neg Y ⋀ X$ sind dann Bool´sche Terme.

Sind $v_{1}, . . ., v_{n}$ Unbestimmte vom Typ $T_{1}, . . ., T_{n}$ (bool oder int) und ist $t (v_{1}, . . ., v_{n})$ ein Term, so heißt $f (v_{1}, . . ., v_{n}) : = t (v_{1}, . . ., v_{n})$ eine Funktionsdefinition vom Typ T.

T ist dabei der Typ des Terms (Vorlage:Mathl).
f: ist der Funktionsname
$v_{1}, . . ., v_{n}$ ist ein formaler Parameter
$t (v_{1}, . . ., v_{n})$ : ist ein Funktionsausdruck

Beispiel

$f (p, q, x, y) : = i f (p \lor q) t h e n 2 x + 1 e l s e 3 y - 1$
$g (x) : = i f e v e n (x) t h e n x / 2 e l s e 3 x - 1$
$h (p, q) : = i f p t h e n q e l s e f a l s e$

Jede Funktionsdefinition hat das Schema Funktionsname(formale Parameter):= Funktionsausdruck

Signatur einer Funktion

Eine Funktion f hat die folgende Funktionsdefinition:

$f (v_{1}, . . ., v_{n}) : = t (v_{1}, . . ., v_{n})$

mit $v_{1}, . . ., v_{n}$ sind vom Typ $T_{1}, . . ., T_{n}$

$t (v_{1}, . . ., v_{n})$ ist vom Typ T

Die Signatur von f ist: $f : T_{1} * . . . * T_{n} \to T$ mit der Struktur

Name mit Stelligkeit: Parameter mit Typ * ... * Parameter mit Typ → Typ des Rückgabewertes

Beispiel einer Funktionsdefinition

f(p,q,x,y) := if (p ∨ q) then 2x + 1 else 3y ‐1

g(x) := if even(x) then x / 2 else 3x ‐1

h(p,q) := if p then q else false, mit h als Funktionsname, (p,q) als formalen Parameter und dem darauffolgenden Funktionsausdruck.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.2.2 zu finden.

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Funktionsdefinition und Signatur

Inhaltsverzeichnis

Funktionsdefinition und Signatur