#2 - JANUAR 2025

Themen in dieser Ausgabe:

Hallo ,

war es nicht gerade erst Januar? Hier ist die zweite Ausgabe der Anomalie und sie ist etwas verspätet. Sozusagen eine Zeitanomalie. In der ersten Ausgabe gab es auch schon mindestens eine Anomalie. Da stand nämlich "Januar 2025", obwohl es noch Dezember 2024 war. Na ja, ich hoffe, dass in dieser Ausgabe keine weiteren Anomalien versteckt sind.

In dieser Ausgabe habe ich dir eine Geschichte über Affen, Mathematik und Komplexität mitgebracht. Ich finde sie total faszinierend, weil sie mir selbst gezeigt hat, wie schlecht ich mir Komplexität und exponentielles Wachstum vorstellen kann.

Außerdem gibt es noch eine Geschichte über eine berühmte Informatikerin. Das möchte ich in den nächsten Ausgaben fortsetzen, denn es gibt noch viele tolle Frauen in der Informatik.

Übrigens wird der Podcast im März 100. Genauer gesagt erscheint die Folge 100, die eigentlich schon die 101 ist, da ich den Podcast damals mit der Folge 0 begonnen habe. In der Informatik fängt man schließlich mit 0 an. Und für die Jubiläumsfolge freue ich mich über kurze Audiobeiträge. Die Details gibt es weiter unten.

Ich wünsche Dir einen tollen Monat und bin zuversichtlich, dass die Februarausgabe der Anomalie noch bis Ende Februar in deiner Inbox ist.

Wenn du Feedback für mich hast, kannst du mir gerne direkt auf diese Mail antworten.

Herzliche Grüße
Wolfgang

Das Affenpuzzle

Als Student las ich ein Buch über unlösbare Probleme in der Informatik. Es hieß Das Affenpuzzle und weitere bad news aus der Computerwelt und stammte von David Harel. Neulich fiel es mir wieder in die Hände, und ich musste über die titelgebende Geschichte nachdenken. Sie faszinierte mich genauso wie damals.

Beim Affenpuzzle handelt es sich um ein Legespiel mit quadratischen Kärtchen. Hier kannst du dir ein Beispiel anschauen. Auf jeder Karte sind vier halbe Affen (jeweils die obere oder untere Hälfte) in unterschiedlichen Farben abgebildet. Insgesamt gibt es vier verschiedene Farben. Das Ziel des Spiels besteht darin, diese Karten zu einem großen Quadrat zu legen, und zwar so, dass an den Kanten jeweils komplette Affen in der passenden Farbe entstehen. Die Gesamtzahl der Karten ist eine Quadratzahl. Also 2x2=4, 3x3=9, 4x4=16, 5x5=25, etc. Zum Lösen dürfen die Karten beliebig gedreht werden.

Zweifelsohne sind solche Puzzles lösbar. Die einfachsten Varianten mit nur 4 oder 9 Karten wird man durch Ausprobieren in einer vertretbaren Zeit korrekt zusammenfügen können. Wenn die Anzahl der Karten steigt, wird das jedoch zunehmend schwerer. Beim Affenpuzzle kann man nämlich recht einfach feststellen, ob eine Lösung korrekt ist. Man muss dazu ja lediglich alle Kanten begutachten und überprüfen, ob sich dort ein einfarbiger und vollständiger Affe befindet. Und es ist gut vorstellbar, dass das auch bei großen Puzzles mit vielleicht 10x10 Karten auch schnell durchführbar ist.

Ganz anders sieht es aber beim Finden der richtigen Kombination aus. Denn es gibt kein Verfahren, mit dem dies schneller geht, als alle Kombinationen durchprobieren. Es existiert also kein effizienter Algorithmus für dieses Problem.

Zum Glück haben wir ja Computer. Wenn es um stumpfes Ausprobieren geht, dann wird das der elektronische Freund und Helfer ja schnell erledigen können. Oder? Tja, das hängt natürlich von der Anzahl der Möglichkeiten ab, die durchprobiert werden müssen. Können das bei einem so einfachen Spiel viele sein?

