Quais são as boas fórmulas matemáticas a saber para programação? [fechadas]

Quais são algumas das fórmulas matemáticas comuns que você aprendeu que o ajudaram a escrever algoritmos melhores e a se tornar um programador melhor?

Exemplo: eu aprendi sobre a fórmula da distância ecludiana: sqrt((x1-x2)^2+(y1-y2)^2)que me ajudou a entender como encontrar objetos semelhantes, comparando dois fatores.

Conhecer as potências de 2 é útil, especialmente ao lidar com operações bit a bit de baixo nível.

A álgebra booleana já foi mencionada, mas eu queria fornecer alguns exemplos práticos.

A álgebra booleana é útil com freqüência quando você trabalha com expressões booleanas complexas (em ifinstruções por exemplo).

Algumas expressões e leis úteis:

Distribuição

A e (B | C) = (A e B) | (A e C)

A (B & C) = (A | B) & (A | C)

Então, da próxima vez que você se deparar com essa expressão:

if((A || B) && (A || C) && (A || D) && (A || E)) { ... }

Você pode reduzi-lo facilmente para:

if(A || (B && C && D && E)) { ... }

Negação e lei de De Morgan

! (! A) = A

! (A e B) =! A | ! B

! (A | B) =! A &! B

Digamos que você tenha essa afirmação:

if(!A && !B && !C) {..}

e você precisa construir o oposto disso. Escrevendo:

if(!(!A && !B && !C)) {...}

funcionaria, mas não parece tão legal quanto este equivalente:

if(A | B | C) {...}

Na minha experiência, as fórmulas matemáticas são usadas para cálculos muito específicos, que podem ou não se aplicar ao seu projeto.

Se você precisar calcular algo, geralmente há uma função em uma biblioteca ou um exemplo de código-fonte ao redor que pode calcular isso para você. Por exemplo, a função PMT () do Excel, que calcula os pagamentos necessários para pagar uma dívida em X% ao longo de períodos Y. Deseja realmente saber como o calcula ou é suficiente apenas chamar o embutido?

Nos últimos 10 anos, acho que não precisei usar nada da biblioteca de matemática além de Ceil (), Min () e Max (), que mostra que, apesar de os computadores terem sido criados para resolver problemas baseados em matemática , o uso comum hoje é a tomada de decisões em torno do fluxo de dados.

Tomemos, por exemplo, o Facebook, que possui uma enorme quantidade de código. Provavelmente há alguma matemática em algum lugar, mas suspeito principalmente na API Crypto, que provavelmente é uma biblioteca de sistemas. Mas o acesso ao banco de dados, as decisões de autorização, a criação de páginas e o roteamento de informações provavelmente não usam muito o Math.

Sim, existem mercados que precisam de muita matemática - finanças, física, engenharia - mas, nesses setores, é mais provável que sua disciplina principal seja matemática / economia, física, engenharia, etc. fórmula f (x) na língua Y?

Um melhor uso do seu tempo, IMO, seria investigar algoritmos (incluindo a notação Big O) e padrões de design.

Não existe uma fórmula que possa torná-lo um programador melhor.

As habilidades relacionadas à matemática podem torná-lo um programador melhor:

• Método científico - maneira de pensar matemática / ciência e resolução de problemas
• Abstração - capacidade de reconhecer abstrações e padrões
• Herança - reutilização de trabalhos / métodos existentes na solução de novos problemas
• Experiência - compreendendo um conjunto de problemas e soluções

É bom saber as fórmulas estatísticas básicas. Eu usei regressão linear pelo menos algumas vezes.

Eu gostaria de mencionar as séries de Taylor, que são bastante úteis para obter aproximações rápidas de funções "mais pesadas". Por exemplo, em sin(x)torno de 0 pode ser aproximado com x-(x*x*x/6).

Em geral, a ideia de que existem maneiras inteligentes de aproximar as coisas rapidamente, em vez de calculá-las para o último dígito significativo (embora, para funções elementares, a maioria dos processadores modernos contenha implementações rápidas e cabeadas, usar o Taylor para aproximar o pecado pode não ser tão significativo ganho de velocidade).

As leis de De Morgan, sobre a transformação de booleano "e" e "ou" em relação às negações, e alguns boatos mais elementares relacionados à lógica booleana (como a negação dupla).

Regra de três (tipo de multiplicação cruzada)

+1 para fórmulas estatísticas básicas.

Vi muitos caras com dificuldade de aplicar essa regra simples no código básico.

Sequência e série de matemática.

