Kurs:Algorithmen und Datenstrukturen/Vorlesung/Zustände

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

Zustände

Ist ${\underline {X}}={X_{1},X_{2},...}$ eine Menge von Variablen (-namen) von denen alle nur Werte aus der Wertemenge W haben können (alle Variablen vom gleichen Typ), dann ist der Zustand Z eine partielle Abbildung.

$Z:{\underline {X}}\to W$ (Zuordnung des momentanen Wertes)

• Beispiel in einem gewissen Zustand

$Z(X_{1})=42$

$Z(X_{2})=17$

$Z(X_{3})=23$

• Nach $X_{1}:=29$ folgt:

$Z(X_{1})=29$

$Z(X_{2})=17$

$Z(X_{3})=23$

Ist $Z:{\underline {X}}\to W$ ein Zustand und wählt man eine Variable X und einen Wert w aus dem Wertebereich W, so ist der transformierte Zustand wie folgt definiert:

$Z(X\leftarrow ~w):{\underline {X}}~\to ~W~mit$ 

$Z_{(X\leftarrow ~W)}~(Y)~\to ~\left\{{\begin{array}{ll}w&falls~X=Y\\Z(Y)&sonst\end{array}}\right.$

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.