Wie ihr dem Titel entnehmen könnt, möchte ich prüfen, ob
zwei Alogorythmen(Funktionen, Prozeduren ,…) das gleiche machen.
Ich möchte das ganze nicht auf Text-Basis machen(also den Code der Algorythmen vergleichen),
sondern wenn möglich den Hash-Wert rein aus den Parameter und den Rückgabewerten errechnen.
Code anzeigen
[spoiler]Folgenden Ansatz habe ich schon gefunden, aber er ist nicht perfekt:
Also, hier einmal zwei algos:
return param + 1;
}
int algo2(int param2) {
final int puffer = param +0,5;
return puffer +0,5;
}
Nicht das beste Beispiel, aber (ich denke) es funktioniert.
Nun würde der Hash-Algorythmus einfach beliebige Zahlen an die Funktion übergeben,
und aus den Rückgabewerten erkannen, ob beide das selbe machen.[/spoiler]
Mir ist aber klar, dass diese Lösung nicht die beste ist(zu viele Falschmeldungen),
kann mir irgendjemand helfen den obigen Algorythmus zu perfektionieren oder
einen neuen zu finden?
Gut, ich habe nicht so genau auf den Code geachtet, als ich das schrieb.
Hier ist eine verbesserte, diesmal auch getestete, Version:
Code anzeigen
[spoiler]
static int algo1(int param1) {
return param1 + 1;
}
static int algo2(int param2) {
param2 += 2;
param2 -= 1;
return param2;
}
public static void main(String[] args) {
for (int i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i++) {
System.out.println(algo1(i) == algo2(i));
}
}
}
[/spoiler]
Was ich eigentlich zeigen wollte, ist das Algorythmen oft das selbe berechnen, aber
anders implementiert sind.
Ist nun ein solcher Algorythmus machbar und gibt es eine Alternative zu meinem, der sehr langsam ist
und zudem fehleranfällig, wenn man nicht alle Werte durchprobiert, was bei manchen Typ sehr aufwändig ist(mal nur um Strings und Objekte zu erwähnen).
Ok, ich glaube, jetzt weiß ich, worauf du hinaus möchtest. Du möchtest sozusagen einen Hash von einem Algorithmus (ja, das schreibt sich mit i) errechnen, der widerspiegelt, was der Algorithmus macht.
Sowas wirst du nicht finden. Es gibt Methoden zur formalen Verifikation von Algorithmen, dazu muss man dann Invarianten aufstellen und mittels Axiomen beweisen, dass der Algorithmus eine bestimmte Sache tut. Das kann man auch ein Stück weit automatisieren, dazu ist Java aber nicht sonderlich gut geeignet (ein besserer Kandidat ist beispielsweise Ada).
Ansonsten ist das Problem nicht mal eben so lösbar, da begibt man sich tief in die akademische Welt hinein
Richtig. So ein Algorithmus würde nämlich endlich zeigen ob N = NP ist oder nicht. @schildi48 falls dich das wirklich interessiert, kannst du dir einmal anschauen was man under Reduktion versteht.
Das wird dir - bei einer so breiten Aufgabenstellung - nicht gelingen. Stand der Dinge ist der: Du kannst nicht einmal feststellen ob ein einzelnes Programm/Prozedur sich beenden wird. (Siehe Halteproblem)
Du kannst das Problem natürlich eingrenzen und versuchen nur die Reduktion verschiedener Algorithmen in dieser Problemklasse zueinander zu beweisen. Dafür müsstest du dann eine Code-Analyse schreiben die das ganze in ein SAT-Problem umformuliert um dies dann an einen SAT-Solver zu übergeben.
Mir persönlich dreht sich da der Kopf, aber ich war immer mehr der Entwickler als Mathematiker.
Java war nur ein Beispiel, im Grunde ist es egal, in welcher Sprache der Algorithmus geschrieben ist, aber:
Warum Ada?
ich habe mich zwar nicht wirklich mit der Sprache befast,
aber ich dachte, das problem sein in einer funktionalen Sprache
am einfchsten zu lößen, da dort die Ergebnisse eines Algorithmus
immer gleich sind???
[QUOTE=schildi48]Java war nur ein Beispiel, im Grunde ist es egal, in welcher Sprache der Algorithmus geschrieben ist, aber:
Warum Ada?
ich habe mich zwar nicht wirklich mit der Sprache befast,
aber ich dachte, das problem sein in einer funktionalen Sprache
am einfchsten zu lößen, da dort die Ergebnisse eines Algorithmus
immer gleich sind???[/QUOTE]
Ja schon, aber mit einem Hash-Wert des Quelltextes kannst du ja nicht mal x+x und 2*x unterscheiden.
In funktionalen Sprachen könntest du theoretisch ALLE Inputs nehmen und die Outputs vergleichen, das ist aber wegen der großen Zahl der Möglichkeiten meistens unmöglich.
Also bleibt dir nur eine Art Modellierung eines Algorithmus (und da bist du eben schon in der theoretischen Informatik, wie oben schon gesagt)
Wie ich das verstehe will er ja nicht den Quelltext Hashen sondern die Parameter und Ausgabe:
Also:
Alg1(17,27,8)=>45
Alg2(17,27,8)=>45
Dann Hash(17,27,8,45) vergleichen mit Hash(17,27,8,45)? Wäre ziemlich sinnfrei, dann braucht man nicht mal hashen - equals oder == reichen da dann doch, oder sehe ich jetzt was falschg? Mal abgesehen von dem Problem aller möglichen Eingaben…
“Algorithmus” hat nichts mit Rhythmus zu tun, sondern dem Gelehrten al-Chwarizmi - der schon genug damit gestraft ist, zu “Algorismi” lateinisiert worden zu sein, also sollten wir ihm wenigsten sein “i” gönnen, und damit auch seine Leistungen anerkennen …
Ich hatte Ada genannt, weil mir in Erinnerung war, dass es dafür Tools gibt, die die formale Verifikation des Programmes teilautomatisieren (scheinbar gibt es da „Penelope“).
Wenn man nach wissenschaftlichen Papers sucht, stößt man auf Publikationen von Anfang der 90er Jahre (beispielsweise noch dieses hier: http://dl.acm.org/citation.cfm?id=75238).
Selbst gearbeitet habe ich damit allerdings nicht, das ist vor meiner Zeit
Da braucht man dann schon Ada SPARK. Durch Einschränkungen der Ada Funktionalität (z.B. im Multithreading) und Annotationen im Code (z.B. Variable X darf Werte annehmen zwischen y und z) können dann die Static Code Checker (Exception handling, Zugriff auf möglicherweise uninitalisierte Variablen, usw.) und Proofing Tools benutzt werden um formale Korrektheit zu beweisen.
Dabei ist wichtig, dass gegen das Design geprüft wird (striktes Design by Contract), also muss das ja irgendwo bekannt gemacht werden muss, eben durch Annotations/„formal comments“ die dann die z.B. Vor- und Nachbedingungen oder unerwünschte Side Effects ausrücken können - manchmal sogar Performance Anforderungen garantieren sollen.
Spätestens da sieht man dass es dann doch schwierig wird…
Allerdings, wenn man das aufmerksam verfolgt, stellt man dann fest, dass so ein Konzept eigentlich mit vielen Programmiersprachen umsetzbar wäre.
Nichtsdestotrotz erfreut sich SPARK bei vielen kritischen Echtzeit Embedded System in der Automobil-/Luft- und Raumfahrt-/SCADA-/Steuerungstechnikbrachen großer Beliebtheit. Wahrscheinlich weil es das erste Framework war, das man so einsetzten konnte, und man einen deutlichen Schritt weiter war im Gegensatz zu reinem Testen gekommen ist.
Der Aufwand so etwas nachzubauen ist groß, ich glaube es gibt ein zwei Projekte die ähnliche Ansätze mit C und C++ gestartet haben aber die sind im akademischen Umfeld in der Startphase hängen geblieben, siehe z.B. Ada/Penelope. War zumindest so als ich das letzte mal was mit SPARK zu tun hatte… ist schon ein paar Jährchen her.
Danke erstmal für die Antworten.
Also, um hier irgendwelche Unklarheiten zu beseitigen:
Ich will herausfinden ob zwei Algorithmen das selbe machen,
ungeachtet der Parameter. @fassy : ich werde mir ada sparc einmal anschauen, danke.
Natürlich rennst du in das Halteproblem. Aber soweit muss man gar nicht ausholen, um zu verstehen, warum so ein Programm nicht funktionieren kann: Es gibt z.B. für manche Probleme mit Primzahlen langsame, exakte Algorithmen und schnelle Algorithmen, die allerdings die Richtigkeit der Riemannschen Vermutung voraussetzen. Bis jetzt hat man kein Gegenbeispiel gefunden, aber wenn dein Programm feststellen könnte, ob beide Algorithmen das gleiche Ergebnis liefern, könntest du damit die Riemann-Hypothese beweisen (oder widerlegen) - was trotz intensiver, hunderfünfzigjähriger Forschung nicht gelungen ist. Klingt etwas abgespaced, findest du nicht?
