Was ist ein Algorithmus?

Metatron

Die Frage klingt vielleicht einfach, aber wie könnte man den Begriff eigentlich halbwegs gelungen definieren?
Wo zieht man z.B. die Grenze zwischen den Begriffen 'Vorgangsweise', 'Methode' und 'Algorithmus'?
Oder auch zwischen 'Programmiertechnik' und 'Algorithmus'?
Und die Abgrenzung zwischen 'Design' und 'Algorithmus' ist auch ziemlich rätselhaft?
Dann wäre da noch das Problem, dass doch ein 'Algorithmus' auch immer eine spezielle 'Datenstruktur' voraussetzt, um überhaupt anwendbar zu sein.
Sind also 'Datenstruktur' und 'Algorithmus' womöglich auch Begriffe, die ein und dasselbe meinen?
'Implementierung' und 'Algorithmus' -> Gibt es da überhaupt einen Bedeutungsunterschied?
Ich vermute allerdings, dass es doch geringfügige Unterschiede zwischen den einzelnen Begriffen gibt, und wäre sehr dankbar für eine Aufklärung, um in Zukunft diese Wörter richtig zu verwenden.

Ein Algorithmus ist eine Vorschrift, die aus eine definierten Eingabe in endlich vielen Schritten ein definierte Ausgabe erzeugt.

Den Rest, kannst du bei Wikipedia lesen: http://de.wikipedia.org/wiki/Algorithmus

Metatron

Hab's gelesen, es scheinen sehr viele Begriffe eine überaus ähnliche Bedeutung zu haben. Der Gedanke kam mir plötzlich, weil pumuckl meinte, statt mit Programmiertricks eine Suchfunktion zu verbessern, wäre es gescheiter, einen besseren Algorithmus zu verwenden, dann kann die Suchfunktion womöglich quadratisch schneller sein. Für meine Problemstellung scheint der Alpha-Beta Algorithmus optimal zu sein. Weil mein Programm leider trotzdem nicht optimal läuft, nahm ich erstmal an, dass es wohl am unüberlegten Design oder vielleicht auch an unglücklich gewählten Datenstrukturen liegen musste. Vielleicht auch an der suboptimalen Implementierung des Algorithmus.
Deshalb bin ich mir plötzlich gar nicht mehr sicher, ob das nicht gar alles ein dasselbe ist: Design, Datenstruktur, Implementierung, Algorithmus.

Wie groß ist denn der jeweilige Anteil an der Performance von den 4 Teilgebieten eines Programms ? Sowas wie 25-25-25-25%, d.h. wenn das Design missglückt wäre das genau so schlimm wie ein unpassend gewählter Algorithmus?
Oder steht der Algorithmus über allem, so von der Art 5-5-5-85% Anteil am Resultat?

Weil ich letzteres nicht ausschließen kann, schau ich mich weiter um, ob's vielleicht doch irgendwo etwas besseres als Alpha_Beta gibt:)

thx mfg

Shade Of Mine

Du kannst das nicht trennen. Ein Algorithmus loest dir ein definiertes Problem aber der Algorithmus muss auch erstmal Designed und Implementiert werden und dann operiert er wahrscheinlich auch noch auf bestimmten Datenstrukturen.

Wenn du nicht weisst warum dein Programm langsam laeuft nimm einen Profiler (sollte bei den meisten Compiler Sets dabei sein) und lass ihn deinen Code analysieren.

idR ist es am effizientesten Datenstrukturen oder Algorithmen auszuwechseln da dies meistens ohne grobe Struktur Aenderungen im Code geht und oft nichtmal das oeffentliche Interface der jeweiligen Funktionen geaendert werden muss - man aber einen enormen Performance gewinn erzielen kann.

Wenn aber dein Algorithmus schon ziemlich ideal ist, dann lass ihn so und such wo die Performance verloren geht.

Metatron schrieb:

