Existe análise matemática algorítmica?

Existem teoria algorítmica dos grafos / teoria dos números / combinatória / teoria da informação / teoria dos jogos.

Existe análise matemática algorítmica?

Segundo o wiki, a análise matemática inclui as teorias de diferenciação, integração, medida, limites, séries infinitas e funções analíticas. Não há problema em focar na análise real (wiki) que lida com os números reais e as funções com valor real de uma variável real.

"Algorítmico" significa estudar algo a partir das perspectivas da teoria da computabilidade e da teoria da complexidade.

A pesquisa em "análise matemática algorítmica" me leva a "análise matemática de algoritmos" ou "aplicações de análise a algoritmos", que não é o que quero dizer.

Confira a rede Computabilidade e complexidade na análise . Citar:

Os tópicos de interesse incluem trabalhos fundamentais sobre vários modelos e abordagens para descrever a computabilidade e a complexidade em relação aos números reais. Eles também incluem investigações teóricas da complexidade, fundamentais e relacionadas a problemas concretos, e novas implementações da aritmética real exata, bem como desenvolvimentos adicionais de pacotes de software já existentes.

(Isenção de responsabilidade: não sou especialista, não hesite em sugerir correções ou, se for o caso, escreva uma resposta mais abrangente.)

$e^x$ não é computável no modelo BSS.

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

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

Formular uma teoria da complexidade para funções reais é, AFAIK, ainda mais difícil. Isso está relacionado ao fato de que computar uma função real é uma computação de ordem superior (uma vez que é usada uma máquina de Turing como entrada); portanto, o tamanho do bit da entrada geralmente não é a coisa certa para medir o tempo de execução. Verifique este artigo de Mark Braverman para uma abordagem para definir a computação real eficiente. Neste ponto, estou muito longe de dizer mais, então vou parar.

A referência clássica para a complexidade do cálculo de funções reais é:

• Ker-I Ko, Complexidade computacional de funções reais, 1991

Veja também o capítulo 7 do livro de Weirauch.

Olhando para esta pergunta mais de dois anos depois de ter sido publicada e, sem ofensas, estou decepcionado com as respostas e comentários.

É o que acontece quando os departamentos de CS do mundo todo rotulam seus tópicos e enganam várias gerações de cientistas e engenheiros.

• As classes de algoritmos em todos os departamentos de CS precisam ser rotuladas novamente para algoritmos discretos .

• Ou o conteúdo atual dessa classe precisa ser reduzido para 50% ou menos (que 50% ou menos inclui Estruturas de Dados ) e a metade restante precisa incluir uma variedade de tópicos de Análise Numérica e Computação Científica .

Porque qual é o núcleo da Análise Matemática ? Análise real e a linha real. E como os números reais são representados nos computadores? ponto flutuante ou precisão arbitrária etc. Então, da próxima vez que você estiver trabalhando em um algoritmo que lide com ponto flutuante e / ou precisão arbitrária como componente principal (não como conteúdo, como na classificação de vários números de ponto flutuante) , saiba que você está fazendo Análise Matemática Algorítmica (AMA)!

E nem me inicie com o universo massivo de tópicos de NA / Ciência da Computação. Sem dúvida, supera todo o TCS. Ao resolver sistemas de vários PDEs não lineares em um computador, você não está apenas utilizando os fundamentos da análise matemática, mas também a análise funcional de ponta em toda a sua glória, com problemas de pesquisa abertos, etc. obter mais AMA do que isso.