Onde estão “Números especiais” mencionados nas matemáticas de concreto usado?

Question

Eu estava olhando através dos conteúdos de Matemática concretas online. Eu tinha pelo menos ouviu falar a maioria das funções e truques mencionados, mas há uma seção inteira sobre Números especiais. Estes números incluem Números Stirling, Números de Euler, Números de harmónicas assim por diante. Agora eu nunca encontrei qualquer um desses números estranhos. Como eles ajudar em problemas computacionais? Onde eles estão geralmente usado?

Answer 1

A maioria destes números contam certos tipos de estruturas discretas (por exemplo, Stirling Números contar Subconjuntos e ciclos). Tais estruturas, e, portanto, estas seqüências, surgem implicitamente no análise de algoritmos .

Há uma extensa lista de OEIS que as listas < em> quase todas as seqüências que aparecem na matemática Concrete . Um breve resumo dessa lista:

• Sequência de Golomb
• Binomial Coeficientes
• Rencontres Números
• Números Stirling
• Números de Euler
• Hyperfactorials
• Números Genocchi

Você pode navegar pelas páginas OEIS para as respectivas sequências para obter informações detalhadas sobre as "propriedades" de essas sequências (embora não exatamente aplicações, se é isso que você está em mais interessados).

Além disso, se você quiser ver os usos reais de essas sequências em análise de algoritmos, flip através do índice de Art of Computer Programming do Knuth, e você vai encontrar muitas referências a "aplicações" destas sequências. John D. Cook já mencionado aplicações de números de Fibonacci e harmônicas; aqui estão mais alguns exemplos:

Números Stirling Cycle surgem na análise do algoritmo padrão que encontra o elemento máximo de um array (TAOCP Sec 1.2.10.): Quantas vezes deve o valor máximo atual ser atualizado quando encontrar o valor máximo? Acontece que a probabilidade de que o máximo terá de haver momentos k atualizados quando encontrar um máximo em uma matriz de elementos n é p[n][k] = StirlingCycle[n, k+1]/n!. A partir disso, podemos deduzir que, em média, atualizações aproximadamente Log(n) será necessário.

Números Genocchi surgir em conexão com contagem do número de BDDs que são "fina" (TAOCP 7.1.4 Exercício 174).

Answer 2

Números harmônicas aparecem quase todos os lugares! Musical Harmonies, análise de Quicksort ... Números Stirling (primeiro e segundo tipo) surgem numa variedade de combinatória e problemas de particionamento. Números de Euler também ocorrem vários lugares, principalmente em permutações e coeficientes de funções polilogarítmo.

Answer 3

Um monte de números que você mencionou são utilizados na análise de algoritmos. Você pode não ter estes números em seu código, mas você vai precisar deles se você quiser estimar quanto tempo levará para que seu código seja executado. Você pode vê-los em seu código também. Alguns destes números estão relacionados com a análise combinatória, contagem de quantas maneiras algo pode acontecer.

Às vezes não é o suficiente para saber quantas possibilidades existem, porque você precisa enumerate sobre as possibilidades. Volume 4 de Knuth TAOCP , em andamento, dá os algoritmos que você precisa.

Aqui está um exemplo do uso Fibonacci números como parte de um problema de integração numérica.

números harmônicas são um análogo discreto de logaritmos e assim eles vêm para cima em equações de diferenças apenas como troncos surgem em equações diferenciais. Aqui está um exemplo de aplicações físicas da Média Harmônica , relacionada com números de harmónicas. Veja o livro Gamma para muitos exemplos de números harmônicos em ação, especialmente o capítulo "é um mundo harmônico."

Answer 4

Estes números especiais podem ajudar em problemas computacionais em muitas maneiras. Por exemplo:

• Você quer descobrir quando seu programa para calcular o GCD de 2 números vai levar a maior quantidade de tempo:. Tente 2 números de Fibonacci consecutivos

• Você quer ter uma estimativa aproximada do fatorial de um número grande, mas o seu programa factorial está levando muito tempo: Use o Stirling aproximação .

• Você está testando para números primos, mas para alguns números que você sempre obter a resposta errada: Poderia ser que você está usando teste de injeção de Fermat, caso em que o noreferrer números Carmicheal são seus culpados.

O caso geral comum máximo que eu posso pensar é em looping. Na maioria das vezes você especificar um loop usando um tipo (start;stop;step) da sintaxe, caso em que pode ser possível para reduzir o tempo de execução usando propriedades dos números envolvidos.

Por exemplo, somando-se todos os números de 1 a n, quando n é grande em um ciclo é definitivamente mais lento do que usando o sum = n*(n + 1)/2 identidade.

Há um grande número de exemplos como estes. Muitos deles estão em criptografia, onde a segurança dos sistemas de informação, por vezes, depende em truques como estes. Eles também podem ajudá-lo com problemas de desempenho, problemas de memória, porque quando você sabe a fórmula, você pode encontrar um caminho mais rápido / mais eficiente para calcular outras coisas -. Coisas que você realmente se preocupam com

Para obter mais informações, consulte a wikipedia, ou simplesmente experimentar Projeto Euler. Você vai começar a encontrar padrões muito rápido.

Answer 5

Não necessariamente um número mágico a partir da referência que você mencionou, mas mesmo assim -

0x5f3759df

- o número mágico famoso usado para calcular inversa da raiz quadrada de um número, dando uma boa primeira estimativa para Newton Aproximação de Raízes , muitas vezes atribuída à obra de John Carmack - mais informações aqui .

Não programação relacionada, hein? :)

Answer 6

É este directamente relacionados com programação? Certamente relacionados, mas eu não sei o quão perto.

Números especiais, como e, pi, etc., vêm-se por todo o lugar. Eu não acho que ninguém iria discutir sobre estes dois. O href="http://en.wikipedia.org/wiki/Golden_ratio" rel="nofollow noreferrer"> Golden_ratio olhar também aparece com incrível frequência, em tudo, desde a arte para outros próprios números especiais (pelo a razão entre os números de Fibonacci sucessivos.)

Várias seqüências e famílias de números também aparecem em muitos lugares em matemática e, portanto, na programação também. Um belo lugar para olhar é a Enciclopédia de seqüências inteiras .

Vou sugerir isso é uma coisa experiência. Por exemplo, quando eu tirei álgebra linear, muitos, muitos anos atrás, eu aprendi sobre os valores e vectores próprios de uma matriz. Eu vou admitir que eu não fiz nada apreciar o significado de valores próprios / eigenvectors até que eu vi-los em uso em uma variedade de lugares. Em estatística, em termos do que eles dizem sobre a incerteza de uma estimativa a partir de uma matriz de covariância, o tamanho ea forma de uma elipse de confiança, em termos de análise de componentes principais, ou o estado a longo prazo de um processo de Markov. Em métodos numéricos, onde eles informá-lo sobre a convergência de um método, seja na otimização ou um solucionador ODE. Em engenharia mecânica, onde você vê-los como tensões principais e as tensões.

Answer 7

discussão no Reddit