Kurs:Algorithmen und Datenstrukturen/Vorlesung/Syntax und Semantik

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

Syntax und Semantik

In diesem Kapitel wird die Syntax und Semantik von imperativen Algorithmen behandelt.

Umsetzung in Programmiersprachen

In realen imperativen Programmiersprachen gibt es fast immer diese Anweisungen, da imperative Algorithmen die Grundbausteine imperativer Programmiersprachen sind. While-Schleifen sind rekursiv definiert, ihre rekursive Auswertung braucht nicht zu terminieren. Bereits Programmiersprachen mit diesen Sprachelementen sind universell. Wir werden uns hier zunächst auf die Datentypen bool und int beschränken und können nun die Syntax imperativer Algorithmen festlegen.

Syntax

<Programmname>:
var X,Y,...:int; P,Q,...:bool; (Variablen Deklaration)
input $X_{1},...,X_{n};$ (Eingabe Variablen)
$\alpha$   (Anweisungen)
output $Y_{1},...,Y_{m}$ (Ausgabe-Variablen)

Semantik

Die Festlegung der formalen Bedeutung ist hier etwas komplexer als bei den funktionalen Algorithmen. Das Ziel ist aber das gleiche: Die Funktion zur Semantikfestlegung.

Die Bedeutung (Semantik) eines imperativen Algorithmus ist eine partielle Funktion:

$[\![PROG]\!]W_{1}\cdot ...\cdot W_{n}\to V_{1}\cdot ...\cdot V_{m}$

$[\![PROG]\!](w_{1},...,w_{n})=(Z(Y_{1}),...,Z(Y_{m}))$

$wobei~Z=[\![\alpha ]\!](Z_{0}),$

$Z_{o}(X_{i})=w_{i},~i=1,..,n$

$und~Z_{0}(Y)=\bot ,~fuer~Variablen~Y\neq X_{i}(i=1,...,n)$

Es gilt:

$PROG$ Programme
$W_{1},...,W_{n}$ Wertebereich der Typen von $X_{1},...,X_{n}$
$V_{1},...,V_{m}$ Wertebereich der Typen von $Y_{1},...,Y_{m}$

Das bedeutet, dass der Algorithmus eine Transformation auf den gesamten initialen Zustand (geg. durch die Eingabe)definiert. Die Bedeutung gibt die Werte der Ausgabevariablen an.

$[\![PROG]\!](w_{1},...,w_{n})=Z(Y_{1},...,Z(Y_{m}))$

$wobei~Z=[\![\alpha ]\!](Z_{0}),$

$Z_{o}(X_{i})=w_{i},~i=1,..,n$

$und~Z_{0}(Y)=\bot ,~fuer~Variablen~Y\neq X_{i}(i=1,...,n)$

Die Funktion Z ist nicht definiert, falls die Auswertung von $\alpha$ nicht terminiert.

Charakterisierung

Die Algorithmenausführung imperativer Algorithmen besteht aus einer Folge von Basisschritten, oder genauer gesagt Wertzuweisungen. Diese Folge wird mittels Selektion und Iteration basierend auf booleschen Tests über dem Zustand konstruiert. Jeder Basisschritt definiert eine Transformation des Zustands. Die Semantik des Algorithmus ist durch die Kombination all dieser Zustandstransformationen zu einer Gesamttransformation festgelegt.

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