Zaunpfahlproblem

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Lattenzaunproblem)
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Der Begriff Zaunpfahlproblem beschreibt ein Logikproblem der Indexierung. Ein Zaunpfahlproblem tritt immer dort auf, wo Unklarheit herrscht, ob eine Zahlenangabe einen Raum oder einen Punkt darstellt, beziehungsweise ob eine Distanz eines, beide oder keines der Endelemente einschließt. Ein Zaunpfahlfehler ist ein Spezialfall eines Off-by-one-Errors. Häufig begegnet man ihnen in der Datenverarbeitung.

Beispiel[Bearbeiten]

Illustration des Zaunpfahlproblems

Frage: Wenn man einen 30 m langen geraden Zaun errichten will und die Zaunpfähle 3 m auseinander stehen sollen, wie viele Pfähle braucht man dafür?

Die intuitive Antwort „10 Pfähle“ ist falsch, denn der Zaun hat zwar 10 Segmente, aber 11 Pfähle. Anfang und Ende des Zauns benötigen je einen Pfahl.

Der umgekehrte Fehler tritt auf, wenn die Anzahl Pfähle gegeben ist und fälschlich angenommen wird, die Länge des Zaunes ergäbe sich aus dem Pfahlabstand multipliziert mit der Anzahl der Pfähle. Aus 11 Pfählen ergibt sich aber kein 33 m langer Zaun, sondern nur ein 30 m langer.

Geschichte[Bearbeiten]

Eines der frühesten Beispiele für einen Zaunpfahlfehler geschah bei der Kalenderreform des Gaius Iulius Caesar. Caesar hatte die Schaltung in jedem vierten Jahr angeordnet, die Priester verstanden dies jedoch nach der Inklusivzählung (siehe unten) als eine Schaltung alle drei Jahre.

Zaunpfahlprobleme in der Informatik[Bearbeiten]

In der Informatik, wo der Begriff des Zaunpfahlproblems am häufigsten Verwendung findet, treten ähnliche Probleme auf. Diese gehören zwei Hauptgruppen an:

  1. Wie werden Abstände gezählt – inklusive eines oder beider Grenzelemente? Wenn es um den Abstand von Elementen in einer Liste geht, muss sich der Softwareentwickler im Klaren darüber sein, ob eines oder beide Grenzelemente mitgezählt werden oder nicht.
  2. Zählung ab 0 oder ab 1: Im Alltag beginnen Menschen Aufzählungen meist bei 1, in vielen – vor allem durch C beeinflussten – Programmiersprachen beginnen Aufzählungen hingegen bei 0. So hat beispielsweise in Java ein Array der Größe 5 Elemente mit den Indizes 0, 1, 2, 3 und 4. Ein typischer Anfängerfehler ist es, in einem solchen Array die Elemente 1 bis 5 auszulesen oder einen falschen Vergleichsoperator zu benutzen.

Beispiel: Welchen Abstand haben Element 20 und Element 30 in einer Liste?

  • Zählung einschließlich beider Grenzwerte („Inklusivzählung“): 11
  • Zählung einschließlich 20, aber ohne 30: 10
  • Zählung ohne 20, aber einschließlich 30: 10
  • Zählung ohne beide Grenzwerte (die dazwischenliegenden Elemente): 9

Verwandte Probleme[Bearbeiten]

Die historische Inklusivzählung[Bearbeiten]

Abstände, Distanzen und Zeiträume wurden von der Antike bis in nachmittelalterliche Zeit hinein nach der „Inklusivzählung“ gezählt. Bei dieser Zählweise wird sowohl das Anfangs- als auch das Endelement einer Folge mitgezählt. Der Startpunkt wird als „1“ definiert und von dort weitergezählt. Der Distanz 0 wird somit der Zahlenwert „1“ zugewiesen, der Distanz 1 der Zahlenwert „2“, usw. Die Werte für Distanzen, Zeiträume usw. sind also bei der Inklusivzählung immer um 1 größer als nach heutiger mathematischer Konvention. Historisch hat die Inklusivzählung ihre Ursache in dem Umstand, dass das Konzept der Zahl Null erst mit der Einführung der arabisch-indischen Zahlen ab dem 13. Jahrhundert in Europa bekannt wurde.

Von der Inklusivzählung rührt zum Beispiel der Brauch her, zu „in einer Woche“ neben „in sieben Tagen“ auch „in acht Tagen“ zu sagen, obwohl jeder weiß, dass eine Woche sieben Tage hat. Der aktuelle Wochentag wird bei der Inklusivzählung mitgezählt:

Wochentag: Montag Dienstag Mittwoch Donnerstag Freitag Samstag Sonntag Montag
„Nummer“ des Tages: 1 2 3 4 5 6 7 8

Ein anderes Beispiel für die Inklusivzählung sind die Namen der musikalischen Intervalle:

Distanz zweier Töne: 0 1 2 3 4 5 6 7
Name des Intervalls: Prime Sekunde Terz Quarte Quinte Sexte Septime Oktave
Kommt von lat. Zahl: 1 2 3 4 5 6 7 8

Dass der in der Musik übliche Name jedes Intervalls um 1 zu groß ist, sieht man unter anderem bei der Addition von Intervallen. Eine Quarte und eine Quinte ergeben zusammen eine Oktave. Aber 4 + 5 ist nicht 8 – vielmehr ist 3 + 4 = 7.

