Où sont « numéros spéciaux » mentionnés en mathématiques concrètes utilisées?

StackOverflow https://stackoverflow.com/questions/901761

Question

je feuilletant le contenu de maths en ligne en béton. Je l'avais au moins entendu la plupart des fonctions et astuces mentionnées, mais il y a toute une section sur les numéros spéciaux. Ces chiffres comprennent les nombres de Stirling, nombres, Eulerian Rangs harmoniques ainsi de suite. Maintenant, je ne l'ai jamais rencontré aucun de ces chiffres étranges. Comment font-ils aider dans les problèmes de calcul? Où sont-ils généralement utilisés?

Était-ce utile?

La solution

La plupart de ces nombres comptent certains types de structures discrètes (par exemple, nombres de Stirling et les cycles comptent Sous-ensembles). De telles structures, et donc ces séquences, se posent implicitement dans le analyse des algorithmes .

Il est une longue liste à OEIS qui liste < em> presque toutes les séquences qui apparaissent en mathématiques béton . Un bref résumé de cette liste:

  • La séquence de Golomb
  • Binomial Coefficients
  • Numéros Rencontres
  • Numéros de Stirling
  • nombre eulérien
  • Hyperfactorials
  • Nombres Genocchi

Vous pouvez parcourir les pages OEIS pour les séquences respectives pour obtenir des informations détaillées sur les « propriétés » de ces séquences (mais pas exactement les applications, si c'est ce que vous êtes plus intéressés).

En outre, si vous voulez voir la vie réelle utilisation de ces séquences dans l'analyse des algorithmes, feuilletez l'index de l'art Knuth de programmation informatique, et vous trouverez de nombreuses références à « applications » de ces séquences. John D. Cook déjà mentionné applications de nombres de Fibonacci et harmoniques; voici quelques exemples:

Numéros de cycle Stirling se produire dans l'analyse de l'algorithme standard qui trouve l'élément au maximum d'un tableau (TAOCP Sec 1.2.10.): Combien de fois doit-il valeur maximale actuelle mise à jour pour trouver la valeur maximale? Il se trouve que la probabilité que le maximum devra être mis à jour de temps k lors de la recherche d'un maximum dans un ensemble d'éléments de n est p[n][k] = StirlingCycle[n, k+1]/n!. De là, on peut en déduire que la moyenne, environ les mises à jour Log(n) seront nécessaires.

Nombres Genocchi SURVIENT comptant le nombre de BDD qui sont "minces" (TAOCP 7.1.4 exercice 174).

Autres conseils

Les nombres harmoniques apparaissent presque partout! Harmonies de musique, l'analyse des Quicksort ... Nombres de Stirling (première et deuxième type) apparaissent dans une variété de problèmes combinatoires et de partitionnement. Les nombres eulériens se produisent également plusieurs endroits, notamment dans les permutations et les coefficients de fonctions polylogarithmes.

Beaucoup de chiffres que vous avez mentionnés sont utilisés dans l'analyse des algorithmes. Vous ne pouvez pas avoir ces chiffres dans votre code, mais vous aurez besoin si vous voulez estimer combien de temps il faudra pour que votre code à exécuter. Vous pouvez les voir dans votre code aussi. Certains de ces chiffres sont liés à combinatoires, en comptant combien de façons quelque chose qui peut arriver.

Parfois, il ne suffit pas de savoir combien de possibilités il y a parce que vous devez Enumerate sur les possibilités. Volume 4 de TAOCP de Knuth, en cours, donne les algorithmes dont vous avez besoin.

Voici un exemple d'utilisation nombres de Fibonacci dans le cadre d'un problème d'intégration numérique.

Rangs harmoniques sont un analogue discret de logarithmes et ils viennent dans les équations de différence comme les journaux viennent dans les équations différentielles. Voici un exemple d'applications physiques des moyens harmoniques , liés aux nombres harmoniques. Voir le livre Gamma pour de nombreux exemples de nombres harmoniques dans l'action, en particulier le chapitre « Il est un monde harmonique. »

Ces numéros spéciaux peuvent aider des problèmes de calcul à bien des égards. Par exemple:

  • Vous voulez savoir quand votre programme pour calculer le PGCD de 2 numéros va prendre le plus long laps de temps. Essayez 2 suite de Fibonacci consécutifs

  • Vous voulez avoir une estimation approximative de la factoriel d'un grand nombre, mais votre programme factoriel prend trop de temps: Utiliser Approximation Stirling.

  • Vous testez des nombres premiers, mais pour quelques chiffres que vous obtenez toujours la mauvaise réponse: Peut-être que vous utilisez Premier essai de Fermat, auquel cas le noreferrer numéros Carmicheal sont vos coupables.

Le cas général le plus courant que je peux penser est en boucle. La plupart du temps vous spécifiez une boucle en utilisant un type de syntaxe (start;stop;step), dans ce cas, il peut être possible de réduire le temps d'exécution en utilisant les propriétés des numéros concernés.

Par exemple, additionnant tous les nombres de 1 à n, lorsque n est grand, une boucle est nettement plus lente que la sum = n*(n + 1)/2 d'identité.

Il existe un grand nombre d'exemples comme ceux-ci. Beaucoup d'entre eux sont en cryptographie, où la sécurité des systèmes d'information parfois dépend sur des trucs comme ceux-ci. Ils peuvent également vous aider à des problèmes de performance, problèmes de mémoire, parce que quand vous connaissez la formule, vous pouvez trouver un moyen de calculer d'autres choses plus rapide / plus efficace -. Choses que vous vous souciez vraiment de

Pour plus d'informations, consultez wikipedia, ou essayez simplement de projet Euler. Vous allez commencer à trouver des modèles assez rapide.

Pas nécessairement nombre magique de la référence que vous avez mentionné, mais tout de même - 

0x5f3759df

- le nombre magique notoire utilisé pour calculer la racine carrée inverse d'un nombre en donnant une bonne première estimation à Newton Rapprochement des racines , souvent attribués à l'œuvre de John Carmack - plus d'infos ici .

Programmation associée Non, hein? :)

Est-ce la programmation directement liée? Sûrement connexes, mais je ne sais pas à quel point.

Numéros spéciaux, tels que e, pi, etc., viennent un peu partout. Je ne pense pas que quelqu'un puisse discuter ces deux. Golden_ratio apparaît aussi avec une fréquence étonnante, dans tout l'art à d'autres numéros spéciaux eux-mêmes (voir le rapport entre les nombres de Fibonacci successifs.)

Diverses séquences et les familles des nombres apparaissent également dans de nombreux endroits en mathématiques et, par conséquent, dans la programmation aussi. Un bel endroit pour regarder est Encyclopédie des séquences entières .

Je suggère c'est une chose d'expérience. Par exemple, quand je pris l'algèbre linéaire, beaucoup, il y a plusieurs années, j'ai appris sur les valeurs propres et vecteurs propres d'une matrice. Je dois admettre que je ne l'ai pas du tout apprécier l'importance des valeurs propres / vecteurs propres jusqu'à ce que je les ai vus en cours d'utilisation dans une variété d'endroits. Dans les statistiques, en termes de ce qu'ils vous disent au sujet de l'incertitude d'une estimation à partir d'une matrice de covariance, la taille et la forme d'une ellipse de confiance, en termes d'analyse en composantes principales, ou l'état à long terme d'un processus de Markov. Dans les méthodes numériques, où ils vous renseignent sur la convergence d'une méthode, que ce soit dans l'optimisation ou un solveur ODE. En génie mécanique, où vous les voyez comme principales contraintes et déformations.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top