Treaps

Das Problem

Das Ordnen und Durchsuchen von grossen Datenmengen sind Aufgaben, die in der Informatik häufig auftreten und schnell ausgeführt werden sollten. Wer will beispielsweise eine halbe Minute warten, bis Facebook beim Login den Benutzernamen in der Datenbank mit Millionen von Benutzern gefunden und mit dem eingegebenen Passwort verglichen hat? Genau dafür braucht es Algorithmen, die Daten geschickt abspeichern und so schnell wiederfinden können. Eine Lösung für diese Aufgaben sind sogenannte Treaps. Der Name setzt sich zusammen aus den Wörtern Tree und Heap und beschreibt die Idee ziemlich genau. Das Konzept der Treaps soll hier aufbauend erklärt werden:

Man versetze sich in die Lage eines (vergleichsweise kleinen) Social Networks, das eine Million Benutzer-IDs (Zahlen) abspeichern und schnell wiederfinden soll. Die offensichtlichste Lösung dafür ist wohl eine Liste. Beim Login geht das System die ganze Liste durch, bis die Benutzer-ID gefunden wurde. Im schlimmsten Fall müssen so also eine Million Zahlen verglichen werden. Wächst das Social Network weiter, so steigt auch die Zeit, die das System braucht, um die passende Benutzer-ID zu finden – und zwar linear. Bei einer Milliarde Benutzer müssen im schlimmsten Fall eine Milliarde Zahlen verglichen werden. Der Menschenverstand genügt um zu sehen, dass so das System irgendwann ziemlich langsam wird. Eine bessere Lösung muss her.

Binäre Suchbäume

Eine Lösung liefern sogenannte binäre Suchbäume (trees). Diese bestehen aus Knoten (nodes) und Verästelungen. Jeder Knoten besitzt eine Zahl (key) und maximal zwei ausgehende Äste (pointers) auf weitere Knoten. Beginnend mit einem obersten Knoten (root) entsteht so gegen unten ein „Baum“ mit immer mehr Verästelungen. Die untersten Knoten besitzen keine ausgehenden Äste mehr, sie werden auch Blätter (leaves) genannt.

Binärer Suchbaum
Grundaufbau eines binären Suchbaumes

Die Idee von binären Suchbäumen ist nun, den Baum so anzuordnen, dass bei jedem Knoten der linke ausgehende Ast auf einen Unterbaum mit kleineren Zahlen als die Zahl des Knotens und der rechte auf einen Unterbaum mit grösseren Zahlen als die Zahl des Knotens zeigt. So entsteht ein besonderer Baum.

Suchbaum
Suchbaum (Suche nach Zahl 25 dargestellt)

Will das System nun eine Zahl in diesem Baum suchen, so beginnt es beim obersten Knoten des Baumes. Mit einem Zahlenvergleich wird überprüft, ob die Zahl des Knotens grösser bzw. kleiner als die gesuchte Zahl ist. Entsprechend folgt es dem linken bzw. rechten Ast des Knotens. Dies wird solange weitergeführt, bis entweder der Knoten mit der richtigen Zahl gefunden wurde, oder der Ast, dem weiter gefolgt werden sollte, nicht mehr vorhanden ist. Im ersten Fall hat das System die Zahl gefunden, im zweiten Fall befindet sich die gesuchte Zahl nicht in der Menge. Das Hinzufügen von Zahlen in die Menge funktioniert sehr ähnlich. Befindet sich die Zahl noch nicht in der Menge, so folgt das System wiederum den entsprechenden Ästen und fügt schliesslich an der fehlenden Stelle einen neuen Knoten und den verbindenden Ast ein. Das Entfernen von Zahlen ist etwas komplizierter, kann aber vom System ebenfalls schnell ausgeführt werden. Ist der Knoten mit der zu löschenden Zahl gefunden, so kann dieser nicht einfach gelöscht werden, da so die verbindenden Ästen zu eventuellen Unterbäumen dieses Knotens fehlen würden. Folglich muss der zu löschende Knoten zuerst durch Rotationen, welche die Suchbaum-Eigenschaften des Baumes erhalten, zu einem Blatt gemacht werden (mehr dazu später). Da Blätter keine Äste zu Unterbäumen besitzen, kann der Knoten dann gelöscht werden. So weit das Konzept. Warum sollte das Abspeichern in dieser Form aber nun so viel besser als die Umsetzung mit der Liste sein?

