ti-enxame.com

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

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.

19
GSto

Conhecer os poderes de 2 é útil, especialmente quando se lida com operações bit a bit de baixo nível.

16
AShelly

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 (nas instruções if _ por exemplo).

Algumas expressões e leis úteis:

distributividade

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 facilmente reduzi-lo 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) {...}
15
serg

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, embora os computadores tenham 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 existe alguma matemática em algum lugar, mas suspeito principalmente na API Crypto, que provavelmente é uma biblioteca de sistema. 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., então suas perguntas seriam 'como posso escrever fórmula f(x) no idioma Y? '

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

9
JBRWilkinson

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 - modo 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
7
Branimir

Eu gostaria de mencionar série Taylor , que são bastante úteis para obter aproximações rápidas de funções "mais pesadas". Por exemplo, sin(x) em 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 até 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).

6
Joonas Pulakka

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

6

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).

3
Peter Eisentraut

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

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

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

2
Pagotti

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 categorizada em áreas como física, renderização, sombreador 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 optar por uma combinação dessas opções e sempre que interessar. Aprender nunca é demais.

2
user4626

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

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.

2
Kurtis

Sequência e séries 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

2
Incognito

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

alt text

especialmente determinação de ângulo.

2
user1842

Métodos de prova

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

Há mais, e 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ê pode manter a intenção em mente ao escrever testes de unidade ou integração.

2
Steven Evers

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

if (x < 10)
    return true;
else
    return false;
1
fredoverflow
  • álgebra
  • trigonometria
  • vetor (operações de matriz)
  • cálculo
  • [várias interpolações e seus derivados]
  • [superfícies, NURBS]

(os que estão entre colchetes são mais do tipo "aplicado")

É difícil dar orientações gerais, pois depende muito do campo em que você se encontra. Mas o que foi dito acima cobre os princípios básicos de muitos graus de engenharia. Lembre-se, 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.

1
Rook

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 em tempo aleatório 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 resultados possíveis 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 do software e evitar encontrar falsos. Essas distribuições mostram que um pequeno número de amostras pode revelar muito sobre seu custo.

1
Mike Dunlavey

Isso pode ser um pouco simples, mas G=(V,E) é bom para se 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.

0
Jason Baker