Habt ihr schonmal mit genetischen Algorithmen professionell gearbeitet?

[Columbo]

Wieviele gibt es davon nochmal?

\sum^{vector::max\\_size()}\_{i = 0} 2^{i\times sizeof(int) \times CHAR\\_BIT} ~=~ \frac{2^{(vector::max\\_size()+1)\times sizeof(int) \times CHAR\\_BIT} - 1}{2^{sizeof(int) \times CHAR\\_BIT}-1}
(Bitte um Bestätigung, ich kenne keine Formel für das Aufsummieren von Zweierpotenzen mit Faktor im Exponenten, das hier kam nur durch ausprobieren heraus)

Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird?

Ich verwette meinen Daumen, dass es in C++ - wo alles endlich ist, auch der Speicher(?) - immer eine absolute Höchstzahl von Operationen gibt, die >= aller Anzahlen von Operationen endlicher Funktionsdurchläufe ist. Das gilt dann als obere Schranke.

Auch Unsinn

Das musst du mir mal erklären. Wie soll ich wissen, ob das Ergebnis das ich von meiner Funktion erhalte richtig ist?
(Edit: ... aber wie überprüfe ich die Korrektheit dieses Referenzalgorithmus? )

[Bashar]

Arcoth schrieb:

Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird?

Ich verwette meinen Daumen, dass es in C++ - wo alles endlich ist, auch der Speicher(?) - immer eine absolute Höchstzahl von Operationen gibt, die >= aller Anzahlen von Operationen endlicher Funktionsdurchläufe ist. Das gilt dann als obere Schranke.

Endlosschleifen existieren bei dir nicht? Außerdem geht es hier nicht um C++.

Auch Unsinn

Das musst du mir mal erklären. Wie soll ich wissen, ob das Ergebnis das ich von meiner Funktion erhalte richtig ist?

Indem du die Spezifikation anwendest. Beispielsweise ist es für einen Sortieralgorithmus absolut nicht nötig, nochmals zu sortieren. Man muss nur prüfen, ob alle Elemente da sind und ob die Ergebnissequenz richtig angeordnet ist.

Edit: ... aber wie überprüfe ich die Korrektheit dieses Referenzalgorithmus?

Indem du sie beweist.

[Columbo]

Man muss nur prüfen, ob alle Elemente da sind und ob die Ergebnissequenz richtig angeordnet ist.

Ah, ich dachte da eher an berechnende Algos. Sowie accumulate oder so.

Endlosschleifen existieren bei dir nicht?

Sind Endlosschleifen auf einmal endlich? Sie werden weiterlaufen und weiterlaufen, und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.
(Ich meinte hier mit Operationen die die der Prozessor ausführt, nicht die die im Code stehen. Vielleicht sollte man eher Taktzyklen nehmen.)

Außerdem geht es hier nicht um C++.

Achso, danke. Volkard hat da nur so Anspielungen gemacht, auf vector<int>, std::sort und so.

[Bashar]

Arcoth schrieb:

Endlosschleifen existieren bei dir nicht?

Sind Endlosschleifen auf einmal endlich? Sie werden weiterlaufen und weiterlaufen, und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

OK, ich verstehe dein Argument. Du sagst, dass Computer effektiv endliche Automaten sind, so dass all die theoretischen Ergebnisse für turingäquivalente Berechenbarkeitsmodelle irrelevant sind. Das ist leider aufgrund der gigantischen Anzahl von Zuständen ein extrem unpraktischer Standpunkt, insbesondere hilft er dir absolut nicht dabei, praktisch die Korrektheit eines beliebigen Algorithmus (besser: Programms) nachzuweisen. Und wenn du mal zurückblätterst, ging es hier genau darum.

[volkard]

Arcoth schrieb:

Wieviele gibt es davon nochmal?

\sum^{vector::max\\_size()}\_{i = 0} 2^{i\times sizeof(int) \times CHAR\\_BIT} ~=~ \frac{2^{(vector::max\\_size()+1)\times sizeof(int) \times CHAR\\_BIT} - 1}{2^{sizeof(int) \times CHAR\\_BIT}-1}

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

