nicht angemeldet
Hi,
Fuer komplexe Aufgaben kann es keine einfachen Algorithmen geben.
Bitte um eine saubere Beweisführung.
Ist das denn nicht die Aussage der Kolmogorov-Komplexität?
Ja, kann man so sagen. Allerdings meinte ich keine Komplexität im mathematischem Sinn, da habe ich mich nicht gut genug ausgedrückt und bitte daher um Entschuldigung.
Also nochmal und ausführlich:
Jede berechenbare Aufgabe A läßt sich in berechenbare Teilaufgaben A_i teilen. Ist A = A_i läßt sie sich logischerweise nicht mehr teilen, wir sind bei der einfachen Turingmaschine angelangt.
Andersrum lassen sich diese Teilaufgaben natürlich auch zusammenfassen, theoretisch zwar in beliebiger Art und Reihenfolge, doch praktische Erwägungen geben einige Regeln vor. trifft man sich in der Mitte kommt man zu recht einfachen Algorithmen und zwar genau die Algorithmen, die bei Sedgwick et al aufgeführt sind. Somit lassen sich auch komplexe Aufgaben auf einige wenige einfache Algorithmen reduzieren. Das Zusammenspiel dieser Algorithmen, der Algorithmus zur Lösung der Aufgabe A also, bleibt dabei mathematisch gesehen natürlich immer noch genau so komplex, wie er von Anfang an war. "Divide&Conquer" wie's so schön heißt.
Und noch etwas steckte in meiner Behauptung: manche komplexen Aufgaben sehen nur so aus, sind aber in Wahrheit höchst simpel.
so short
Christoph Zurnieden