Die Bisektion oder fortgesetzte Bisektion ist ein Verfahren der Mathematik und der Informatik. Durch sie wird eine sehr schnell konvergierende Folge von Intervallschachtelungen erzeugt. Das Wort setzt sich zusammen aus Bi "Zwei" und Sektion von Sectio. Es steht also für Zwei-Teilung.

Einleitung

Grundsätzlich finden Bisektionsverfahren immer dann Anwendung, wenn ein Problem gelöst werden kann, indem es in zwei etwa gleichgroße Teilprobleme zerlegt wird, die dann einzeln für sich behandelt werden können. Ein einfaches Beispiel stellt folgende Aufgabe dar:

Gesucht ist eine Zahl zwischen 1 und 1000. Die soll ein Spieler erraten, er erhält als Hinweis immer nur "größer" und "kleiner". Angenommen die Zahl sei 512.

Verwendet der Spieler zum Raten die Bisektion, ergibt sich folgender Dialog:

• 500 - größer
• 750 - kleiner
• 625 - kleiner
• 562 - kleiner
• 531 - kleiner
• 515 - kleiner
• 512 - Treffer

Man beachte hier den Vorteil gegenüber der einfacheren linearen Suche: Hätte der Spieler bei 1 begonnen, so hätte der Dialog folgenden Verlauf genommen:

• 1 - größer
• 2 - größer
• ...
• 511 - größer
• 512 - Treffer

Anstatt sieben Fragen hätte er also 512 Fragen gebraucht, die Bisektion ist hier also deutlich effizienter.

Laufzeit und Konvergenz

Der diskrete Fall

Im diskreten Fall, also wenn das zugrundeliegende Problem nur eine endliche Anzahl von zu testenden Lösungen besitzt, kann ein solches Problem immer als eine Suche aufgefasst werden: Finde aus einer endlichen Menge M ein Element x mit der Eigenschaft p(x)=0. p soll hierbei eine Funktion

sein, wobei wir fordern, dass p(y)=0 genau dann gilt, wenn unsere gesuchte Eigenschaft erfüllt ist, also y=x. Um dieses Problem mittels Bisektion zu lösen, fordern wir weiterhin, dass

• p(y)<0 falls y<x
• p(y)>0 falls y>x

Unsere Funktion p gibt uns also nicht nur den Treffer an (bei p(x)=0), sondern weist uns im anderen Fall auch die Richtung, in der wir weitersuchen müssen. Wir setzen dabei natürlich stillschweigend voraus, dass M durch eine Relation < geordnet wird.

Wieviele Versuche, also Auswertungen von p, benötigen wir nun, um x zu finden? Nehmen wir an, M habe m Elemente. Wir teilen also M in zwei möglichst gleich große Hälften, indem wir zunächst p für ein Element möglichst nah der Mitte von M auswerten. Den Fall, dass sich M nur in zwei ungefähr gleich große Hälften teilen lässt (weil es eine ungerade Anzahl von Elementen hat), unterschlagen wir auch, er wirkt sich bei großen Elementzahlen so gut wie nicht aus. Nach jedem Schritt können wir also eine Hälfte der zuletzt untersuchten Menge getrost verwerfen, unsere aktuelle Menge halbiert sich mit jeder Auswertung von p. Das Verfahren endet spätestens, wenn die letzte Menge nur noch ein Element enthält, dieses muss das gesuchte sein. Um also eine Menge der Größe m durch fortgesetztes Halbieren auf 1 zu reduzieren, sind n Schritte notwendig mit:

Mathematisch formuliert hat unser Verfahren also eine Laufzeit O(log(m)) (siehe auch: Landau-Symbole).

Der kontinuierliche Fall

Im kontinuierlichen Fall ist als Lösung meist ein Intervall gesucht, dieses ist Teilintervall eines anderen endlichen Intervalls. Die Anzahl der möglichen Lösungen ist unendlich, da ja jedes Teilintervall (meist einer bestimmten Länge) infrage kommt! Ein Beispiel soll dies verdeutlichen:

Gesucht ist die Nullstelle einer streng monoton steigenden Funktion f im Intervall [a,b]. Diese soll mit einer Genauigkeit angegeben werden. Genauer gesagt suchen wir also ein Teilintervall von [a,b], dass die Nullstelle enthält und höchstens die Länge hat. Wir können hier nicht einfach alle solchen Intervalle durchprobieren, dies sind ja unendlich viele! Bisektion kann uns jedoch helfen:

• Eine streng monoton steigende Funktion f hat in einem Intervall [l,r] genau dann eine Nullstelle, wenn f(l)<0 und f(r)>0 ist.

