Lokalität in Algorithmen
-
habe ich allerdings keine unterschiedlichen Problemstellungen betrachtet, sondern die Daten ansich angepasst, damit sich entsprechende Vorteile ergeben
Das ist normal, weil es zu unuebersichtlich wird.
In meiner Denkweise beseitigt man hierbei die Globalität der Problemstellung, wodurch man dann lokal auf Teildaten arbeiten kann. Und das ist dann natürlich super effizient.
Ja, z.B. Divide & Conquer wie erwaehnt, Dynamic Programming, ... Aber das ist fuer Informatiker natuerlich, also nichts besonderes. Am besten zu sehen bei rekursiven Ansaetzen, Reduktion auf ein einfacheres Problem, und zwar so lange bis es trivial loesbar ist. Diagonalisierung einer Matrix, da wird auch erstmal eine Zeile betrachtet.
irgendwo Formalisierungen derartiger Aspekte geben
Hast du doch schon genannt, Divide & Conquer oder dynamische Programmierung. Woran das liegt? Keine Ahnung, aber wir koennen nur begrenzt viel auf einmal machen. Liegt vielleicht an unserer sequenziellen Denkweise, oder das hauptsaechlich Maenner in diesen Berufen zu finden sind.
-
knivil schrieb:
irgendwo Formalisierungen derartiger Aspekte geben
Hast du doch schon genannt, Divide & Conquer oder dynamische Programmierung. Woran das liegt? Keine Ahnung, aber wir koennen nur begrenzt viel auf einmal machen. Liegt vielleicht an unserer sequenziellen Denkweise, oder das hauptsaechlich Maenner in diesen Berufen zu finden sind.
Ich suche eher nach übergeordneten Konzepten. Divide&Conquer oder auch Dynamische Programmierung sind ganz konkrete Techniken bei der Entwicklung von Algorithmen. Mir geht es um die Klassifikation von Problemstellungen.
-
(gelöscht, was hier stand kommt viel besser im nächsten Posting von Christoph.)
-
Gregor schrieb:
Und auch bei Graphenalgorithmen wird es so etwas geben. Da kenne ich mich zwar nicht wirklich aus, aber ich bin mir ziemlich sicher, dass es dort eine ganze Menge Problemstellungen gibt, die in einem Graphen mit nur wenig Kanten wesentlich effizienter zu lösen sind als in einem vollständigen Graphen.
Ich glaube was du hier suchst, sind Baumzerlegungen. Die Baumweite eines Graphen ist eine natürliche Zahl, die misst, wie ähnlich ein Graph einem Baum ist. Bäume haben Baumweite 1, eine Clique mit n Knoten hat Baumweite n-1. Größer als n-1 kann die Baumweite eines Graphen mit n Knoten nie werden. Cliquen sind also in diesem Sinne maximal nicht-lokal.
Auf Graphklassen beschränkter Baumweite sind zum Beispiel Probleme wie "Ist der Graph 3-färbbar?", "Hat der Graph einen Hamilton-Kreis?" deterministisch in Linearzeit in der Größe des Eingabegraphen lösbar. Diese Probleme sind auf allgemeinen Graphen NP-vollständig, und damit ist es unwahrscheinlich, dass die auf allgemeinen Graphen überhaupt sub-exponentiell lösbar sind, geschweige denn in Linearzeit.
Im Prinzip steckt hinter Baumzerlegungen und den schnellen Algorithmen letztendlich auch "nur" dynamic programming, aber auf eine unglaublich clevere Art und Weise. Hier wird Lokalität ziemlich geschickt ausgenutzt. Der Grundgedanke ist, dass dynamic programming auf Bäumen super funktioniert, aber auf allgemeinen Graphen nicht, und man einen Weg finden wollte, wie man dynamic programming auf allgemeinen Graphen trotzdem anwenden kann.
edit: Da Gregor als Physiker in der Zeit zurückreisen kann, hat er von mir von den Baumzerlegungen erfahren bevor ich sie hier nennen konnte.
-
Ist auf jeden Fall gut, wenn man schon mal ausschließen kann, was man nicht meint.
Ich dachte eigentlich auch an Teile und Herrsche, Binäre Suche, Operatorenüberladungen, lazy evaluations/Reduktion oder Formuliermöglichkeiten in Haskell oder die vielen Dialekte von Lisp und Lisp ist ja so ein morph-ding.
Zum Thema Modularität fällt mir noch so einiges ein, wäre ja z.B. nicht schlecht, mal Windows modular zu laden. Früher, als die Rechner noch viel zu wenig Arbeitsspeicher hatten, konnte man sich sparsame, modular angelegte Betriebsysteme je nach Bedarf laden (könnte man heutzutage auch machen, um mehr kürzere Bootzeiten und höhere Sicherheit zu erreichen). Bei entsprechend globaler Technik könnten Betriebsysteme ganz andere Maschinen hervorzaubern, (in dem Sinne, mein Rechner kann auch ein Föhn sein oder so). Fasm mag ich u.a. deswegen, weil man eigentlich (wirklich) alles machen kann, ohne Riesenbibliotheken und Schnittstellenprobleme oder Eingeschränktheiten mitzuschleppen. In Assembler profitiert man sehr von sorgsamer Modulbauweise, etwa um Fehler einzuschränken und um die Lesbarkeit und Plegeleichtigkeit zu erhöhen. Aber Assembler eignet sich wohl kaum für wissenschaftliche Journalartikel.
...oder wenn jede neue Programmier-Sprache nicht immer gleich anderes Klimbim mitschleppen würde, sowas wie Kommentarzeichen jedes mal anders, oder Klammerregelungen, Schlüsselbegriffe oder äußere Konventionen, das muß in Zukunft anders werden, standardisierter, glaube ich, sonst kommt man vielleicht gar nicht mehr so recht hinter den technischen Fortschritt hinterher(diverse Basic-Dialekte haben wohl auch nicht gerade zur Verbreitung der netten Einsteigersprache Basic beigetragen). Wenn man von C nach Haskell umsteigt, darf man sich erstmal wundern, z.B. wo wohl die BinäreOctalHexzahlausgabe versteckt ist, oder wie man das Celsius/Fahrenheit Proggi aus K+R hinbekommt (man bräuchte 2 senkrecht-Listen), sowas muss auch nicht unbedingt sein. Vom Vertrauten zum Unvertrauten ist ein leichterer Weg als totale Überfremdung.
-
Christoph schrieb:
Gregor schrieb:
Und auch bei Graphenalgorithmen wird es so etwas geben. Da kenne ich mich zwar nicht wirklich aus, aber ich bin mir ziemlich sicher, dass es dort eine ganze Menge Problemstellungen gibt, die in einem Graphen mit nur wenig Kanten wesentlich effizienter zu lösen sind als in einem vollständigen Graphen.
Ich glaube was du hier suchst, sind Baumzerlegungen. Die Baumweite eines Graphen ist eine natürliche Zahl, die misst, wie ähnlich ein Graph einem Baum ist. Bäume haben Baumweite 1, eine Clique mit n Knoten hat Baumweite n-1. Größer als n-1 kann die Baumweite eines Graphen mit n Knoten nie werden. Cliquen sind also in diesem Sinne maximal nicht-lokal.
das ist sicherlich eine Möglichkeit, diese Lokalität zu fassen.
Wobei es das auch nur bedingt trifft. Nimm zum Beispiel einen Gittergraph, man würde ja gerne sagen, dass der unglaublich lokal ist -- ist er aber in diesem Sinne nicht, er hat Baumbreite .Es gibt übrigens noch eine ganze Reihe weitere solcher Graphparameter: Pfadbreite, Branch-Width (keine Ahnung wie das auf deutsch heißt), Clique-Width etc. und für viele davon gibt es Probleme, die sich bezüglich dem jeweiligen Paramter effizient lösen lassen.
Vielleicht geht auch Fixed-Parameter Tractability in die Richtung die Du suchst: http://en.wikipedia.org/wiki/Fixed-parameter_tractability
Da ist die Idee, dass man die Komplexität von NP-schweren Problemen versucht in einem Parameter k einzufangen, der unabhängig von der Eingabegröße ist. Instanzen die bezüglich dem Parameter leicht sind, lassen sich dann auch bei sehr großen Eingabegrößen noch leicht lösen. Ich denke dieser Ansatz subsummiert den Effekt, den Du von Deinem Lokalitätseffekt vermutlich erhoffst.
-
Bei dieser Frage geht es nicht um 'informatorisches' und die 'Lokalität' (was immer das ist). Für alle Algorithmen ist zunächst einmal das Ziel wichtig und wie man dieses Ziel rechenbar und dann lösbar beschreiben kann. Für viele Dinge in der realen Welt gibt es keine verlässlichen Algorithmen zur Lösung, weil man die Parameter und die Zusammenhänge nicht kennt oder man dafür keine ausreichende Information erhalten kann.
-
berniebutt schrieb:
Bei dieser Frage geht es nicht um 'informatorisches' und die 'Lokalität' (was immer das ist).
Doch, genau um Lokalität geht es, und zwar per Definition, weil Gregor nämlich nach Lokalität gefragt hat. Du bist einfach nur off-topic.
-
Um nochmal auf den Startpost zurückzukommen, bzw. darauf, dass das Thema im Studium nicht angesprochen wurde: das Ganze wird sehr allgemein unter dem Lokalitätsprinzip der Informatik zusammengefasst. Quasi eine Pi*Daumen Regel wie die 80/20 Regel, die sich auf die räumliche und zeitliche Lokalität von Daten bezieht.
-
maximAL schrieb:
Um nochmal auf den Startpost zurückzukommen, bzw. darauf, dass das Thema im Studium nicht angesprochen wurde: das Ganze wird sehr allgemein unter dem Lokalitätsprinzip der Informatik zusammengefasst. Quasi eine Pi*Daumen Regel wie die 80/20 Regel, die sich auf die räumliche und zeitliche Lokalität von Daten bezieht.
Das beschreibt aber eher eine andere Art von Lokalität,nämlich die von Daten zum effizienteren Zugriff. Das macht aber nicht den Unterschied zwischen Problemen, die effiziente Lösungen zulassen und solche diees nicht tun. -- Zumindest ist das bei allem so was ich auf die schnelle zum Thema Lokalitätsprinzip gefunde habe.