Jeux mathématiques

Ces sujets reposent sur un exposé mathématique.

Ondes Wifi

Tout tient dans cet article : Helmhurts.

Pentomino

Un pentomino est un puzzle style Tétris (voir la page Wikipédia). Sur une grille, on doit disposer des pièces toutes différentes mais constituée d’un nombre fixe de carrés pour former un rectangle sans trous. Comment faire avec une méthode systématique ?

Vous pouvez soit vous lancer dans le vide, soit lire le document suivant pentominoes.pdf. Encore une fois, la résolution du puzzle constitue l’essentiel du projet, l’interface graphique est accessoire et la sortie pourrait tout-à-fait être réalisée en mode texte.

../_images/pent1.png ../_images/pent2.png

Recherche exacte d’un motif, d’une expression

L’objectif est assez simple puisqu’il s’agit de rechercher une expression, un mot dans toutes les pages Wikipédia. Néanmoins, rechercher une expression parmi plusieurs millions de pages est assez long et il est nécessaire d’optimiser les algorithmes utilisés (voir Algorithme de recherche de sous-chaîne ou la version anglaise, plus complète). Dans un premier temps, on pourra comparer deux variantes parmi les cinq proposées :

Dans un second temps, on s’intéressera à la meilleure approche possible pour implémenter trois combinaisons logiques entre deux mots :

  • Ce document doit contenir m1 et m2.

  • Ce document doit contenir m1 ou m2.

  • Ce document doit contenir m1 et m2 avec au plus n mots entre m1 et m2.

Recherche approximative d’un motif, d’une expression

Il arrive qu’on ne connaisse pas l’orthographe d’un mot qu’on cherche ou qu’on se trompe tout simplement et pourtant on souhaite toujours retrouver l’ensemble des documents Internet (ici Wikipedia seulement) qui contiennent une version approchée d’un mot ou d’une expression. La page Approximate String Matching décrit le problème et donne quelques liens vers des solutions. Ces méthodes sont souvent utilisées pour la recherche de sous-séquences ADN et sont très coûteuses en calcul.

Lorsque la séquence à chercher est courte, l’utilisation d’une distance de Levenstein (voir également Smith-Waterman ou encore BLAST) améliorée est encore possible pour un temps de calcul raisonnable.

Lorsqu’on veut rechercher par exemple si un texte est largement inspiré d’une page Wikipédia, la chaîne est beaucoup plus longue et il faut ruser pour obtenir un temps de calculer raisonnable. On a recours à des chaînes de Markov, ou des q-grams (voir aussi celui-ci). L’objectif n’est pas nécessairement d’utiliser ces méthodes mais de développer des idées simples permettant de rechercher un long texte dans le corps de Wikipedia.

Saurez-vous ruser ?

Problème du voyageur de commerce

C’est un problème assez classique : problème du voyageur de commerce qui consiste à trouver le plus court chemin passant par tous les noeuds d’un graphe. Le terme mathématique est : circuit hamiltonien

On pourra essayer différents algorithmes :

Un article sur les heuristiques utilisées lors de la résolution :

Exemple d’utilisation :

Problème des tournées de véhicules

Le problème de tournées de véhicules est une extension du voyageur de commerce. Pour le résoudre, on pourra s’inspirer de l’article : Technical Note: Split algorithm in O(n) for the vehicle routing problem.

Construction d’une texture

On veut peindre une image à l’aide d’un motif présent sur une image plus petite. Le problème survient lorsqu’on la duplique, en collant deux fois la même image côte à côte, les deux bords s’ajustent rarement. L’article Texture Synthesis by Non-parametric Sampling propose une méthode pour contourner ce problème. On pourra aussi regarder le site des auteurs. L’objectif est d’implémenter l’algorithme. Dans un deuxième temps, on pourra s’intéresser au même genre de méthode mais appliquer au débruitage d’une image. On s’inspire pour cela de l’article A Review Of Image Denoising Algorithms (chapitre 5). L’idée consiste à utiliser la redondance dans les images pour trouver dans une partie non bruitée de l’image l’informatique cherchée.

Simulation d’une loi statistique avec un algorithme d’optimisation A*

L’objectif est d’implémenter l’algorithme décrit par l’article A* Sampling, Chris J. Maddison, Daniel Tarlow, Tom Minka.

Recalage d’un réseau

Structure de données adaptée à la recherche de palindromes

Le projet a des aspects mathématiques et informatiques. Il part d’un problème : découvrir tous les palindromes inclus dans une chaîne de caractères. Il propose un algorithme rapide qui s’appuie sur une structure de données adaptées. Le projet consiste à implémenter la méthode décrite par l’article et de l’adapter à d’autres problèmes.

Implémentation d’une grammaire probabiliste pour traiter le langage naturel

Les grammaires (voir grammaires non contextuelles permettent d’analyser un texte en taggant les mots ou en les catégorisant. Le projet consiste à implémenter l’algorithme décrit dans le document suivant : Probabilistic Context-Free Grammars (PCFGs) puis d’appliquer cela sur des articles d’un journal, une page Wikipédia…

Distance entre deux arbres : Robinson–Foulds (2016)

On sait calculer une distance entre deux séquences qu’on appelle distance d’édition ou distance de Levenshtein. Il paraît difficile d’adapter cette distance au cas de deux arbres mais une telle distance existe : distance de Robinson–Foulds. L’objectif du projet est d’implémenter cette distance et de l’application à des arbres de décision, telle que ceux produits par scikit-learn.

Résolution de systèmes d’inéquations (2016)

On se débrouille beaucoup mieux avec la résolution d’un système linéaire d’équations. Mais des inéquations, on préfère quand il s’agit de minimiser ou maximiser. Et quand il ne s’agit de rien de tout ça, on peut s’orienter vers les idées proposées dans l’article : Exact algorithms for linear matrix inequalities.

Sujet plutôt très mathématique puisqu’il s’agit d’implémenter un algorithme de résolutions de tels systèmes.

Elaboration d’un clavier (2017)

Le clavier Azerty n’est pas le plus aimé mais il a encore la vie dure. L’article suivant Bépo, Dvorak, Colemak… A la recherche du clavier français qui pourrait remplacer l’azerty aborde quelques façons de concevoir un clavier. L’idée de ce projet est de concevoir un clavier qui minimise une fonction d’utilité, de voir si cette utilité est différente pour un programmeur et un romancier.

Impression 3D (2018)

L’article suivant introduit un algorithme mathématique pour dessiner une structure complexe avec une imprimante 3D.

Détection de période dans les séquences qui préservent l’ordre (2018)

Le sujet s’appuie sur l’article String Periods in the Order-Preserving Model. On considère deux séquences (X_1, ..., X_n) et (Y_1, ..., Y_n) où chaque X_i et Y_i sont choisis dans un ensemble fini d’entiers. On dit que les séquences sont équivalentes en ordre (noté X \approx Y) si :

\forall i, j \in [1,...,n], \; X_i < X_j \Leftrightarrow Y_i < Y_j

Example : 5 2 7 5 1 3 10 3 5 \approx 6 4 7 6 3 5 9 5 6

L’article se pose la question de détection de période dans ce type de séquences.