en!gma - Mo 25.07.05 13:41
Titel: herausfinden von algorithmen?

---

hiho
wollte mal fragen ob es wohl möglich wäre ein programm zu schreiben das algorithmen herausfindet?

hab mir das in etwa so vorgestellt, dass zB 10 oder mehr ergebnisse angibt.
und das programm versucht einen algorithmus darin zu finden.
mal ein beispiel:

1=1
2=4
3=9
4=16
5=25

nun soll das programm halt ausspucken zahl*zahl oder sowas in der art.

ist sowas überhaupt möglich?
wenn ja, gibt es sowas villeicht schon?

mfg

en!gma

jaenicke - Mo 25.07.05 13:48

---

Sowas ist durchaus möglich...

Ich würde es zwar anders machen, aber ich gebe hier mal eine sehr einfache Methode an.

Du kannst zum Beispiel einfach einen Interpreter für mathematische Funktionen benutzen, und dann zufällige Funktionen durch Konkatenieren von Operatoren und der Variable bzw. zusätzlich mit Klammerung erzeugen. Bekommt eine davon das gewünschte Ergebnis mit den anderen Angaben überprüfen.

Das dauert zwar sehr lange, wenn es auch nur ETWAS komplizierter ist, erfordert aber keinen komplizierten Code.

Solche Interpreter gibts inzwischen wie Sand am Meer auch kostenlos. Beispielsweise in der JVCL vom Projekt JEDI...

Alstar - Mo 25.07.05 13:51

---

Solche Folgen bzw. Reihen (falls es solche sind), kannst Du auch relativ leicht mittels eines Terms bestimmen, aber ich glaube nicht, dass Du Dich darauf beschränken möchtest?!

Alstar

en!gma - Mo 25.07.05 13:55

---

das war jetzt wirklich nur ein kleines beispiel

ich habe später eher daran gedacht
sowas wie

61=3500
54=3159
oder sowas

oder villeicht schon sowas

5817581=851591758917589758

oder noch länger.

jaenicke - Mo 25.07.05 13:58

---

Alstar hat folgendes geschrieben:

Solche Folgen bzw. Reihen (falls es solche sind)

Was sollte es denn sonst sein???

Darunter versteht man (mathematisch gesehen natürlich) schließlich nur eine geordnete Folge von Zahlen, die durch irgendeine Vorschrift in dieser folge bestimmt werden.
Dies kann explizit, wie im obigen Beispiel, oder rekursiv durch Angabe der Berechnungsvorschrift des jeweils nächsten Folgeglieds aus dem vorherigen geschehen.

Und das schließt wohl alles ein, was en!gma meint...

Gausi - Mo 25.07.05 14:00

---

Ich würde generell dagegen wetten ;-)

Ich kann das jetzt nicht formal beweisen, aber das Problem, welches du hier ansprichst, würde ich spontan in dieselbe Ecke einordnen wie das sogenannte "Halteproblem". Dabei geht es darum, dass man einen Algorithmus gegeben hat, und eine Eingabe für diesen Algorithmus. Das Halteproblem ist, zu entscheiden, ob der Algorithmus ein Ergebnis ausspuckt, oder endlos weiterrechnet. Das Halteproblem ist nicht entscheidbar.

Dein Problem halte ich auf den ersten Blick für noch komplizierter. :gruebel:

Wenn du gewisse Forderungen an die Algorithmen bzw. mathematischen Formeln stellst, die du herausfinden willst, lässt sich da bestimmt was machen - sonst nicht.

en!gma - Mo 25.07.05 14:01

---

angenommen ich hätte wirklich
10 von solchen gleichungen

5817581=851591758917589758
9r51809=5912850189581905890
98180959018590=578758215190589511985
58918905915=5718950810

wär das denn auch noch möglich?
oder wären die berechnungszeiten viel zu lang?
aber könnte ich villeicht ein kleines beispiel für so ein programm, also nur in die richtung kriegen? =)
wäre nett,
von mir aus auch nur meta code, halt das ich nen anfang hab

uall@ogc - Mo 25.07.05 15:39

---

ohne jetzt viel zu schreiben:

1 = 1
2 = 4
3 = 1
4 = 5
5 = 9
6 = 2
7 = 6
8 = 5
9 = 3
10 = 6
11 = 8
12 = 9

das sind die nachkommastellen von PI
wenn du dafür jetzt ne formel entwickelst biste mein persönlicher gott :) aber jetzt nicht PI normal ausrechen und mit modulo etc. die stelle rausfiltern, sondern eine formel bei der ich z.b. 13 eingebe und ich würde die nächste stelle bekommen

und meinst immer noch du willst dich damit versuchen?

en!gma - Mo 25.07.05 16:05

---