Dies führt zu folgendem Algorithmus:
1. Wir setzen l=a und r=b.
2. Teste, ob [l,r] eine Nullstelle enthält. Wenn nicht, breche ab.
3. Teste, ob ist. Wenn ja, haben wir unser Intervall gefunden!
4. Sonst teile [l,r]] in der Mitte und setze das Verfahren mit beiden Teilintervallen rekursiv bei 2. fort.

Wie ist nun die Laufzeit dieses Verfahrens? Ähnlich wie im diskreten Fall endet der Algorithmus spätestens, wenn das Intervall die Länge unterschreitet. Also:

Wir haben somit eine logarithmische Laufzeit in Abhängigkeit vom Verhältnis der Intervalllänge zur gewünschten Genauigkeit.

Bisektion und binäre Bäume

Es besteht ein enger Zusammenhang zwischen der Bisektion und den sogenannten binären Bäumen. Ein binärer Baum ist - vereinfacht geasagt - eine Struktur, die aus Knoten und Kanten besteht. Knoten kann man sich hierbei als eine von oben nach unten in verschiedenen Ebenen angeordnete Menge von kleinen Kreisen vorstellen. Jeder Knoten ist mit genau einem Knoten der darüberliegenden Ebene (über eine Kante) verbunden, mit der darunterliegenden Ebene ist er mit höchstens zwei Knoten verbunden. Die Kanten nach unten sind genau nach einer rechten und einer linken Kante unterschieden. Auf der obersten Ebene liegt nur ein Knoten, der keine Verbindung nach weiter oben hat, er heißt Wurzel des Baumes. Ein Knoten, der keine Nachfolger auf tieferer Ebene hat, heißt Blatt.

Während einer Bisektion wird nun in jedem Schritt eine Entscheidung getroffen, ob mit der linken oder der rechten Teilmenge fortgesetzt werden soll. Durchlaufe ich einen binären Baum von der Wurzel beginnend nach unten, so muss ich in jedem Knoten entscheiden, ob ich der linken oder der rechten Kante folgen will. Zu einer gegebenen Mengengröße und einem Bisektionsverfahren gibt es also genau einen zugeordneten binären Baum, der alle potentiellen Verläufe der Bisektion beschreibt. Eine tatsächliche Durchführung mit einer gegebenen Menge entspricht dann einem Weg durch den Baum von oben nach unten. Der Baum hat dabei genau so viele Blätter, wie das gegebene Problem mögliche Ergebnisse liefern kann. Da sich mit jeder Entscheidung in einem Knoten die Anzahl der noch möglichen Ergebnisse etwa halbiert, hat er ungefähr

log₂m

Ebenen. Dies entspricht der Laufzeit unserer Bisektion, weil die Anzahl der Ebenen ja die Weglänge von oben nach unten festlegt, die wiederum gleich der Laufzeit ist. Der sich durch diese Zuordnung ergebende Baum entspricht einem balancierten binären Suchbaum.

Bisektion und binäre Zahlen

Angenommen, wir möchten die Zahlen { 0,...,m-1 } lediglich unter Zuhilfenahme der Ziffern 0 und 1 darstellen. Für gewöhnlich wird dies dann mit binären Zahlen erledigt, das heißt die 0 wird als 0 dargestellt, die 1 als 1, die 2 als 10, die 3 als 11 und so weiter. Wie zählen wie im gewöhnlichen Dezimalsystem, bloß beschränken wir uns dabei auf die Ziffern 0 und 1, anstatt 0 bis 9 zu verwenden.

Wir haben auch erfahren, dass sich Elemente einer geordneten Menge durch Bisektion finden lassen: Wenn wir eine Zahl zwischen 0 und m-1 wählen, können wir sie mittels Bisektion durch eine Folge von "größer-oder-gleich"- und "kleiner"-Entscheidungen kennzeichnen. Wählen wir als m immer eine Potenz von 2, so können wir immer auf das Element "rechts der Mitte" tippen, da die Menge eine gerade Größe hat. Für m=8 haben wir zum Beispiel die Menge { 0,...,7 }, um nun die 2 zu finden, würden wir wie folgt tippen:

4 ? kleiner
2 ? größer oder gleich (wir verzichten hier auf den "Treffer")
3 ? kleiner

Damit ist die 2 genau beschrieben. Setzen wir nun für "kleiner" die 0 und für "größer oder gleich" die 1, so ergibt sich 010. Dies ist genau die binäre Darstellung der 2.

Weblinks

• http://www.numa.uni-linz.ac.at/Staff/haase/Lectures/Kurs-C/Script/html/node73.html