[volkard]

Arcoth schrieb:

und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

Oh, das erinnert mich an http://de.wikipedia.org/wiki/Fleißiger_Biber#Die_Funktion_S

[Columbo]

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

Ja, aber immer wenn ich mit dir diskutiere werde ich total mathegeil. Kannst du das erklären?

volkard schrieb:

Arcoth schrieb:

und an einem bestimmten Punkt hat der Prozessor mehr Operationen ausgeführt als eine endlicher Funktionsdurchlauf jemals ausführen könnte.

Oh, das erinnert mich an http://de.wikipedia.org/wiki/Fleißiger_Biber

Danke! Das schaue ich mir gleich an.

@Bashar: Ja, ist genau was ich meine.

[Columbo]

Mir hätte eine Abschätzung wie "auf üblichen PCs 1000…000 (mindestens eine Milliarde Nullen)" gereicht.

Ja, aber laut meiner Kalkulation ist es deutlich größer als $10^{10^9}$:

\frac{2^{(4611686018427387903+1)\*4\*8} - 1}{2^{32}-1} = \frac{2^{147573952589676412928} - 1}{2^{32}-1} \approx 2^{147573952589676412898} \approx 10^{147573952589676412898 * log_{10}2} \approx 10^{4.4424*10^{19}}

[volkard]

Arcoth schrieb:

ich kenne keine Formel für das Aufsummieren von Zweierpotenzen mit Faktor im Exponenten

Zweierpotenten kenn ich auch nicht, aber (sizeof(int)×CHAR_BIT)-Potenzten.

2⁸⁺²16+2²⁴⁺²32 = 8¹⁺⁸2+8³⁺⁸4 = http://de.wikipedia.org/wiki/Geometrische_Reihe#Verwandte_Summenformel_1

[Columbo]

2⁸⁺²16+2²⁴⁺²32 = 8¹⁺⁸2+8³⁺⁸4

Das sollte wohl 256 sein, als Basis auf der rechten Seite.

Außerdem haste falsch verlinkt. Die Formel die wir suchen habe ich im Übrigen vor einem Monat in der Schule durchgenommen (bei Geometric Progressions):
$s_n = \frac{q^{n+1}-1}{q-1}$
In diesem Fall ist $q$ nämlich $2^{sizeof(int)*CHAR\_BIT}$, und wenn ich mich nun nicht böse irre, hatte ich also die richtige Formel.

[volkard]

Arcoth schrieb:

2⁸⁺²16+2²⁴⁺²32 = 8¹⁺⁸2+8³⁺⁸4

Das sollte wohl 256 sein, als Basis auf der rechten Seite.

Ups, klar.

Arcoth schrieb:

Außerdem haste falsch verlinkt. Die Formel die wir suchen habe ich im Übrigen vor einem Monat in der Schule durchgenommen (bei Geometric Progressions):
$s_n = \frac{q^{n+1}-1}{q-1}$

Nicht mein Tag.

Arcoth schrieb:

In diesem Fall ist $q$ nämlich $2^{sizeof(int)*CHAR\_BIT}$, und wenn ich mich nun nicht böse irre, hatte ich also die richtige Formel.

Das glaube ich gerne. So Formeln "beweise" ich, indem ich 4 oder 5 Messwerte teste und so wie die aussieht, hat sie nicht mehr Kraft zum Komischsein, um den Test fälschlicherweise zu bestehen.

[Mechanics]

volkard schrieb:

⁽¹⁾ https://www.google.de/#q=cray+endlosschleifen

Warum eigentlich? Ich finde nur "Beispiele", aber keine Origin Story für den Witz.

[Columbo]

@Volkard: Wau, danke für den Busy Beever Link. Das ist genau was ich meinte. Spezifisch die von Radó definierte S-Funktion trifft es (die leider nicht entscheidbar ist).

[hustbaer]

@Mechanics
Ich vermute der Ursprung davon ist nicht mehr nachvollziehbar. Cray hat halt lange Zeit sehr sehr schnelle Rechner hergestellt. Ich will mich mal nicht zu weit aus dem Fenster lehnen indem ich sage "die schnellsten", aber sie waren auf jeden Fall ganz vorne mit dabei.
Und für Normalsterbliche unleistbar.