naja egal dann hat sich das wohl erledigt :)

Tobias1 - Mo 25.07.05 16:12

---

uall@ogc hat folgendes geschrieben:

10 = 6

10=5 !!! :D


Ich glaube bei so einer Folgen-Suchmaschiene müsste man ein riesen Raster machen und alle bekannten Folgen eingeben.
So müsste bei der Eingabe erstmal alles durchprobiert werden, ob das zu der Folge 14-15-16-... oder zu der Folge 0-1-3-6-10-.. oder 1-4-1-5- passt.

Gausi - Mo 25.07.05 16:29

---

Ich möchte nur noch mal kurz einwerfen, dass ich das ganze Vorhaben für prinzipiell unmöglich halte. Nicht unmöglich im Sinne von das "dauert zu lang" oder "das braucht zu viel Speicher", sondern unmöglich wie "man kann sich nicht selbst am Ellenbogen und am Hinterkopf lecken".

en!gma - Mo 25.07.05 16:37

---

naja ein bischen misstrauisch war ich von anfang an :)
schade,
schön wärs gewesen :)
naja thread kann dann auch geschlossen werden

maxk - Mo 25.07.05 17:30

---

Wieso schließen? Wenn noch jemand eine Frage hat, ist diese doch hier gut untergeracht ;) Ich glaube übrigens nicht, dass es ganz unmöglich ist. Schließlich kann unser Gehirn eine solche Aufgabe ganz gut bewältigen, d.h. das auch Computer dazu früher oder später in der Lage sein werden 8)

Gruß,
maxk

Gausi - Mo 25.07.05 17:48

---

Keine Angst, hier wird nicht geschlossen.

Zu "unser Gehirn kann das": Hier mal ein kleines Rätsel Nenne mir den zugrundeliegenden Algorithmus und ersetze das ? durch die richtige Zahl. 5 ist übrigens falsch! (Sorry, falls das altbekannt ist, mir fiel grad nix neues ein)

Zur Unmöglichkeit: Es ist mathematisch beweisbar (und das ist gar nicht sooo kompliziert), dass man folgende Frage nicht beantworten kann:

Gegeben: Ein beliebiges Programm P und eine Eingabe a für das Programm.
Frage: Hält das Programm P mit dieser Eingabe irgendwann an - Ja oder Nein?

uall@ogc - Mo 25.07.05 18:43

---

Gausu in dem fall wäre 5 wohl richtig, da es hier nur um einen Algorythmus geht der die Eingaben alle richtig abbildet

d.h. bei den 3 eingaben wäre f(x) = x/2
der richtige alg.

auch wenns nicht der ist den du meinst

DaClown - Mo 25.07.05 19:00

---

was ist denn die richtige Antwort diese Zahlkette Gausi, 17? (p=8; q=1; while (true) do x:=((x+8+q*4)mod 24)/2; oder so ähnlich ??)

en!gma - Mo 25.07.05 19:06

---

in dem fall nach dem ich gefragt hatte, wäre 5 richtig :)

Gausi - Mo 25.07.05 19:18

---

Richtige Lösung ist 10 -> 4
Folgendes Verfahren habe ich verwendet:
Es gibt nunmal ein paar mehr Sachen, die man mit Zahlen machen kann, als +,-,*,/,DIV, MOD...

jasocul - Mo 25.07.05 19:18

---

@Gausi:
5 ist bei deiner Aufgabe selbstverständlich korrekt. Es kann auch mehrere Lösungen geben. Wenn du sagst, dass es falsch ist, dann ist die Menge der Informationen nicht hinreichend.

Ob es Aufgaben dieser Art gibt, die nicht mit einem Algo lösbar sind, weiß ich nicht.
Theoretisch gehe ich davon aus, dass alles was aufgrund von vorhandenen Informationen analysiert werden kann, auch mit Algos festgestellt werden kann. Vielleicht sind wir einfach noch nicht in der Lage das zu prgrammieren.
Ich kann mich an Zeiten erinnern, wo gesagt wurde, dass Spracherkennung à la Enterprise unmöglich ist. Wenn man aber die Fortschritte betrachtet ...

Gausi - Mo 25.07.05 19:45

---

jasocul hat folgendes geschrieben:

@Gausi: 5 ist bei deiner Aufgabe selbstverständlich korrekt. Es kann auch mehrere Lösungen geben. Wenn du sagst, dass es falsch ist, dann ist die Menge der Informationen nicht hinreichend.

Siehst du, und genau das versuche ich unter anderem klarzumachen. Aufgabe ist es laut Thread-Titel, aus einigen Paaren (Eingabe-Ausgabe) den zugrundeliegenden Algorithmus herauszufinden. Ich glaube, dass mein Beispiel eindeutig zeigt, dass dies schonmal aufgrund der begrenzten Zahl an Eingabedaten nicht möglich ist.