Lasst uns das mal für die Kantenlängen 1-5 durchrechnen. Bei nur einer einzigen Karte könnte man niemals einen kompletten Affen bekommen. Das ist langweilig. Bei einer Kantenlänge von zwei, also vier Karten sieht das schon anders aus. Die Anzahl der möglichen Kombinationen setzt sich aus zwei Faktoren zusammen. Zum einen die Permutationen der vier Karten, also die verschiedenen Reihenfolgen, an die die Karten gelegt werden.

Für die erste Position kann man immer aus vier Karten wählen. Bei der zweiten kann man immer aus drei wählen, bei der dritten aus zwei und bei der letzten gibt es immer nur noch eine Karte. Um die Summe aller möglichen Permutationen zu bekommen, muss man nun lediglich die einzelnen Möglichkeiten miteinander multiplizieren. Also in diesem Fall: 4x3x2x1. Wenn ihr vier unterschiedliche Münzen zur Hand nehmt, dann könnt ihr das auch mal selbst durchspielen. Ich finde, dass solche mathematischen Konzepte manchmal schwierig sind, wenn man nur darüber nachdenkt. Ein praktisches Ausprobieren hilft mir da immer. Als Alternative zu den Münzen kann man natürlich auch ein kleines Programm schreiben. Diese Berechnung entspricht übrigens der Fakultätsfunktion und 4x3x2x1 kann man daher auch so schreiben: 4!.

Die Fakultät ist dafür bekannt, dass sie sehr schnell enorm groß wird. Das ist leicht nachvollziehbar, da ja in jedem Schritt das komplette vorherige Ergebnis mit der nächsten Zahl nochmal multipliziert wird. Schauen wir uns einmal die möglichen Permutationen der Kärtchen für ein Affenpuzzle mit einer Seitenlänge von 2-5 an:

4! = 24
9! = 362.880
16! = 20.922.789.888.000
25! = 15.511.210.043.000.000.000.000.000

Ich staune bei solchen Zahlen immer wieder aufs Neue. Beim Affenpuzzle ist es jedoch mit den Permutationen der Karten noch nicht getan. Denn jede Karte kann rotiert werden und so vier mögliche Ausrichtungen einnehmen. Doch wie viele Varianten einer einzelnen Permutation gibt es?

Bei nur einer Karte wären es vier. Bei zwei Karten könnte man für jede der vier möglichen Ausrichtungen der ersten Karten die zweite Karte ebenfalls vier mal unterschiedlich ausrichten. Das wären dann also 4x4 unterschiedliche Ausrichtungen. Bei drei Karten könnte man dann zusätzlich für jede Ausrichtung der zweiten Karte die dritte Karte viermal unterschiedlich ausrichten. Insgesamt wären das 4x4x4 unterschiedliche Ausrichtungen. Man kann hier gut ein Muster erkennen. Die Anzahl der Karten findet sich in der Anzahl der Vieren wieder, die miteinander multipliziert werden. Mathematisch kann man das abkürzen und als Potenz schreiben. Also Vier hoch n, wobei n die Anzahl der Karten ist. Aus 4x4x4 wird so 4^3 (sprich vier hoch drei). Und auch hier wird schnell klar, dass enorm große Zahlen entstehen, da ja für jede zusätzliche Karte alles bisherige nochmal vervierfacht wird. Und diese Zahlen bekommen wir dann für unser Beispiel:

4^4 = 256
4^9 = 262.144
4^16 = 4.294.967.296
4^25 = 1.125.899.906.842.624

Um nun die endgültige Anzahl der Möglichkeiten zu erhalten, müssen wir beide Zahlen miteinander multiplizieren. Denn für jede einzelne Permutation können ja alle Karten nochmal beliebig gedreht werden. Die Anzahl aller Möglichkeiten berechnet sich also aus der Anzahl der Permutationen der Reihenfolge multipliziert mit der Anzahl der unterschiedlichen Ausrichtungen aller Karten. Viel Text für eine kurze Formel: n! * 4^n

