Czy istnieje algorytmiczna analiza matematyczna?

Istnieją teorie grafów algorytmicznych / teoria liczb / kombinatoryka / teoria informacji / teoria gier.

Czy istnieje algorytmiczna analiza matematyczna?

Według wiki analiza matematyczna obejmuje teorie różniczkowania, całkowania, miary, limitów, szeregów nieskończonych i funkcji analitycznych. Można skupić się na analizie rzeczywistej (wiki), która zajmuje się liczbami rzeczywistymi i funkcjami wartości rzeczywistej zmiennej rzeczywistej.

„Algorytmiczny” oznacza badanie czegoś z perspektywy teorii obliczalności i teorii złożoności.

Googlowanie „algorytmicznej analizy matematycznej” prowadzi mnie do „matematycznej analizy algorytmów” lub „zastosowania analizy do algorytmów”, co nie mam na myśli.

Sprawdź sieć obliczalności i złożoności w analizie . Zacytować:

Tematy zainteresowań obejmują fundamentalne prace nad różnymi modelami i podejściami do opisu obliczalności i złożoności w stosunku do liczb rzeczywistych. Obejmują one również badania teoretyczne dotyczące złożoności, zarówno fundamentalne, jak i dotyczące konkretnych problemów, oraz nowe implementacje dokładnej prawdziwej arytmetyki, a także dalszy rozwój już istniejących pakietów oprogramowania.

(Uwaga: nie jestem ekspertem, nie krępuj się sugerować poprawki lub napisz bardziej wyczerpującą odpowiedź, jeśli tak.)

$e^x$ nie jest obliczalny w modelu BSS.

$f: \mathbb{R} \to \mathbb{R}$$f(x)$$x$

$f:[0,1] \to [0,1]$

Sformułowanie teorii złożoności rzeczywistych funkcji jest, AFAIK, jeszcze trudniejsze. Jest to związane z faktem, że obliczenie rzeczywistej funkcji jest obliczeniem wyższego rzędu (ponieważ jako dane wejściowe przyjmuje maszynę Turinga), więc rozmiar bitów danych wejściowych zwykle nie jest właściwy do pomiaru czasu działania. Sprawdź ten artykuł Mark Braverman pod kątem jednego podejścia do definiowania efektywnego obliczania rzeczywistego. W tym momencie jestem daleko od mojej głębi, aby powiedzieć więcej, więc przestanę.

Klasyczne odniesienie do złożoności obliczeń rzeczywistych funkcji to:

• Ker-I Ko, Złożoność obliczeniowa rzeczywistych funkcji, 1991

Zobacz także rozdział 7 w książce Weirauch.

Patrząc na to pytanie ponad dwa lata po opublikowaniu i bez urazy jestem rozczarowany odpowiedziami i komentarzami.

Tak się dzieje, gdy działy CS na całym świecie błędnie opisują swoje tematy i wprowadzają w błąd wiele pokoleń naukowców i inżynierów.

• Albo Klasy Algorytmów we wszystkich działach CS muszą zostać ponownie oznakowane na Algorytmy dyskretne .

• Lub obecna zawartość tej klasy musi zostać zmniejszona do 50% lub mniej (ta 50% lub mniej obejmuje struktury danych ), a pozostała połowa musi zawierać pewien asortyment tematów z analizy numerycznej i obliczeń naukowych .

Ponieważ jaki jest rdzeń analizy matematycznej ? Analiza rzeczywista i prawdziwa linia. A w jaki sposób liczby rzeczywiste są reprezentowane w komputerach? zmiennoprzecinkowa lub dowolna precyzja itp. Więc następnym razem pracujesz nad dowolnym algorytmem, który zajmuje się zmiennoprzecinkową i / lub dowolną precyzją jako kluczowym składnikiem (nie jako treść, jak podczas sortowania wiązki liczb zmiennoprzecinkowych) , wiedz, że wykonujesz algorytmiczną analizę matematyczną (AMA)!

I nawet nie zaczynaj mi z ogromnym wszechświatem tematów NA / Computational Science. Prawdopodobnie krąży nad całym TCS. Kiedy rozwiązujesz na komputerze systemy wielu nieliniowych PDE, nie tylko wykorzystujesz podstawy analizy matematycznej, ale także najnowocześniejszą analizę funkcjonalną w pełnej krasie, z otwartymi problemami badawczymi itp. Nie może dostać więcej AMA niż to.