Cray war daher ne Zeitlang einfach DIE Marke an die man dachte wenn es um sauschnelle Rechner ging. Das unverwechselbare Äussere einiger Modelle hat wohl auch zur Bekanntheit der Marke beigetragen:
http://perso.telecom-paristech.fr/~blanchet/SIP_UE_INF227/histoire/images/0062.cray.xmp.lg.jpg
Bzw. hier eine wohl recht gut bekannte Szene aus einem Film (Sneakers (1992)):
http://disruptdecentralisedisintermediate.files.wordpress.com/2011/12/sneakers_cray_y-mp.jpg

[volkard]

hustbaer schrieb:

Ich will mich mal nicht zu weit aus dem Fenster lehnen indem ich sage "die schnellsten", aber sie waren auf jeden Fall ganz vorne mit dabei.
Und für Normalsterbliche unleistbar.

Ganz genau.

Wikipedia meint http://en.wikipedia.org/wiki/Cray-2

The Cray-2 was a supercomputer with four vector processors built with emitter-coupled logic and made by Cray Research starting in 1985. At 1.9 GFLOPS peak performance, it was the fastest machine in the world when it was released, replacing the Cray X-MP in that spot. The Cray-2 was replaced as the world's fastest computer by the ETA-10G in 1990.[citation needed]

Die Dinger waren irreal schnell. Herausgehoben aus dieser Welt. Soo weit vorne, daß man an seiner Logik zweifeln mag, die sagt, daß das gar nicht sein kann. Und das macht den Witz mit den Endlosschleifen so gut.

Inhaltsverzeichnis von http://en.wikipedia.org/wiki/History_of_supercomputing

1 Beginnings: 1950s and 1960s
2 The Cray era: mid-1970s and 1980s
3 Massive processing: the 1990s
4 Petaflop computing in the 21st century

[Thilo87]

Hehe, warum leiden wir Menschen eigentlich nicht an Endlosschleifen?

[Bashar]

Thilo87 schrieb:

Hehe, warum leiden wir Menschen eigentlich nicht an Endlosschleifen?

Weil wir vorher aufgeben.

[Thilo87]

Eine intelligente Maschine bräuchte also auch die Fähigkeit, aufgeben zu können, um nicht in Endlosschleifen zu landen. Ihre Intelligenz erkennt man dann daran, inwiefern sie beurteilen kann, ob ein Algorithmus wahrscheinlich funktionieren wird.

[Columbo]

Thilo87 schrieb:

Eine intelligente Maschine bräuchte also auch die Fähigkeit, aufgeben zu können, um nicht in Endlosschleifen zu landen.

Nein. Eine Maschine tut exakt das was der Programmcode vorgibt. Der Programmierer braucht die Fähigkeit, richtigen Code zu schreiben und falschen zu erkennen. Wenn die Maschine schon falschen Code selber erkennen muss, läuft irgendwas schief.

[Fytch]

Thilo87 schrieb:

Eine intelligente Maschine bräuchte also auch die Fähigkeit, aufgeben zu können, um nicht in Endlosschleifen zu landen.

Was unterscheidet Endlosschleifen von sehr sehr langsamen Algorithmen?

Edit:
Das war ein wenig unglücklich formuliert. Für langsame aber definitiv lösbare / entscheidbare Probleme lässt sich oft eine obere Schranke angeben. Gemeint war eher so etwas was gleich einen Post weiter unten erwähnt wurde:

intelligenterpost schrieb:

Beweis mal, ob das Programm richtig ist, das die Riemannvermutung wiederlegt, d.h. ob es terminiert oder nicht.

Eine bessere Artikulation wäre demnach zu fragen, was Endlosschleifen von semi-entscheidbaren Algorithmen (ein Algorithmus selbst kann nicht semi-entscheidbar sein, oder? Lediglich die Definitionsmenge...) unterscheidet (so beispielsweise der Miller-Rabin-Primzahltest).