Existe-t-il une analyse mathématique algorithmique?

Il y a la théorie algorithmique des graphes / théorie des nombres / combinatoire / théorie de l'information / théorie des jeux.

Existe-t-il une analyse mathématique algorithmique?

Selon wiki, l'analyse mathématique comprend les théories de la différenciation, de l'intégration, de la mesure, des limites, des séries infinies et des fonctions analytiques. Il est normal de se concentrer sur une analyse réelle (wiki) qui traite des nombres réels et des fonctions à valeur réelle d'une variable réelle.

"Algorithmique" signifie étudier quelque chose du point de vue de la théorie de la calculabilité et de la théorie de la complexité.

La recherche sur «l'analyse mathématique algorithmique» me conduit à «l'analyse mathématique des algorithmes» ou «applications de l'analyse aux algorithmes», ce qui n'est pas ce que je veux dire.

Découvrez le réseau Computability and Complexity in Analysis . Citation:

Les sujets d'intérêt comprennent les travaux de base sur divers modèles et approches pour décrire la calculabilité et la complexité sur les nombres réels. Ils comprennent également des investigations théoriques sur la complexité, à la fois fondamentales et par rapport à des problèmes concrets, et de nouvelles implémentations de l'arithmétique réelle exacte, ainsi que de nouveaux développements de progiciels déjà existants.

(Avertissement: je ne suis pas un expert, n'hésitez pas à suggérer des corrections ou à écrire une réponse plus complète si vous l'êtes.)

$e^x$ n'est pas calculable dans le modèle BSS.

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

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

La formulation d'une théorie de la complexité pour les fonctions réelles est, AFAIK, encore plus délicate. Cela est lié au fait que le calcul d'une fonction réelle est un calcul d'ordre supérieur (car il prend une machine de Turing en entrée), donc la taille en bits de l'entrée n'est généralement pas la bonne chose pour mesurer le temps d'exécution. Consultez cet article de Mark Braverman pour une approche de la définition d'un calcul réel efficace. À ce stade, je suis loin de ma profondeur pour en dire plus, alors je vais m'arrêter.

La référence classique pour la complexité du calcul des fonctions réelles est:

• Ker-I Ko, Complexité informatique des fonctions réelles, 1991

Jetez également un œil au chapitre 7 du livre de Weirauch.

En examinant cette question plus de deux ans après sa publication et, sans m'offenser, je suis déçu des réponses et des commentaires.

C'est ce qui se produit lorsque les départements CS du monde entier trompent leurs sujets et trompent plusieurs générations de scientifiques et d'ingénieurs.

• Soit les classes d' algorithmes dans tous les départements CS doivent être réétiquetées en algorithmes discrets .

• Ou le contenu actuel de cette classe doit être réduit à 50% ou moins (ce 50% ou moins comprend les structures de données ) et la moitié restante doit inclure un assortiment de sujets de l' analyse numérique et du calcul scientifique .

Parce que quel est le cœur de l'analyse mathématique ? Analyse réelle et ligne réelle. Et comment les nombres réels sont-ils représentés dans les ordinateurs? virgule flottante, ou précision arbitraire, etc. Donc, la prochaine fois que vous travaillez sur un algorithme qui traite de la virgule flottante et / ou de la précision arbitraire comme un composant de base (pas comme un contenu, comme dans le tri d'un groupe de nombres à virgule flottante) , sachez que vous faites de l'analyse mathématique algorithmique (AMA)!

Et ne me lancez même pas dans le vaste univers des sujets NA / Computational Science. Il éclipse sans doute l'ensemble du TCS. Lorsque vous résolvez des systèmes de plusieurs PDE non linéaires sur un ordinateur, vous utilisez non seulement les principes fondamentaux de l'analyse mathématique, mais l'analyse fonctionnelle de pointe dans toute sa splendeur, avec des problèmes de recherche ouverts, etc. obtenir plus d'AMA que cela.