Und wir bekommen wirklich große Zahlen:

4! * 4^4 = 6.144
9! * 4^9 = 95.126.814.720 (Das sind schon ~95 Milliarden)
16! * 4^16 = 9.862.698.310.000.000.000.000.000.000.000
25! * 4^25 = 74.640.699.430.000.000.000.000.000.000.000.000.000.000.000.000.000
Das sind absurd große Zahlen. Zu viel für den Taschenrechner Aber was ist denn nun mit unseren Computern? Die sind doch schnell und vor allem werden sie laufend schneller.

Nehmen wir einmal an, dass ein Computer 1000 Kombinationen pro Sekunde testen kann. Das wären dann pro Stunde 3,6 Millionen. Für die Variante mit 9 Karten bräuchte unser Computer dann rund 26.424 Stunden, was rund 3 Jahren entspricht. Puh, ganz schön lange. Aber Computer sind ja auch in Wirklichkeit viel schneller. Was also, wenn der Computer 1 Million Mal schneller wäre und nicht 1000, sondern 1 Milliarde Möglichkeiten pro Sekunde prüfen könnte?

Die Variante mit den 9 Karten kennt rund 95 Milliarden Kombinationen, sodass man rund 95 Sekunden braucht, um alle Möglichkeiten durchzuprobieren. Aber schon bei der nächsten Stufe hätte man wieder ein Problem. Denn die Variante mit einer Kantenlänge von vier bräuchte rund 2,85 Millionen Jahre, falls man 1 Milliarde Kombinationen pro Sekunde testen könnte. Bei der Variante mit der Kantenlänge 5 käme man sogar auf 554 Trillionen Jahre.

Und da wird schnell klar, dass es völlig egal ist, wie leistungsfähig ein Computer ist, bzw. wie stark die Leistungsfähigkeit anwächst. Durch die Erhöhung der Kantenlänge um nur eine Karte wächst die Anzahl der möglichen Kombinationen extrem an. Man spricht hier von einem exponentiellen Wachstum. Die Anzahl der Möglichkeiten steigt beim Affenpuzzle nicht mit einer konstanten Rate (also linear), sodass bei einer Verdopplung der Karten beispielsweise die Anzahl der Möglichkeiten fest verdoppelt oder auch verzehnfacht wird.

Stattdessen sorgt jede einzelne zusätzliche Karte für immer mehr Möglichkeiten als alle Karten davor, da die Varianten einer jeden Karte miteinander multipliziert werden. Und in diesem Beispiel sogar doppelt - einmal im Rahmen der Fakultät bezüglich der Position und noch einmal bezüglich der Rotation der Karte.

Und an dieser Stelle ist es auch egal, wie schnell ein Computer ist. Selbst wenn ein Gerät nicht 1 Milliarde, sondern 1 Billion an Möglichkeiten pro Sekunde prüfen könnte, hätte das bald keine Auswirkung mehr auf die Berechenbarkeit. Denn dann bräuchte man immer noch 554 Billionen Jahre, um das Affenpuzzle mit einer Kantenlänge von 5 zu lösen. Und es ist aktuell nicht mehr vorstellbar, dass ein Computer in der Zukunft imstande sein wird, das Rätsel zu lösen. Die Leistungsfähigkeit von Computern hat sich in den letzten 40 Jahren stetig vergrößert. Aber eben bei weitem nicht exponentiell. Es gibt ja das bekannte Mooresche Gesetz (benannt nach Gordon Moore, einem der Mitgründer von Intel), das besagt, dass sich die Menge der Transistoren in integrierten Schaltkreisen alle 18 Monate verdoppelt. Davon kann man in etwa ableiten, dass sie die Leistungsfähigkeit von Computern ebenfalls alle 18 Monate verdoppelt. Und bisher passt das auch mehr oder weniger. Das ist beeindruckend, aber bei weitem kein exponentielles Wachstum.

