Habt ihr schonmal mit genetischen Algorithmen professionell gearbeitet?

[Columbo]

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.
(Dafür ist natürlich ein Referenzalgorithmus nötig)

[loll]

Arcoth schrieb:

(Dafür ist natürlich ein Referenzalgorithmus nötig)

lol

[volkard]

Thilo87 schrieb:

Und wenn man genetische Algorithmen und KNNs einsetzt (einsetzen könnte), um bessere Algorithmen für spezielle Probleme zu generieren?

Also der da hat geschnallt, was ihm passierte und schaltete einen Schritt zurück:
http://www.acooke.org/malbolge.html

[Gregor]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Im Allgemeinen geht das so nicht. Bashar hat ja schon das Halteproblem erwähnt. Woher weißt Du, ob ein Algorithmus irgendwann terminieren wird? Du kannst das Ergebnis des Algorithmus also nicht mit einer Referenz vergleichen, weil Du unter Umständen kein Ergebnis vom Algorithmus kriegst. Jenseits davon ist der Ansatz nicht praktikabel, da es wohl meistens in Abhängigkeit der Problemgröße exponentiell viele Instanzen einer Problemstellung geben kann. Wenn man also so an die Sache herangeht, dann wird man nie fertig.

Was allerdings teilweise funktioniert ist eine formelle Übersetzung von "Code" in andere Darstellungen bzw. Semantiken, so dass man den Code auf eine Form zurückführt, die der formellen Spezifikation des Algorithmus entspricht. Allerdings geht das nur bei stark eingeschränkten Sprachen.

...siehe zum Beispiel da: https://de.wikipedia.org/wiki/Formale_Semantik#Formale_Semantik_in_der_Informatik

[volkard]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Schon bei sowas einfachem wie sort() kann ich nicht glauben, daß man mit Rumprobieren und Vergleichen weit kommt.

Alle vector<int> aufzuzählen stelle ich mir ein wenig mühsam vor. Wieviele gibt es davon nochmal?

Vielleicht tut das zu testende Programm gar nicht bei allen Eingaben anhalten? Das macht das Testen recht mühsam. Man bräuchte schon eine sagenumwobene Cray⁽¹⁾.

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

[Bashar]

Arcoth schrieb:

Halteproblem, Satz von Rice?

Die Korrektheit von Algorithmen in der Programmierung kann man beweisen, in dem man alle möglichen Werte die von den Funktionsparametern angenommen werden können durchgeht.

Wieso zitierst du etwas, um es dann vollkommen zu ignorieren?

(Dafür ist natürlich ein Referenzalgorithmus nötig)

Auch Unsinn

[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