Gibt es eine algorithmische mathematische Analyse?

Es gibt algorithmische Graphentheorie / Zahlentheorie / Kombinatorik / Informationstheorie / Spieltheorie.

Gibt es eine algorithmische mathematische Analyse?

Laut Wiki umfasst die mathematische Analyse die Theorien der Differenzierung, Integration, Messung, Grenzen, unendlichen Reihen und analytischen Funktionen. Es ist in Ordnung, sich auf die reale Analyse (Wiki) zu konzentrieren , die sich mit den reellen Zahlen und reellen Funktionen einer reellen Variablen befasst.

"Algorithmisch" bedeutet, etwas aus den Perspektiven der Berechenbarkeitstheorie und der Komplexitätstheorie zu studieren.

Das Googeln von "algorithmischer mathematischer Analyse" führt mich zu "mathematischer Analyse von Algorithmen" oder "Anwendungen der Analyse auf Algorithmen", was ich nicht meine.

Überprüfen Sie das Netzwerk für Berechenbarkeit und Komplexität in der Analyse . Zitat:

Zu den interessanten Themen gehören grundlegende Arbeiten zu verschiedenen Modellen und Ansätzen zur Beschreibung der Berechenbarkeit und Komplexität über die reellen Zahlen. Dazu gehören auch komplexitätstheoretische Untersuchungen, sowohl grundlegend als auch in Bezug auf konkrete Probleme, sowie neue Implementierungen exakter reeller Arithmetik sowie Weiterentwicklungen bereits vorhandener Softwarepakete.

(Haftungsausschluss: Ich bin kein Experte, kann Korrekturen vorschlagen oder eine umfassendere Antwort schreiben, wenn Sie dies sind.)

Das Erweitern der Berechenbarkeit und Komplexität auf die reellen Zahlen (was ein erster Schritt bei der Analyse ist) ist schwierig und wurde auf verschiedene ungleiche Arten durchgeführt. Eines davon ist das BSS-Modell (Blum-Shub-Smale), das Turing-Maschinen um die Fähigkeit erweitert, algebraische Operationen mit reellen Zahlen zu speichern und auszuführen. Die resultierende Theorie hat einen algebraischen Geschmack, z. B. sind alle berechenbaren Funktionen stückweise halbalgebraisch. Das Modell ist interessant, weist jedoch einige seltsame Merkmale auf, die es unrealistisch erscheinen lassen, zumindest als Modell dafür, wie Computer tatsächlich mit der Berechnung reeller Zahlen umgehen. Zum Beispiel erlaubt es die Berechnung mit nicht berechenbaren Konstanten: Die Konstantenfunktion mit dem Wert Chaitins Konstante ist im BSS-Modell berechenbar. Andererseits ist im BSS-Modell nicht berechenbar.$e^x$

Ein anderer Ansatz kann im Bereich der berechenbaren Analyse gefunden werden , und ich denke, das ist es, wonach Sie suchen. Eine Einführung finden Sie im Buch von Weihrauch (die Einführung und das Kapitel über berechenbare reelle Zahlen finden Sie auf der verlinkten Seite und geben Ihnen eine gute Vorstellung davon, was los ist). Es gibt hier noch einige nicht ganz äquivalente Modelle, aber die grobe Idee ist, dass rationale Zahlen eine endliche Repräsentation haben, und dann konstruieren Sie die berechenbaren Reals genauso, wie Sie die Reals als Vervollständigung der Rationals konstruieren. Analog zur Definition eines Real als (Äquivalenzklasse von) einer Cauchy-Folge von Rationalen wird ein berechenbares Real von einer Turing-Maschine gegeben, die willkürlich gute Annäherungen daran berechnet. Dann eine Funktion f ( x ) $f: \mathbb{R} \to \mathbb{R}$ ist berechenbar, wenn eine Turing-Maschine beliebig gute Näherungen von berechnen kann, wenn (als Orakel) eine Maschine willkürlich gute Näherungen von berechnet .$f(x)$$x$

Es gibt faszinierende Zusammenhänge zwischen berechenbarer Analyse und klassischer / moderner Analyse und vielen anderen Bereichen, beispielsweise der algorithmischen Zufälligkeit. Ein einfaches Beispiel für einen Satz ist, dass alle berechenbaren Funktionen stetig sind. Um ein differenzierteres Beispiel zu geben (ohne auf die Details einzugehen), gibt es interessante Gegenstücke zu klassischen Theoremen in der Analyse, z. B. ein Analogon zu Rademachers Theorem ist, dass alle berechenbaren Lipschitz-Funktionen sind an allen algorithmisch zufälligen Punkten differenzierbar (für den richtigen Begriff der algorithmischen Zufälligkeit).$f:[0,1] \to [0,1]$

Die Formulierung einer Komplexitätstheorie für reale Funktionen ist AFAIK noch schwieriger. Dies hängt mit der Tatsache zusammen, dass das Berechnen einer realen Funktion eine Berechnung höherer Ordnung ist (da eine Turing-Maschine als Eingabe verwendet wird), sodass die Bitgröße der Eingabe normalerweise nicht das richtige ist, um die Laufzeit zu messen. In diesem Artikel von Mark Braverman finden Sie einen Ansatz zur Definition einer effizienten realen Berechnung. An diesem Punkt bin ich weit aus meiner Tiefe heraus, um mehr zu sagen, also werde ich aufhören.

Die klassische Referenz für die Komplexität der Berechnung realer Funktionen lautet:

• Ker-I Ko, Computerkomplexität realer Funktionen, 1991

Schauen Sie sich auch Kapitel 7 in Weirauchs Buch an.

Wenn ich mir diese Frage mehr als zwei Jahre nach ihrer Veröffentlichung ansehe, bin ich von den Antworten und Kommentaren enttäuscht.

Dies ist der Fall, wenn CS-Abteilungen auf der ganzen Welt ihre Themen falsch kennzeichnen und mehrere Generationen von Wissenschaftlern und Ingenieuren irreführen.

• Entweder müssen die Algorithmenklassen in allen CS-Abteilungen in diskrete Algorithmen umbenannt werden .

• Oder der aktuelle Inhalt dieser Klasse muss auf 50% oder weniger reduziert werden (50% oder weniger enthalten Datenstrukturen ), und die verbleibende Hälfte muss eine Auswahl von Themen aus der numerischen Analyse und dem wissenschaftlichen Rechnen enthalten .

Denn was ist der Kern der mathematischen Analyse ? Reale Analyse und die reale Linie. Und wie werden reelle Zahlen in Computern dargestellt? Gleitkomma oder willkürliche Genauigkeit usw. Wenn Sie also das nächste Mal an einem Algorithmus arbeiten, der Gleitkomma und / oder willkürliche Genauigkeit als Kernkomponente behandelt (nicht als Inhalt, wie beim Sortieren einer Reihe von Gleitkommazahlen) , wissen Sie, dass Sie Algorithmic Mathematical Analysis (AMA) durchführen!

Und bringen Sie mich nicht einmal in das riesige Universum der NA / Computational Science-Themen ein. Es stellt wohl die gesamte TCS in den Schatten. Wenn Sie Systeme mit mehreren nichtlinearen PDEs auf einem Computer lösen, nutzen Sie nicht nur die Grundlagen der mathematischen Analyse, sondern auch die neuesten Funktionsanalysen in ihrer ganzen Pracht, einschließlich offener Forschungsprobleme usw. Dies ist nicht möglich Holen Sie sich nicht mehr AMA als das.