Aber was bleibt nun vom Affenpuzzle? Für mich die Erkenntnis, dass Komplexität manchmal auf den ersten Blick nicht sichtbar ist. Und es kann absolut faszinierend sein, solch einer Sache auf den Grund zu gehen. Ich kann das Buch von David Harel wärmstens empfehlen. Es hat auch nach über 20 Jahren nichts von seiner Faszination verloren. Und natürlich taugt die Geschichte vom Affenpuzzle auch als perfektes Smalltalk Thema für die nächste Party. Oh, und falls ihr in der nahen Zukunft einmal einer KI gegenübersteht und diese lange beschäftigen müsst, dann schlagt doch mal die Lösung eines Affenpuzzles vor.

Wie hat euch diese Geschichte gefallen? Ich freue mich über euer Feedback. Dazu könnt ihr mir einfach auf diese Mail antworten.

Quellen

Bedeutende Frauen der Informatik:
Grace Hopper

In dieser Ausgabe der Anomalie habe ich euch wieder eine bedeutende Informatikerin mitgebracht. Vielleicht kennt ihr sie schon aus Folge #9 von den Digitalen Anomalien. Falls nicht, kann ich euch diese Folge nur wärmstens empfehlen. Grace Hopper wird oftmals nur im Zusammenhang mit dem ersten Bug der Computergeschichte genannt. Doch ihre Biografie beinhaltet so viel mehr.

Sie wurde als Grace Brewster Murray am 9. Dezember 1906 in New York City geboren. In einer Zeit, in der Frauen nicht die gleichen Möglichkeiten wie Männer hatten, zeigte sie schon als Kind eine große Neugier und ein starkes Interesse an Mathematik. Ihr Vater unterstützte sie und setzte sich dafür ein, dass sie die gleichen Chancen wie ein Mann erhielt – was zu dieser Zeit alles andere als selbstverständlich war. Grace besuchte das Vassar College in Poughkeepsie, New York, und schloss dort mit einem Bachelor in Physik ab, und zwar mit Auszeichnung. Danach machte sie ihren Master in Mathematik und Physik an der renommierten Yale University, ebenfalls mit Auszeichnung.

1930 heiratete sie Vincent Hopper und arbeitete von 1931 bis 1943 als Mathematiklehrerin am Vassar College. 1934 promovierte sie in Mathematik an der Yale University und wurde die erste Frau, die dort diesen Titel erhielt. Nach dem Angriff auf Pearl Harbor meldete sich Hopper 1943 freiwillig zur US Navy. Zunächst wurde sie abgelehnt, da sie die Anforderungen nicht erfüllte, doch später trat sie der Navy Reserve bei und wurde nach Harvard zum Bureau of Ships Communication versetzt, um dort an einem Geheimprojekt zu arbeiten.

Dabei handelte es sich um den Mark I, einen elektromechanischen Rechner mit 15 m Länge und 750.000 beweglichen Teilen. Er konnte grundlegende mathematische Operationen durchführen und wurde für militärische Berechnungen genutzt. Grace Hopper war die dritte Person, die den Rechner programmierte, und sie erstellte das Benutzerhandbuch, das als das erste seiner Art gilt.

Am 9. September 1947 fand Hopper eine Motte, die sich in einem Relais des Nachfolgers Mark II verklemmt hatte. Sie dokumentierte dies als den „ersten tatsächlichen Fall eines Bugs“ und prägte damit den Begriff in der Computerwelt.

Nach dem Krieg wurde Hopper zu einer Expertin in einem aufstrebenden Bereich. Von 1949 bis 1952 arbeitete sie bei der Eckert-Mauchly Computer Corporation und von 1952 bis 1971 für die UNIVAC Division der Sperry Rand Corporation.

Dort entwickelte sie A-0, den ersten Compiler. Das war ein Programm, das leicht verständliche und ans Englische angelehnte Begriffe in eine für Computer verständliche Sprache übersetzte. Die erste Programmiersprache, die dies nutzte und ebenfalls von Grace Hopper entwickelt wurde, war Flow-Matic. Grace Hopper spielte eine entscheidende Rolle bei der Entwicklung von COBOL, einer Programmiersprache, die die Programmierung vereinfachte und portabler machte. Sie war als Beraterin tätig und bemerkte später, dass COBOL zu 95 % auf Flow-Matic basierte.

