Project Euler

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Project Euler ist eine englischsprachige Webseite. 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 auffrischen, erhalten oder verbessern 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 617 Probleme (Stand: Dezember 2017)[2] von unterschiedlichen Schwierigkeitsgraden. Die Probleme sind so angelegt, dass sie von 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.[3] Erfahrungen aus der Lösung einfacherer Probleme und die diskutierten Lösungsstrategien anderer Nutzer kann er in die Lösung schwererer 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.[4] Es soll etwa 678.142 registrierte Benutzer geben, die mindestens eines der Probleme gelöst haben (Stand: Februar 2017).[5]

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.“[6]

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 weiss 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 weiss,, die Ameise dreht sich um 90 Grad nach links, und besucht das nächste Feld;
  2. wenn die Ameise auf einem weissen 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 weissen Feldern beginnt, wie viele Felder sind schwarz, nachdem die Ameise 1018 Züge gemacht hat?“[7]

Hier fragt sich etwa, wie das Gitternetz mit der schwarz/weiss-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.[8]

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 Implementation online. Unter anderem wird jetzt konsequent auf das Abspeichern von Mailadressen verzichtet.[9]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. projecteuler.net
  2. Colin Hughes: Recent Problems - Project Euler. Abgerufen am 31. Dezember 2017 (englisch).
  3. projecteuler.net (nur für angemeldete Benutzer zugänglich)
  4. projecteuler.net (nur für angemeldete Benutzer zugänglich)
  5. projecteuler.net (nur für angemeldete Benutzer zugänglich)
  6. Problem 1
  7. [1]
  8. https://projecteuler.net/languages
  9. projecteuler.net