[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]
Die Anzahl der verfügbaren Elementaroperationen - wie immer man "elementar" in einem gegebenen Zusammenhang definiert - ist beschränkt, ebenso ihre Ausführzeit. Aus der sprachlichen Beschreibung des Algorithmus muß die Abfolge der einzelnen Verarbeitungsschritte eindeutig hervorgehen. Hierbei sind gegebenenfalls Wahlmöglichkeiten zuzulassen, denn es kann vorkommen, daß innerhalb einer Klasse von gleichartigen Problemen, die sich z.B. nur durch den Wert gewisser Parameter voneinander unterscheiden, unterschiedliche Lösungswege zu beschreiten sind. In solchen Fällen muß genau festgelegt werden, wie die Auswahl eines Verarbeitungsablaufs zu erfolgen hat.
Beispiel (Bisektion) Von einer stetigen Funktion f:[a,b]->R, deren Werte an den Randpunkten des Intervalls [a,b] unterschiedliche Vorzeichen besitzen, also
erfüllen, weiß man aus der Analysis, daß sie mindestens eine Nullstelle besitzt: Es gibt ein
Zur (näherungsweisen) Bestimmung einer dieser Nullstellen kan man folgendermaßen vorgehen: Man ermittelt den Funktionswert f(xm) am Intervall-Mittelpunkt xm: = (a+b)/2. Ist f(xm)=0, so wurde mit xm bereits eine Nullstelle gefunden. Andernfalls muß entweder
gelten. Im ersten Fall liegt in (a,xm) mindestens eine Nullstelle von f, im zweiten Fall in (xm,b). Man hat somit ein Intervall der Länge (b-a)/2 gefunden, das für eine weitere Nullstellensuche in Frage kommt.
Wieder holt man diesen Vorgang, so trifft man entweder einmal exakt auf eine Nullstelle am Mittelpunkt eines Teilintervalls von [a,b], oder man kann auf diese Art ein Intervall hinreichend kleiner Länge ermitteln, von dem man sicher weiß, daß es eine Nullstelle von f enthält.