jasocul hat folgendes geschrieben:

Ob es Aufgaben dieser Art gibt, die nicht mit einem Algo lösbar sind, weiß ich nicht.

Glaub mir: Es gibt Probleme, die sind nicht lösbar. Das ist eine mathematische Tatsache. Es ist nicht so, dass man meint, sie sind nicht lösbar, weil man bisher keine Metode gefunden hat, sie zu lösen. Sondern man hat gezeigt, dass es keine Lösung geben kann. Würde es eine Lösung geben, würde sich das selbst widersprechen. Man erhält dann so Aussagen wie "X ist genau dann gerade, wenn X ungerade ist."

jasocul hat folgendes geschrieben:

Theoretisch gehe ich davon aus, dass alles was aufgrund von vorhandenen Informationen analysiert werden kann, auch mit Algos festgestellt werden kann. Vielleicht sind wir einfach noch nicht in der Lage das zu prgrammieren.

Tut mir leid, dir da ein paar Illusionen nehmen zu müssen, aber das ist ganz einfach nicht richtig. Wir sind nicht nur nicht in der Lage, es zu programmieren, es liegt in der Natur des Problems, dass es nicht lösbar ist.

jasocul hat folgendes geschrieben:

Ich kann mich an Zeiten erinnern, wo gesagt wurde, dass Spracherkennung à la Enterprise unmöglich ist. Wenn man aber die Fortschritte betrachtet ...

Das ist was anderes - soll keine faule Ausrede sein. Ist einfach so. :mrgreen:

jasocul - Mo 25.07.05 20:29

---

Ich hoffe, dass es durch das Quoten jetzt nicht unübersichtlich wird. Sonst brauchen wir eine Algrithmus für die Analyse. :mrgreen:

Gausi hat folgendes geschrieben:

jasocul hat folgendes geschrieben: @Gausi: 5 ist bei deiner Aufgabe selbstverständlich korrekt. Es kann auch mehrere Lösungen geben. Wenn du sagst, dass es falsch ist, dann ist die Menge der Informationen nicht hinreichend. Siehst du, und genau das versuche ich unter anderem klarzumachen. Aufgabe ist es laut Thread-Titel, aus einigen Paaren (Eingabe-Ausgabe) den zugrundeliegenden Algorithmus herauszufinden. Ich glaube, dass mein Beispiel eindeutig zeigt, dass dies schonmal aufgrund der begrenzten Zahl an Eingabedaten nicht möglich ist.

Eingigen wir usn darauf, dass die notwendigen und hinreichenden Bedingungen Mindestvoraussetzung sind? :wink:

Gausi hat folgendes geschrieben:

jasocul hat folgendes geschrieben: Ob es Aufgaben dieser Art gibt, die nicht mit einem Algo lösbar sind, weiß ich nicht. Glaub mir: Es gibt Probleme, die sind nicht lösbar. Das ist eine mathematische Tatsache. Es ist nicht so, dass man meint, sie sind nicht lösbar, weil man bisher keine Metode gefunden hat, sie zu lösen. Sondern man hat gezeigt, dass es keine Lösung geben kann. Würde es eine Lösung geben, würde sich das selbst widersprechen. Man erhält dann so Aussagen wie "X ist genau dann gerade, wenn X ungerade ist."

Nur mal am Rande zur Info: Ich habe Mathe studiert. (Wenn auch nicht bis zum Schluss). Die Form der Beweisführung ist mir also bekannt. Um die Sachen geht es auch nicht. Es ging hier glaube ich Reihen und Folgen. Wenn diese mit dem menschlichen Verstand erfassbar sind und man dafür eine "Formel" finden kann, dann sollte es auch mit einem Programm lösbar sein. Der Aufwand steht auf einem anderen Blatt.

Gausi hat folgendes geschrieben:

jasocul hat folgendes geschrieben: Theoretisch gehe ich davon aus, dass alles was aufgrund von vorhandenen Informationen analysiert werden kann, auch mit Algos festgestellt werden kann. Vielleicht sind wir einfach noch nicht in der Lage das zu prgrammieren. Tut mir leid, dir da ein paar Illusionen nehmen zu müssen, aber das ist ganz einfach nicht richtig. Wir sind nicht nur nicht in der Lage, es zu programmieren, es liegt in der Natur des Problems, dass es nicht lösbar ist.

Du hast es leider flasch herum interpretiert. Wenn das Problem lösbar ist, dann sollte es möglich sein, einen Algorithmus zu finden.

Gausi hat folgendes geschrieben:

