Récemment, une question a été posée lors d'un forum en ligne: combien les mathématiques sont-elles demandées dans les conditions d'un vrai programmeur, à quelle fréquence les utilise-t-il et quels sont ses domaines? Et voici ma réponse.
Tout d'abord, comme presque tous les programmeurs, j'utilise
la logique booléenne , de l'analyse des expressions logiques pour les instructions conditionnelles et les critères de sortie, pour aligner ces expressions, par exemple, avec
les lois de Morgan . La plupart de nos travaux frisent le
calcul des prédicats du premier ordre et d'autres logiques de prédicats sous forme d'analyse des conditions préalables, des invariants, etc. (bien qu'il puisse sembler que nous faisons d'autres tâches).
De plus, je m'engage souvent dans l'analyse de la complexité des algorithmes. Les dimensions des ensembles de données en cours de traitement de nos jours sont énormes. Lors d'une conférence
Techonomy 2010
, Eric Schmidt a déclaré que le volume de données créées par l'humanité aujourd'hui en seulement deux jours est égal au volume de toutes les données existantes dans le monde en 2003. Il est important pour moi de pouvoir traiter de larges segments de ces volumes et d'en bénéficier. Et dans ce sens, comprendre la
complexité spatio-temporelle des opérations que nous appliquons aux données est la clé pour déterminer si certains calculs sont en principe possibles. Contrairement aux types plus traditionnels d'
analyse O ou d'
analyse thêta, les facteurs constants à de telles échelles ont un effet significatif: le facteur 2 ne modifie pas la complexité temporelle asymptotique de l'algorithme, mais nécessitera une augmentation du nombre de processeurs de 10 000 à 20 000, et une telle différence de consommation les ressources seront tangibles. En conséquence, les calculs deviennent plus sophistiqués. Exemples: puis-je prendre un calcul linéaire et le réduire à un calcul logarithmique? Est-il possible de réduire la consommation de mémoire de trois fois? Et ainsi de suite.
Souvent, je dois calculer la variante la plus défavorable de la limite supérieure, disons, la taille de certains ensembles de données. Dans de nombreux cas, ces calculs peuvent être non triviaux. Ou vous devrez peut-être analyser une
formule de récurrence pour vérifier comment elle change à mesure que la profondeur de la récursivité augmente. Pour cela, je dois, entre autres choses, connaître le
théorème de base sur les relations de récurrence et comment comprendre les principes d'analyse des
séries de
nombres . Et cela peut sembler incroyable, mais cela signifie parfois que je dois calculer l'
intégrale (bien que la plupart du temps uniquement les intégrales de
Riemann ). Ou puis-je simplement résoudre la relation récursive et obtenir un
nombre fini de solutions ? Dois-je recourir à
l'algèbre linéaire ? Cela conduit à des choses comme la
génération de fonctions , les
nombres de Stirling ,
les calculs
matriciels . Si vous êtes curieux de savoir ce qui est inclus dans l'ensemble des concepts mathématiques fondamentaux nécessaires à la compréhension de l'informatique, reportez-vous au premier volume de «The Art of Programming» de Donald Knuth, ou «Concrete Mathematics» de Knut, Ronald Graham et Oren Patashnik.
Je fais beaucoup de calculs de base en termes d'agrégation, de combinaison et de transformation de données, et la
combinatoire (compter le nombre, trouver des symétries dans différentes dimensions, etc.) m'aide dans ce domaine. Je pense que les exemples dans ce domaine sont évidents.
J'utilise beaucoup de
mathématiques discrètes , en particulier pour rechercher des systèmes algébriques dans des opérations sur des ensembles de données particulièrement volumineux. Est-il possible d'afficher telle ou telle structure à l'aide de l'
homomorphisme comme un certain
groupe ou
anneau , ce qui sera plus clair pour moi? Existe-t-il une option avec une connexion moins étanche? Puis-je appliquer l'
action d'un groupe à un ensemble pour créer un modèle spéculatif de transformation qui simplifie le raisonnement? Puis-je définir une topologie pour l'analyse des données? Vous seriez surpris si vous saviez combien de choses peuvent être décrites en utilisant
des topologies discrètes . Et encore moins surprenante serait la demande d'
inégalité triangulaire .
Je travaille beaucoup avec la
théorie des graphes . "Création de sites Web" - nécessite non seulement la possibilité de placer des images mignonnes de chats sur la page. Ce processus implique également l'insertion de nœuds dans le graphique global des
hyperliens . L'ajout d'une seule page entraîne une augmentation potentielle du nombre de bords de graphique, ce qui, à son tour, peut avoir un effet qui n'est pas évident à première vue sur les performances, l'analyse, le classement des moteurs de recherche et d'autres caractéristiques. Comprendre les conséquences de tels changements peut aider à obtenir des informations intéressantes, telles que la croissance du graphique. Il s'avère que cette
dynamique est douloureusement similaire à une
loi de puissance : le World Wide Web est un
réseau sans échelle . Quel est le
chemin le
plus court entre deux nœuds de ce graphique? À quoi ressemblera un tel réseau si vous essayez de le présenter sous forme de graphe
planaire ou
bipartite ? Quand est-il possible de rencontrer ces propriétés, si cela est bien sûr possible? Mais que se passe-t-il si nous ne considérons pas le World Wide Web comme un graphique, mais l'ensemble du réseau routier d'Amérique du Nord, d'Europe ou d'Asie?
Il y a d'autres conséquences de cette connaissance. Souvent, les gens ne comprennent pas que les pages Web modernes ne sont pas seulement des documents
HTML avec des liens et d'autres ressources, mais
des structures de données
arborescentes connectées les unes aux autres dans un
graphique . Ces arbres sont souvent explorés, traités et mis à jour dynamiquement en raison de l'interaction entre le navigateur Web de l'utilisateur et un serveur (grâce à des technologies telles que
AJAX ).
MathJax en est un excellent exemple. Ou
Gmail . Comprendre comment ils fonctionnent implique un certain niveau de connaissance de
l'informatique symbolique et de
l'analyse sémantique des éléments de page. Les auteurs de MathJax avaient besoin d'écrire un programme capable de parcourir un arbre généré à partir d'un
modèle objet d'un document , de trouver des éléments mathématiques, de les «
ranger » et de les remplacer dynamiquement par de nouveaux éléments dessinés. Peut-être que certains utilisateurs qui verront comment cela fonctionne ne seront pas très impressionnants, mais des choses assez compliquées se produisent sous le capot. Je n'ai généralement pas à faire quelque chose de similaire (je ne travaille pas avec le front-end), mais tout le temps je fais des choses similaires à
Lisp . Veuillez noter que Lisp a été à l'origine affiné par le traitement mathématique des informations symboliques: ses macros couvrent entièrement les problèmes de traitement des expressions symboliques.
Je travaille beaucoup avec des
séries chronologiques . Comment la consommation de trafic ou de ressources évolue-t-elle? Quelles tendances peuvent être mises en évidence? Est-ce que tel ou tel saut se manifeste dans le retard dans la réponse aux demandes ou la consommation de mémoire
saisonnière ? Comment le
taux de changement de quelque chose réagit-il lorsque les données d'entrée varient dans différentes dimensions? Y a-t-il une
corrélation avec un événement externe?
Je travaille beaucoup avec l'analyse statistique des données, non seulement pour déterminer les caractéristiques de performance, mais aussi pour comprendre les données en tant que telles. En plus de rechercher dans l'arbre DOM susmentionné des métadonnées sémantiques (par exemple, des
microdonnées et
microformats ,
RDF , d'autres données
XML avec un
schéma spécifique), j'essaie également de comprendre
des données non structurées . Quelle est la probabilité que ce texte soit une adresse postale? Ou s'agit-il de
coordonnées graphiques ? Dans quel contexte apparaît-il? Est-ce du
spam ? Est-ce même logique? Cela ressemble-t-il au résultat d'un générateur de texte basé sur
des chaînes de
Markov ? Peut-être s'agit-il d'une série de citations tirées d'une œuvre littéraire bien connue? Ou un fragment d'une discussion littéraire? Ou peut-être s'agit-il d'une discussion sur le spam contenant un fragment littéraire? Je continue de rire chaque fois que je pense à un courrier indésirable contenant des publicités sur les drogues enveloppées dans un fragment du «Maître et Marguerite» de Boulgakov.
Théorie des catégories .
Les types dans les langages de programmation informatique correspondent à peu près aux catégories, et les
monades et les
foncteurs peuvent être utilisés pour simplifier sérieusement et élégamment certaines constructions. Par exemple, dans le langage de programmation
fonctionnelle Haskell, les monades sont utilisées pour les
E / S et pour
la modélisation d'
état . Lorsqu'il s'agit de programmes simplifiés, il est plus facile de les faire fonctionner. C’est plus facile d’en parler, c’est plus facile à comprendre, à changer, etc. Les types peuvent souvent être déterminés sur la base d'un raisonnement logique, ce qui conduit à l'apparition de
cas particuliers (qui peuvent également être utilisés dans des problèmes de raisonnement généraux). Réfléchissez à ce qui se passe si vous utilisez les
conclusions pour appliquer des fonctions logiques, telles que celles utilisées dans
prolog , pour
transformer des graphiques dans
des systèmes distribués .
Les systèmes distribués nous ramènent à la théorie des graphes. Des dysfonctionnements se produisent dans des systèmes du monde réel, des excavateurs déchirant des fibres, des tremblements de terre, des éruptions volcaniques se produisent et des chalutiers de pêche endommagent les câbles marins. Pour comprendre les conséquences de tels événements et déterminer les meilleures façons d'y répondre, vous devez comprendre les caractéristiques du graphique de réseau. Les algorithmes de routage et l'analyse de réseau sont étroitement liés à des choses telles que la
recherche du chemin le plus court entre les nœuds d'un graphique. L'
algorithme de Dijkstra vous y aidera.
Et pourtant, comment répartir la charge d'un grand calcul entre des centres de données situés dans différentes parties du monde? Ici, vous aurez également besoin de connaissances en physique: à l'échelle d'Internet, la
vitesse de la lumière se transforme en «goulot d'étranglement».
La dissipation thermique ,
la densité de courant par unité de surface et bien d'autres sont des exemples de ce que les programmeurs doivent prendre en compte lorsqu'ils travaillent avec des tâches réelles. Dois-je héberger un centre de données en Islande? Des sources de refroidissement et d'énergie géothermique bon marché créent des conditions attrayantes, mais qu'en est-il du délai minimum pour les utilisateurs qui pourraient être intéressés par la location d'équipement dans un tel centre de données? Quelle est la distance le long de l'arc d'un
grand cercle entre, par exemple, l'Islande et Londres, ou Berlin et Amsterdam? Calculer tout cela est assez simple, mais pour cela, il est nécessaire d'avoir certaines connaissances mathématiques. Pouvons-nous envoyer des fibres d'Islande vers un autre centre? Quel est le délai moyen? Quelle est la probabilité de rupture d'un câble sous-marin en mer du Nord pendant 12 mois d'exploitation? Et pendant 48 mois?
Bien sûr, la
théorie des algorithmes , la
théorie des automates , l'
analyse syntaxique ,
la grammaire formelle ,
les langages réguliers sont tous des domaines de connaissance que les programmeurs traitent constamment. Je travaille souvent avec l'analyse et
la mise en correspondance de modèles . Lorsque vous travaillez avec des données du monde réel, même des ensembles de très petite taille peuvent contenir des éléments qui peuvent entraîner
un comportement pathologiquement médiocre lors de l'utilisation, par exemple, de
techniques de retour en arrière . En utilisant
des expressions régulières pour faire correspondre les données, je dois faire attention et m'assurer que ces expressions sont
vraiment régulières .
En utilisant une
machine avec une mémoire de stockage pour analyser
la grammaire sans contexte (ce qui, en passant, se produit chaque fois que vous envoyez une demande à un serveur
HTTP ), je dois m'assurer de limiter la profondeur de récursivité pour éviter d'épuiser la
pile d'appels du processeur, ce qui nécessite une compréhension les principes sous-jacents du calcul et les mathématiques sur lesquelles ils reposent.
Si j'ai besoin d'écrire mon propre
algorithme de descente récursive pour une grammaire inhabituelle et qu'il ne peut pas correspondre à
LALR (1) (donc je ne peux pas simplement utiliser
yacc ou
bison ), je dois faire attention ou garder la pile d'état distincte de la récursion procédurale. Cette compréhension est également nécessaire si je fais le tour de l'arborescence DOM (ou de toute structure de données définie de manière récursive).
Certains langages de programmation considèrent cela comme une difficulté dans le travail d'un programmeur et le contournent en utilisant
des piles segmentées . Bien sûr, ce serait formidable si je pouvais définir ma collection de certaines des ressources analysées sous la forme d'une
fonction (au sens mathématique). Et comment serait-ce cool si cela se résumait à une sorte de problème d'
optimisation de programmation linéaire ?
Veuillez noter qu'aucune des informations ci-dessus n'est une connaissance ésotérique. Tout cela est basé sur l'expérience des tâches et des données du monde réel. Bien sûr, je ne fais pas tout cela tous les jours, mais la plupart de ces connaissances que j'applique régulièrement, et seulement certaines - de temps en temps. L'observation, l'expérience et l'heuristique ont probablement plus d'influence sur le processus qu'elles ne le devraient (les modèles heuristiques sont souvent incomplets et inexacts). Ai-je suffisamment de connaissances mathématiques pour calculer l'
erreur moyenne entre la réalité et mon modèle heuristique?
C'est l'essence même de l'informatique, ainsi que la façon dont ils interagissent avec la programmation et les réalités de l'informatique moderne. Être un professionnel de l'informatique n'est pas la même chose qu'un expert dans le domaine de la théorie informatique, et comme beaucoup le soulignent à juste titre, un tel expert est beaucoup plus proche d'un mathématicien appliqué que d'un artisan spécialisé. En aucun cas, je ne veux minimiser l'importance de tels professionnels, car ils sont utiles et sont universellement respectés, mais je veux juste noter que l'informatique est autre chose.
(Soit dit en passant, je ne suis pas moi-même un expert en informatique. J'ai étudié les mathématiques pures et mon occupation professionnelle est beaucoup plus proche de l'ingénierie.)
