Wird Smoothed Analysis außerhalb der Wissenschaft verwendet?

24

Hat die geglättete Analyse Eingang in die Hauptstromanalyse von Algorithmen gefunden? Ist es für Algorithmenentwickler üblich, geglättete Analysen auf ihre Algorithmen anzuwenden?

algorithms complexity-theory algorithm-analysis Gilles 'SO - hör auf böse zu sein'
quelle
11
Wenden Menschen außerhalb der Wissenschaft eine Art Komplexitätsanalyse auf ihre Algorithmen an?
Dave Clarke
2
Was @ DaveClarke sagt; Vielleicht sollte er nach strengen (oder nicht trivialen) Analysen fragen . Ich erwarte, dass viele Praktiker sich ihre Algorithmen ansehen, die Schachtelungstiefe der Schleifen zählen und sagen: "Dies ist !". O(n3)
Raphael
3
Auf der Suche nach einer anderen Verwendung der geglätteten Analyse als Simplex fand ich eine Liste, die von einem der Jungs zusammengestellt wurde, der die Technik entdeckte.
Raphael
1
@ DaveClarke Wie wäre es mit Leuten, die bei IBM, HP oder NTT arbeiten? Sollten sie diese Art von Analyse nicht verwenden?
Marcos Villagra
1
@ DaveClarke tue ich.
Kevin

Antworten:

12

Ich könnte mich irren, aber ich betrachte die geglättete Analyse als eine Möglichkeit , das Verhalten von Algorithmen in der Praxis zu erklären , die schlechte theoretische Garantien haben (Simplex, k-Mittelwerte usw.). Ich bin mir nicht sicher , was es bedeuten würde , verwenden geglättet Analyse in der Praxis, mit Ausnahme der Verwendung einer bestimmten Heuristik mit schlechter Worst-Case - Leistung zu rechtfertigen ( "My heuristische bla bla Worst-Case - Verhalten hat aber eine geglättete Analyse zeigt , dass es wird mach dich gut in der Praxis etc etc ")

Suresh
quelle
2
Das Problem ist, dass bis jetzt die großen Erfolge bei der geglätteten Analyse darin bestanden, die derzeitige Praxis zu erklären, sodass die Praktiker möglicherweise nur mit den Worten reagieren: "Nun, es ist schön, dass gezeigt werden kann, dass alles, was ich getan habe, Sinn ergibt." Ich weiß nicht, ob sich jemand dafür entschieden hat, eine bisher weniger bekannte Heuristik zu verwenden, WEIL die Analyse geglättet wurde.
Suresh
Formale geglättete Analyse ist sehr schwierig, es gibt keinen Grund, warum jemand, der nicht theoretisch ist, es übertreffen sollte. Wenn Sie es andererseits als eine Heuristik betrachten, die zum Analysieren eines Algorithmus verwendet wird (die Eingabe ist nämlich halbzufällig), wird sie wahrscheinlich die ganze Zeit verwendet.
Yuval Filmus
3

Die Art und Weise, wie Menschen Algorithmen in der realen Welt analysieren, unterscheidet sich stark von der akademischen Welt. Während es im akademischen Bereich das Ziel ist, eine nachweislich korrekte Obergrenze für die Laufzeit zu finden, ist es im wirklichen Leben das Ziel zu verstehen, wie der Algorithmus funktioniert und welche Optimierungen die Laufzeit verbessern können. Es gibt zwei Hauptmethoden, die in der Wissenschaft verboten sind, aber in der Praxis angewendet werden:

  • Die Methode der Annäherung. Hier verwenden Sie viele vereinfachende Annahmen, um die Laufzeit eines Algorithmus vorherzusagen. Ähnlich wie theoretische Physiker.
  • Experimentieren. Sie führen Ihren Algorithmus aus und messen mehrere Statistiken - wie viel Zeit für jedes Teil aufgewendet wurde, wie oft jede Funktion aufgerufen wurde, wie oft jeder Zweig ausgeführt wurde usw. Diese Informationen können zur Optimierung des Algorithmus verwendet werden. Experimente werden auch verwendet, um herauszufinden, ob einige Annäherungen, die während der Analyse des Algorithmus vorgenommen wurden, in der Praxis funktionieren oder nicht.

Abgesehen davon glaube ich nicht, dass es üblich ist, einen Algorithmus in der Praxis zu analysieren, außer einen Fülltext in eine verwandte akademische Publikation einzufügen. Der Fokus liegt je nach Thema entweder auf Software-Engineering oder auf Low-Level-Optimierung.

Schließlich ist eine geglättete Analyse eine Heuristik, mit der erklärt werden kann, warum Algorithmen in der Praxis besser funktionieren, als es der schlimmste Fall vermuten lässt, nämlich weil einige der Eingaben in gewissem Sinne "zufällig" sind. Diese Heuristik kann verwendet werden, um das Verhalten des Algorithmus zu approximieren, wenn die Approximationsmethode verwendet wird.

Yuval Filmus
quelle
"Während in der Wissenschaft das Ziel ist, eine nachweislich korrekte Obergrenze für die Laufzeit zu finden" - das ist ein Ziel, nicht das Ziel. Es gibt auch viel Arbeit zur durchschnittlichen Fallanalyse, auch wenn der durchschnittliche CS-Student möglicherweise nicht viel davon sieht (weil es relativ schwierig ist). "Zu verstehen, wie der Algorithmus funktioniert" ist wohl die Grundlage aller Algorithmen in der Wissenschaft.
Raphael