Wie groß ist denn der jeweilige Anteil an der Performance von den 4 Teilgebieten eines Programms ? Sowas wie 25-25-25-25%, d.h. wenn das Design missglückt wäre das genau so schlimm wie ein unpassend gewählter Algorithmus?
Oder steht der Algorithmus über allem, so von der Art 5-5-5-85% Anteil am Resultat?

Das kann man so nicht beantworten. Da musst du schon einen Profier nehmen und schauen, wo dein Programm viel Zeit verschwendet. Grundsätzlich kann dich jeder Fehler, Design-, Programmierfehler und falscher Algorithmus, Performance kosten.

Wenn du aber einen falschen Algorithmus auswählst, so kannst du den nicht durch Programmiertricks wieder ausgleichen. Wenn du aber einen guten Algorithmus wählst, kannst du ruhig ein paar Taktzyklen verschwenden, wenn dieser entsprechend besser ist. (Siehe http://de.wikipedia.org/wiki/Landau-Symbole)

Zu deiner Suchfunktion: Ich weis ja nicht, was du machst. Je nach Suche, würde es sich lohnen einen Inder vor der Suche anzulegen, und darauch mittels Binärer Suche zu arbeiten.

Metatron

UCI-Schach-Engine, die zweite.
Dass beim ersten Versuch nicht gleich ein Fritz daraus werden konnte, war wohl naheliegend.
Ursprünglich nur elementaren Minimax verwendet -> Für 3 Halbzüge rechnete das Ding rund eine Minute.
Dann auf Alpha_Beta Suche umgestellt -> Immerhin 5 Halbzüge in 8 Sekunden Rechenzeit.
Mehr war beim ersten Versuch nicht drinnen, alle mir bekannten Programmiertricks haben da nicht mehr recht weitergeholfen.

Also das Gleiche von vorne, und etwas gründlicher durchdacht.
Profi-Engines schaffen 13 Halbzüge und mehr in 8 Sekunden, und 'unter der Haube' wird auch dort mit Alpha_Beta Suche und weiterentwickelten Varianten davon (Negascout, Nullzugpruning etc.) gearbeitet, deren Implementierung mir erstmal noch zu schwierig erscheint.
Zielsetzung wären diesmal 7 Halbzüge in 8 Sekunden, was für mich als Hobby-Programmierer schonmal zufriedenstellend wäre.

Bei Schach hat man leider das Problem, dass mit jedem Halbzug Suchtiefe, den man dazunimmt, die Anzahl der zu prüfenden Stellungen überaus geschwind explodiert. (nimmt man an, dass in einer 'durchschnittlichen' Stellung ca. 40 Züge möglich sind, auf die der Gegner dann jeweils widerum mit ca. 40 verschiedenen Zügen antworten kann, heißt das im Klartext, dass bereits
in einer Suchtiefe von 5 ca. 40 x 40 x 40 x 40 x 40 = rd. 100 Millionen mögliche Folgestellungen sich ergeben können.) Zum Glück lassen sich mit Alpha_Beta Algorithmus (und einer entsprechend komplexen Bewertungsfunktion) rund 90% davon wegprunen, aber auch dann müssen immer noch 10 Millionen Mal Zugtabellen generiert und 10 Millionen Stellungen bewertet werden.

Den größten Einfluss auf die Performance haben so gesehen der Zuggenerator sowie die Bewertungsfunktion (die einerseits so komplex wie möglich und andererseits eine so kurze Laufzeit wie möglich haben muss, damit Alpha_Beta erfolgreich prunen kann), bei den beiden Funktionen geb' ich bei meinem zweiten Versuch mein bestes Und wie's aussieht, wird's auch besser. Zuggenerator ist erstmal dreimal so schnell wie der alte. (Hauptsächlich nehm ich QueryPerformanceCounter zur Bestimmung der Laufzeit her? Ist doch in Ordnung?)

thx für Tipps
(und lieber einen schlampig implementierten Bit-Sort- als ein perfekt implementierten Bubble-Sort Algorithmus Das ist jetzt auch klar.
mfg