Kurs:Algorithmen und Datenstrukturen/Vorlesung/Funktionsdefinition und Signatur

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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_{int}$ eine Menge von Variablen vom Typ $T_{int}$ und $C_{int}=\mathbb {N} ={1,2,3...}$. Mögliche Funktionen auf natürliche Zahlen sind

• $+:int$ x $int\to int$
• $*:int$ x $int\to int$

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_{bool}$ eine Menge von Variablen vom Typ $T_{bool}$ und $C_{bool}={true,false}$. Mögliche Funktionen auf Bool´sche Termes sind

• $\bigwedge :bool$ x $bool\to bool$
• $\neg :bool\to bool$

true $\bigwedge$ und $\neg Y\bigwedge 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 (${}v_{1},\ldots ,v_{n}$).
• 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):=if~(p\lor 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$

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.