Project Euler

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Project Euler ist eine englischsprachige Website. Sie enthält eine Reihe von Problemstellungen, die mithilfe von Mathematik und Programmierung gelöst werden können. Die Zielgruppe der Website sind Menschen, die an Mathematik und algorithmischer Effizienz interessiert sind und ihre Kenntnisse anwenden und erweitern möchten.[1]

Project Euler wurde im Oktober 2001 von Colin Hughes gegründet. Seine Motivation besteht darin, „dem forschenden Geist eine Plattform zu bieten, um in unbekannte Bereiche einzutauchen und neue Konzepte in einem unterhaltsamen Kontext zu lernen“. Die Seite enthält über 700 Probleme (Stand: Oktober 2020)[2] in unterschiedlichen Schwierigkeitsgraden und es werden regelmäßig neue veröffentlicht. Die Probleme sind so angelegt, dass sie mit einem effizienten Algorithmus, der auf einem mittelmäßig starken Computer ausgeführt wird, innerhalb von einer Minute gelöst werden können. Sobald ein angemeldeter Benutzer das richtige Ergebnis eingetragen hat, erhält er Zugriff auf einen Diskussionsthread zu diesem Problem, in dem die Benutzer ihre unterschiedlichen Lösungsstrategien darstellen können.[1] Erfahrungen aus der Lösung einfacherer Probleme und die diskutierten Lösungsstrategien anderer Nutzer kann er in die Lösung schwierigerer Probleme einbringen.

Die Website ist kostenlos und ohne Anmeldung nutzbar, zur Überprüfung der Ergebnisse und zur Teilnahme an Diskussionen ist jedoch eine kostenlose Registrierung notwendig.

Die Benutzer stammen nach Eigenaussage aus 219 Ländern, wobei die meisten Benutzer aus dem englischsprachigen Raum und Europa kommen sollen. Es soll etwa 1.027.375 registrierte Benutzer geben, die mindestens eines der Probleme gelöst haben (Stand: Juli 2020).[3]

Einige Beispielprobleme[Bearbeiten | Quelltext bearbeiten]

Das erste Problem des Project Euler lautet:

„Wenn wir alle natürlichen Zahlen unter 10 auflisten, die Vielfache von 3 oder 5 sind, so erhalten wir 3, 5, 6 und 9. Die Summe dieser Zahlen ist 23. Finde die Summe aller Vielfachen von 3 oder 5 unter 1000.“[4]

Während dieses Problem noch mit grundlegender Schul-Mathematik und ein paar grundlegenden Operationen in der jeweiligen Programmiersprache gelöst werden kann, bedingt die Lösung anderer Probleme die weit fortgeschrittene Kenntnis mathematischer und informatischer Konzepte, so zum Beispiel Datenstrukturen, Graphentheorie, Zahlentheorie und die Erarbeitung effizienter Algorithmen.

Im Problem 25 muss das Programm die Fibonacci-Folge so lange entwickeln, bis die Zahl 1000 Ziffern lang ist. Dies überfordert die verfügbaren Datentypen der meisten Programmiersprachen bei Weitem. Zum Beispiel ist der Maximalwert eines 32-bit unsigned integer 4.294.967.295 (10 Stellen), während mit 64 bit zwanzig Dezimalstellen möglich sind. So muss die schriftliche Addition aus der Schulmathematik, welche mit einer unbegrenzten Anzahl Dezimalstellen umgehen kann, in ein Computerprogramm überführt werden.

Problem 349 betrifft Langton's Ameise:

„Eine Ameise bewegt sich auf einem Gitternetz, dessen Felder entweder weiß oder schwarz sind. Die Ameise bewegt sich vom einen Feld zum anderen in vier Richtungen (links, rechts, nach oben, nach unten), und zwar nach den folgenden Regeln:
  1. wenn die Ameise auf einem schwarzen Feld ankommt, wechselt die Farbe des Feldes auf weiß, die Ameise dreht sich um 90 Grad nach links, und besucht das nächste Feld;
  2. wenn die Ameise auf einem weißen Feld ankommt, wechselt die Farbe auf schwarz, die Ameise dreht sich um 90 Grad nach rechts, und besucht das nächste Feld.
Wenn die Ameise auf einem Gitternetz mit gänzlich weißen Feldern beginnt, wie viele Felder sind schwarz, nachdem die Ameise 1018 Züge gemacht hat?“[5]

Hier fragt sich etwa, wie das Gitternetz mit der schwarz/weiß-Information gespeichert werden muss, und wie das einmal gespeicherte Gitternetz wachsen kann, falls die Ameise am Rand des Gitters ankommt.

Verwendete Programmiersprachen[Bearbeiten | Quelltext bearbeiten]

Die angemeldeten Teilnehmer können angeben, welche Programmiersprache sie für die Lösung der Aufgaben benutzen. Im Oktober 2017 waren, in absteigender Reihenfolge, Python, C/C++, Java, C#, Haskell, Ruby, PHP, Matlab, Perl und Scala die zehn beliebtesten Programmiersprachen. Auf die ersten vier entfallen 74 % aller angemeldeten Benutzer, auf die beliebtesten zehn Sprachen 87 %, während die beiden wissenschaftlichen Werkzeuge Mathematica und R auf 0,96 % respektive 0,63 % kommen.[6]

Vorübergehende Abschaltung 2014[Bearbeiten | Quelltext bearbeiten]

Am 16. Juni 2014 wurde die Project-Euler-Seite abgeschaltet und durch einen Hinweis ersetzt, der ein nicht näher genanntes Sicherheitsproblem als Grund nennt. Am 22. Juni wurde ein Einbruch, sowie der mögliche Diebstahl der Passwort-Datenbank-Tabelle eingeräumt. Ab 27. Juni konnte die Auskunftsfunktion wieder genutzt werden. Am 16. August 2014 ging die Seite in einer völlig neuen Implementierung online. Unter anderem wird jetzt konsequent auf das Abspeichern von Mailadressen verzichtet.[7]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b About - Project Euler. Abgerufen am 11. September 2020.
  2. Colin Hughes: Recent Problems - Project Euler. Abgerufen am 19. Oktober 2020 (englisch).
  3. projecteuler.net (nur für angemeldete Benutzer zugänglich)
  4. Problem 1, Summe der Vielfachen von 3 oder 5 unter 1.000
  5. Langton's ant problem 349
  6. https://projecteuler.net/languages
  7. projecteuler.net, News