jasocul hat folgendes geschrieben: Ich kann mich an Zeiten erinnern, wo gesagt wurde, dass Spracherkennung à la Enterprise unmöglich ist. Wenn man aber die Fortschritte betrachtet ... Das ist was anderes - soll keine faule Ausrede sein. Ist einfach so. :mrgreen:

Ist keine Ausrede. Was du sagst stimmt. Worauf ich hinaus wollte: Nur weil wir jetzt noch zu doof dazu sind, muss das in 10 Jahren ja nicht mehr so sein.

Ich hätte Lust mal ausführlich über solche Dinge zu fachsimpeln. Mein Studium liegt zwar schon ein wenig zurück, aber da köntest du ja Rücksicht drauf nehmen. :wink:

Spaceguide - Di 26.07.05 22:53

---

Hmm, eigentlich sollte es zu jeder Zahlenreihe mit n (a,b)-Tupeln ein Polynom der Ordnung n-1 geben mit f(a)=b. Das lässt sich bei endlichen n auch in endlicher Zeit berechnen.

blocade - Mi 27.07.05 02:46

---

naja, wenn man so eine folge in einer rationalen funkion wiedergeben will wird das sicherlich mit jeder folge gehen.
je länger und 'komplizierter' sie ist, desto 'komplizierter' wird auch die funktion.

man nüsste doch einfach nur einsetzen:

f(1) = a1
f(2) = a2
f(3) = a3
f(4) = a4
.
.
.
f(n) = an


dann guckt man noch wie viele wendestellen (bzw hoch und tiefpunkte) die funktion hat und kann dann doch mit funktion f(x) mit x element N bestimmen!?

solche lösungen wie gaudi gebracht hat sind damit natürlich nciht möglich.

zemy - Mi 27.07.05 15:21

---

Wenn du dich auf x Element N beschränkst, wirst du wohl kaum auf nen genauen Wert für deine Extrema bzw. Wendepunkte kommen. Die Ableitung bleibt zwar ganzrational, die Lösungen aber bestimmt nicht.

Eine Funktion n-ten Grades bei n gegebenen Werten sollte sich jedoch fast immer über ein Gleichungssystem berrechen lassen. Annäherungen per Logarythmus, Exponentialfunktion oder ähnlichem währen auch denkbar. Wenns der GTR kann, wirds wohl ein P4 auch hinbekommen ;)

Ich kann nutr mit Mathe Sek.2 dienen, das Studium kommt noch. Alsokeine Garantie für Korrektheit...

MfG Zemy

Spaceguide - Do 28.07.05 10:59

---

Wenn mich meine Erinnerung nicht täuscht, kann man die 2er-Tupel auch einfach als komplexe Zahlen auffassen, das Array mit den Tupeln durch eine Fourier-Transformation jagen und bekommt das Polynom, welches die Reihe beschreibt. Alle Potenzen mit Koeffizient 0 kann man dann wegwerfen.

MiChri - Fr 29.07.05 00:27

---

Moin
Zu erst mal Gausi, dein Programm P mit Eingabe A Problem ist für Laien nicht ganz nach zu vollziehen, denn es ist ja berechenbar (wenn es gilt wird die Antwort auf jeden Fall richtig ausgegeben) aber halt "nur" nicht entscheidbar (nach keiner Zeit t kann gesagt werden, dass P nicht anhält).

Das mit dem Algorithmen-Bastel-Programm hat damit sehr wenig zu tun. So kann man mit einem Polynom bis x^10
bei gegebenen Funktionswerten f(Y1)=X1,f(Y2)=X2 ... eine schöne Funktion also einen Algo bauen, der alles erfüllt.
Aber es gibt natürlich unendlich viele Folgen, die diese Teilmenge haben. Dadurch ist aber nur die Sinnhaftigkeit aber nicht die Machbarkeit fraglich.

Also mit theoretischen Grüßen
Christian

iX0r - Sa 30.07.05 08:03

---

Ein Polynom zu finden, welches genau n Punkte korrekt interpoliert ist ohne Probleme berechenbar (Newton, Lagrange ...)
Eine andere Sache ist diese Fortführung von Reihen und Folgen, da es dort leider unendliche viele Lösungen gibt (für alle möglichen vorgegebenen Zahlenpaare), und damit ist das Finden einer Vorschrift hinfällig, denn du findest vielleicht eine, aber niemals alle.
Prinzipiell halte ich dieses Problem aber, im Gegensatz zu Gausi für lösbar. Die Einschränkung ist jedoch, dass man mit einem Algorithmus immer nur bestimmte Lösungen finden kann, was natürlich wiederum nicht völlig dem Problem entspricht.
Naja, am Ende sind wir ja auch nur ne Menge von Schaltern und Knöpfen und determinieren so durch unsere Welt :-)