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

19

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.

GSto
la source
2
Je ne pense pas que ce soit la formule de distance euclidienne.
Greg Hewgill
@Larry @Greg édité.
GSto
haha que diriez-vous de la séquence fibo ... bon pour l'analyse comparative
aggietech
1
Date d'achèvement = (date estimée + nombre de jours restants / 2) ^ (temps au travail / temps à la maison) * Nombre de pizzas gratuites
Skizz
7
vous trouverez peut-être intéressant de savoir que si vous avez juste besoin de comparer les distances, vous pouvez sauter l' sqrtétape. Pour une boucle intérieure serrée, cela pourrait être important.

Réponses:

16

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

AShelly
la source
+1 - Être capable de se convertir aux bases 2, 16, 10 et 8 est indispensable.
mouviciel
2
Je ne suis pas sûr de la base-8, mais je suis d'accord avec 2,16 et 10 conversions. Vous devez être capable de le faire dans un délai raisonnable, mais pas nécessairement instantanément.
Incognito
Mon seul professeur est un animal hexagonal. Convertit dans sa tête des chiffres ridicules et j'ai été TA pour lui pendant un an environ, la classe a toujours été impressionnée comme moi.
Chris
Je déteste la base 8 :)
1
Avec les macros, les énumérations et les champs de bits dans les langues modernes, dans quels cas les gens ont-ils besoin de connaître les puissances de 2, qui sont des nombres fondamentalement magiques ... setsockopt(...SO_KEEPALIVE..)est beaucoup plus facile à lire ou à écrire quesetsockopt(...16...)
JBRWilkinson
15

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) {...}
serg
la source
2
Le problème avec cela, c'est s'il s'agit de règles commerciales réelles, car celles-ci ont tendance à CHANGER. Si tel est le cas, vous devez reconstruire l'expression d'origine afin de la modifier, puis l'optimiser à nouveau. Les responsables ont tendance à grogner en faisant cela.
Et c'est là qu'une carte de Karnaugh peut vous aider. Cela ne fonctionne bien que sur 4 drapeaux booléens à la fois, mais si vous en avez besoin de plus, bonne chance!
Job
3
+1 pour la loi de De Morgan. Je suis étonné du peu de gens qui semblent l'avoir appris et qui savent comment l'appliquer.
Fortyrunner
Vous avez oublié celui - ci: (P -> Q) <=> (!P | Q). Je l'utilise tout le temps car très peu d'environnements proposent un opérateur d'implication logique, c'est une équivalence très pratique pour les contraintes SQL CHECK.
mu est trop court le
La loi de Karnaugh et De Morgan est quelque chose qu'on vous enseigne généralement à utiliser dans les cours de génie électrique, mais pas dans les cours de génie informatique. Ce qui est étrange, car des applications peuvent être trouvées dans ce dernier comme l'utilisation pratique de la loi de De Morgan mentionnée ci-dessus.
Spoike du
9

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.

JBRWilkinson
la source
1
+1 parce que cela semble être une déclaration raisonnable - il n'y a pas de formule spécifique que vous devriez connaître, mais le concept de complexité algorithmique (notation Big O) est très important.
Michael H.
Beaucoup de mathématiques ... Décide avec quelles publicités vous déranger.
Je suis d'accord que la quantité de mathématiques nécessaire est généralement assez faible, bien que mon expérience ne soit pas aussi faible que la vôtre - je finis par utiliser périodiquement des éléments trigonométriques dans les graphiques.
Loren Pechtel
7

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
Branimir
la source
-1, l'homme a posé des questions sur les FORMULES DE MATH utiles. Je ne peux pas croire que cette réponse ait été votée du tout.
Jas
6

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

Joonas Pulakka
la source
3

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

Peter Eisentraut
la source
2

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.

Pagotti
la source
+1 pour la multiplication croisée. Dans certains logiciels sujets à des problèmes de dépassement d'entier, la multiplication croisée est utilisée pour vérifier que les résultats ne dépassent pas.
rwong
2
Pas grave. Cela devrait être ancré dans la tête d'un diplômé du secondaire qui souhaite étudier la CS.
Job
@Job: Dans un monde théorique, c'est vrai!
Pagotti
2

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

texte alternatif

en particulier la détermination de l'angle.


la source
quel est le gamma dans cette équation?
Matt Ellen
1
@Matt Ellen: l'angle du côté à travers le côté C (IOW, l'angle entre A et B)
Lie Ryan
2
Et bien sûr, cas particulier pour les triangles rectangles:a^2 + b^2 = c^2
Note à soi-même - pensez à un nom
2

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.


la source
2

Méthodes de preuve

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

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.

Steven Evers
la source
2

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.

Kurtis
la source
1
pourquoi est-il bon de savoir pour la programmation?
Matt Ellen
@MattEllen: Il vous permet de résoudre les 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.
Tikhon Jelvis
1
  • 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.

Tour
la source
1

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;
fredoverflow
la source
Je ne suis pas sûr de comprendre comment l'algèbre booléenne aide à empêcher un utilisateur d'écrire cela? Pouvez-vous proposer ce que l'utilisateur devrait y écrire? (Je suppose que return x <10; mais je peux me tromper.)
Chris
1
Vous avez raison - il doit renvoyer x <10. Pense-y de cette façon. L'évaluation (x <10) renvoie un résultat booléen. L'instruction if se décompose alors en [si x est en effet inférieur à 10] si (true) renvoie true; ou [si x est supérieur ou égal à 10] si (faux) ... sinon retourne faux;
Eric Olsson
2
Le (x <10) peut séparer deux analyses de rentabilisation. Avec le formulaire détaillé, vous pouvez faire plus que simplement renvoyer des valeurs, ce qui est très agréable en mode maintenance, car vous pouvez limiter les modifications au minimum
1

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.

Mike Dunlavey
la source
0

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.

Jason Baker
la source