XD blog

blog page

algorithme


2014-10-11 Machine learning et algorithme

Il existe plein d'outils pour manipuler les données, pandas, R, Excel, ... Ces outils font la plupart des choses pour nous et pourtant parfois, on a besoin de calculer un indicateur imprévu. C'est la cas du drawdown qui est un indicateur financier qu'on calcule parfois sur la performance d'un produit financier. Naïvement, on implémente une solution qui n'est pas toujours optimale et pourtant son calcul est identique à celui de la sous-séquence de plus grande somme qui est un algorithme classique.

2014-06-14 Sports Scientist et Big Data

Les équipes de football équipent leurs joueurs de capteurs, un sur chaque jambe. Ils enregistrent leurs déplacement, les trajectoires des ballons, et moulinent le tout grâce à des statisticiens spécialisés dans le domaine : Big data football club, Le football professionnel à l'heure du big data, Big Data: Would number geeks make better football managers?. Sports Scientist est le terme qui regroupe les métiers qui étudient le sport sous un angle scientifique. Le statisticien est devenu l'un d'entre deux.

2014/10/30

Un article plus récent paru sur le sujet : La Data Révolution (dans le football et l'Equipe).

2015/02/01

Un autre article plus récent paru sur le sujet : Crowdsourcing ou algorithme : comment évaluer le prix d’un joueur de foot ? (rue89).

2014-06-11 Torsion de problèmes

Il n'existe le plus souvent aucun algorithme qui réponde exactement à un problème, surtout si c'est le vôtre. Mais ça ne veut pas dire qu'il n'existe pas de solution. Avec un peu d'imagination, il faut arriver à tordre le problème initial pour exploiter des algorithmes connus. Cette torsion sera d'autant plus facile qu'on connaît d'algorithmes. Par exemple, voici trois problèmes :

Et voici trois classes d'algorithmes :

Sauriez-vous apparier un problème avec une classe d'algorithmes qui mèneraient à la solution ?

Un indice : Inférer les trajectoires des velib

2013-11-09 Compter les pièces de monnaie pour obtenir un montant

On est amené presque tous les jours à compter les pièces dans son porte-monnaie pour payer la baguette, le fromage ou la bouteille de vin. Comment écrire un algorithme qui donne la liste des pièces qu'il faut piocher dans son porte-monnaie pour payer ? On s'intéressera seulement au cas où on cherche à composer le montant juste. Cela revient à chercher un sous-ensemble S de pièces dans l'ensemble P des pièces du portefeuille pour composer le montant M :

 M = \sum_{ p \in S } p

Une façon naïve de construire l'ensemble S est de procéder comme on le fait souvent, c'est-à-dire à prendre la pièce la plus grosse, de voir si elle dépasse le montant N puis de passer à la seconde plus grande et ainsi de suite. Soit :

Cela donne le programme suivant :


more...

2013-11-08 De l'idée au programme informatique

Lorsqu'on apprend à programmer, on a souvent une idée précise de l'objectif à atteindre et pourtant, on reste perplexe devant l'écran ne sachant pas par où commencer. Par exemple, si on dispose d'une matrice de trois colonnes :
xypoids
AC3
AD1
AE4
BD6
Et on souhaite calculer combien de fois on a le couple (x,y) divisé par combien de fois on a x :

 \frac{ \# (x,y) } { \# x }

Par exemple, si x=A et y=D, on aura 1 / (3 + 1 + 4) = 0.125. Maintenant, comment s'y prend-on ?

Tout d'abord, on cherche à calculer un ratio de trucs qui ne sont pas des nombres entiers. Un dictionnaire est tout indiqué pour stocker ces trucs car il permet d'associer n'importe quoi (valeur) à presque n'importe quoi (clé). La valeur est une somme d'entiers, la clé est un couple de lettres ou une lettre. Sans me soucier des petits détails, voilà ce que j'ai envie d'écrire comme premier jet :

l = [ ['A','B', 3], ['A','C', 1], 
      ['A','E', 4], ['B','D', 6], ]

def transition(l):
    d = {}
    for x,y,n in l :
        d [x,y] += n  # erreur ici : KeyError: ('A', 'B')
        d [x] += n
    
    for x,y in d :
        d[x,y] /= d [x]
    return d
    
print (transition(l))

Bien sûr ça ne marche pas (voir l'erreur ci-dessus). Mais j'ai foi en moi. La logique est bonne. Lorsque j'écris d [a,b] += n, je suppose que le couple (x,y) existe dans le dictionnaire même la toute première fois. Et c'est pas possible ! Il est vide au début.


more...

2013-03-26 L'informatique, une matière moins noble

Quand j'ai soutenu ma thèse, j'ai découvert que mon doctorat m'offrirait moins de portes académiques tout simplement parce celui-ci me désignait comme docteur en informatique et non en mathématiques. Je ne sais pas si c'est toujours le cas mais l'informatique a toujours eu en France un côté moins noble parce que très appliqué. Aujourd'hui, des phénomènes comme Big Data, Data Scientist prennent de l'ampleur et avec eux l'utilisation de l'informatique. Il est pratiquement impossible de se passer des ordinateurs, dès qu'on aborde un sujet un tant soit peu appliqué, il faut savoir coder, ce que j'ai très peu fait dans un cadre scolaire, ce que j'ai beaucoup fait en dehors de l'école et surtout au travail. On peut prétendre que cela s'apprend facilement, que comprendre les maths est plus difficile, et qu'avec un peu de pratique, on saura faire. Il me serait difficile de réfuter ça, c'est comme ça que j'ai appris. Toutefois, c'est un peu comme les gammes au piano, plus on en fait, plus on est à l'aise.

Cette division math/info est beaucoup moins présente dans les pays anglosaxons où les mathématiques appliquées et l'informatique s'appellent computer science. Lors des entretiens d'embauche, il est rare de passer au travers d'exercices de codes. C'est parfois même le premier filtre écrit préalable au premier entretien. Entre quelqu'un que cela ne rebute pas et quelqu'un qui prend la chose de haut, les sociétés n'hésitent pas longtemps. Même s'il est prétendument facile de devenir programmeur, de nombreuses compagnies ont tendance à rejeter des candidats qui n'ont jamais beaucoup programmé si c'est un élément important du poste à pourvoir.

Les smartphones sont aussi de petits ordinateurs programmables. Il est probable que d'autres objets du quotidien gagneront en complexité et deviendront à leur tour pilotables à l'aide un langage de programmation. Je pense que c'est un outil dont il faudrait commencer l'apprentissage plus tôt. Il en serait moins rébarbatif et, accessoirement, n'en limiterait plus l'usage aux seuls geeks. C'est d'ailleurs le cas dans certains pays de l'est comme la Roumanie. Maîtriser la programmation pourrait faire gagner beaucoup de temps à quiconque se sert d'Excel au quotidien.

Lorsqu'on doit pondre un algorithme qui doit tourner en production 24h sur 24, savoir coder est très important. Il peut y avoir des facteurs 10 ou 100 sur le même algorithme programmé de façon plus ou moins efficace. Savoir programmer n'est pas tout, il est utile d'apprendre les tournures de phrases les plus fréquentes, d'acquérir une sorte de culture générale du domaine, savoir ce que sont des tableaux, des arbres, savoir quand il est préférable d'utiliser l'un plutôt que l'autre, savoir pourquoi quand on divise un problème en deux, on passe d'un coût en O(n) à un coût en O(ln(n)), comprendre pourquoi il vaut mieux utiliser un index lorsqu'on fait une jointure sur deux tables SQL...

En ce qui concerne l'informatique, j'ai quasiment tout appris en pratiquant, parce que terminer un programme signifie aussi l'avoir compris. La pratique permet aussi de comprendre qu'il existe rarement un programme optimal en toute circonstance et qu'on choisira une façon de coder plutôt qu'une autre en fonction du volume, de la nature des données qu'on manipule. De ce fait, beaucoup de programmes sont une compilation complexe de recettes simples. On s'aperçoit aussi parfois qu'on retrouve le même algorithme sous différents visages, plus court chemin dans un graphe de Djikstra, distance d'édition de Levenstein, séquence la plus probable de Viterbi.

Je manipule tellement de données qu'en regarder quelques-unes ne suffit plus à donner une vue d'ensemble. Il faut sans cesse agrégrer, classifier, régresser. Ce travail est quasiment impossible si on ne sait pas programmer. Cette culture algorithmique me permet bien souvent d'aller plus vite, d'obtenir les mêmes résultats en un temps moindre avec, parfois, une certaine élégance.

Pour finir, je conseille l'écoute d'une émission de radio que j'ai découverte après avoir écrit ceci : L'éloge du savoir, Algorithmes, machines et langages (entretien avec Gérard Berry) L'informatique est train de changer la façon d'organiser nos vies et il est mal enseigné aujourd'hui et surtout trop tard. Que sera notre monde dans les prochaines années (et non les prochaines décennies) ? Nos dirigeants ne prennent la mesure des changements que l'informatique n'a pas fini d'apporter comme le dit Michelle Volle dans cet article : Pour comprendre l'iconomie.


Xavier Dupré