Kurs:Algorithmen und Datenstrukturen/Vorlesung/Grundidee Funktionaler Programmierung

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

Funktionale Algorithmen

In diesem Kapitel wird die funktionale Programmierung behandelt.

Grundidee

Definition zusammengesetzter Funktionen durch Terme mit Unbestimmten.

Ein Beispiel einer einfachen Funktionsdefinition ist $f(x)=5x+1$.

Erinnerung Definition Term :
*Variable ist ein Term 
*Konstanten-Symbol ist ein Term 
*Sind $t_{1},...,t_{n}$ Terme und f ein n-stelliges Funktionssymbol, so ist $f(t_{1},...,t_{n})$ ein Term

Beispiele für Terme

Unbestimmte (Symbole)

• $x,y,z$ … vom Typ int
• q,p,r … vom Typ bool

Terme mit Bestimmten

• 1+1, 3*2, ...

Terme mit Unbestimmten

• Terme vom Typ int
  • x, x-2, 2x+1, (x+1)(y-1)

Terme vom Typ bool

• $p,p\wedge true,(p\lor true)\Rightarrow (q\lor false)$

Definition

Ein funktionaler Algorithmus ist eine Menge von Funktionsdefinitionen $f_{1}$ bis $f_{m}$ mit:

$f_{1}(v_{1},_{1},...,v_{1},_{n_{1}}):=t_{1}(v_{1},_{1},...,v_{1},_{n_{1}}),$
...
$f_{m}(v_{m},_{1},...,v_{m},_{n_{m}}):=t_{m}(v_{m},_{1},...,v_{m},_{n_{m}}).$

Die erste Funktion $f_{1}$ wird wie beschrieben ausgewertet und ist die Bedeutung (=Semantik) des Algorithmus.

$f_{1}$ ist die zustands-bestimmende Eingabe aus der die Werte der Ausgabe abgelesen werden.

Funktionale Algorithmen sind die Grundlage einer Reihe von universellen Programmiersprachen, z.B. APL und Lisp. Diese Programmiersprachen werden als funktionale Programmiersprachen bezeichnet.

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 zu finden.