Kurs:Algorithmen und Datenstrukturen/Vorlesung/Funktionsdefinition und Signatur




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.