Já vi muitas escolas ensinando "escrever um loop para somar todos os números entre x e y" em vez de "algoritmos são INCRÍVEIS"

Também ... https://docs.google.com/viewer?url=http://courses.csail.mit.edu/6.042/fall10/mcs-ftl.pdf

Lei dos Cossenos , muito importante para muitos problemas geométricos,

especialmente determinação de ângulo.

A programação é um campo muito amplo. A fórmula matemática depende da área de programação em que você está. Se você gosta de gráficos, programação de jogos, precisa conhecer mais trigonometria, geometria. A programação de jogos pode ser mais categorizada em áreas como física, renderização, shader ... e a lista continua. Portanto, se você é um especialista em simulação de física, deve saber coisas relacionadas à Física.
Se você gosta de segurança, deve ser um especialista em Teoria dos Números.
Em geral, você pode fazer uma combinação desses, e qual seja o seu interesse. Aprender nunca é demais.

Métodos de Prova

Mais notavelmente, os que usei com frequência relativa:

• Prova de exaustão (muitas vezes esquecida, mas considerando o poder das máquinas atualmente, muitas vezes é mais viável do que alguns pensariam)
• Prova por indução
• Prova por contradição

Existem mais, e eu já usei muitos deles em um ponto ou outro, mas esses são os 3 que me lembro de ter usado de relance. Eles também são infinitamente úteis se você puder manter a intenção deles ao escrever testes de unidade ou integração.

T (n) = aT (n / b) + f (n), a> = 1, b> 1

O Teorema Mestre é bom saber para programação. Permite resolver relações de recorrência que podem ajudá-lo a encontrar a complexidade dos algoritmos recursivos. Isso é particularmente importante ao escrever um algoritmo no estilo "dividir e conquistar". Grosso modo, você pode usar o teorema mestre para obter a complexidade se souber a complexidade de cada "etapa" e o fator de ramificação.

• álgebra
• trigonometria
• vetor (operações de matriz)
• cálculo
• [várias interpolações e seus derivados]
• [superfícies, NURBS]

(aqueles entre parênteses são mais do tipo "aplicado")

É difícil dar orientações gerais, pois depende muito do campo em que você se encontra. Mas o exposto acima aborda o básico de vários graus de engenharia. Lembre-se de que essas categorias geralmente se sobrepõem (trigonometria + operações da matriz, cálculo + operações da matriz e assim por diante).

Eu sempre tenho um manual de matemática por perto. Muitas vezes, alguém não tem certeza de algo e ajuda a apresentá-lo de maneira organizada.

Conhecer álgebra booleana ajuda muito. Evita que você escreva códigos como

if (x < 10)
    return true;
else
    return false;

Para problemas de otimização, é bom entender a probabilidade do log. Por exemplo, se você está tentando minimizar uma soma de quadrados, é o mesmo que maximizar o log da probabilidade, porque (grosso modo)

log( Product( exp( -(x[i]-mean)^2 )) )
  =
  - Sum( (x[i]-mean)^2 )

Outros favoritos no domínio do ajuste de desempenho são as distribuições Binomial e Beta. Eles são muito simples de calcular.

Se você coletar 10 amostras aleatórias do estado de um programa, e ele estiver em uma determinada condição por F = 40% do tempo, será como um experimento de sorteio com uma moeda injusta. O número de vezes que você a verá nessa condição é uma distribuição binomial com média 10 * 0,4 = 4 e desvio padrão de sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

Por outro lado, se você pegar 10 amostras e vê-lo nessa condição em 4 amostras, o que isso diz sobre o tamanho de F? Os possíveis resultados são 0, 1, 2, 3, 4, ..., 9, 10. Essas são 11 possibilidades, e a possibilidade que você viu (4) é a quinta. Portanto, pegue 11 números aleatórios uniformes (0,1) e os ordene. A distribuição do quinto é a distribuição de F, uma distribuição Beta. Seu modo é 4/10. Sua média é 5/11. Sua variância é 5 * 6 / (11 ^ 2 * 12) = 0,021 e desvio padrão = 0,144.

Muitas pessoas pensam que é necessário um grande número de amostras para localizar problemas de desempenho de software e evitar encontrar falsos. Essas distribuições mostram que um pequeno número de amostras pode revelar muito sobre seu custo.

Isso pode ser um pouco simples, mas G=(V,E)é bom ter em mente. Em outras palavras, um gráfico é um conjunto de vértices e arestas. Os gráficos são muito úteis para representar muitas coisas.