Man stelle sich einen perfekten Baum vor: Jeder Knoten – bis auf die Blätter ganz unten – besitzt genau zwei Äste auf Unterbäume. Zählt man nun die Knoten der verschiedenen Ebenen ausgehend vom obersten Knoten, so stellt man exponentielles Wachstum fest: 1, 2, 4, 8, 16, 32, … Die Anzahl der Knoten – und somit auch die Anzahl der Zahlen, die im Baum gespeichert werden können – nimmt sehr schnell zu. Für die Operationen wie das Finden, Hinzufügen oder Löschen von Zahlen ist aber nur die Höhe des Baumes von Bedeutung. Bei 7 Zahlen braucht das System höchstens 3 Zahlenvergleiche, dann ist die Zahl gefunden. Die Anzahl der benötigten Operationen wächst folglich nur wie der Logarithmus der Anzahl Zahlen in der Menge. Bei einer Million Zahlen sind also nur log₂1’000’000 ≅ 20 Operationen nötig. Bei einer Milliarde genügen log₂1’000’000’000 ≅ 27. Das zeigt die Effektivität von Suchbäumen.

Perfekte und entartete Bäume
Ein „perfekter“ Baum (links) gegenüber einem „entarteten“ Baum (rechts)

„Entartete“ Bäume

Ein Problem gibt es aber noch: Wir haben hier von einem „perfekten“ Baum gesprochen. Was garantiert, dass der Baum wirklich „perfekt“ wird? Fügt man beispielsweise die Zahlen in geordneter Reihenfolge dem Baum zu, so entsteht ein entarteter Baum, der eigentlich wieder das Analoge zur besprochenen Liste darstellt. Das Problem des binären Suchbaumes ist also, dass der Baum bestehend aus den gleichen Zahlen auf verschiedene Weisen aufgebaut werden kann. Im schlimmsten Fall liefert er so gegenüber der Liste gar keinen Vorteil mehr. Dies sollte verhindert werden. Genau deshalb braucht es das Konzept des Heaps. Ein Heap ist ein Baum, bei dem jeder Knoten eine Priorität besitzt. Derjenige Knoten mit der höchsten Priorität befindet sich zuoberst. Alle Unterbäume müssen Knoten kleinerer Priorität aufweisen.

Heap
Heap mit Prioritäten (weiss)

Treaps

Der Treap verbindet die Konzepte des Suchbaumes und des Heaps: Jeder Knoten besitzt eine Zahl (key), eine zufällige Priorität (priority) und maximal zwei ausgehende Äste (pointers). Wiederum müssen alle Knoten des linken Unterbaumes eines Knoten eine kleinere Zahl aufweisen und diejenigen im rechten Unterbaum eine grössere. Dabei muss aber auch die Heap-Eigenschaft erfüllt werden: Alle Knoten in den Unterbäumen eines Knotens müssen eine kleinere Priorität aufweisen als der Knoten selber. Somit wird der Treap eindeutig: Zuoberst befindet sich der Knoten mit der grössten Priorität. Der linke Ast zeigt auf denjenigen Knoten, der im Unterbaum der Knoten mit kleineren Zahlen die grösste Priorität besitzt. Analog zeigt der rechte Ast auf denjenigen Knoten, der im Unterbaum der Knoten mit grösseren Zahlen die grösste Priorität besitzt. Dies wird so weitergeführt und der ganze Baum kann eindeutig aufgebaut werden (mit vollständiger Induktion beweisbar). Die zufällige Wahl der Prioritäten „garantiert“ unter den Gesetzen der Wahrscheinlichkeit einen annehmbar „perfekten“ Baum.

