Kurs:Algorithmen und Datenstrukturen/Vorlesung/Ausdrücke

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

Ausdrücke

Ausdrücke entsprechen im Wesentlichen den Termen einer funktionalen/logischen Sprache, jedoch stehen an der Stelle von Unbestimmten nun Variablen. Die Auswertung von Termen ist zustandsabhängig:

Gegebener Term:  $2\cdot X+1$
Wert im Zustand Z ist durch $2\cdot Z(X)+1$ bestimmt

Wert eines Ausdrucks

Der Wert eines Ausdrucks $t(X_{1},...,X_{n})$ wird mit $Z(t(X_{1},...,X_{n}))$ bezeichnet:

$Z(2\cdot X+1)=2\cdot Z(X)+1$

Damit ist auch die Wertzuweisung mit Variablen möglich

$X:=t(X_{1},...,X_{n})$

Der Transformierte Zustand ist definiert als:

$[\![X:=t(X_{1},...,X_{n})]\!](Z)=Z\langle X\leftarrow Z(t(X_{1},...,X_{n}))\rangle$

Den Zustand liest man so, dass X dem Wert des Ausdrucks $t(X_{1},...,X_{n})$ zugeordnet wird. Die Semantikklammern bedeuten, dass eine Anweisung als eine Funktion auf Zuständen definiert ist.

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