Intervallhalbierungsverfahren - Informatives

Definition des Intervallhalbierungsverfahrens

• Das Verfahren wird in der Mathematik regelmäßig angewandt. Es handelt sich aber auch um eine Technik, die in der Informatik benutzt wird, um Abläufe effizienter zu gestalten.
• Der Vorgang wird auch kurz Bisektion genannt. Das lateinische Wort wird meist bevorzugt, da "Intervallhalbierungsverfahren" lang und umständlich ist.
• Doch sowohl aus dem deutschen als auch aus dem lateinischen Namen kann man bereits eine Erklärung ableiten.
• Während "bi" schlicht "zwei" heißt, meint "Sektion" so viel wie "Schnitt". Dies bedeutet, dass man eine Gesamtmenge in zwei gleiche Teile untergliedert.
• Jede Teilmenge kann erneut zerlegt werden. So soll ein Problem in Teilprobleme aufgeteilt werden, was die Lösungsfindung erleichtern soll.

Ein Zahlenbeispiel der Bisektion

• In der Schule wird das Intervallhalbierungsverfahren meist mit einem simplen Rechenspiel erklärt. Dabei sollen Sie annehmen, dass eine Zahl zwischen 1 und 1.000 gesucht wird. Der Lehrer weiß, sagt jedoch nicht, dass die Zahl 503 ist.
• Sollen Sie nun die Zahl selbst erraten, kann dies mit Glück sofort gelingen oder aber auch 1.000 Schritte brauchen. Gehen Sie geradlinig vor und beginnen bei der Vermutung bei 1, benötigen Sie 503 Versuche für die Problemlösung.
• Nutzen Sie jedoch das Verfahren der Bisektion, werden Sie schneller zum Ziel kommen. Sie müssen die Menge von 1.000 zunächst in gleiche Teile aufgliedern. Sie fragen daher nicht nach einer Zahl, sondern danach, ob die Lösung größer als 500 ist.
• Die Antwort wird "Ja" lauten, sodass Sie die zweite Teilmenge von 0 bis 500 nun ignorieren können. Das Teilgebiet 500 bis 1.000 können Sie nun erneut in in zwei Sektionen teilen, sprich eine weitere Intervallhalbierung durchführen.
• Sie fragen demnach nun, ob die Zahl größer als 750 ist. Da die Antwort "Nein" ist, können Sie weitergehen: Ist die Zahl kleiner als 625?
• Die Antwort "Ja" führt zu weiteren Teilmengen, bis die Frage nach 504 mit "kleiner" und die folgende nach 502 mit "größer" beantwortet wird.
• So wissen Sie durch das ständige Halbieren der zutreffenden Teilmenge schneller, welche Zahl gesucht wurde.