Treap
Treap mit Zahlen (schwarz) und Prioritäten (weiss)

Das Auffinden von Zahlen im Treap funktioniert gleich wie zuvor. Das Hinzufügen von Zahlen wird allerdings etwas komplizierter: Wie zuvor fügt man einen neuen Knoten an der benötigten Stelle an, da dieser aber nun eine zufällige Zahl als Priorität besitzt, könnte eventuell die Heap-Eigenschaft verletzt sein (wenn die Priorität grösser ist als diejenige des Knotens darüber).

Einfügen einer neuen Zahl
Einfügen einer neuen Zahl in den Treap. Die Heap-Eigenschaft wird verletzt und muss nun durch Rotationen wiederhergestellt werden.

In diesem Fall müssen Rotationen durchgeführt werden, welche die Suchbaum-Eigenschaften erhalten. Diese sind unten dargestellt:

Rotationen bei Suchbäumen
Rotationen von Unterbäumen, welche die Suchbaumeigenschaften erhalten.

Ist die Priorität des rechten Knotens zu gross, so wird eine Linksrotation durchgeführt, ist umgekehrt diejenige des linken zu gross, so wird gegen rechts rotiert. Man sieht leicht, dass dabei die Suchbaum-Eigenschaft erhalten bleibt. Das Löschen von Zahlen kann ebenfalls mit diesen Rotationen umgesetzt werden. Dabei setzt man die Priorität des zu löschenden Knoten auf -1 (kleiner als alle möglichen Prioritäten) und führt so lange Rotationen durch, bis die Heap-Eigenschaft wieder erfüllt ist. Nun ist der zu löschende Knoten zwingend ein Blatt des Treaps und kann somit entfernt werden.

Ich habe das Konzept des Treaps in der Programmiersprache C++ als Klasse umgesetzt. Der Quellcode ist am Ende dieses Beitrages zu finden. Die besprochenen Funktionen (Suchen, Hinzufügen, Löschen) und noch weitere sind als Memberfunktionen der Klasse Treap umgesetzt. Ich habe die Funktionen getestet, falls der Code aber dennoch Fehler enthalten sollte, wäre ich an Feedback interessiert.

 

Quellen

Quellcode Treap (C++): treap.cpp

Quelle Beitragsbild: Wikipedia
Quelle: Vorlesung Informatik für Mathematiker und Physiker, ETH

Rapid sucht Objekte

Das Fahrzeug Rapid kann nun Objekte anhand ihrer Farbe erkennen. Dazu wird der Rapid vor ein gewünschtes Objekt gestellt und das Selbststeuerungs-Programm gestartet. Der eingebaute Raspberry Pi 2 schiesst nun über das Kamera-Modul ein Foto und liest die Pixelfarben von Hundert Pixeln (ein 10×10-Quadrat) in der Mitte des Bildes aus. Dann berechnet er die durchschnittliche Farbe (den RGB-Wert) dieser Hundert Pixel. Diese Farbe wird in der Folge als gesuchte Farbe bezeichnet.

Aufnahme vorher
Aufgenommenes Bild
Aufnahme nachher
10×10-Quadrat (schwarz eingezeichnet)

Anhand der gesuchten Farbe werden nun Objekte verglichen. Der Rapid schiesst laufend weitere Fotos, erkennt Objekte ähnlicher Farbe und steuert auf sie zu. Als „ähnlich“ gilt eine Farbe, wenn alle ihre RGB-Werte nicht mehr als ± 20 von der gesuchten Farbe abweichen.

Suche

Unten ist ein aufgenommenes Foto des Rapid zu sehen. Darunter sieht man das gleiche Foto nach der Bildauswertung. Bereiche, die eine ähnliche Farbe wie die gesuchte Farbe aufweisen, sind weiss eingezeichnet, alle anderen schwarz. Der Schwerpunkt der weissen Bereiche ist mit dem grün-gelben Quadrat gekennzeichnet. Die Farbe dieses Quadrates stellt die gesuchte Farbe dar. Da sich der Schwerpunkt ungefähr in der Mitte des Bildes befindet, fährt der Rapid nun geradeaus.

