Depuis que je programme en Python, j’entasse les petits bouts de code utiles ou potentiellement réutilisables dans « Goulib », ma librairie perso et néanmoins disponible en open-source (licence LGPL) sur Pypi, GitHub, ReadTheDocs pour la doc, avec des notebooks Jupyter de démo. Comme la valeur d’un code se mesure surtout par les tests […]
Algorithmes
8 articles
Tombé l'autre jour sur un problème idiot mais intéressant : calculer le 10^19 ième terme de la suite de Fibonacci. Idiot parce que ça ne sert à rien. Intéressant parce que ça sous-entend qu'il existe une manière de calculer le n-ième terme de cette suite définie par récurrence sans calculer les termes précédents. En effet, calculer les termes les uns après les autres prendrait dans les 300'000 ans à raison d'une microseconde par terme.
Voici un petit problème qui se présente assez fréquemment sous diverses formes, et pour lequel j’ai été surpris de ne pas trouver de solution bien documentée. Le cas le plus simple apparaît souvent dans les tableurs : en calculant des pourcentages arrondis, le total ne fait parfois pas 100%. En […]
Les amateurs de jeux de cartes savent qu’il faut accorder beaucoup d’attention au brassage des cartes pour éviter la triche, mais qu’en est-il par exemple dans les jeux de poker en ligne ? Les informaticiens se sont beaucoup cassé la tête sur le tri des données, mais relativement peu sur […]
Le gars qui m’a pourri ma dernière soirée du printemps s’appelle Mike Croucher. Sur son blog « Walking Randomly » il a négligemment posé le problème suivant: Il est possible d’écrire beaucoup d’entiers comme la somme des cubes de 3 entiers, par exemple: 99 = (-5)^3 + 2^3+ 6^3 Un exemple plus compliqué est: 91 = […]
Dans les années 800, le mathématicien perse Abou Jafar Muhammad Ibn Mūsa al-Khuwārizmī introduit le zéro (indien) dans les chiffres arabes, décrit comment résoudre les équations du second degré, et propose de résoudre certains problèmes mathématiques en répétant une séquence d’opérations jusqu’à ce qu’un « critère d’arrêt » soit satisfait. Au XIIème siècle, […]
En informatique, le tri est une opération incontournable car il est beaucoup plus rapide de rechercher une information dans une liste triée que dans un fouillis. C’est pourquoi j’ai longtemps cru qu’une liste triée contenait plus d’information qu’une liste non triée, car je voyais le tri comme un pré-traitement permettant […]
Si vous ne connaissez pas Shazam, demandez à un propriétaire d’iPhone (eux) ou de Google Phone sous Androïd (nous) de vous montrer cette application incroyable. Si personne dans votre entourage ne vit au 21ème siècle, vous pouvez toujours regarder cette démonstration en video. Vous ne rêvez pas : Shazam est capable […]