Kurs:Algorithmen und Datenstrukturen/Vorlesung/Definiertheit

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

Definiertheit von imperativen Algorithmen

Gegeben ist folgender Algorithmus:

$f(x):=if~x==0~then~0~else~f(x-1)$

Auf welchen Eingaben ist der Algorithmus definiert?

Auswertung:

$f(0)\to 0$

$f(1)\to f(0)\to 0$

$f(2)\to f(1)\to f(0)\to 0$

$f(x)\to 0\forall x\in int,x>0$

$f(-1)\to f(-2)\to ...$ Diese Auswertung terminiert nicht!

Somit gilt:

$f(x):=\left\{{\begin{array}{ll}0&falls~x\geq 0\\\bot &sonst\end{array}}\right.$