Zum Inhalt springen

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Funktionsdefinition und Signatur

Aus Wikiversity




Funktionsdefinition und Signatur

[Bearbeiten]

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

Funktionsdefinition

[Bearbeiten]

Eine 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

[Bearbeiten]

Sei 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

[Bearbeiten]

Sei 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

[Bearbeiten]

Sei 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

[Bearbeiten]

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

Signatur einer Funktion

[Bearbeiten]

Eine 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

[Bearbeiten]

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.


R-0 Discussion R-3