Hopper blieb bis 1966 in der Reserve der US Navy und trat dann in den aktiven Dienst zurück, um bei verschiedenen Computerproblemen zu helfen. Sie wurde Director of Navy Programming Language Group und arbeitete fast 20 Jahre an einem Projekt zur Standardisierung von Programmiersprachen. 1988 erreichte sie den Dienstgrad Rear Admiral (lower half), den höchsten Rang, den eine Frau bis dahin erreicht hatte.

Grace Hopper starb am 1. Januar 1992 und wurde mit allen militärischen Ehren auf dem Nationalfriedhof Arlington beerdigt. Sie hinterließ ein bedeutendes Erbe in der Informatik und wurde für ihre Beiträge vielfach ausgezeichnet.

Grace Hopper war eine außergewöhnliche Frau und eine Computerpionierin, deren starker Wille und Innovationsgeist bis heute inspirieren. Ich denke gerne an diese beiden Zitate von ihr:

„The most dangerous phrase in the language is, 'We’ve always done it this way.'“

„It's easier to ask forgiveness than it is to get permission.“

Quellen

Links und Leseempfehlungen

Taschenrechner Heute kennt man Taschenrechenr vermutlich als App auf dem Smartphone. Als ich noch zur Schule ging, war es revolutionär, irgendwann einen solarbetriebenen Casio Taschenrechner zu bekommen, den man tatsächlich im Schulunterricht verwenden durfte. Aber egal ob Hardware oder App: Die Usability von Taschenrechnern ist ein Thema für sich.

https://lcamtuf.substack.com/p/ui-is-hell-four-function-calculators

Bilder können täuschen Eine Illustration kann beim Verständnis eines Sachverhalts helfen. Dabei muss man aber auch aufpassen, dass man sich nicht in die Irre führen lässt. Dieser kleine Artikel ist ein gutes Beispiel dafür.

https://www.charlespetzold.com/blog/2025/01/Very-Wrong-Math.html

Eine Geschichte des C64 Mein erster Computer war ein gebrauchter Commodore VC20. Und danach folgte ein C64, mit dem ich sehr viel Zeit verracht habe. Hier wird die Geschichte des C64 in zwölf ikonischen Objekten erzählt. Eine schöne Zeitreise.

https://www.jesperjuul.net/c64/history/

Die Saturn V Im Jahr 2014 war ich in Florida. Und was besucht man dort? Natürlich das Kennedy Space Center. Das ist ein wirklich magischer Ort, da man sich hier viele Exponate aus der Geschichte der Raumfahrt anschauen kann. Beispielsweise die geborgenen Apollo Kapseln, das Space Shuttle Atlantis oder eine Saturn V Rakete. Und letztere ist wirklich unglaublich groß. Die Konstruktion war eine absolute Meisterleistung und dieser Atrikel geht auf die Entstehungsgeschichte ein.

https://www.smithsonianmag.com/air-space-magazine/we-built-saturn-v-180964759/

Neulich im Podcast

Digitale Anomalien #95: Biber, die aus dem Himmel fallen (Analoge Anomalien #5)

Nach dem Zweiten Weltkrieg stand Idaho vor einem ungewöhnlichen Problem: Biber mussten aus überfüllten Gebieten in entlegene Wildnis umgesiedelt werden. Die Lösung? Einfallsreiche Biologen entwickelten eine Methode, die heute als „Beaver Drop“ bekannt ist – Biber wurden in speziell entwickelten Kisten per Fallschirm aus Flugzeugen abgeworfen.

Diese Episode erzählt die faszinierende und fast unglaubliche Geschichte einer der wohl ungewöhnlichsten Naturschutzaktionen aller Zeiten.

https://digitaleanomalien.de/95-biber-die-aus-dem-himmel-fallen-analoge-anomalien-5/

Digitale Anomalien #96: Der große Postskandal

