Quelles sont les bonnes formules mathématiques à connaître pour la programmation? [fermé]

Quelles sont les formules mathématiques quelque peu courantes que vous avez apprises qui vous ont aidé à écrire de meilleurs algorithmes et à devenir un meilleur programmeur?

Exemple: J'ai appris la formule de la distance écludienne: sqrt((x1-x2)^2+(y1-y2)^2)ce qui m'a aidé à comprendre comment trouver des objets similaires en comparant 2 facteurs.

Connaître les pouvoirs de 2 est pratique, en particulier lorsqu'il s'agit d'opérations au niveau du bit de bas niveau.

L'algèbre booléenne a déjà été mentionnée, mais je voulais fournir quelques exemples pratiques.

L'algèbre booléenne est très pratique lorsque vous travaillez avec des expressions booléennes complexes (dans des ifinstructions par exemple).

Quelques expressions et lois utiles:

Distributivité

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

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

Alors la prochaine fois que vous tomberez sur une telle expression:

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

Vous pouvez facilement le réduire à:

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

Négation et loi de De Morgan

! (! A) = A

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

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

Disons que vous avez une telle déclaration:

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

et vous devez en construire l'opposé. L'écriture:

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

fonctionnerait, mais n'a pas l'air aussi cool que cet équivalent:

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

D'après mon expérience, les formules mathématiques sont utilisées pour des calculs très spécifiques, qui peuvent ou non s'appliquer à votre projet.

Si vous avez besoin de calculer quelque chose, il y a généralement une fonction dans une bibliothèque ou un exemple de code source qui peut le calculer pour vous. Par exemple, la fonction PMT () d'Excel, qui calcule les paiements requis pour rembourser une dette à X% sur Y périodes. Voulez-vous vraiment savoir comment il le calcule ou suffit-il d'appeler celui intégré?

Au cours des 10 dernières années, je ne pense pas avoir eu besoin d'utiliser quoi que ce soit de la bibliothèque Math autre que Ceil (), Min () et Max (), ce qui montre que même si les ordinateurs ont été conçus pour résoudre des problèmes mathématiques , l'utilisation courante aujourd'hui est la prise de décision concernant le flux de données.

Prenez, par exemple, Facebook, qui a une énorme quantité de code. Il y a probablement des maths quelque part, mais je soupçonne principalement dans l'API Crypto, qui est probablement une bibliothèque système. Mais l'accès à la base de données, les décisions d'autorisation, la création de pages et le routage des informations n'utilisent probablement pas beaucoup de mathématiques.

Oui, il y a des marchés qui ont besoin de beaucoup de mathématiques - finance, physique, ingénierie - mais dans ces industries, votre discipline principale est plus susceptible d'être les mathématiques / économie, physique, ingénierie, etc., donc vos questions seraient `` comment puis-je écrire formule f (x) dans la langue Y? »

Une meilleure utilisation de votre temps, IMO, serait d'étudier les algorithmes (y compris la notation Big O) et les modèles de conception.

Aucune formule ne peut faire de vous un meilleur programmeur.

Les compétences en mathématiques peuvent faire de vous un meilleur programmeur:

• Méthode scientifique - pensée mathématique / scientifique et résolution de problèmes
• Abstraction - capacité de reconnaître les abstractions et les schémas
• Héritage - réutilisation des travaux / méthodes existants pour résoudre de nouveaux problèmes
• Expérience - comprendre un ensemble de problèmes et de solutions

Les formules statistiques de base sont bonnes à savoir. J'ai utilisé la régression linéaire au moins quelques fois.

Je voudrais mentionner les séries Taylor qui sont très utiles pour obtenir des approximations rapides des fonctions "plus lourdes". Par exemple, sin(x)environ 0 peut être approximé avec x-(x*x*x/6).

En général, l'idée qu'il existe des moyens intelligents d'approximer les choses rapidement, au lieu de les calculer au dernier chiffre significatif (bien que pour les fonctions élémentaires, la plupart des processeurs modernes contiennent des implémentations câblées rapides, donc l'utilisation de Taylor pour approximer le péché peut ne pas être si importante gain de vitesse).

Les lois de De Morgan, sur la transformation booléenne "et" et "ou" par rapport aux négations, et quelques bribes plus élémentaires connexes sur la logique booléenne (comme la double négation).

Règle de trois (type de multiplication croisée)

+1 pour les formules de statistiques de base.

J'ai vu beaucoup de gars avec difficulté appliquer cette règle simple sur le code de base.

Mathématiques de séquence et de série .

J'ai vu trop d'écoles enseigner "écrire une boucle pour additionner tous les nombres entre x et y" au lieu de "les algorithmes sont IMPRESSIONNANTS"

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