Aufnahme vorher
Originalbild
Aufnahme nachher
Bildauswertung

Hier ist ein weiteres Bild-Paar zu sehen. Wiederum zeichnet der Rapid die Bereiche mit Ähnlichkeit zur gesuchten Farbe weiss, der Schwerpunkt wird mit dem gelb-grünen Quadrat angezeigt. Da sich der Schwerpunkt nun eher rechts im Bild befindet, steuert der Rapid leicht nach rechts.

Aufnahme vorher
Originalbild
Aufnahme nachher
Bildauswertung

Wird nirgends auf dem Bild eine ähnliche Farbe zur gesuchten Farbe gefunden (im unteren Bild sind keine weissen Bereiche zu sehen), so führt der Rapid eine Linksdrehung aus, um zu sehen, ob sich irgendwo sonst im Raum noch ein gesuchtes Objekt befindet.

Aufnahme vorher
Originalbild
Aufnahme nachher
Bildauswertung

Video

Auf folgendem Video ist die ganze Suche zu sehen:

Quellen

Quelle Bilder: Luc Schnell
Quelle Video: Luc Schnell (auf Youtube)

Projekt Rapid

Rapid

Das Fahrzeug Rapid (Raspberry Pi drive) habe ich diesen Sommer gebaut. Die Hauptkomponenten sind ein Raspberry Pi 2, eine L298-Brücke (zum Ansteuern der Motoren), zwei Getriebemotoren und ein 7,2 V RC-Akku. Das Gehäuse ist eine einfache Tupperbox (aus der Brockenstube). In einem ersten Schritt habe ich das Fahrzeug so gebaut, dass man es entweder über WLAN oder Bluetooth fernsteuern kann. In der nächsten Zeit werde ich daran arbeiten, dass der Rapid durch eine Kamera die Steuerung selber übernehmen kann.

P1040352

Funktionsweise

Das Fahrzeug ist folgendermassen aufgebaut: Die L298-Brücke versorgt die Motoren mit der für die Drehrichtung und -geschwindigkeit erforderlichen Spannung bzw. Leistung. Gespiesen wird sie selber vom RC-Akku (befindet sich unten im Rapid), die Befehle erhält sie vom Raspberry Pi (über die GPIO-Pins). Der Rapid kann nur über die Drehgeschwindigkeit der Räder gesteuert werden, da man die Achsen nicht bewegen kann. Der technische Begriff dazu lautet Pulse Width Modulation (PWM). Soll das Fahrzeug beispielsweise eine Linkskurve vollführen, so sendet der Raspberry Pi über die Pins die Information, dass die Räder rechts schneller drehen sollen als diejenigen links. Im Extremfall (um sich auf der Stelle zu drehen) kann man sogar die linken Räder rückwärts drehen lassen. Die Fernsteuerung funktioniert entweder über WLAN (SSH-Verbindung mit dem Raspberry Pi) oder Bluetooth (da Wii-Vernbedienungen über Bluetooth kommunizieren, kann man eine solche verwenden).

Video

Das folgende Video zeigt den Startprozess und die Fernsteuerung des Rapid:

Arbeitsschritte

Zuerst erfolgte das Zusammenbauen der einzelnen Komponenten. Die Motoren erhielt ich als Bauset. Leider waren die mitgelieferten Achsenstäbe zu kurz für die Tupperbox, deshalb musste ich noch längere nachbestellen. Den Raspberry Pi habe ich mit dem System Raspbian in Betrieb genommen (gute Anleitungen dazu gibt es auf raspberrypi.org).