Als 1999 bei der britischen Post ein neues Softwaresystem namens Horizon eingeführt wurde, war eigentlich schon klar, dass dies nicht reibungslos verlaufen würde. Zu viele Probleme waren im Vorfeld aufgetreten. Aber nachdem bereits eine Milliarde Pfund in das Projekt geflossen waren, wollte man die Software auch nicht einfach aufgeben.

Und so wurden nach und nach 19.000 kleine und unabhängige Postämter, so genannte Sub-Postoffices, mit dem System ausgestattet. Schon bald gab es Beschwerden über fehlerhafte Abrechnungen. Doch die Post wollte das nicht wahrhaben und bezichtigte die Subpostmeister des Diebstahls. Damit begann ein Unrecht, das mehr als zwei Jahrzehnte andauern sollte. Menschen verloren ihr Geld, ihre Freiheit und in einigen Fällen sogar ihr Leben.

Eine Wende zeichnete sich erst ab, als ein Betroffener, Alan Bates, dies nicht mehr hinnehmen wollte. Er kämpfte zwanzig Jahre lang um Gerechtigkeit für sich und andere. Und am Ende hatte er Erfolg.

Diese Episode erzählt die Geschichte des großen Postskandals. Und am Ende gibt es leider kein richtiges Happy End. Denn keine Entschädigung der Welt kann das Leid wieder gut machen, das so viele Betroffene erfahren mussten.

https://digitaleanomalien.de/96-der-grosse-postskandal/

Digital Future #75: Zephyr – Das Echtzeitbetriebssystem für IoT-Geräte

In dieser Folge unterhalte ich mich mit einem Kollegen über das Betriebsystem Zephyr für IoT Geräte. Ich kannte Zephyr vorher noch nicht wirklich und das Gesrpäch gab mir einen ganz guten Überblick über das Thema.

https://digital-future.podigee.io/75-zephyr-das-echtzeitbetriebssystem-fur-iot-gerate

Zeitflimmern #5: The Adam Project
Zusammen mit meinem Freund Matze spreche ich über den Zeitreisefilm The Adam Project. Der Film aus dem Jahr 2022 hat uns gut unterhalten.

https://zeitflimmern.de/episode/the-adam-project

Last, but not least

Der Podcast wird 100 Seit rund drei Jahren gibt es den Podcast Digitale Anomalien und im März wird Folge 100 erscheinen. Das ist ein toller Meilenstein. Den Podcast würde es aber nicht so lange geben, wenn ihn niemand hören würde. Und darum würde ich in Folge 100 gerne euch zu Wort kommen lassen. Ich freue mich über kleine Audio-Einspieler mit einer Länge von 1-2 Minuten. Erzählt mir doch einmal, was euch am Podast gefällt oder wie ihr auf ihn aufmerksam geworden seit. Schickt mir eure Einspieler gerne als mp3 an feedback@digitaleanomalien.de

Die Grobe Pixel Spendenaktion In der letzten Ausgabe hatte ich die Spendenaktion zu Weihnachten angekündigt. Insgesamt sind dabei 852€ zusammengekommen, die Christian und ich zu gleichen Teilen an die Arche und die Amadeu Antonio Stiftung geben. Vielen Dank für eure Unterstützung!

Twitch Im Januar gab es auf Twitch meinen ersten Talk mit einem Gast. Christian war zu Gast und wir haben über den Einsatz von KI Tools in der Softwareentwicklung gesprochen. Das hat Spaß gemacht und ich habe vor, sowas zukünftig öfter zu machen. Außerdem wird es Anfang März zum Release der Folge 100 vom Podcast eine kleine Live Show auf Twitch geben. https://www.twitch.tv/herrschoch

PS: Füge meinen Absender hallo@digitaleanomalien.de deinen Kontakten hinzu, damit der Newsletter auch zuverlässig bei dir ankommt und nicht im Spam landet.

Das Affenpuzzle

Bedeutende Frauen der Informatik: Grace Hopper

Links und Leseempfehlungen

Neulich im Podcast

Last, but not least

Bedeutende Frauen der Informatik:
Grace Hopper