Zeitrechnung[Bearbeiten]

Jahr null[Bearbeiten]

Die christliche Zeitrechnung kennt kein Jahr null, sondern geht vom Jahr 1 v. Chr. direkt ins Jahr 1 n. Chr. über. In der astronomischen Zeitrechnung wird dagegen das Jahr 1 v. Chr. als Jahr null gerechnet.

Christliches Jahr: 2 v. Chr. 1 v. Chr. 1 n. Chr. 2 n. Chr.
Astronomisches Jahr: -1 0 1 2

Jahrhunderte[Bearbeiten]

Das bekannte Logo des Filmstudios 20th Century Fox. Auch im Englischen bezeichnet 20th century das Jahrhundert von 1901-2000.

Es gab kein „nulltes Jahrhundert“. Das 1. Jahrhundert dauerte vom 1. Januar 1 n. Chr. bis zum 31. Dezember 100 n. Chr. Ein Jahrhundert umfasst immer die hundert Jahre, die mit dem entsprechenden vollen Jahr enden. Entsprechend wird der Zeitraum vom 1. Januar 1901 bis zum 31. Dezember 2000 als das 20. Jahrhundert bezeichnet, und das 21. Jahrhundert begann am 1. Januar 2001.

Im Italienischen werden neben der normalen Bezeichnung der Jahrhunderte („XX secolo“) auch umgangssprachlich die Jahrhunderte so benannt, dass „Novecento“ (wörtlich: neunhundert) den Zeitraum von 1900-1999 bezeichnet. Dies ist jedoch nur für Jahrhunderte ab dem Jahr 1100 möglich. Im Englischen gibt es in ähnlicher Weise die Möglichkeit, mit „1900s“ den Zeitraum 1900-1999 zu bezeichnen. Bei der letzten Jahrtausendwende feierten auch viele im deutschsprachigen Raum den Jahrtausendwechsel bereits 1999/2000 anstatt 2000/2001.

Jahrestage[Bearbeiten]

Jahrestage (zum Beispiel Geburtstage) feiern die Vollendung und nicht den Beginn der angegebenen Jahre. Ein Mensch, der seinen 18. Geburtstag feiert, beginnt deshalb nicht an diesem Tag sein 18. Lebensjahr – vielmehr hat er schon volle 18 Jahre gelebt und beginnt sein 19. Lebensjahr.

Der Tag der Geburt eines Menschen ist also sozusagen sein „0. Geburtstag“, ähnlich wie die Markierung 0 auf einem Zentimetermaß.

Geburtstag:  Geburt   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18
                   \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
Lebensjahr:         1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18

In einigen Kulturkreisen (z.B. China) ist das hingegen anders: der Tag der Geburt ist der „1. Geburtstag“.

Finden der Mitte[Bearbeiten]

Wird beim Zählen mit 1 begonnen, dann entspricht die Mitte nicht der Hälfte der Anzahl der Elemente. Zum Beispiel sei eine Skala von 1 bis 10 gegeben. Die 5 liegt hierbei nicht in der Mitte der Skala, sondern darunter. Die tatsächliche Mitte liegt bei 5,5:

1 2 3 4 5 6 7 8 9 10
         ^Mitte

Auch Folgendes mag zunächst unintuitiv erscheinen oder „überraschen“: Von fünf Elementen, nummeriert 1 2 3 4 5, ist das mittlere Element das mit der Nummer 3 – obwohl die Hälfte von 5 bekanntlich 2½ ist.

Bei einer Skala von 0 bis 10 hingegen hat man 11 Indizes und die Mitte liegt bei 5:

0 1 2 3 4 5 6 7 8 9 10
          ^Mitte

Der Grund hierfür ist der gleiche wie beim oben beschriebenen Zaunpfahlproblem. Die obere Skala hat die Indizes 1 bis 10. Diese werden als Punkte betrachtet. Damit beschreibt die Skala jedoch nur eine Länge (Strecke, Distanz zwischen Anfang und Ende) von 9, denn 10 – 1 = 9. Ihre Mitte liegt daher bei der Hälfte von 9, gerechnet ab dem Index 1: 1 + (9 / 2) = 5,5.

Die untere Skala mit den Indizes 0 bis 10 hingegen beschreibt eine Länge von 10 und ihre Mitte liegt bei 0 + (10 / 2) = 5.

Stockwerke[Bearbeiten]

Im deutschen Sprachraum ist der 1. Stock das erste aufgestockte Geschoss, im Gegensatz zum Erdgeschoss. In vielen Kulturen hat jedoch das Erdgeschoss die Nummer 1. Auch hier kommt es zum Zaunpfahlproblem: Stockwerk 3 oder drei Treppen hoch? Wenn in Deutschland statt Stockwerken Ebenen durchnummeriert werden, dann wird oft im Erdgeschoss mit dem Zählen bei 1 angefangen.

Bei drei oder auf drei?[Bearbeiten]

„Bei drei oder auf drei?“ ist ein berühmtes Zitat aus der Actionfilm-Reihe Lethal Weapon. Hier ist das Problem, ob man die gemeinsam geplante, überraschende Aktion beginnen soll, nachdem man bis drei gezählt hat oder genau dann, wenn man drei sagt.