Als nächsten Schritt baute ich die Komponenten in die Tupperbox ein. Die L298-Brücke habe ich etwas erhöht, damit mehr Luft durchströmen kann und das Bauteil nicht überhitzt. Die Räder sind mit Madenschrauben an den Motorachsen fixiert. Die beiden Motoren habe ich an der Unterseite der Tupperbox festgeschraubt.  Nicht definitiv fixiert habe ich den Raspberry Pi, damit er noch aus der Box herausgenommen und an einen Bildschirm angeschlossen werden kann.

Der dritte Schritt bestand aus der Verkabelung. Hier muss sehr vorsichtig vorgegangen werden, da Fehler nicht verziehen werden und durchaus in einem kaputten Raspberry Pi enden können (was bei mir unglücklicherweise geschah). Im zweiten Anlauf hat es dann aber funktioniert.

Während dem letzten Schritt musste der Raspberry Pi noch programmiert werden, damit er auf Benutzereingaben reagieren und das Fahrzeug steuern kann. Ich habe dazu extra die Programmiersprache Python gelernt. Mit ihrer raffinierten Einfachheit passt sie sehr gut zum Raspberry Pi. Damit war der Bau des Rapid abgeschlossen.

 

Quellen

Quelle Bilder: Luc Schnell
Quelle Video: Luc Schnell (auf Youtube)

500 Milliarden Worte

Historischer_Bibliothekssaal

„In Büchern liegt die Seele aller gewesenen Zeit.“ So lautet ein Zitat des schottischen Historikers Thomas Carlyle (1795-1881). Damit hat er sicher nicht unrecht. Wäre es beispielsweise nicht interessant, sich durch die Bücher einer ganzen Bibliothek zu lesen und zu schauen, was die Autoren zu welcher Zeit beschäftigte? Wenn man untersuchen würde, wie häufig ein bestimmtes Wort in den Büchern einer gewissen Zeit vorkam, so könnte man viel über die Vergangenheit erfahren. Zu welcher Zeit gewann beispielsweise das Wort „Kolonie“ in Büchern an Bedeutung? Wann wurde „Mondlandung“ oft erwähnt? Wie sieht es beispielsweise mit „Telegramm“, „Fax“, „E-Mail“ oder „SMS“ aus?

Wahrscheinlich haben sich Jon Orwant und Will Brockman, zwei Mitarbeiter von Google,  ähnliche Gedanken gemacht. Jedenfalls haben sie 2010 das Tool Google Ngram Viewer veröffentlicht. Dieses basiert auf 5.2 Millionen Büchern (mit insgesamt über 500 Milliarden Wörtern), die zwischen 1500 und 2008 veröffentlicht und im Rahmen von Google Books digitalisiert worden sind. Mit Google Ngram Viewer kann man genau wie oben beschrieben ein bestimmtes Wort suchen und erhält ein Liniendiagramm, das dessen Häufigkeit in der Literatur im Laufe der Zeit darstellt. Meiner Meinung nach lohnt es sich, die Seite zu besuchen. Die Antworten zu den oben stehenden Fragen sind hier aufgelistet:

 

1. Kolonie

Die Häufigkeit der Verwendung des Wortes „Kolonie“ begann im deutschen Sprachraum um 1880 stark zuzunehmen. Dies ist wohl kaum ein Zufall, da zu dieser Zeit der Kolonialismus des deutschen Reiches begann. Um 1945 nimmt die Häufigkeit stark ab. Dieses Jahr wird auch als Ende des Kolonialismus angesehen.

Ohne Titel

2. Mondlandung

Wann hat sie wohl stattgefunden?

Ohne Titel

3. Kommunikationsmittel

Die Bedeutung des Telegramms hat in den letzten 50 Jahren (zumindest in der Literatur) stetig abgenommen. Das Wort „Fax“ hat seine besten Zeiten wohl hinter sich und auch die Bedeutung des E-Mails könnte noch sinken. Die Häufigkeit von „SMS“ nimmt in Büchern langsam zu, ist aber noch nicht sehr hoch.

Ohne Titel

 

Quellen

