Kurs:Algorithmen und Datenstrukturen/Vorlesung/Funktionsdefinition und Signatur
Funktionsdefinition und Signatur
BearbeitenIn diesem Kapitel wird die Funktionsdefinition und Signatur von funktionalen Algorithmen behandelt.
Funktionsdefinition
BearbeitenEine Funktion f ist eine Relation zwischen einer Eingabemenge X und einer Ausgabemenge 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 . Ist eine Funktion so heißt X Eingabemenge und Y Ausgabemenge. In der funktionalen Programmierung sind Ein‐ und Ausgabemengen üblicherweise Terme eines bestimmten Typs.
Termdefinition
BearbeitenSei T ein Typ, eine Menge von Variablen vom Typ T und eine Menge von Konstanten vom Typ T. Dann ist jedes ist ein Term vom Typ T, jedes ein Term vom Typ T und ist eine Funktion und sind Terme vom Typ T, so ist ein Term vom Typ T.
Beispiel Terme natürlicher Zahlen
BearbeitenSei int der Typ der natürlichen Zahlen, eine Menge von Variablen vom Typ und . Mögliche Funktionen auf natürliche Zahlen sind
- x
- x
3+4, (8+9)*10, X*4+1 sind dann Terme natürlicher Zahlen.
Beispiel Bool´sche Terme
BearbeitenSei bool der Typ der Bool´sche Terme, eine Menge von Variablen vom Typ und . Mögliche Funktionen auf Bool´sche Termes sind
- x
true und sind dann Bool´sche Terme.
Sind Unbestimmte vom Typ (bool oder int) und ist ein Term, so heißt eine Funktionsdefinition vom Typ T.
- T ist dabei der Typ des Terms ( ).
- f: ist der Funktionsname
- ist ein formaler Parameter
- : ist ein Funktionsausdruck
Beispiel
BearbeitenJede Funktionsdefinition hat das Schema Funktionsname(formale Parameter):= Funktionsausdruck
Signatur einer Funktion
BearbeitenEine Funktion f hat die folgende Funktionsdefinition:
mit sind vom Typ
ist vom Typ T
Die Signatur von f ist: mit der Struktur
Name mit Stelligkeit: Parameter mit Typ * ... * Parameter mit Typ → Typ des Rückgabewertes
Beispiel einer Funktionsdefinition
Bearbeiten- 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
BearbeitenDa 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.