Loi des cosinus , très importante pour beaucoup de problèmes géométriques,

en particulier la détermination de l'angle.

La programmation est un domaine très large. La formule mathématique dépend du domaine de programmation dans lequel vous vous trouvez. Si vous êtes dans le graphisme, la programmation de jeux, vous devez en savoir plus sur la trigonométrie, la géométrie. La programmation des jeux peut être classée dans des domaines comme la physique, le rendu, le shader ... et la liste continue. Donc, si vous êtes un expert en simulation physique, vous devez connaître les choses liées à la physique.
Si vous êtes en sécurité, vous devez être un expert en théorie des nombres.
En général, vous pouvez utiliser une combinaison de ceux-ci et quel que soit votre intérêt. Apprendre ne fait jamais de mal.

Méthodes de preuve

Plus particulièrement, ceux que j'ai utilisés avec une fréquence relative:

• Preuve par épuisement (souvent négligé, mais compte tenu de la puissance des machines de nos jours, c'est souvent plus viable que certains ne le pensent)
• Preuve par induction
• Preuve par contradiction

Il y en a plus, et j'en ai utilisé beaucoup à un moment ou à un autre, mais ce sont les 3 que je me souviens avoir utilisés en un coup d'œil. Ils sont également infiniment utiles si vous pouvez garder à l'esprit leur intention lors de l'écriture de tests unitaires ou d'intégration.

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

Master Theorem est bon à savoir pour la programmation. Il vous permet de résoudre des relations de récurrence qui peuvent vous aider à trouver la complexité des algorithmes récursifs. Ceci est particulièrement important lors de l'écriture d'un algorithme de style "diviser pour mieux régner". En gros, vous pouvez utiliser le théorème maître pour obtenir la complexité si vous connaissez la complexité de chaque "étape" et le facteur de branchement.

• algèbre
• trigonométrie
• vecteur (opérations matricielles)
• calcul
• [diverses interpolations et leurs dérivées]
• [surfaces, NURBS]

(ceux entre parenthèses sont plutôt du type "appliqué")

Il est difficile de donner des directives générales, car cela dépend fortement du domaine dans lequel vous vous trouvez. Mais ce qui précède couvre les bases de nombreux diplômes d'ingénieur. Remarquez que ces catégories se chevauchent souvent (trigonométrie + opérations matricielles, calcul + opérations matricielles, etc.).

J'ai toujours un manuel mathématique à proximité. On est souvent incertain de quelque chose, et il est utile de le présenter de manière organisée.

Connaître l'algèbre booléenne aide beaucoup. Cela vous empêche d'écrire du code comme

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

Pour les problèmes d'optimisation, il est bon de comprendre la vraisemblance du journal. Par exemple, si vous essayez de minimiser une somme de carrés, cela revient à maximiser le journal de la probabilité, car (grosso modo)

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

Les distributions binomiales et bêta sont d'autres favoris dans le domaine de l'optimisation des performances. Ils sont très simples à calculer.

Si vous prenez 10 échantillons aléatoires de l'état d'un programme et qu'il est dans une certaine condition pour F = 40% du temps, alors c'est comme une expérience de tirage au sort avec une pièce injuste. Le nombre de fois où vous le verrez dans cette condition est une distribution binomiale avec une moyenne de 10 * 0,4 = 4 et un écart-type de sqrt (10 * 0,4 * 0,6) = sqrt (2,4) = 1,55.

D'un autre côté, si vous prenez 10 échantillons et que vous le voyez dans cet état sur 4 échantillons, qu'est-ce que cela vous dit sur la taille de F? Les résultats possibles sont 0, 1, 2, 3, 4, ..., 9, 10. C'est 11 possibilités, et la possibilité que vous avez vue (4) est la 5e. Donc, prenez 11 nombres aléatoires uniformes (0,1) et triez-les. La distribution du 5ème est la distribution de F, une distribution Beta. Son mode est 4/10. Sa moyenne est de 5/11. Sa variance est de 5 * 6 / (11 ^ 2 * 12) = 0,021 et l'écart-type = 0,144.

Beaucoup de gens pensent qu'un grand nombre d'échantillons est nécessaire pour localiser les problèmes de performances logicielles et éviter d'en trouver de faux. Ces distributions montrent qu'un petit nombre d'échantillons peut en révéler beaucoup sur leur coût.

Cela peut être un peu simple, mais G=(V,E)c'est une bonne chose à garder à l'esprit. En d'autres termes, un graphique est un ensemble de sommets et d'arêtes. Les graphiques sont tellement utiles pour représenter beaucoup de choses.