Beitragsbild: upload.wikimedia.org
Wikipedia: Google Ngram Viewer
Diagramme: Screenshots aus Google Ngram Viewer

Beam me up, Scotty

Easter Eggs

Im Beitrag „Google easter eggs“ vom letzten Mai habe ich einige eingebaute Eastereggs der Google-Suchmaschine aufgelistet. In diesem Beitrag folgen nun weitere versteckte Dinge aus dem Internet und aus Programmen.

Easter Eggs in Microsoft Word

Wenn man bei Word in einem leeren Dokument =rand(200,1) eingibt und dann auf  Enter klickt, wird das ganze Dokument mit Text gefüllt. Je nach Version kann dieser aus dem Satz „Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.“ (interessant weil er jeden Buchstaben des Alphabets enthält) oder der Bedienungsanleitung von Word bestehen.

Easter Eggs in Webdings

Eine andere Besonderheit ist in der Schriftart Webdings eingebaut. Gibt man die Abkürzung NYC ein und wechselt dann auf diese Schriftart, so erscheinen die Symbole eines Auges, eines Herzens und einer Stadt. Dies soll so viel wie „I (eye) love New York“ bedeuten. Bei der Schrift Wingdings wird NYC zu einem Totenkopf, einem Davidsstern und einem Daumen, der nach oben zeigt. Einige glauben dies sei eine (unpassende) Anspielung auf die Geschehnisse von 9/11. Laut den Herstellern der Schrift soll es aber reiner Zufall sein.

Easter Eggs in Youtube

Gibt man den Spruch beam me up, scotty aus Star Trek in das Suchfeld von Youtube ein, so werden die Suchergebnisse „hereingebeamt“.

Bei der Eingabe fibonacci reihen sich die Ergebnisse in der Fibonacci-Schneckenform an.

Das Eingeben der Tastenkombination 1980 während des Abspielen eines Videos startet das Retro-Spiel „Missile Command“, bei dem man das Video von herunterfallenden Bomben beschützen muss.

Easter Eggs in Wikipedia

Auch Wikipedia hat eine (beschränkt) versteckte Besonderheit vorzuweisen. Klickt man auf der Seite Easter Egg beim Foto auf den Igel, so erscheint ein Bild.

Easter Eggs in Facebook

Auf Facebook sind hinter den Zeichenkombinationen   (^^^)   <(„)   :|]    :putnam:   die Smileys eines Hais, eines Pinguins, eines Roboter und des Kopfes eines Facebook-Mitarbeiters versteckt.

Easter Eggs in Google Calculator

Was the answer to life the universe and everything + the number of horns on a unicorn gibt, kann man sich vom Google Calculator ausrechnen lassen. Wer „The Hitchhiker’s Guide to the Galaxy“ kennt, kann es auch im Kopf ausrechnen. Alle anderen: Don’t panic.

 Quellen

Quelle Beitragsbild: wwwai.wu-wien.ac.at

Illegale Farben

lucsblog Kopie

Viele DVDs und Programme werden heute mit geheimen Schlüsseln (Zahlen oder Buchstaben) kodiert, so dass sie nicht illegal vervielfältigt werden können. Wenn also diese Codes geknackt und über das Internet verbreitet werden, so kann dies zu einem grossen Problem für die Hersteller werden. Deshalb fordern einige, dass das Verbreiten von geheimen Schlüsseln für illegal erklärt wird. Somit gäbe es dann illegale Zahlen- oder Buchstabenfolgen. Aber es geht sogar noch einen Schritt weiter. Jeder Buchstabe kann in Zahlen und diese dann weiter in eine hexadezimale Zeichenkette (16er-System) umgewandelt werden. Diese werden in der Informatik gebraucht, um Farben zu definieren. So kann dann der Schlüssel als eine Kombination verschiedener Farben weitergegeben werden (was heutzutage auch so gemacht wird). Somit gibt es Farben, die nicht veröffentlicht werden sollten. Aber eine Farbe kann man ja auch nicht wirklich per Gesetz verbieten…

