Gamme pythagoricienne
En musique, on change d’octave en doublant la fréquence. On passe à la quinte en multipliant par 3/2.
Billets en français
Aho-Corasick
Étant donnée une liste de chaînes de caractères L, construire une structure de données qui permet en temps linéaire d’identifier toutes les occurrences des mots de L à l’intérieur d’un mot S donné.
Meilleur developpeur de France 2023
Le 9 mars 2023 avait lieu la compétition Meilleur Développeur de France 2023. Les algorithmes nécessaires sont résoudre les problèmes sont assez simples, mais il faut coder rapidement. Après coup, et à tête reposée, voici comment on aurait pu résoudre certains des problèmes.
Six dates importantes en algorithmique
- -300
- Algorithme d’Euclide (qui date peut-être de l’école de Pythagore 530 av. J.C.)
Parcours en profondeur de Trémaux, parcours main gauche de Pledge
Parcours en profondeur de Trémaux
Comment décomposer un nombre en facteurs premiers ?
Étant donné n on veut produire en temps linéaire deux tableaux factor et primes, tel que primes contienne tous les nombres premiers entre 2 et n, et que factor[x] contienne le plus petit facteur de x, avec facteur[x]==x si x est premier.
Comment planifier une todo-list ?
Introduction
Dessiner sans lever le crayon !
Introduction
Utiliser Paint pour les sudokus
Introduction
Nos conseils pour l'option ICN : idées à coder
Voici des idées d’activités pour l’option ICN au lycée, ou plus généralement toute activité de programmation pour lycéens.
Google Codejam 2017 - 1B
Nous décrivons ici des solutions pour la ronde 1B du concours Google Codejam 2017.
Le Compte est bon ?
Pourrez-vous résoudre cette énigme du jeu Le Compte est bon ?
Solutions du Google Hash Code 2017 - Streaming Videos
Nous décrivons ici notre petite expérience avec le concours Google Hashcode 2017 : Optimize Cache Servers for YouTube.
Google Hashcode - Pizza Régina
Le concours annuel Google Hashcode consiste à résoudre en équipe une instance d’un problème NP-complet. Résoudre veut dire ici produire une solution faisable. La valeur objectif atteinte est le score de la solution. Les problèmes présentés sont assez purs, comparés à ceux du concours annuel Roadef challenge, qui contiennent beaucoup plus de contraintes et sont plus proches d’un problème réel.
Qualifications Facebook Hacker Cup 2017
Pour commencer l’année, ce week-end de l’épiphanie ont eu lieu les qualifications de Facebook Hacker Cup.
Mariages stables, ou comment marier le Prix Nobel d'économie aux sites de rencontres
Note : Une partie de cet article a été reprise d’ici, mais pas de panique, je suis une co-auteure.
Arbres de Merkle : la structure de données à l'origine de git, BitTorrent, Bitcoin, Ethereum, The DAO et autres blockchains
Merkle trees (1979)
Le principe est simple : calculer le hash d’un nœud à partir d’un hash de ses fils. Dans un arbre binaire, pour un nœud ayant pour fils $h_1$ et $h_2$ : \(h(noeud) = h(h1, h2)\).
SWERC 2016 à Porto
Le saviez-vous ? Du 19 au 20 novembre 2016 ont eu lieu les épreuves régionales SWERC du concours de programmation ICPC à Porto, au Portugal.
- 11 problèmes
- 5 heures
- 3 personnes et 1 clavier par équipe
SWERC 2015
Et voici les photos de SWERC 2015.
Sous-modularité
Par Guillaume Aubian.
Réduction de réseaux par l'algorithme LLL
Par Thomas Espitau.
Classement Elo, algorithme EM
Classement Elo
Une projection des joueurs d’échecs sur $\mathbf{R}_+$ (leur score). Ça a été proposé par Arpad Elo il y a assez longtemps.
Aujourd’hui, c’est utilisé par des plateformes comme Codeforces ou HackerRank.
128 algorithmes
Voici les slides de notre conférence du 29 mars 2016 au NUMA.
Structures de données
Voici une structure de données des structures de données.
Résolution de problèmes algorithmiques
On peut distinguer trois types de problèmes.
Arbre de Fenwick
C’est une structure de données dynamique : elle permet de stocker un tableau de $n$ valeurs et de réaliser efficacement les opérations suivantes :
- mettre à jour une valeur du tableau ;
- calculer la somme d’une plage du tableau.
Compte rendu du workshop algo n° 1
Présents :
- Guillaume Aubian
- Clément Beauseigneur
- Maxim Berman
- Thomas Espitau
- Thomas Domingues
- Jill-Jênn Vie
- X
Debuggue mon flot max (si t'es cap)
Pourquoi sur le graphe de capacités suivantes :
J’obtiens un flot max à 13 :
o
Compte rendu de l'atelier n° 1
Table des matières
Généralités
- Prise en main
- Lecture d’un fichier
- Écriture dans un fichier
- Format des chaînes de caractères
- Sous-listes
- Parcourir une liste
Activités