Beispiel: Von Buchstaben zu Farben

Da ich hier nicht illegale Schlüssel verbreiten möchte, nehme ich als Beispiel die Folge „LUCSBLOG“. Diese Buchstabenfolge kann mit der ASCII-Zeichenkodierung in binäre Zahlen (2er-System) umgewandelt werden. Die Zeichenfolge sieht dann so aus:

L = 01001100
U = 01010101
C = 01000011
S = 01010011
B = 01000010
L = 01001100
O = 01001111
G = 01000111

„LUCSBLOG“ wurde also nun zur Zahl „01001100 01010101 01000011 01010011 01000010  01001100 01001111 01000111“. Im Dezimalsystem lautet diese Zahl „5500376544776572743“ und im Hexadezimalsystem „4C554353424C4F47″. Eine Farbe besteht in der Informatik aus einer 6-stelligen Hexadezimalzahl. Es ergeben sich somit die Farben „4C5543“ und „53424C„, die restlichen Ziffern („4F47“) bleiben übrig. In einem Mal- oder Bildbearbeitungsprogramm kann man nun diese Farben in ein Bild malen. Den Rest schreibt man einfach unten hin. Die Farben im Beitragsbild entsprechen der Buchstabenfolge „LUCSBLOG“.

Schon hat man aus einer Text- oder Zahlenfolge eine Farbfolge gemacht. Diese sollte jedoch, wenn die ursprüngliche Folge ein geheimer Schlüssel war, nicht unbedingt verbreitet werden…

 

Nützliche Links:
Text zu Binär – Umrechner
Binär – Umrechner
Farben anzeigen

Quellen:
Illegal Numbers – Numberphile

19. Januar 2038

iStock_000009996218Medium-Kopie

Im Jahr 2038 wird das Ende unserer Zeit sein, wenn wir nicht vorher handeln. Das Ganze ist aber nicht schon wieder eine neue Weltuntergangs-Theorie, sondern hat mit Informatik und Mathematik zu tun…

Viele heutige Computersysteme berechnen die aktuelle Uhrzeit, indem sie die verstrichenen Sekunden seit dem 1. Januar 1970 00:00:00 (Zeitzone ±0)  abzählen. Diese werden als vorzeichenbehaftete 32-Bit-Zahl gespeichert. Eine 32-Bit-Zahl besteht aus 32 Stellen, die entweder eine 1 oder eine 0 enthalten können. Es können also 232 (= 4’294’967’296) verschiedene Zahlen dargestellt werden. Da es eine vorzeichenbehaftete Zahl ist (+ und -), können somit die Zahlen von -2’147’483’648 bis +2’147’483’647 (beim + als letzte Ziffer eine 7, da die 0 ja auch dazugehört) gespeichert werden. Umgerechnet bedeutet das die Zeitspanne vom 13. Dezember 1901 20:45:52 Uhr bis zum 19. Januar 2038 um 3:14:07 Uhr. Computersysteme, welche die aktuelle Zeit als vorzeichenbehaftete 32-Bit-Zahl speichern, werden also vom 19. Januar 2038 zurück zum 13. Dezember 1901 springen. Dies kann beispielsweise bei Banken verheerende Folgen haben. Deshalb sollten sie vorher auf 64-Bit umsteigen, womit dann Daten bis ins Jahr 292’277’026’596 dargestellt werden können (sollte vorerst reichen). Mit unserer „32-Bit-Zeit“ werden wir nur noch höchstens ca. 25 Jahre leben können, dann wird alles zu Ende gehen…

Übrigens: Diesen Beitrag habe ich so eingestellt, dass er am 5. Juli 2013 um 03:53:20 Uhr (Zeitzone ±0) veröffentlicht wird. Warum wohl?

 

Quellen: Unixzeit (Wikipedia) und „End of Time (Unix)“, Numperphile (Youtube)

Quelle Beitragsbild: erlebnisreise-mexiko.de