« VISI201 CMI : visite de laboratoire » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
Aucun résumé des modifications
 
(257 versions intermédiaires par 28 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
* Cours du semestre 2 du parcours CMI Informatique (licence INFO).


* Responsable pour 2023--2024: Jacques-Olivier Lachaud
[[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]
* Responsable 2016--2023 : Jacques-Olivier Lachaud


= Descriptif =
Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique dans tous les compilateurs et interpréteurs. Mais la plupart des analyseurs syntaxiques ne se contentent pas seulement de valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe détenant le sens de la chaîne d'entrée.


L'objectif du module est de faire découvrir les laboratoires, le monde de la recherche et les enseignants-chercheurs et chercheurs, ainsi que la réflexion scientifique. Cela se fait de deux manières.
== Les grammaires ==


D'abord, une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (environ 5 par an). [[https://www.lama.univ-savoie.fr/pagesmembres/lachaud/CMI_html/news Planning séminaires CMI]]
=== Les symboles de grammaire ===


Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.
Toutes les grammaires sont composées de symboles regroupés sous deux catégories, les terminaux et le non-terminaux.


Les étudiants choisissent ensuite d'approfondir un sujet proposé par les enseignants, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail se fait en interaction avec un tuteur académique (5-6 contacts au moins). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé, et du code si le sujet s'y prête.
Les terminaux sont les symboles les plus petits ne pouvant être subdivisé, ils forment la chaîne d'entrée.


= Projets réalisés (2023-2024) =
Les non-terminaux sont des symboles pouvant être subdivisé, il servent à regrouper d'autre symboles. Il sont toujours associés à des productions décrivant les subdivisions possible.


* [[Calcul approché de l'élément majoritaire, et autres algorithmes approchés]] par Teva PHILIPPE (tuteur: Pierre HYVERNAT)
* [[Surfaces polygonales et surfaces de subdivision]] par Vetea STOLL (tuteur: Jacques-Olivier LACHAUD)
* [[Calcul des valeurs de Grundy pour des jeux octaux]] par Mathieu BRUNOT (tuteur: Valentin GLEDEL)
* [[Cryptanalyse informatique de quelques systèmes de chiffrement "historiques"]] par Gabriel ESAT (tuteur: Pierre HYVERNAT)
* [[Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta]] par Chloé FAUCON (tuteur: Valentin GLEDEL)
* [[Modélisation de la ruine du joueur]] par Albert KULAS (tuteur: Céline LABART)
* [[Calibration de caméra et reconstruction 3D]] par Noah CUNEO (tuteur: Stéphane BREUILS)


= Sujets proposés (2023-2024) =
Par exemple une grammaire pourrait définir le non-terminal <math>float</math> qui englobe toutes les expressions de littéraux de flottants, ce non-terminal se subdiviserait selon <math>float \rightarrow nombre\ .\ nombre</math>, ainsi toutes les chaînes d'entrées composées d'un nombre puis un point et un nombre pouront être englobées par le non-terminal <math>float</math>.


== [[Calcul approché de l'élément majoritaire, et autres algorithmes approchés]] ==
<ul>
<li>4.2</li>
<li><math>nombre\ .\ nombre</math></li>
<li><math>float</math></li>
</ul>


'''Tuteur :''' Pierre Hyvernat
=== Les productions de grammaires ===


'''Résumé :''' en informatique, il est parfois préférable d'accepter un résultat "pas complètement correct", si cela permet d'être plus rapide. Un des premiers problèmes de ce genre est le problème du voyageur de commerce : aucune méthode efficace pour calculer le meilleur trajet n'est connue, mais sous certaines conditions, il existe une méthode efficace qui donne un résultat "pas trop éloigné de l'optimum".
Les productions décrivent les subdivisions de non-terminaux, dans le cas d'une grammaire non-contextuelle toutes les productions sont de la forme :


Un autre exemple est celui de la recherche de l'élément majoritaire : c'est l'élément qui apparait le plus souvent dans une liste. Ici, il est facile d'écrire une fonction qui le calcule exactement, mais dans le cas du "big data" qui évolue constamment, la méthode naïve prend trop de temps, et trop de mémoire. En 2005, A. Metwally, D. Agrawal et A. El Abbadi on décrit une méthode approchée pour ce problème. Le programme correspondant est beaucoup plus rapide que la méthode naïve et n'a besoin que d'une quantité de mémoire bornée. Le résultat n'est pas toujours le bon, mais l'erreur faite est connue.
<math>A \rightarrow \gamma </math>


Ce qui est surprenant dans cette méthode est qu'elle semble fausse à première lecture !
<ul>
<li><math>A</math> : un non-terminal.</li>
<li><math>\gamma</math> : une composition de terminaux et non-terminaux.</li>
</ul>


'''Objectifs :''' comprendre la méthode générale en lisant l'article de A. Metwally, D. Agrawal et A. El Abbadi, et l'implémenter en Python (ou un autre langage). Pour valider la méthode, il serait intéressant de voir si cette méthode approchée peut être plus rapide qu'un générateur aléatoire adéquat de valeurs sur lequel on la brancherait.
Un non-terminal peut être dérivé par une des ses productions associées, il est alors réécrit par la partie droite d'une production. Cette opération mène à une proto-phrase, cette proto-phrase est une phrase si elle est constituée seulement de terminaux.
De même il est possible de réduire une proto-phrase en un non-terminal par une des productions ayant en partie droite la proto-phrase.


'''Référence :''' Ahmed Metwally, Divyakant Agrawal et Amr El Abbadi, ''Efficient Computation of Frequent and Top-k Elements in Data Streams'', https://www.cse.ust.hk/~raywong/comp5331/References/EfficientComputationOfFrequentAndTop-kElementsInDataStreams.pdf
=== La hiérachie de Chomsky ===


== [[Surfaces polygonales et surfaces de subdivision]] ==
La hiérachie de Chomsky définit quatre classes de grammaires, chacune pouvant décrire toutes les règles des grammaires de hiérarchie inférieur, les grammaires générales couvrent toutes les grammaires possibles.


'''Tuteur :''' Jacques-Olivier Lachaud
[[Fichier:Chomsky.png|300px]]


'''Résumé :''' Les surfaces polygonales, et notamment les surfaces triangulées ou quadrangulées, sont la brique de base des modèles géométriques 3D, utilisés par exemple dans tous les jeux vidéos 3D, les effets spéciaux pour les films, ou la conception et fabrication assistée par ordinateur. Parfois ces surfaces ont une géométrie un peu trop facettée. Les processus de subdivision de surface permettent de raffiner progressivement une surface polygonale (en subdivisant les faces et en replaçant les sommets) de manière à obtenir une surface de plus en plus lisse. D'ailleurs on peut montrer que la surface limite est bien est une surface lisse.
Le niveau le plus faible est attribué aux grammaires régulières.


<ul>
<table>
<tr>
<li>Les grammaires régulières sont d'une forme linéaire gauche ou droite, chaque non-terminal peut être associé à une composition de terminaux et un non-terminal en préfixe ou suffixe seulement.
<td>[[File:Suzanne-1.png|200px]]</td>
<math>N \rightarrow A\gamma</math> <math>N \rightarrow \gamma A</math>
<td>[[File:Suzanne-s1.png|200px]]</td>
</li>
<td>[[File:Suzanne-s2.png|200px]]</td>
<li>Les grammaires algébrique (ou non-contextuelles) offrent une plus grande liberté en autorisant d'associer à un non-terminal n'importe quelle combinaison de terminaux et non-terminaux.
<td>[[File:Suzanne-s3.png|200px]]</td>
<math>N \rightarrow \gamma</math>
<td>[[File:Suzanne-s4.png|200px]]</td>
</li>
</tr>
<li>Les grammaires contextuelles sont semblables aux grammaires algébrique mise à part l'ajout d'un contexte autour des productions en partie gauche et partie droite.
<tr>
<math>\alpha N\beta \rightarrow \alpha \gamma \beta</math>
<td>Surface polygonale</td>
</li>
<td>1 subdivision</td>
<li>Les grammaires régulières rendent possible l'association de n'importe quelle composition de non-terminaux et terminaux vers une autre composition.
<td>2 subdivisions</td>
<math>\gamma \rightarrow \phi</math>
<td>3 subdivisions</td>
</li>
<td>4 subdivisions</td>
</ul>
</table>


'''Objectifs :''' Il s'agira de comprendre comment représenter une surface polygonale en mémoire (pour l'affichage on utilisera polyscope, une bibliothèque python), comment charger une surface à partir d'un format simple (wavefront OBJ). Ensuite on étudiera plus particulièrement les surfaces de subdivision dite Catmull-Clark, que l'on implémentera.
=== Les grammaire non-contextuelles ===


'''Référence :'''
Les grammaires non-contextuelles sont définits de la forme <math>G = (V, A, S, P)</math>.
* [https://en.wikipedia.org/wiki/Catmull–Clark_subdivision_surface Catmull-Clark subdivision]
* On utilisera [https://polyscope.run/py/ Polyscope] pour visualiser les surfaces en 3D avec python.
* Un [https://codimd.math.cnrs.fr/s/TmrOWEmyJ tutorial] pour créer/charger les surfaces polygonales en python et polyscope.
* [https://www.blender.org Blender] un logiciel open-source pour créer des modèles 3D et calculer des rendus par lancer de rayons.


== [[Calcul des valeurs de Grundy pour des jeux octaux]] ==
<ul>
<li><math>V</math> : l'ensemble des non-terminaux de la grammaires.</li>
<li><math>A</math> : l'ensemble des terminaux.</li>
<li><math>S</math> : le non-terminal axiome.</li>
<li><math>P</math> : l'ensemble des productions associant un non-terminal à une composition de non-terminaux et terminaux : <math> N \rightarrow \alpha </math>.</li>
</ul>


'''Tuteur :''' Valentin Gledel
Dans un contexte plus technique il suffit de préciser l'axiome et les productions car ces dernières listent tout les non-terminaux et terminaux existant.
L'axiome joue un rôle important dans la validation d'un mot par une grammaire, si des dérivations successives partant de l'axiome mènent à une phrase correspondant au mot d'entrée alors l'entrée est validé. De même si la phrase correspondante au mot d'entrée et réduite jusqu'à obtenir l'axiome.


'''Résumé :''' Les jeux combinatoires impartiaux sont des jeux à deux joueurs, à informations parfaites (pas de hasard ni d'information cachée) et dans lesquels dans chaque position les joueurs disposent toujours du même ensemble de coups l'un que l'autre. Par exemple les échecs ne rentrent pas dans cette catégorie car si c'est aux blancs de jouer, ils ne peuvent bouger que les pièces blanches tandis que si c'est au noirs de jouer, ils ne peuvent jouer que les pièces noires. Les ensembles de coups possibles ne sont pas les mêmes.
Plus formellement, soit <math>\omega</math> le mot d'entrée : <math>S \xrightarrow{*} \omega</math>.
Dans l'étude de ces jeux, la question qu'on se pose est de savoir quel joueur gagnerait si les deux joueurs jouaient parfaitement. Un outil pratique dans la résolution de cette question est la notion de valeur de Grundy d'un jeu. En effet, si on connait la valeur de Grundy d'un jeu J1 et d'un jeu J2 alors on sait quel joueur gagne si on joue en même temps sur J1 et sur J2.
Les jeux octaux forment une sous-classe des jeux combinatoires impartiaux qui contient des jeux proches du célèbre jeu de Nim et, en particulier, le "jeu de Fort Boyard" fait partie de cette catégorie.
Dans ce sujet on se propose de calculer la valeur de Grundy pour des jeux octaux.


'''Objectifs :''' Comprendre ce qu'est la valeur de Grundy d'un jeu et calculer la valeur de Grundy de plusieurs jeux octaux. On pourra ensuite écrire un programme générique qui trouve la valeur de Grundy de jeux octaux sous forme générique, voire même prouver la périodicité des valeurs de Grundy de certains jeux.
== Les analyseurs lexicaux ==


'''Références :'''
L'analyse lexicale couvre toutes les règles de la grammaire régulière, elle est utilisée pour faciliter le travail de l'analyseur syntaxique par la reconnaissance de certain groupe de lexème (les noms de variables, les nombres entiers, les nombres flottants) en unité lexicale. Ces unités lexicales seront utilisées comme terminaux par l'analyseur syntaxique et formeront donc la chaine d'entrée.
* https://fr.wikipedia.org/wiki/Jeu_octal
* https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy


La plupart des règles d'une grammaire régulière sont décrites avec des expressions rationnelles se basant sur trois opérations fondamentales : la concaténation, l'union et l'étoile de Kleene. Chacune de ces opérations produit un ensemble de mot pouvant être reconnu par le motif.


== [[Cryptanalyse informatique de quelques systèmes de chiffrement "historiques"]] ==
<ul>
<li>La concaténation permet de créer un singleton avec la concaténation de deux mots, autrement dit reconnaître que la concaténation de deux mots. <math>ab \rightarrow \{ab\}</math></li>
<li>L'union crée un ensemble constituée des deux mots, elle reconnaît l'un de deux mots seulement. <math>a|b \rightarrow \{a, b\}</math> </li>
<li>L'étoile de Kleene permet de créer un ensemble contenant toutes les combinaisons d'un ensemble ainsi que le vide. <math>(a|b)^* \rightarrow \{\epsilon, a, b, ab, ba, aab, ...\}</math> </li>
</ul>


'''Tuteur :''' Pierre Hyvernat
L'analyseur lexicale sépare en premier la chaine selon les blancs et d'autres séparateurs supplémentaires tels que les signes de ponctuations et les opérateurs, ensuite chaque portion de la chaine d'entrée est analysée selon un ensemble de règles rationnelles pour déterminer son unité lexicale.


'''Résumé :''' pendant longtemps, "craquer" les systèmes de chiffrement ("codes secrets") se faisait essentiellement à la main, et les outils informatiques ont rendu la plupart des systèmes historiques obsolète. Pourtant, sauf dans quelques cas particuliers, l'ordinateur ne peut pas casser un code simplement en testant toutes les possibilités. Il faut trouver une méthode plus efficace.
Par exemple la chaine d'entrée "float i = 4.2 + 5;" sera découpée en {"float", "i", "=", "4.2", "+", "5", ";"}, ensuite selon les règles suivantes (utilisant le format de regex POSIX) :


L'objectif sera d'étudier et d'implémenter quelques uns de ces systèmes simples :
<ul>
* chiffrement,
<li> type <math> \rightarrow </math> (int|float|bool) </li>
* déchiffrement,
<li> id <math> \rightarrow </math> ([A-z]([A-z]|[0-9])*)[^(int|float|bool)] </li>
* décryptage (càd déchiffrement sans utiliser la clé secrète).
<li> op_assign <math> \rightarrow </math> = </li>
<li> float <math> \rightarrow </math> [0-9]*\.[0-9]*f? </li>
<li> int <math> \rightarrow </math> [0-9]* </li>
<li> end <math> \rightarrow </math> ; </li>
<li> op <math> \rightarrow </math> \+|\-|/|\* </li>
</ul>


Les systèmes de chiffrement considérés seront
On obtiendra donc un ensemble des unités lexicales reconnues : {type, id, op_assign, float, op, int, end}.
* substitutions monoalphabétiques, décryptées en utilisant la méthode "aléatoire" du [https://fr.wikipedia.org/wiki/M%C3%A9thode_hill-climbing "hill-climbing"],
* le [https://en.wikipedia.org/wiki/Straddling_checkerboard "straddling checkerboard"], décrypté par recherche exhaustive sur les positions des "blancs" dans la clé, et en le transformant en substitutions monoalphabétique,
* le [https://fr.wikipedia.org/wiki/Chiffre_de_Hill code de Hill], décrypté en utilisant un mot probable, ou la conjonction d'une recherche exhaustive sur les lignes de la clé suivie des tests exhaustifs de toutes leurs permutations.


Suivant le temps et l'intérêt, on pourra soit regarder d'autres systèmes de chiffrement, soit essayer d'améliorer l'analyse du chiffre de Hill en combinant la seconde méthode avec la méthode du Hill-climbing.
=== Les automates finis ===


'''Références :'''
Un analyseur lexicale peut être construit avec un automate finis car d'après le théorème de Kleene toutes les grammaires régulière sont reconnu par un automate finis.
* [https://pierre-hyvernat.apps.math.cnrs.fr/data/Enseignement/1920/info910/tp1.html Parties 1 et 2 d'un TP de cryptographie]


Théorème de Kleene : l’ensemble des langages rationnels sur un alphabet A est exactement l’ensemble des langages sur A reconnaissables par automate fini.


== [[Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta]] ==
L'automate suivant reconnaît le motif <math>a^*b^*</math>


'''Tuteur :''' Valentin Gledel
[[Fichier:Automate-ab.png|400px]]


'''Résumé :''' Le jeu Puissance 4 est un jeu bien connu dans lequel deux
Malheureusement la limite des analyseurs lexicaux et très vite atteint notamment avec le motifs de la forme <math>a^nb^n</math>. Dans ce cas il faut trouver un moyen de compter le nombre de a consommé pour essayer de consommer le même nombre de b, or les automates finis ne dispose pas de mémoire supplémentaire où placer ce compteur. Ce type de motif est fortement utilisé dans les languages de programmations pour vérifier le bon nombre de parenthèses, accolades etc…
joueurs placent alternativement des jetons dans une grille 7 par 6. Le
premier joueur qui réussit à aligner 4 jetons gagne la partie.
La simplicité des règles du jeu et le nombre restreint de coups
possibles à chaque moment de la partie font de ce jeu un bon candidat
pour implémenter les algorithmes de jeux minimax et alpha-beta. Ces
algorithmes effectuent une recherche jusqu'à une certaine profondeur
dans l'arbre des coups possibles. Ils évaluent ensuite les positions à
la profondeur choisie à partir d'une "mesure" choisie par le
programmeur. Puis, ils choisissent un coup à jouer en fonction de la
position donnant le meilleur résultat.


'''Objectif :''' Implémenter le jeu Puissance 4, trouver des mesures pour
== Les analyseurs syntaxiques ==
évaluer des positions de ce jeu, implémenter l'algorithme minimax et
l'algorithme alpha-beta, comparer les résultats de ces algorithmes.


'''Références :'''
L'analyse syntaxique suit l'analyse lexical en se basant sur les unités lexicales définit par ce dernier nommé lexèmes. Ces unités lexicales sont utilisées en tant que terminaux par l'analyseur syntaxique dans une liste de lexèmes.
* https://fr.wikipedia.org/wiki/Algorithme_minimax
* https://fr.wikipedia.org/wiki/%C3%89lagage_alpha-b%C3%AAta


== [[Modélisation de la ruine du joueur]] ==
Les algorithmes d'analyseur syntaxiques se basent tous sur le même type d'automates : les automates finis à pile. Les deux majeurs techniques connus sont l'analyse descendante et l'analyse ascendante. La première consiste à dériver l'axiome de la grammaire jusqu'à obtenir le mot d'entrée, la seconde technique consiste à réduire le mot d'entrée jusqu'à obtenir l'axiome.
Ces deux techniques sont considéré comme opposé par leur façon de traiter les proto-phrases, l'analyseur descendant va toujours dériver et l'analyseur ascendant toujours réduire. Malgré cette symétrie, ces deux types d'analyseur n'utilisent pas les mêmes ensembles de règles.


'''Tuteur :''' Céline Labart
=== Les automates finis à pile ===


'''Résumé :''' Nous nous intéressons à l'étude des gains d'un joueur à la roulette. Celui-ci arrive au casino avec une certaine somme en poche et joue à la roulette tant qu'il n'est pas ruiné ni que ses gains atteignent une somme qu'il s'est fixée. A chaque fois qu'il joue, le joueur gagne ou perd un euro avec une certaine probabilité.
Les automates finis à pile forment une extension des automates finis par l'adjonction d'une mémoire organisée en pile.


'''Objectifs :'''
Ils permettent de couvrir les limitations des analyseurs lexicaux en reconnaissant les motifs de la forme <math>a^nb^n</math>.
* Simulation d'une partie
* Calcul de la probabilité de gagner
* Calcul du temps moyen de jeu
* Estimation numérique de ces deux quantités à l'aide de la loi des grands nombres


'''Références :'''
[[Fichier:Automate-pile-ab.jpg|400px]]
* Lien pour commencer : [https://www.idpoisson.fr/malrieu/wp-content/uploads/sites/3/2019/06/modale.pdf Modélisation aléatoire]


== [[Planarité de graphes]] ==
Ce type d'automate est utilisé pour les analyseurs syntaxique tant descendant que ascendant.


'''Tuteur :''' Sébastien Tavenas
=== Les analyseurs descendants ===


'''Résumé :''' Un graphe est dit planaire si on peut le "dessiner" dans le plan de façon à ce que les arêtes ne se croisent pas. Donné un graphe, est-il facile de tester s’il est planaire ? Pour commencer, il est facile de certifier qu’un graphe est planaire en donnant le "dessin" du graphe dans le plan. Mais comment montrer qu’un graphe n’est pas planaire ? Kuratowski a montré qu’un graphe n’est pas planaire si et seulement si il contient un mineur (ie, un sous-graphe) qui est K5 (le graphe complet avec 5 sommets) ou K3,3 (le graphe biparti complet avec chaque partie ayant 3 sommets). Ainsi, pour montrer qu’un graphe n’est pas planaire, il suffit de montrer une subdivision qui est K5 ou K3,3. Il semble alors possible de trouver un algorithme qui donné un graphe, soit retourne un "dessin" du graphe planaire dans le plan, soit trouve une subdivision K5 ou K3,3 garantissant que le graphe n’est pas planaire.
Le principe de l'analyse descendante est assez simple à mettre en œuvre. L'analyseur initialise une proto-phrase contenant l'axiome de la grammaire, à chaque étape l'analyseur va lire le symbole à gauche de la proto-phrase. Si celui ci est un terminal alors on le compare avec le début de la chaîne d'entrée, si il correspond on consomme le début de la chaine d'entrée ainsi que le terminal au début de la proto-phrase, au contraire on signale une erreur. Si le début de la proto-phrase est un non-terminal alors on le remplace par la partie droite de l'une de ses productions.


'''Objectif :''' Comprendre la notion de graphe planaire et le théorème de Kuratowski. Coder un programme de détection de planarité (plusieurs algorithmes linéaires existent pour ce problème).
Le pseudo code correspondant est le suivant :


'''Référence :'''
<pre>
* [https://fr.wikipedia.org/wiki/Graphe_planaire Wikipédia - Graphe planaire]
initialiser une pile contenant S
Tant que la pile et la chaine d'entrée sont non-vide
soit C le premier lexème de la chaine d'entrée
soit T le sommet de la pile
Si T est non-terminal
choisir une production P de T
dépiler le sommet de la pile
empiler la partie droite de P
Sinon si T équivaut C
dépiler le sommet de la pile
consommer le lexème C
Sinon
erreur
</pre>


Si nous utilisons la grammaire contenant les deux productions <math>S \rightarrow aSb</math> et <math>S \rightarrow \epsilon </math> (<math>\epsilon</math> pour ne rien consommer ou ajouter), <math>S</math> est l'axiome de la grammaire implicitement.
La trace de l'algorithme descendant du mot d'entrée "aabb" est alors :


== [[Calibration de caméra et reconstruction 3D]] ==
{| class="wikitable"
|-
! Pile
! Entrée
! Opération
|-
| S
| aabb
|
|-
| aSb
| aabb
| dériver par <math>S \rightarrow aSb</math>
|-
| Sb
| abb
| consommer a
|-
| aSbb
| abb
| dériver par <math>S \rightarrow aSb</math>
|-
| Sbb
| bb
| consommer a
|-
| bb
| bb
| dériver par <math>S \rightarrow \epsilon</math>
|-
| b
| b
| consommer b
|-
|
|
| consommer b et valider le mot
|-
|}


'''Tuteur :''' Stéphane Breuils
Malgré la simplicité de cette technique, deux problèmes majeurs sont présents et mènent tous deux à utiliser un ensemble restreint de règles de grammaire par rapport aux grammaires algébriques.


'''Résumé :'''
Le premier problème concerne la récursivité gauche. Si l'algorithme ne sait pas exactement comment choisir les productions à appliquer et que la grammaire possède des productions de la forme <math>N \rightarrow N\alpha</math> ou autrement dit des productions associant le même non-terminal à gauche et au début de le partie droite de la production, alors la dérivation du sommet d'une proto-phrase contenant <math>N</math> mènera toujours à avoir le même non-terminal au sommet et l'algorithme ne pourra jamais arrêter de dériver.
Nous explorons dans ce projet la calibration de caméras à partir d’un ensemble de points de correspondance et son utilisation pour reconstruire des objets en 3D. L'idée est de pouvoir dimensionner précisément des éléments photographiés.


'''Objectifs :'''
<ul>
* Comprendre la modélisation d'une caméra (paramètres intrinsèques, extrinsèques)
<li> <math> N </math> </li>
* Etudier des méthodes de rectification épipôlaires consistant à transformer des images avec des homographies.
<li> <math> N\alpha </math> </li>
* Effectuer des calibrations de caméras et discuter des méthodes d'estimation de la profondeur.
<li> <math> N\alpha\alpha </math> </li>
<li> <math> N\alpha\alpha\alpha </math> </li>
<li> <math> N\alpha\alpha\alpha\alpha </math> </li>
<li> … </li>
</ul>


'''Références :'''
Pour contrer ce problème il existe une méthode permettant de transformer la récursivité gauche en une récursivité droite d'un non-terminal secondaire :
* La bibliothèque OpenCV : https://docs.opencv.org/4.9.0/
* Tutoriel calibration : https://docs.opencv.org/4.x/d9/db7/tutorial_py_table_of_contents_calib3d.html
* Hartley, R., & Zisserman, A. (2003). Multiple view geometry in computer vision. Cambridge university press.


= Archive des sujets réalisés =
Soit <math>N \rightarrow N\alpha</math> <math>N \rightarrow \beta</math>


== Projets 2023-2024 ==
<ul>
<li> <math>N \rightarrow \beta N'</math> </li>
<li> <math>N' \rightarrow \alpha N'</math> </li>
<li> <math>N' \rightarrow \epsilon </math> </li>
</ul>


En effet, les règles initiales mènent intuitivement aux motifs de la forme <math>\beta \alpha \alpha \alpha ...\alpha</math>. Remplacer la récursivité gauche consisterait en réécrire les règles donnant les mêmes motifs, soit <math>\beta</math> en préfixe suivi d'une règle linéaire droite pour les <math>\alpha</math>.


== Projets 2022-2023 ==
Le second problème des analyseurs descendant et le déterminisme lors du choix des productions à dériver. L'algorithme doit dériver un non-terminal selon la production qui à le plus de chance de réussir l'analyse. Dans l'exemple de la trace de l'analyse du mot "aabb", il fallait lors de la troisième dérivation dériver selon <math>S \rightarrow \epsilon</math> seulement.
Dans le cas contraire non-déterministe, l'algorithme pourrait autoriser de revenir en arrière dans l'analyse lors d'erreur et d'appliquer les productions restantes jusqu'à ne plus avoir de production et donc signaler une véritable erreur.


* [[media:Mcmanus-2023.pdf|Programmation du robot NAO]] par Ronan MCMANUS (Tuteur : Christophe CARMAGNAC)
==== Les analyseurs à symbole de prévision ====
* [[media:Cusumano-2023.pdf|Vision en relief, anaglyphes et auto-stéréogrammes à partir d'images RGB+profondeur]] par Lilian CUSUMANO (Tuteur : Jacques-Olivier LACHAUD)
* Tables de hachage et dictionnaires par Morgane FAREZ (Tuteur : Pierre HYVERNAT)
* Réductions de problèmes par Solène BELISSARD (Tuteur : Pierre HYVERNAT)
* Détection d’anomalies en « temps réel » via la plateforme de streaming d’évènements Kafka par Franz-Maximilien CERON (Tuteur : David TELISSON)
* [[media:Kant-aliagas-2023.pdf|Recherche de chemin en temps réel par A*]] par Cassandre KANT-ALIAGAS (Tuteur : Lucas CHARDONNET)
* [[media:Gossin-2023.pdf|Rendu rapide de scènes 3D]] par Cassiopée GOSSIN (Tuteur : Colin WEILL-DUFLOS)
* [[media:Moiroud-2023.pdf|Détection de droites dans les images avec la transformée de Hough]] par Elliott MOIROUD (Tuteur : Stéphane BREUILS)
* [[media:Rexhepi-2023.pdf|Stratégies mixtes et programmation linéaire par Ilirian REXHEPI]] (Tuteur : Sébastien TAVENAS)
* [[media:Rey-2023.pdf|Géométrie discrète, Convexité des polyominos, Combinatoire des mots]] par Lukas REY (Tuteur : Jacques-Olivier LACHAUD)


== Projets 2021-2022 ==
Un analyseur à symbole de prévision, nommé LL(k) ou k est le nombre de symboles, lors d'une dérivation va lire k symboles au début de la chaine d'entrée pour déterminer la production à dériver contenant ces k symboles en préfixe. La plupart des analyseurs se contentent de 1 symbole de prévision.
* [[ Détection d’anomalies par Isolation Forest : application pour l’industrie 4.0]] par Mila DESMET (Tuteur : David TELISSON)
* [[Machines de Turing]] par Emeline CHOLLET (Tuteur : François BOUSSION)
* [[Géométrie discrète, Convexité des polyominos, Combinatoire des mots]] par Joris DUBOIS (Tuteur: Jacques-Olivier LACHAUD)
* [[Origami, axiomes de Huzita/Justin et ReferenceFinder]] par Mathys AUBERT (Tuteur : Pierre HYVERNAT)
* [[Les "claviers"]] par Amélie HACQUE (Tuteur : Pierre HYVERNAT)
* [[Fractales de Newton et sensibilité aux conditions initiales]] par Paul SCHULTZ (Tuteur: Jacques-Olivier LACHAUD)
* [[Approximation numérique de calculs intégraux]] par Enzo MAUTI (Tuteur : Dionysos GRAPSAS)
* [[Instant Insanity]] par Numa Ciribino (Tuteur : Sébastien TAVENAS)
* [[Automates cellulaires]] par Mattéo LUQUE (Tuteur : Gérald CAVALLINI et Jacques-Olivier LACHAUD)
* [[Simulation de fluides]] par Maxime ROUSSEAU (Tuteur : Colin WEILL-DUFLOS)


== Projets 2020-2021 ==
En amont de l'analyse un algorithme est utilisé pour générer une table de la forme <math>PRODUCTION(N, c) \rightarrow P</math>.
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Utilisateur:Maxent_Bernier#Transform.C3.A9e_en_distance_discr.C3.A8te.2C_diagramme_de_Voronoi_discret.2C_axe_m.C3.A9dian_et_squelette Transformée en distance discrète, diagramme de Voronoi discret, axe médian et squelette] par Maxent BERNIER (Tuteur : Jacques-Olivier LACHAUD)
<ul>
* [[Clustering par K-means, segmentation d'image]] par Paul AUBRY (Tuteur : Jacques-Olivier LACHAUD)
<li> <math>N</math> : Le non-terminal courant (au sommet de la proto-phrase). </li>
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Base_de_donn%C3%A9es_orient%C3%A9es_Graphe,_similarit%C3%A9_et_recommandation Base de données orientées Graphe, similarité et modèles prédictifs] par Luca Policastro (Tuteur : Gérald Cavallini)
<li> <math>c</math> : Le lexème courant (au sommet de la chaine d'entrée) utilisé comme préfixe. </li>
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Ensemble_de_Mandelbrot_et_autres_fractales Ensemble de Mandelbrot et autres fractales] par Andrien MONTMAYEUR (Tuteur : Pierre Hyvernat)
<li> <math>P</math> : la production ayant pour préfixe <math>c</math> </li>
* Complexité pratique contre complexité théorique
</ul>
* [[Etude du protocole gRPC]] par Alexandre Desbos (Tuteur : David Télisson)
* [[Valeurs de Sprague-Grundy pour le jeu de Wythoff]] par Nolann SANMARTI (Tuteur : Sébastien Tavenas)
* [[Modélisation de réseaux sociaux, base de données orientées graphe]] par Baptiste Griva (Tuteur : Gerald Cavallini)
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Mod%C3%A9lisation_de_la_ruine_du_joueur Modélisation de la ruine du joueur] par Emilien Boitouzet (Tuteur : Céline Labart)


== Projets 2019-2020 ==
Dans le cas de productions sans <math>\epsilon</math>, l'algorithme va pour chaque non-terminal lire toutes les productions associées. Pour chacune des productions déterminer les préfixes possibles, en parfois dérivant jusqu'à obtenir un terminal à gauche, puis associer cette production avec ses préfixes dans la table.


* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Transform%C3%A9e_Burrows_Wheeler Compression et transformée de Burrow-Wheeler] par Simon LEONARD (Tuteur : Pierre HYVERNAT)
Dans l'exemple d'une grammaire reconnaissant les déclarations de variables avec initialisation optionnelle par les règles suivantes :
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/VISI201_Backtracking_(PICHENOT_Simon) Backtracking] par Simon PICHENOT (Tuteur : Pierre HYVERNAT)
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images_avec_numpy Transfert de couleur (version 2)] par Florian DUFAURE (Tuteur : Jacques-Olivier LACHAUD)
* [[Génération fractale de terrains]] par Hugo REY (Tuteur : Jacques-Olivier LACHAUD)
* [http://os-vps418.infomaniak.ch:1250/mediawiki/index.php/Architectures_Orient%C3%A9es_Micro-Services#Architecture_orient.C3.A9e_micro-services Architectures Orientées Micro-Services] par Romain NEGRO (David TELISSON)
* [[Apprentissage automatique]] par Evan L'HUISSIER (Tuteur : Tom HIRSCHOWITZ)
* [[Algorithmes probabilistes/déterministes pour tester la primalité d'un entier]] par Juliette NEYRAT (Tuteur : Sébastien TAVENAS)
* [[Base de données orientées Graphe et similarité]] par Romain PAJEAN (Gérald CAVALLINI)
* [[Modèles d'évolution de populations]] par Théo GUESDON (Tuteur : Jimmy GARNIER)


== Projets 2018-2019 ==
<ul>
<li> <math>decl \rightarrow type\,id\,decl'</math> </li>
<li> <math>decl' \rightarrow =\, expr\,;</math> </li>
<li> <math>decl' \rightarrow ; </math> </li>
</ul>


* [[Transport optimal par coupe 1D et transfert de couleurs entre images]] par Lucas CHARDONNET (Tuteur : Jacques-Olivier LACHAUD)
Cette grammaire reconnait les mots "int i = 0;" et "int i;" de la façon suivante :
* [[Génération et résolution de labyrinthes II]] par Romain THEODET (Tuteur : François BOUSSION)
* [[Rest & Pub-Sub : protocole hybride pour l'IoT]] par Ewan RAKOTOANOSY (Tuteur : David TELISSON)
* [[La suite de Conway et la classification périodique des "éléments"]] par Yohann THEPAUT (Tuteur : Pierre HYVERNAT)
* [[Initiation à la démonstration sur ordinateur et certification de logiciel]] par Loïc DORNET (Tuteur : Tom HIRSCHOWITZ)
* [[Dilemme du prisonnier]] par Christophe CARMAGNAC (Tuteur : Gérald CAVALLINI)


== Projets 2017-2018 ==
<ul>
<li> Dérivation de l'axiome : <math>type\,id\,decl'</math></li>
<li> Reconnaissance de <math>type</math> et <math>id</math> par respectivement "int" et "i"</li>
<li> Dérivation de <math>decl'</math> par l'une de ses productions</li>
<li> Suite de l'analyse avec l'une des deux productions de <math>decl'</math> </li>
</ul>


* [[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]] par Tristan PORTERIES (Tuteur : Pierre HYVERNAT)
Ici est mis en évidence le branchement lors de la dérivation de <math>decl'</math>, la table des productions par symbole de prévision est :
* [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] par Nils RUET (Tuteur : Jacques-Olivier LACHAUD)
* [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] par Rémi BOUVIER (Tuteur : Laurent VUILLON)
* [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] par Robin WAGNER (Tuteur : Jacques-Olivier LACHAUD)
* [[Pavages de Penrose]] par Brunelle CORDIER-PIERRE-BES (Tuteur : Pierre HYVERNAT)


{| class="wikitable"
|-
! Non-terminal
! Préfixe
! Production
|-
| <math>decl</math>
| <math>type</math>
| <math>decl \rightarrow type\,id\,decl'</math>
|-
| <math>decl'</math>
| =
| <math>decl' \rightarrow =\,expr\,;</math>
|-
| <math>decl'</math>
| ;
| <math>decl' \rightarrow ;</math>
|-
|}


== Projets 2016-2017 ==
Lors de la dérivation de <math>decl'</math>, l'analyseur va interroger la table de production pour le lexème en sommet d'entrée, dans le cas des deux mots "int i = 0;" et "int i;" ce symbole sera respectivement "=" ou ";". Ces deux symboles donnent dans la table deux productions valide pour continuer l'analyse.


* [[Algorithme de rendu de scène 3D par Z-buffer]] par Raphaël TOURNAFOND (Tuteur : Jacques-Olivier LACHAUD)
Dans le cas où le préfixe n'est pas associer à une production, l'analyseur peut signaler une erreur car cela signifie que n'importe quelle dérivation mènera à une erreur lors de la reconnaissance du premier symbole terminal.
* [[Traitement d'image]] par Ambroise DECOUTTERE (Tuteur : Jacques-Olivier LACHAUD)
* [[Nim et la théorie des jeux impartiaux]] par Luca CHAPELLE (Tuteur : Pierre HYVERNAT)
* [[Calculabilité et modèles de calcul]] par Thibaut CHAMINADE (Tuteur : Rodolphe LEPIGRE)
* [[Génération et résolution de labyrinthes]] par Candice ROBERT (Tuteur : Xavier PROVENCAL)


= Archive des projets proposés =
En ce qui concerne les grammaires possédant des productions en <math>\epsilon</math>, ces productions sont valide pour n'importe quelle préfixe mais sont soumise à une condition supplémentaire sur les symboles rencontrés après l'usage des non-terminaux de ces productions.


Soit une production <math>N \rightarrow \epsilon</math>, nous regardons toutes les productions utilisant le non-terminal <math>N</math> de la forme <math>L \rightarrow N\gamma</math> et associant dans la table la production <math>N \rightarrow \epsilon</math> avec tous les préfixes de <math>\gamma</math>.


== Sujets proposés 2022-2023 ==
Dans le même exemple de grammaire reconnaissant les déclarations de variables, les règles peuvent s'écrire :


* Programmation du robot Nao
<ul>
* Vision en relief, anaglyphes à partir d'images RGB+profondeur
<li> <math>decl \rightarrow type\,id\,decl'\,;</math> </li>
* Vision en relief, auto-stéréogrammes à partir d'une image de profondeur
<li> <math>decl' \rightarrow =\,expr</math> </li>
* Tables de hachage et dictionnaires
<li> <math>decl' \rightarrow \epsilon </math> </li>
* Réductions de problèmes
</ul>
* Détection d’anomalies en « temps réel » via la plateforme de streaming d’évènements Kafka
* [[Recherche de chemin en temps réel par A* ]]
* Rendu rapide de scènes 3D
* Détection de droites dans les images avec la transformée de Hough
* Stratégies mixtes et programmation linéaire


Le non-terminal associé à la production <math>decl' \rightarrow \epsilon </math> et utilisé seulement dans <math>decl \rightarrow type\,id\,decl'\,;</math> et le symbole suivant <math>delc'</math> est ";". <math>decl' \rightarrow \epsilon </math> et donc associé à ";" dans la table comme pour la grammaire précédente sans productions utilisant <math>\epsilon</math>.


=== Programmation du robot Nao ===
{| class="wikitable"
|-
! Non-terminal
! Préfixe
! Production
|-
| <math>decl</math>
| <math>type</math>
| <math>decl \rightarrow type\,id\,decl'\,;</math>
|-
| <math>decl'</math>
| =
| <math>decl' \rightarrow =\,expr</math>
|-
| <math>decl'</math>
| ;
| <math>decl' \rightarrow \epsilon</math>
|-
|}


* Tuteur : Christophe Carmagnac
=== Les analyseurs ascendants ===
* Résumé : Nao est un robot programmable. Il dispose d'une API qui permet de le controler à distance. Il possède divers capteurs qui remontent des données en temps réel. Nao est donc une base intéressante pour faire des projets axés sur la robotique sans avoir à se soucier des contraintes électroniques. Dans ce projet, on cherchera à créer des programmes permettant à Nao d'analyser et d'intéragir avec son environnement.
* Objectifs :
*# Implémenter un algorithme permettant à Nao de se déplacer
*# Reconnaître différents objets tels qu'une tasse de café en utilisant Python
*# Faire en sorte que Nao prenne un objet
*# Créer un programme permettant de déplacer un objet de manière autonome
* Liens pour démarrer
** [https://www.aldebaran.com/fr/nao Présentation de Nao]
** [http://doc.aldebaran.com/2-8/index_dev_guide.html Documentation de l'API de Nao] (seulement disponible en http)


=== [[ Vision en relief, anaglyphes à partir d'images RGB+profondeur ]] ===
Le principe de l'analyse ascendante est de réduire successivement une phrase correspondant à la chaine d'entrée jusqu'à obtenir l'axiome de la grammaire. Ce type d'analyseur nécessite la création en amont d'une table d'analyse difficilement concevable manuellement.


* Tuteur: Jacques-Olivier Lachaud
Cette table d'analyse se base sur deux opérations, réduire et décaler. Décaler consiste à déplacer un terminal en sommet de la chaine d'entrée dans la pile d'analyse, réduire consiste à remplacer le sommet de la pile d'analyse correspondant à la partie droite d'une production par le non-terminal associé à cette production.
* Résumé: La vision en relief nécessite de construire 2 images d'une scène 3D, une pour l'oeil gauche, l'autre pour l'oeil droit. A moins d'avoir des dispositifs particuliers, le procédé le plus simple pour construire et visualiser une image en relief est l'anaglyphe, c'est-à-dire construire une seule image mélangeant les 2 vues, la vue gauche en rouge, la vue droite en cyan, et d'utiliser de simples lunettes colorées rouge-cyan. Nous allons construire de tels anaglyphes, mais à partir d'images couleurs (RGB) qui ont aussi une profondeur par pixel. Ces images sont devenues très courantes avec la Kinect de la Xbox. On verra que l'on peut ainsi donner une impression de relief, mais que ces images ont aussi des défauts.
* Objectifs:
*# Comprendre le procédé anaglyphe et la différence de point de vue entre nos deux yeux
*# Lire les images RGB+Z et fabriquer une image anaglyphe (on utilisera OpenCV avec python)
*# Faire la même chose en flux video.
*# Corriger l'entrée en profondeur pour améliorer le rendu.
* Liens pour démarrer
** [https://fr.wikipedia.org/wiki/Anaglyphe Anaglyphe sur wikipedia]
** [https://paperswithcode.com/datasets?mod=rgb-d Datasets RGB+Z (films)]
** [https://rgbd-dataset.cs.washington.edu/dataset.html Dataset RGB+Z (formes plus simples)]
<table>
<tr>
<td> RGB </td>
<td> Profondeur </td>
<td> Anaglyphe </td>
</tr>
<tr>
<td>[[Fichier:Rgb.png|300px]]</td>
<td>[[Fichier:Depth.png|300px]]</td>
<td>[[Fichier:Anaglyph.png|300px]]</td>
</tr>
</table>


=== Vision en relief, auto-stéréogrammes à partir d'une image de profondeur ===
Pour la grammaire suivante et le mot d'entrée "aabb" :


* Tuteur: Jacques-Olivier Lachaud
<ul>
* Résumé: La vision en relief nécessite de construire 2 images d'une scène 3D, une pour l'oeil gauche, l'autre pour l'oeil droit. Nous proposons ici d'étudier une technique qui permet d'avoir une vision en relief à partir d'une seule image ! Le procédé, appelé (auto-)stéréogramme encode l'image pour l'oeil gauche et l'image pour l'oeil droit dans la même image. L'idée est d'utiliser une image qui se répète par bandes verticales régulièrement (genre tous les 60 pixels). Ensuite, c'est l'observateur qui, en faisant converger ses yeux au-delà de l'écran, ne fait pas voir les mêmes bandes à ses yeux. En modifiant légèrement les motifs de répétition, nos 2 yeux ne voient pas la même chose et nous voyons la scène en relief !
<li><math> S \rightarrow aSb </math></li>
* Objectifs:
<li><math> S \rightarrow ab </math></li>
*# Comprendre le procédé stéréogramme
</ul>
*# Mettre au point l'algorithme de calcul d'une telle image à partir d'un motif (donné ou généré) et d'une image de profondeur.
*# On pourra utiliser OpenCV avec python
*# On peut même faire la même chose avec un flux video d'images de profondeur.
* Liens pour démarrer
** [https://fr.wikipedia.org/wiki/Autostéréogramme Auto-stéréogramme sur wikipedia]
<table>
<tr>
<td> Profondeur </td>
<td> Stéréogramme 1 </td>
<td> Stéréogramme 2 </td>
<td> On voit ci-dessous le procédé qui consiste en des décalages de motifs. Malheureusement sous cette forme, notre cerveau a beaucoup de peine à le reconstruire</td>
</tr>
<tr>
<td>[[Fichier:Stereogram-depth.png|300px]]</td>
<td>[[Fichier:Stereogram-1.png|300px]]</td>
<td>[[Fichier:Stereogram-2.png|300px]]</td>
<td>[[Fichier:Stereogram-3.png|300px]]</td>
</tr>
</table>


=== [[Tables de hachage et dictionnaires]] ===
La trace de l'analyse ascendante est :


* tuteur : Pierre Hyvernat
{| class="wikitable"
|-
! Pile
! Entrée
! Opération
|-
|
| aabb
|
|-
| a
| abb
| décaler
|-
| aa
| bb
| décaler
|-
| aab
| b
| décaler
|-
| aS
| b
| réduire par <math> S \rightarrow ab </math>
|-
| aSb
|
| décaler
|-
| S
|
| réduire par <math> S \rightarrow aSb </math> et valider
|-
|}


* Résumé : les ordinateur peuvent facilement représenter un tableau de ''n'' cases par une zone de ''n'' cases mémoires consécutives. Le plus simple pour représenter un ''dictionnaire'' (comme un Python) est d'utiliser un tableau où chaque case contient à la fois la clé et la valeur. Ceci est particulièrement inefficace car savoir si une clé est valide (càd apparait dans le dictionnaire) est lent.
Malheureusement il ne suffit pas de reconnaître la partie droite d'une production sur le sommet de la pile pour réduire par celle ci.
Le contre-exemple est le suivant :
Soit une grammaire linéaire droite de la forme <math>A \rightarrow aA</math>, <math>A \rightarrow a</math> et le mot "aa".
En premier "a" est décalé, puis réduit par la production <math>A \rightarrow a</math>, puis le second "a" est décalé pour obtenir sur la pile d'analyse "Aa". Aucune production n'a le motif "Aa" en partie droite pourtant le mot "aa" est bien valide intuitivement. Pour réussir cette analyse il aurait fallu décaler les deux "a" pour obtenir "aa", réduire le dernier en "aA" selon <math>A \rightarrow a</math> et enfin réduire en "A" selon <math>A \rightarrow aA</math>.


* Objectifs :
Les réductions valide sont nommées manche, ils dépendent de l'état de la pile.
*# regarder comment implémenter les ''tables de hachage''. Cette structure permet de représenter les dictionnaire de manière plus efficace,
*# comprendre comment fonctionnent quelques ''fonctions de hachage''. Ces fonctions permettent de transformer chaque clé en indice de case d'un tableau standard. Les clés deviennent donc des nombres entiers, et il alors possible de faire des recherche par dichotomie pour accélérer la recherche.
*# regarder différentes manières de gérer les ''collisions'', car même avec une fois la fonction de hachage bien choisie, 2 clés différentes peuvent donner le même indice.


* liens utiles :
==== Les tables d'analyse ====
** [https://fr.wikipedia.org/wiki/Table_de_hachage tables de hachage sur Wikipedia] [https://en.wikipedia.org/wiki/Hash_table (plus complet, mais en anglais)]
** [https://thepythoncorner.com/posts/2020-08-21-hash-tables-understanding-dictionaries/ des explications sur les] [https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented/9022835#9022835 tables de hachage] [https://stackoverflow.com/questions/56097997/how-does-python-implement-dictionaries/56098068 et les dictionnaires en python]


=== [[Réductions de problèmes]] ===
La table d'analyse représente les différents états de l'automate à pile formant l'analyseur, ces états sont calculés en se basant sur la notion d'item de production.


* Tuteur : Pierre Hyvernat
Un item de production représente l'état actuel de validation d'une production, ou autrement dit, le nombre de symboles validés lors de l'analyse.


* Résumé : en complexité algorithmique, le concept de "réduction de problème" est fondamentale. L'idée est simplement de transformer un type de problèmes que l'on souhaite résoudre en un problème que l'on sait résoudre. Le problème "couverture exacte" est le suivant : étant donné un tableau à 2 dimensions de booléens, on cherche une liste de lignes pour mettre ''exactement une valeur "vraie" sur chaque colonne''. Malgré son apparence abstraite, de nombreux problèmes peuvent être transformés en une instance de "couverture exacte" :
Pour une production de la forme <math>N \rightarrow \alpha \gamma \beta</math> il existe 4 items, en cas générale il existe n + 1 items pour une production de n symboles en partie droite. Ces items sont notés :
** les sudokus
** le recouvrement d'une région par des polyominos
** le problème des ''n'' reines ("comment placer ''n'' reines sur un échiquier ''n*n''" sans qu'elles ne s'attaquent)
** le casse-tête [https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/dominosa.html dominosa]


* Objectifs :
<ul>
*# comprendre un peu le problème "couverture exacte"
<li><math>N \rightarrow \bullet \alpha \gamma \beta</math></li>
*# programmer quelques réductions (en python) qui permettront d'utiliser un solveur pour la couverture exacte afin de résoudre d'autres problèmes.
<li><math>N \rightarrow \alpha \bullet \gamma \beta</math></li>
<li><math>N \rightarrow \alpha \gamma \bullet \beta</math></li>
<li><math>N \rightarrow \alpha \gamma \beta \bullet</math></li>
</ul>


* Liens utiles
Par exemple l'item <math>N \rightarrow \alpha \bullet \gamma \beta</math> signifie que l'analyse à reconnu <math>\alpha</math> et espère reconnaître <math>\gamma \beta</math>. Le dernier item <math>N \rightarrow \alpha \gamma \beta \bullet</math> signifie que tous les symboles de la productions ont été reconnu et donc la production peut servir de réduction.
** [https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_la_couverture_exacte couverture exacte sur Wikipedia]


=== Détection d’anomalies en « temps réel » via la plateforme de streaming d’évènements Kafka ===
Tout d'abord pour pouvoir d'écrire des items de l'axiome de la grammaire, nous devons définir une grammaire augmenté similaire à la grammaire initiale mais avec l'adjonction d'un non-terminal <math>S'</math> et de la production <math>S' \rightarrow S</math>. Ainsi l'état initiale de l'analyse est décrit par <math>S' \rightarrow \bullet S</math>, aucun symbole n'est reconnu.


* Tuteur : David Télisson
Deux fonctions vont être utilisées sur ces items, en particulier sur des ensembles d'items. La fonction <math>Fermeture(X)</math> et <math>Transition(X, c)</math>.
* Résumé : Depuis une dizaine d’années, l’avènement de l’Internet des Objets (IoT) a fait apparaitre de nouvelles problématiques en matière de détection d’anomalies dans un flux de données « temps réel ». En effet, les capteurs disséminés peuvent transmettre des données erronées : dérive de sonde, problème d’alimentation, malveillance, etc. La plupart de ces anomalies sont détectées a posteriori en analysant les données stockées en base. Idéalement, il faudrait détecter ces anomalies dès qu’elles se produisent, avant même d’être insérées en base de données.
* Objectifs :
*# Déployer une maquette simple (arduino + capteurs) qui alimente une plateforme de streaming d’événements Kafka et simuler des anomalies (ex : approcher une source de chaleur d'un capteur de température).
*# Implémenter l'algorithme isolation forest en Python (librairie Scikit-Learn) dans un consommateur Kafka pour de détecter une donnée anormale en « temps réel »
* Liens utiles
** https://kafka.apache.org/documentation/
** https://kafka-python.readthedocs.io/en/master/
** https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html


=== Recherche de chemin en temps réel par A* ===
<math>Fermeture(X)</math> prend en argument un ensemble d'item.
Soit un item <math>N \rightarrow \gamma \bullet \alpha</math> de <math>X</math>, si <math>\alpha</math> est un terminal alors ajouter cet item dans le résultat, sinon si <math>\alpha</math> est un non-terminal alors concaténer au résultat <math>Fermeture(Y)</math> où <math>Y</math> et l'ensemble de toutes les items des productions de <math>\alpha</math> avec le point en première position : <math>\{\alpha \rightarrow \bullet \beta, \alpha \rightarrow \bullet \delta, ...\}</math>


* Tuteur : Lucas Chardonnet
<math>Transition(X, c)</math> prend en argument un ensemble d'item et un terminal, Soit <math>N \rightarrow \alpha \bullet c \beta</math> de <math>X</math>, concaténer au résultat <math>Fermeture(\{N \rightarrow \alpha c \bullet \beta\})</math>.
* Résumé : Il existe plusieurs méthodes de recherche de chemin entre un point d'arrivé et un point de départ, qui se basent sur des données représentées par graphe. L'algorithme A* (A étoile ou A star en anglais) permet de trouver un chemin parmi les plus courts entre ces deux points, en temps réel. On propose ici d'implémenter et de visualiser cet algorithme.
* Objectifs:
*# Créer une structure de données pour représenter un graphe.
*# Implémenter l'algorithme A* en utilisant cette structure.
*# Visualiser l'algorithme au travers d'une interface graphique.
* Liens utiles :
** https://fr.wikipedia.org/wiki/Algorithme_A*


=== Rendu rapide de scènes 3D ===
Ces deux fonctions vont permettre de déterminer les états de l'automates, chaque état et un ensemble d'items faisant partie de la collection canonique de l'analyseur. <math>Fermeture(S' \rightarrow \bullet S)</math> est l'état initiale <math>I_0</math> puis <math>Transition(X, c)</math> détermine tous les états atteignables par un décalage de c, et enfin un état où aucune transition n'est possible mais contenant un item de la forme <math>N \rightarrow \gamma \bullet</math> produira une réduction par <math>N</math>.


* Tuteur: Colin Weill-Duflos
<ul>
* Résumé : On cherche à implémenter des méthodes permettant de faire du rendu de scène 3D. On se base sur la rastérisation de triangles, qui est la méthode employée pour faire du rendu en temps réel (par exemple jeux vidéos). D'autres méthodes existent comme le path tracing, plutôt utilisé dans le rendu différé (pour un film d'animation par exemple). Une implémentation de rastérisation de triangles et de z-buffer (technique de gestion de la profondeur) a déjà été réalisée une année précédente, permettant donc d'afficher des triangles en rendant compte de la profondeur. On cherche à la poursuivre pour afficher une scène illuminée.
<li><math> S \rightarrow aSb </math></li>
* Objectifs:
<li><math> S \rightarrow ab </math></li>
*# comprendre les travaux réalisés autour de la rastérisation et du z-buffer
</ul>
*# rajouter une lumière et modifier l'affichage des triangles pour prendre en compte l'illumination
*# utiliser des textures pour le calcul des couleurs
*# rajouter des calculs d'ombres à l'aide de shadow maps
* Pour aller plus loin:
*# Afficher des modèles 3D
*# Utiliser une pipeline graphique (type OpenGL) pour faire ces calculs
*# Contrôles de la caméra
* Liens:
** [Travaux réalisés](https://www.lama.univ-savoie.fr/mediawiki/index.php/Algorithme_de_rendu_de_sc%C3%A8ne_3D_par_Z-buffer)
** [Modèle d'illumination](https://fr.wikipedia.org/wiki/Ombrage_de_Phong)


=== Détection de droites dans les images avec la transformée de Hough ===
La grammaire ci-dessus produits les états suivant :


* Tuteur : Stéphane Breuils
<ul>
* Résumé : La détection de droites est un sujet vaste en traitement d’images et vision par ordinateur. Le problème est de détecter des droites dans une image. Ces droites font en général plus d’un pixel de large, et sont parfois coupées par d’autres objets de l’image. Ce projet consiste à traiter le problème de la détection de lignes avec une implantation de la transformée de Hough, introduite par Paul Hough.
<li><math>Fermeture(\{S' \rightarrow \bullet S\}) = \{
* Objectifs:
S' \rightarrow \bullet S,
*# Comprendre et implémenter la transformée de Hough,
S \rightarrow \bullet aSb,
*# Montrer son intérêt et ses limites sur différentes images,
S \rightarrow \bullet ab
*# Appliquer le même principe que Hough pour la détection de cercles et d'ellipses.
\} = I_0</math></li>
* Lien pour démarrer
<li><math>Transition(I_0, S) = \{
** [Hough](https://fr.wikipedia.org/wiki/Transform%C3%A9e_de_Hough)
S' \rightarrow S \bullet
\} = I_1</math></li>
<li><math>Transition(I_0, a) = \{
S \rightarrow a \bullet Sb,
S \rightarrow a \bullet b,
S \rightarrow \bullet aSb,
S \rightarrow \bullet ab
\} = I_2</math></li>
<li><math>Transition(I_2, S) = \{
S \rightarrow aS \bullet b
\} = I_3</math></li>
<li><math>Transition(I_2, a) = I_2</math></li>
<li><math>Transition(I_2, b) = \{
S \rightarrow ab \bullet
\} = I_4</math></li>
<li><math>Transition(I_3, b) = \{
S \rightarrow aSb \bullet
\} = I_5</math></li>
</ul>


L'automate résultant est le suivant :


=== Stratégies mixtes et programmation linéaire ===
[[Fichier:Automate-lr.png|400px]]


* Tuteur : Sébastien Tavenas
=== Les arbres abstraits de syntaxe ===
* Résumé : Considérons le jeu à deux joueurs suivant. Chacun des deux joueurs écrivent un nombre entier entre 1 et 10 sur une feuille. Puis ils comparent les deux nombres. Si les deux joueurs ont écrit le même nombre, rien ne se passe. Si les deux nombres se suivent, le joueur ayant inscrit le plus petit donne 5 jetons à l'autre. Dans tous les autres cas, c'est le joueur ayant inscrit le plus grand nombre qui donne 1 jeton à l'autre joueur. Pour la même raison que pour le jeu Pierre-Feuille-Ciseau, jouer tout le temps le même coup ne semble pas optimal. Des stratégies optimales pour ces jeux sont appelées mixtes. En fait, trouver la stratégie optimale d'un tel jeu (plus précisément, d'un jeu à somme nulle) revient à résoudre un problème de programmation linéaire associé.
* Objectifs:
*# Comprendre les notions de stratégie mixte, de programmation linéaire et leur lien,
*# En utilisant une librairie de programmation linéaire, écrire un programme qui calcule les stratégies optimales de différents jeux,
*# Comprendre (et essayer d'implémenter) la méthode du simplexe.
* Lien pour démarrer
** [Stratégies mixtes](https://en.wikipedia.org/wiki/Strategy_(game_theory)#Mixed_strategy)
** [Programmation linéaire] (https://en.wikipedia.org/wiki/Linear_programming)


== Sujets proposés 2021-2022 ==
Les arbres abstraits de syntaxe contiennent le minimum de sens de la chaine d'entrée, soit dans la plupart des languages de programmation les opérateurs, les opérandes et les structures de donnée.


* Détection d’anomalies par Isolation Forest : application pour l’industrie 4.0
Dans l'exemple d'un bout de code HTML <nowiki>"<h1>Titre</h1>"</nowiki> nous voudrions obtenir un arbre nous indiquant seulement la présence de la balise <nowiki>"<h1>"</nowiki> contenant le mot "Titre" :
* Machines de Turing
* Géométrie discrète, Convexité des polyominos, Combinatoire des mots
* Origami, axiomes de Huzita/Justin et ReferenceFinder
* Les "claviers"
* Fractales de Newton et sensibilité aux conditions initiales
* Approximation numérique de calculs intégraux
* Instant Insanity
* Automates cellulaires
* Simulation de fluides


=== [[ Détection d’anomalies par Isolation Forest : application pour l’industrie 4.0]] ===
[[Fichier:AST-h1.png|200px]]


* Tuteur : David Télisson
Pour obtenir cette arbre il faut transformer l'arbre de dérivation en sortie de l'analyseur syntaxique avec des attributs de productions.
* Résumé : Cette 4ième ère de l’industrie se définit comme la convergence du monde numérique virtuel avec les produits et objets du monde réel. Ainsi, l’Internet of Things (IoT) se diffuse progressivement dans toutes les strates de l’industrie en intégrant des capteurs et des services qui se connectent à d’autres équipements pour échanger des données. Ce déploiement massif d’objets entraine la collecte puis le traitement de données plus ou moins sensibles selon le contexte. Pour diverses raisons (pannes de capteurs, erreurs de paramétrages, évolution de l’environnement,…) un certain nombre de données peuvent être erronées et entrainer des conséquences sur l’usage. Des méthodes d'apprentissage automatique, permettent la détection d'anomalies. Ainsi l’algorithme non supervisé « Isolation Forest » permet de détecter des anomalies dans un jeu de données en isolant les données atypiques (celles qui sont trop différentes de la plupart des autres données). Cet algorithme calcule, pour chaque donnée du jeu, un score qui reflète à quel point la donnée en question est atypique.
* Objectifs du projet :
*# Etudier et comprendre l’algorithme « Isolation Forest »
*# Tester les lib dédiées du framework Scikit-learn sur un jeu de données type
* Quelques liens :
** Isolation Forest Presentation: https://www.youtube.com/watch?v=cRzeotaFDwk
** Scikit-learn: https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html
** Dataset : https://www.kaggle.com/nphantawee/pump-sensor-data


==== Les arbres de dérivation ====


=== [[Machines de Turing]] ===
Les arbres de dérivation notent toutes les dérivations ou réductions de productions au cours de l'analyse. Lors de la dérivation d'une production <math>N \rightarrow \alpha \beta</math> nous produirons un sous arbre avec en racine le non-terminal <math>N</math> et en nœuds enfants les symboles <math>\alpha</math> et <math>\beta</math> :


* Tuteur: François Boussion
[[Fichier:AST.png|200px]]
* Résumé : Une machine de Turing est un modèle de calcul, qui représente de manière abstraite le fonctionnement des ordinateurs. Toutes les fonctions calculables (ie. tous les algorithmes qui terminent) peuvent être simulées par une machine de Turing. L'objectif est de comprendre ce modèle théorique, et de l'implémenter dans le langage de son choix.
* Objectifs :
*# comprendre les machines de Turing
*# coder (dans le langage de son choix) une machine de Turing, réalisant une opération basique (ajouter 1, soustraire 1, multiplier par 2...)
*# coder une machine de Turing universelle
* Liens pour débuter :
** https://fr.wikipedia.org/wiki/Machine_de_Turing
** http://zanotti.univ-tln.fr/turing/


Malheureusement la majorité des grammaires utilisées par les analyseurs descendant produisent des arbres de dérivation éloigné des arbres abstraits de syntaxe, comme la grammaire suivante :


=== [[Géométrie discrète, Convexité des polyominos, Combinatoire des mots]] ===
<ul>
<li><math> E \rightarrow id\ E'</math></li>
<li><math> E' \rightarrow op\ id\ E'</math></li>
<li><math> E' \rightarrow \epsilon </math></li>
</ul>


* Tuteur: Jacques-Olivier Lachaud
Cette grammaire optimisée pour l'analyse descendante par la suppression de l'ambiguité et l'utilisation de préfixes unique, produit pour le mot d'entrée "5 + 2 - 3" l'arbre de dérivation :
* Résumé: Les régions d'intérêt ou formes dans les images ont une géométrie particulière. Leur contour est un chemin avec seulement 4 directions possibles, car les points du chemin n'ont que des coordonnées entières. Comment faire pour retrouver des éléments de la géométrie Euclidienne classique dans ce cas ? Par exemple, quid de l'aire du périmètre, de la convexité, des tangentes, des points d'inflexion ? Comment reconnaître que la forme est un rectangle tourné de 30 degrés ? Nous verrons comment nous pouvons aborder ce problème au travers d'un outil commun, appelé mot de Christoffel. Il conduit à des algorithmes simples et rapides pour analyser la géométrie des contours dans les images.
* Objectifs:
*# Comprendre les difficultés d'appliquer la géométrie classique sur les formes définies dans les images
*# Comprendre les mots de Christoffel, ses différentes définitions combinatoires et géométriques, la pente d'un tel mot, et lien avec les fractions continues
*# Déterminer la convexité d'un contour en utilisant les mots de Christoffel.
*# Si le temps le permet, savoir calculer un mot de contour à partir d'une image noir et blanc
*# Coder tout ça pour faire un peu d'analyse d'image, genre identifier combien de côtés à un polygone rasterisé dans une image.
* Liens pour démarrer
** [[https://bollu.github.io/lyndon-christoffel-convex-hull.html Petit topo Mot de Christoffel et convexité]]
** [[https://www.lama.univ-savoie.fr/pagesmembres/lachaud/People/LACHAUD-JO/Talks/chambery-ejc-2010.pdf Plus avancé (partie droites et applications)]]
<table>
<tr>
<td> Triangle digital </td>
<td> Pentagone digital </td>
<td> Forme non convexe </td>
<td>Diverses définitions de polyominos convexes</td>
<td>Mots de Christoffel</td>
</tr>
<tr>
<td>[[Fichier:Triangle-50-n.png|100px]]</td>
<td>[[Fichier:Pentagon-50-n.png|100px]]</td>
<td>[[Fichier:Flower-50-3-n.png|100px]]</td>
<td>[[Fichier:Convex-polyominos.gif|300px]]</td>
<td>[[Fichier:Christoffel-word.png|500px]]</td>
</tr>
</table>


=== [[Origami, axiomes de Huzita/Justin et ReferenceFinder]] ===
[[Fichier:AST-expr.png|400px]]


* Tuteur : Pierre Hyvernat
==== Les grammaires attribuées ====
* Résumé : la trisection (exacte) d'un angle quelconque n'est pas possible en utilisant uniquement un compas et une règle (non graduée). Si cet angle est tracé sur une feuille de papier, il existe pourtant une séquence de plis pour le découper en 3 angles égaux ! En étant volontairement provocateur, on peut donc dire que l'origami (pliage depapier) est plus puissant que la géométrie (utilisation du compas et de la règle) !
* Objectifs : comprendre comment on modélise les plis autorisés (axiomes de Justin/Huzita) et visualiser les (approximation des) points constructibles par un petit nombre de plits. On pourra pour ceci utiliser la base de données générée par le programme ReferenceFinder. Idéalement, il faudrait ensuite développer un programme qui reconstruit une telle base de données.
* Références :
*# Jacques Justin, Résolution par le pliage de l'équation du troisième degré et applications géométriques https://publimath.univ-irem.fr/numerisation/ST/IST86008/IST86008.pdf
*# George Martin, *Geometric Constructions* (partie 10)
*# Jean-Paul Delahaye, les mathématiques de l'origami https://www.cristal.univ-lille.fr/~jdelahay/pls/255.pdf
*# Robert Lang, ReferenceFinder https://www.langorigami.com/article/referencefinder/
*# Roger Alperin et Robert Lang, One- Two- and Multi-Fold Origami Axioms https://langorigami.com/wp-content/uploads/2015/09/o4_multifold_axioms.pdf


Les transformations entre arbre de dérivation et arbre abstrait de syntaxe sont décrites par des règles attribués à chacune des productions. Ses règles permettent de lire ou écrire des attributs de symbole.
Pour éviter toute ambiguité entre les symboles dans les productions, les symboles de même nom sont renommés en <math>N_i</math>, <math> E' \rightarrow op\ id\ E'</math> devient <math> E_1' \rightarrow op\ id\ E_2'</math>.


=== [[Les "claviers"]] ===
Les règles se regroupent en deux catégories, les règles synthétisées et les règles héritées.


* Tuteur : Pierre Hyvernat
Les règles synthétisées modifient le non-terminal à gauche d'une production en fonction des attributs des symboles à droite de la production.
* Résumé : chaque touche d'un clavier affiche un caractère. On peut alors écrire tous les mots possibles en appuyant successivement sur les touches pertinentes. Sur un clavier cassé (par exemple, parce qu'il a reçu du café), les touches n'ont plus forcément le comportement attendu : la première touche peut inscrire "ktjh", le seconde "uta", etc. Il n'est alors plus forcément possible d'écrire tous les mots possibles, mais il est facile de comprendre ce que l'on peut faire. Lorsque le comportement de ces touches peut inclure des déplacement (gauche / droite) et la touche "backspace", la situation peut devenir infernale ! Quatre jeunes étudiants en thèse ont récemment développé cette théorie.
En gardant le même exemple de grammaire, la production <math>E' \rightarrow \epsilon </math> doit produire un noeud vide, elle est associée à <math>E'.noeud = noeud()</math>. De même la production <math> E_1' \rightarrow op\ id\ E_2'</math> définit le noeud <math>E_1'</math> avec l'operateur : <math>E'_1.noeud = noeud(op.val)</math>.
* Objectifs : l'objectif est de se familiariser avec les notions de théorie des langages et de regarder les premiers résultats de cette théorie, les astuces mises en œuvre pour étudier les langages engendrés et les questions ouvertes. L'implémentation de petits programmes pour faciliter l'étude de ces langages n'est pas obligatoire, mais forcément recommandé !
* Références :
*# Yoan Géran, Bastien Laboureix, Corto Mascle, Valentin D. Richard, Keyboards as a New Model of Computation Keyboards as a New Model of Computation https://drops.dagstuhl.de/opus/volltexte/2021/14489/pdf/LIPIcs-MFCS-2021-49.pdf (ou la version longue : https://arxiv.org/abs/2102.10182)
*# diapos d'un exposé donné au LAMA en décembre 2021


=== [[Fractales de Newton et sensibilité aux conditions initiales]] ===
Les règles héritées modifient des symboles à droite de la production en fonction des autres symboles à droite, les nœuds voisins, ou le non-terminal à gauche de la production.
Ainsi la production <math> E_1' \rightarrow op\ id\ E_2'</math> doit basculer la valeur <math>id</math> dans le nœeud <math>E_2'</math>, elle est donc associée à la règle <math>E'_2.noeud.ajouter(noeud(id.val))</math>.


* Tuteur: Jacques-Olivier Lachaud
La totalité des règles est :
* Résumé: De modèles en apparence simples peuvent naître des comportements complexes. On parle souvent de Chaos ou d'effet papillon. Nous allons ici étudier un algorithme simple et itératif pour trouver des solutions à l'équation f(z)=0 (où z est un nombre complexe). Comme en général f a plusieurs solutions, cet algorithme qui part d'une position z0 va arriver (s'il arrive) sur une des solutions. Or cet algorithme est sensible aux conditions initiales (pas trop surprenant), mais cette sensibilité est très curieuse et parfois une variation infinitésimale amène sur n'importe quelle solution ! L'image ci-dessous montre cette sensibilité aux conditions initiales, en mettant la couleur de la solution trouvée au point de départ (rappelons que z0 est un nombre complexe, donc un point du plan).
* Objectifs:
*# Comprendre l'algorithme de Newton de recherche de solutions à f(z)=0
*# Implémenter cet algorithme et afficher pour chaque pixel d'un domaine choisi la solution trouvée (avec une couleur) pour faire de jolies images
*# Si le temps le permet, on verra comment aussi faire des images 3D !
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Fractale_de_Newton Fractale de Newton (Wikipedia)]]
** [[https://images.math.cnrs.fr/La-methode-de-Newton-et-son-fractal-en-3D.html?lang=fr Images des mathématiques: fractales de Newton]]
[[fichier:Fractale-newton.png|400px]]


=== [[Approximation numérique de calculs intégraux]] ===
<ul>
* Tuteur : Dionysios Grapsas
<li> <math> E \rightarrow id\ E' \Longrightarrow E.noeud = E'.noeud </math> </li>
* Résumé : L’utilisation de l’ordinateur comme une supercalculette est le moyen que nous disposons aujourd’hui pour calculer les solutions des problèmes “compliqués” de la mécanique, dont les solutions exactes ne sont pas connues (aéronautique, météorologie, éléctromagnétisme, …). Le calcul intégral permet de s’initier à cet approche, de se rendre compte de sa puissance (résolution rapide de problèmes difficiles / impossible à calculer manuellement), de ses limitations (les solutions ne sont jamais “exactes”), ainsi que l’importance de tous les choix qu’on fait pendant la construction et l’implémentation des méthodes numériques aux résultats finaux.
<li> <math> E'_1 \rightarrow op\ id\ E'_2 \Longrightarrow E'_1.noeud = noeud(op.val) E'_1.noeud.ajouter(E'_2.noeud)</math> </li>
* Objectifs :
<li> <math> E' \rightarrow \epsilon \Longrightarrow E'.noeud = noeud() </math> </li>
*# Implémenter des méthodes de calcul intégral déterministes (méthodes de quadrature) et probabilistes (Monte-Carlo)
<li> <math> E \rightarrow id\ E' \Longrightarrow E'.noeud.ajouter(noeud(id.val)) </math> </li>
*# Comparer leurs résultats et leur efficacité sur plusieurs cas de figure
<li> <math> E'_1 \rightarrow op\ id\ E'_2 \Longrightarrow E'_2.noeud.ajouter(noeud(id.val)) </math> </li>
*# Calcul intégral en plusieurs dimensions
</ul>


=== [[Instant Insanity]] ===
Dans notre cas les attributs <math>N.noeud</math> contiennent les nœuds de l'arbre abstrait de syntaxe et donc <math>E.noeud</math> est l'arbre abstrait de syntaxe entier. Un problème se pose toujours lors de l'ordre d'application des règles. En effet la règle <math>E \rightarrow id\ E' \Longrightarrow E'.noeud.ajouter(noeud(id.val))</math> nécessite que <math>E'</math> contienne déjà un attribut <math>noeud</math> valide.
Pour résoudre ce problème, il est possible de préfixer l'ordre d'exécution des règles manuellement lors de leur conception ou déterminer par une analyse l'ordre d'exécution par la construction d'un arbre de dépendance entre les règles. Dans ce cas, les règles n'ayant aucune dépendance sont exécuté puis les autres.


* Tuteur : Sébastien Tavenas
== Le programme exemple ==
* Résumé : Instant Insanity est un puzzle qui a été vendu sous différents noms. Le but est, étant donnés 4 cubes dont les faces sont coloriées (par exemple, en rouge, jaune, vert et bleu), on veut empiler les 4 cubes de telle sorte à ce que chaque "côté" de la colonne contienne les 4 couleurs. Par exemple, vous pouvez essayer avec ces 4 patrons de cubes :
[[Fichier:Instant_insanity_Cube.png]]


Ce puzzle peut facilement être généralisé à n cubes et n couleurs. On cherche à écrire un algorithme qui, si c'est possible trouve un bon empilement. Toutefois, ce jeu a été un des premiers puzzles à avoir été montré NP-complet (par Robertson et Munro en 1978).
Pour mettre en application les algorithmes d'analyse syntaxique, un programme à été écrit avec le support de l'analyse descendante et ascendante simple.
* Objectifs :
Ce programme est disponible dans le dépôt : https://github.com/panzergame/analyseur_cmi
*# Comprendre ce qu'est un problème NP-complet
*# Comprendre pourquoi ce puzzle est NP-complet
*# Coder une heuristique ou utiliser un SAT-solveur
*# Chercher si d'autres puzzles sont aussi NP-complets
* Références pour commencer :
*# [[https://en.wikipedia.org/wiki/Instant_Insanity Page wikipedia du jeu]]
*# [[https://en.wikipedia.org/wiki/NP-completeness Page wikipedia sur la NP-complétude]]


=== [[Automates cellulaires]] ===
Un fois compilé, l'exécutable build/analyzer prend quatre arguments :
*Tuteur : Gérald Cavallini
* Résumé : La théorie des automates cellulaires est relativement simple, une série de règles permet de modifier l’état spatial et temporel d’une cellule en fonction de son voisinage. Cette théorie se décline en de nombreux cas d’étude, automate circulaire cyclique, 2D, 3D … En théorie, les automates cellulaires permettent aussi de réaliser toutes sortes de calculs.Le jeu de la vie imaginé par John Horton Conway en 1970 est un automate cellulaire.
* Objectifs : Le but de ce sujet est d’expliquer si possible au moyen de programmes simples :
*# la classification des automates cellulaires
*# les automates cellulaires remarquables
*# l’équivalence avec les machines de Turing
*# la notion d’universalité
*# les caractéristiques du jeu de la vie
* Liens pour démarrer
** https://mathworld.wolfram.com/CellularAutomaton.html
** https://www.techno-science.net/glossaire-definition/Automate-cellulaire-page-6.html
** https://lig-membres.imag.fr/prost/L3_INFO_MCAL_MT/projet.html
<table>
<tr><td>
[[fichier:Automate_1.png|300px]]
</td><td>
[[fichier:Simuca.gif|300px]]
</td></tr>
</table>


=== [[Simulation de fluides]] ===
<ul>
* Tuteur: Colin Weill-Duflos
<li>input_file : Fichier texte à analyser.</li>
* Résumé : Lorsque l'on veut afficher de l'eau sur un écran, on veut généralement représenter son mouvement sans qu'un animateur n'ait à préciser à la main le déplacement de chaque polygone représentant la surface de l'eau. Pour cela, on emploie des modélisation physiques du fluide pour simuler son comportement, puis on effectue un rendu du fluide ainsi modélisé. Les modèles physiques employés pour simuler un fluide sont complexes (voir les équations de Navier-Stokes) et font apparaître des phénomènes comme des vortex, des vagues... Il faut donc des méthodes de simulation fines capturant la complexité de ces phénomènes.
<li>bnf_file : Fichier de description des productions.</li>
* Objectifs :
<li>regex_file : Fichier de description des règles lexicales et des séparateurs.</li>
*# implémenter un simulateur physique de fluide suivant la méthode "SPH" pour des scènes simples
<li>method : La méthode d'analyse, naive pour LL récursif, stack pour LL avec pile et slr pour SLR.</li>
*# implémenter une méthode pour afficher le fluide ainsi simulé.
<li>Résultat : un historique de l'analyse en console et un arbre de dérivation au format .dot : derivation_tree.dot.</li>
* Références
</ul>
** Video demo : https://www.youtube.com/watch?v=3de4YLqlMFQ
** http://www.cs.columbia.edu/~batty/teaching/COMS6998/SPH_overview.pdf
** https://en.wikipedia.org/wiki/Smoothed-particle_hydrodynamics


[[Fichier:Sph.png|500px]]
Les fichiers de description de règles bnf_file et regex_file utilise le format Backus Naur Form, encadrant chaque non-terminal par "<>" et associant des productions à des non-terminaux grâce à "::=", ainsi <math>N \rightarrow ab</math> s'écrit :
<pre>
<N> ::= a b
</pre>


== Sujets proposés 2020-2021 ==
Pour analyser les expressions simple de la forme "a + b", il faut tout d'abord définir les règles de l'analyseur lexical ainsi que les séparateurs additionnels :


<pre>
<separator> ::= +-/*


* Transformée en distance discrète, diagramme de Voronoi discret, axe médian et squelette
<integer> ::= [0-9]*
* Clustering par K-means, segmentation d'image
<float> ::= [0-9]*\.[0-9]*f?
* Base de données orientées Graphe, similarité et modèles prédictifs
<identifier> ::= [A-z]([A-z]|[0-9])*
* Algorithmes d'approximation numérique de la mesure de Mahler
<operator> ::= \+|\-|/|\*
* Ensemble de Mandelbrot et autres fractales
* Complexité pratique contre complexité théorique
* Etude du protocole gRPC
* Valeurs de Sprague-Grundy pour le jeu de Wythoff
* Modèle mathématique SIR pour décrire la propagation d'une épidémie
* Modélisation de réseaux sociaux, base de données orientées graphe
* Modélisation de la ruine du joueur


=== [[Transformée en distance discrète, diagramme de Voronoi discret, axe médian et squelette]] ===
</pre>


* Tuteur: Jacques-Olivier Lachaud
Ici quatre unités lexicales sont définit pour reconnaitre les entiers (integer), les flottants (float), les noms (identifier) et les opérateurs (operator). De plus les opérateurs sont aussi utilisés pour séparer la chaîne d'entrée.
* Résumé: La transformée en distance permet de situer l'éloignement de tout point du plan ou de l'espace à un ensemble donné. C'est un outil de base dans beaucoup d'algorithmes de traitement d'image ou de données 3D. Pour les images, on peut l'utiliser pour filtrer des objets, comparer deux objets, extraire son squelette, mettre en correspondance deux objets. Dans le cas de nuage de points 3D acquis par laser, on peut utiliser cet outil pour reconstruire une surface approchant ces points. Dans ce travail, on se concentrera sur la transformée en distance dans le cas des images 2D (appelé cas discret). Les objets traités seront des ensembles de pixels, par exemple des caractères écrits si on fait de l'analyse de texte scanné. On s'intéressera aux algorithmes spécifiques à ce contexte, ainsi qu'à quelques applications.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier le lien avec l'axe médian et les squelettes
*# Coder un algorithme de calcul de la transformée en distance et du diagramme de Voronoi dans le cas des images 2D, ainsi que l'extraction de l'axe médian discret.
*# Si le temps le permet, on s'intéressera aussi à l'extraction d'un squelette "topologique", qui contient l'axe médian discret.


* Liens pour démarrer
Ensuite pour un analyseur ascendant les règles seront au format BNF :
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
** [[https://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]


<pre>
<table>
<tr>
<value> ::= identifier | float | integer
<td>Pixels en entrée</td>
<expr> ::= <value> operator <expr> | <value>
<td>Transformée en distance</td>
<root> ::= <expr>
<td>Diagramme de Voronoi</td>
</pre>
<td>Squelette topologique</td>
</tr>
<tr>
<td>[[Fichier:dt-input.png|300px]]</td>
<td>[[Fichier:dt-output.png|300px]]</td>
<td>[[Fichier:dt-voronoi.png|300px]]</td>
<td>[[Fichier:skel.png|150px]]</td>
</tr>
</table>


=== Base de données orientées Graphe, similarité et modèles prédictifs ===
Ici nous validons les mots composés de valeurs entremêler d'opérateurs, où les valeurs peuvent être des noms, entiers ou flottants. Le nom-terminal <pre><root></pre> et le nom prédéfinit pour l'axiome de la grammaire.


* Tuteur : Gérald Cavallini
Pour le fichier input_file contenant "5 + 4.2 - 80", l'exécution de la commande avec le méthode slr produit en console un récapitulatif des règles présentes puis un historique de l'analyse et un affichage de l'arbre de dérivation qui se retrouve aussi dans derivation_tree.dot :
* Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
* Objectifs :
*# Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
*# Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
*# Proposer un une validation du modèle prédictif.
* Liens pour commencer
** https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard
** https://www.machinelearningplus.com/nlp/cosine-similarity/
** https://neo4j.com/
** https://movielens.org/


[[Fichier:Analyseur-resultat.png|400px]]
[[Fichier:Neo4j.jpg|400px]]

=== [[Clustering par K-means, segmentation d'image]] ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le partitionnement de données (ou data clustering) est l'opération visant à découper un ensemble de données en des groupes disjoints, tel que chaque groupe est le plus homogène possible. C'est un procédé à la base de nombreux algorithmes d'analyse de données, et reste encore une tâche difficile, avec de nombreuses définitions possibles. Nous nous intéresserons ici à une méthode standard, relativement simple à mettre en oeuvre, et qui permet de découper un ensemble de données en K groupes, où K est donné. on l'appelle K-means ou algorithme des K-moyennes. Elle opère sur des données où nous pouvons calculer une distance entre toute paire de données. On appliquera cet algorithme aux images couleurs. On verra qu'on peut l'utiliser pour réduire considérablement le nombre de couleurs d'une image tout en la préservant au maximum. On verra aussi, en modifiant la distance, comment utiliser cet algorithme pour faire de la segmentation d'image, c'est-à-dire décomposer une image en ses régions homogènes afin d'identifier les objets d'intérêt.
* Objectifs:
*# Comprendre l'algorithme des k-moyennes et comment l'appliquer à l'analyse d'images couleurs
*# Implémenter cet algorithme avec Python/numpy
*# Tester les distances entre couleurs, et les distances couleur+géométrie
*# Montrer son intérêt sur différentes images, ainsi que ses limites
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/K-moyennes

<table>
<tr>
<td>Image en entrée</td>
<td>Clustering K=256</td>
<td>Clustering K=10</td>
<td>Spatial clustering K=10, c=0.5</td>
</tr>
<tr>
<td>[[Fichier:Kowloon-small.png]]</td>
<td>[[Fichier:Kowloon-k256.png]]</td>
<td>[[Fichier:Kowloon-k10.png]]</td>
<td>[[Fichier:Kowloon-k10-s0_5.png]]</td>
</tr>
</table>

=== [[Algorithmes d'approximation numérique de la mesure de Mahler]] ===

* Tuteur : Denys DUTYKH (CR CNRS, Denys.Dutykh@univ-smb.fr)
* Résumé : Le LAboratoire de MAthématiques (LAMA UMR 5127) de l'USMB se distingue par la grande diversité des recherches menées au sein de cette unité ainsi que par des synergies, parfois surprenantes et inattendues, qui existent entre ses membres. Le présent projet s'inscrit parfaitement dans cette optique. Notamment, nous avons une chance au LAMA d'avoir parmi nous un expert international sur la conjecture de Lehmer et qui se trouve involontairement à l'origine du sujet décrit ci-dessous. Plus précisément, la conjecture de Lehmer porte sur certaines propriétés de l'ensemble de toutes les mesures de Mahler des polynômes univariés à coefficients entiers. La résolution de cette conjecture ne figure pas parmi les objectifs premiers de ce stage même si une telle finalité serait très bien vue par l'encadrant. Dans le premier temps nous allons plutôt étudier et comparer les différentes approches numériques qui existent pour le calcul de la mesure de Mahler d'un polynôme (éventuellement de très grand degré) donné. Si le temps le permet, nous pouvons nous intéresser aussi au calcul de la mesure de Mahler pour des polynômes multivariés bien que cette tâche ait un niveau de difficulté bien supérieur. En cas de difficultés imprévues, nous pourrons ponctuellement consulter l'expert local sur la question qui est toujours très généreux pour partager ses connaissances pointues sur le sujet. Enfin, un certain goût mathématique et une passion (même si elle est dormante) pour la théorie des nombres sont absolument nécessaires pour savourer pleinement le travail sur la mesure de Mahler.
* Liens pour démarrer
*# https://mathworld.wolfram.com/LehmersMahlerMeasureProblem.html
*# https://en.wikipedia.org/wiki/Mahler_measure

[[Fichier:mahler-1.gif]]
[[Fichier:mahler-2.gif]]


=== [[Ensemble de Mandelbrot et autres fractales]] ===

* Tuteur : Pierre Hyvernat

* Résumé : l'ensemble de Mandelbrot est un sous-ensemble des points du plan avec une structure extrêmement complexe. Comme de nombreuses fractales, cet ensemble donne naissance à des visuels surprenants tels que<br />[[Fichier:mandelbrot.jpg]]<br />La couleur d'un point ''c'' du plan dépend uniquement de la vitesse à laquelle l'itération de la fonction ''z -> z*z + c'' diverge et il est donc facile d'écrire un programme qui dessine (une approximation de) l'ensemble de Mandelbrot. Écrire un programme ''efficace'' est un peu plus complexe, et ce encore plus dans des langages comme Python !

* Objectifs :
*# écrire une version "naïve" du programme en Python pur,
*# écrire une seconde version du programme en utilisant des bibliothèques de calcul comme numpy afin de comparer les vitesse d'execution,
*# appliquer certaines optimisation et étudier lors impact sur le temps de calcul,
*# à des niveaux de zoom extremes, la précision des nombres flottants n'est plus suffisante. Il peut être intéressant de tester un calcul beaucoup plus lent, mais avec une précision supérieure,
*# étendre ces programmes pour dessiner les ensembles de julia correspondant à un point du plan.

* Quelques liens
** https://en.wikipedia.org/wiki/Mandelbrot_set
** https://en.wikipedia.org/wiki/Plotting_algorithms_for_the_Mandelbrot_set
** https://www.math.univ-toulouse.fr/~cheritat/wiki-draw/index.php/Mandelbrot_set


=== [[Complexité pratique contre complexité théorique]] ===
* Tuteur : Pierre Hyvernat

* Résumé : la complexité ''théorique'' d'un algorithme est une estimation du nombre d'opérations élémentaires nécessaires pour que l'algorithme termine, en fonction de ses arguments. On ne peut pas donner de réponse exacte, et cette complexité prend typiquement la forme : "le nombre d'opérations élémentaires pour trouver le minimum d'un tableau (avec l'algorithme standard) est proportionnel à la taille du tableau". La complexité ''pratique'' d'un programme est simplement le temps qu'il met sur certains arguments. Par exemple "mon programme du tri bulle prend 4 secondes sur un tableau de taille 10000".<br /> Normalement, une meilleur complexité théorique se traduit par une meilleur complexité pratique, mais ce n'est pas toujours le cas. Nous allons implémenter et comparer plusieurs programmes et étudier la différence entre ces deux notions de complexité. Python sera le langage initial, mais suivant l'étudiant, d'autres langages plus bas niveau pourront être utilisés.

* Objectif :
*# comprendre la définition de complexité théorique
*# implémenter des algorithmes pour le même problème et comparer les complexités pratiques et théoriques, comme par exemple
*#* multiplication naive / méthode de Karatsuba / méthode de Toom-Cook
*#* recherche de la mediane naive / méthode quickselect / méthode linéaire
*#* tri par insertion / tri rapide / tri fusion
*# expliquer d'où peuvent venir les différences constatées, et chercher comment améliorer la complexité "pratique" des programmes correspondants.

* quelques liens :
** multiplication de Karatsuba : http://gersoo.free.fr/Download/docs/kar.pdf
** recherche de la médiane linéaire : https://fr.wikipedia.org/wiki/M%C3%A9diane_des_m%C3%A9dianes
** algorithme quickselect : https://fr.wikipedia.org/wiki/Quickselect

=== [[Etude du protocole gRPC]] ===

* Tuteur : David Télisson
* Résumé : « gRPC est un framework RPC ([https://fr.wikipedia.org/wiki/Remote_procedure_call Remote procedure call]) open source initialement développé par Google. Il utilise le [https://fr.wikipedia.org/wiki/Hypertext_Transfer_Protocol/2 protocole HTTP/2] pour le transport, [https://fr.wikipedia.org/wiki/Protocol_Buffers Protocol Buffers] comme langage de description d'interface (IDL : interface description language), et offre des fonctionnalités telles que l'authentification, la transmission bidirectionnelle et le contrôle de flux, par le blocage ou non des communications par annulation ou délais d'attente. Il permet la construction de liaisons client/serveur multiplateforme pour de nombreux langages » [source wikipedia]
* Objectifs du projet :
*# Etudier et comprendre ce protocole
*# Comparer avec les protocoles RPC historiques : XML-RPC ou JSON-RPC
*# Implémentez un PoC (preuve de concept) simple qui montre le fonctionnement du protocole entre deux applications développées dans des langages différents (Python et JavaScript).
* Liens pour démarrer :
** https://opensource.google/projects/grpc
** https://grpc.io/docs/languages/python/quickstart/
** https://grpc.io/docs/languages/node/quickstart/

=== [[Valeurs de Sprague-Grundy pour le jeu de Wythoff]] ===

* Tuteur : Sébastien Tavenas
* Résumé : Le jeu de Wythoff est un jeu à deux joueurs nécessitant deux piles de pièces. Chacun à leur tour, les joueurs retirent des pièces d’une des deux piles ou des deux piles en même temps. Il y a toutefois une contrainte : si le joueur choisit de retirer des pièces des deux piles en même temps, alors il doit retirer le même nombre de pièces dans chacune des deux piles. Le joueur ramassant la dernière pièce est déclaré vainqueur. Une description équivalente du jeu est la suivante. Une dame d’échecs est placée quelque part sur une un grand échiquier. À tour de roles, chaque joueur déplace la reine vers l’angle bas-gauche du plateau : soit vers le bas, soit en diagonal (bas-gauche), soit vers la gauche du nombre de cases désiré. Le joueur mettant la dame dans la case à l’angle de l’échiquier est déclaré vainqueur. Ce jeu est une variation du célèbre jeu de Nim. Comme ce dernier on connait aujourd’hui l’ensemble des positions perdantes et gagnantes. Toutefois ce jeu devient vite plus compliqué que le jeu de Nim : la stratégie optimale est basée sur les suites de Beatty et l'on ne connait pas d'algorithme pour calculer les valeurs de Sprague-Grundy pour ce jeu en temps polynomial.
* Objectifs du projet :
*# Etudier et comprendre les stratégies pour le jeu de Wythoff
*# Implémenter un algorithme jouant parfaitement
*# Implémenter un algorithme calculant les valeurs de Sprague-Grundy des positions (sans trop se soucier de son efficacité)
*# Si le temps le permet, on pourra s'intéresser à la périodicité additive des valeurs de Sprague-Grundy dans les position de ce jeu.
* Quelques liens :
** Présentation du jeu de Wythoff : https://fr.wikipedia.org/wiki/Jeu_de_Wythoff
** À propos des valeurs de Sprague-Grundy : https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy
** L'introduction de cet article est une bonne entrée en matière sur les valeurs de Sprague-Grundy de ce jeu : http://library.msri.org/books/Book56/files/43nivasch.pdf
** Preuve de la périodicité additive des valeurs de Sprague-Grundy : [http://riverrock.org/~howard/wythoff2.pdf A simple FSM-based proof of the additive periodicity of the Sprague–Grundy function of Wythoff’s game]


=== [[ Modèle mathématique SIR pour décrire la propagation d'une épidémie]] ===

* Tuteur : Jimmy Garnier
* Résumé : Pour les États et pour les organisations internationales, connaître l’évolution d’une épidémie humaine (grippe H1N1, virus Ebola, coronavirus), animale ou végétale est primordial. Un des outils de gestion est la modélisation mathématiques. Il convient dès à présent de préciser que les modèles mathématiques sont des modèles simplifiés, ayant des limites dont il faut être conscient. Dans ce travail, on s'intéressera au modèle SIR qui est un exemple de modèle à compartiments, c’est à dire que l’on divise la population en plusieurs catégories. Pour une population donnée, on étudie la taille de trois sous-populations au cours du temps t :
** S(t) représente les personnes saines (susceptible en anglais) au temps t,
** I(t) les personnes infectées (infected), et
** R(t) les personnes guéries (recovered);
** N=S(t)+I(t)+R(t) représente alors la population constante totale au cours du temps.
* Objectif:
*# Écrire mathématiquement ce modèle d'équations différentielles ordinaires (ODE). Comprendre et intérpréter chaque terme et paramètre du modèles.
*# Analyser mathématiquement ce modèle (existence et unicité des solutions), taux de reproduction et théorème du seuil.
*# Implémenter ce modèle en python à l'aide des librairies mathématiques (numpy, odeint).
*# Représenter graphiquement les résultats du modèle.
* Liens pour démarrer
** [https://images.math.cnrs.fr/Modelisation-d-une-epidemie-partie-1.html?lang=fr Introduction aux modèle SIR]
** [https://www.springer.com/gp/book/9780387952239 Analyse mathématiques des ODE] J D Murray, Mathematical Biology, Springer
** [https://elc.github.io/posts/ordinary-differential-equations-with-python/ Résolution numérique d'ODE Python]

<table>
<tr>
<td>[[Fichier:Sir-1.png|300px]]</td>
<td>[[Fichier:Sir-2.png|300px]]</td>
<td>[[Fichier:Sir-3.jpg|300px]]</td>
</tr>
</table>

=== [[Modélisation de réseaux sociaux, base de données orientées graphe]] ===

* Tuteur : Gérald Cavallini
* Résumé : Les réseaux sociaux sont devenus des cas d'études extrêmement importants dans de nombreux domaines, communication, médecine ... Ce sont des graphes qui présentent des caractéristiques particulières : coéfficient d'agglomération (clustering), longeur moyen des chemins. Des algorithmes existent pour générer ces graphes et obtenir des modéles proches des réseaux sociaux réels. Un type particulier de réseau social et le réseau « petit
monde » ou chaque individu est relié à un autre par un nombre maximum de relations faible.
* Objectifs :
** implémenter ces algorithmes dans un langage de programmation et créer un réseaux social au moyen de la base de données orientée graphe Neo4j.
* Liens pour démarrer
*# [https://fr.wikipedia.org/wiki/Théorie_des_graphes Théorie des graphes]
*# [https://interstices.info/routage-dans-les-petits-mondes/ Comment fonctionne l’effet « petit monde » ?]
*# [http://theses.univ-lyon2.fr/documents/lyon2/2005/mague_jp/pdfAmont/mague_jp_chapitre4.pdf Réseaux de type petit monde]
*# [https://hal.archives-ouvertes.fr/hal-01416524/document Un modèle de génération de graphes “ petit monde ”imitant les réseaux sociaux]

<table>
<tr>
<td>[[Fichier:Smallworld.png|300px]]</td>
<td>[[Fichier: Smallworld-2.jpg|300px]]</td>
</tr>
</table>

=== [[Modélisation de la ruine du joueur]] ===

* Tuteur : Céline Labart
* Résumé : nous nous intéressons à l'étude des gains d'un joueur à la roulette. Celui-ci arrive au casino avec une certaine somme en poche et joue à la roulette tant qu'il n'est pas ruiné ni que ses gains atteignent une somme qu'il s'est fixée. A chaque fois qu'il joue, le joueur gagne ou perd un euro avec une certaine probabilité.
* Objectifs :
*# Simulation d'une partie
*# Calcul de la probabilité de gagner
*# Calcul du temps moyen de jeu
*# Estimation numérique de ces deux quantités à l'aide de la loi des grands nombres
* Lien pour commencer :
*# [https://www.idpoisson.fr/malrieu/wp-content/uploads/sites/3/2019/06/modale.pdf Modélisation aléatoire]

== Sujets proposés 2019-2020 ==


* Compression et transformée de Burrow-Wheeler
* Backtracking
* Transfert de couleur (version 2)
* Génération fractale de terrains
* Architectures Orientées Micro-Services
* Apprentissage automatique
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Base de données orientées Graphe, similarité et modèles prédictifs

=== Compression et transformée de Burrow-Wheeler (lien : [[Transformée Burrows Wheeler]]) ===

* Tuteur : Pierre Hyvernat
* Résumé : La transformée de Burrow-Wheeler est l'étape clé de l'algorithme de compression bzip2. C'est une transformation de texte (suite d'octet) qui ne modifie pas la taille, mais ajoute suffisamment de motifs redondants pour améliorer un autre algorithme de compression (algorithme de Huffman dans le cas de bzip2)
* Objectif : L'objectif est de comprendre le fonctionnement de cette transformation (et de son inverse) et d'implémenter une version naïve de l'algorithme de compression / décompression et de tester sur quelques exemples. Les améliorations de l'algorithme seront ensuite abordées.
* Liens : Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation [[https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf PDF]]

=== Backtracking (lien : [[VISI201 Backtracking (PICHENOT Simon)]])===

* Tuteur : Pierre Hyvernat
* Résumé et objectif : La notion de "backtracking" est fondamentale en algorithmique : il s'agit essentiellement de tester des solutions partielles à un problème, en revenant en arrière dès qu'une incohérence est découverte. Le point de départ sera le fascicule 4.5b de D. Knuth "Introduction to backtracking" et permettra de se familiariser avec les concepts, la terminology et des exemples, qu'il faudra implémenter. Une suite possible sera la notion de réduction de problèmes et l'algorithme-X qui permet de "factoriser" de nombreux problèmes de backtracking en un seul algorithme.
* Liens : D. Knuth, "the art of computer programming introduction to backtracking" [[https://www-cs-faculty.stanford.edu/~knuth/fasc5b.ps.gz PS]]

=== Transfert de couleur (version 2) ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous étudierons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.
{| class="wikitable alternance center"
|+ Transfert de couleur
|----
! scope="col" | Input !! scope="col" | Output
|----
| [[Fichier:horseshoe.jpg|200px]] || [[Fichier:horseshoe-fjord-n40.jpg|200px]]
|----
| [[Fichier:fjord.jpg|200px]] || [[Fichier:fjord-horseshoe-n40.jpg|200px]]
|}
* Objectifs:
*# Comprendre la version 1 fait par [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]], comprendre les qualités et limites de l'approche (sur quelle type d'image ça marche assez bien par exemple)
*# Adapter l'algorithme pour qu'il puisse traiter des images de tailles différentes
*# Réécrire le code en utilisant la bibliothèque python NUMPY pour accélérer les calculs
*# Changer les espaces de couleurs utilisés: RGB ne convient pas très bien pour mesurer le coût du transport. Transformer le code pour qu'il puisse utiliser plutôt l'espace [[https://fr.wikipedia.org/wiki/L*a*b*_CIE_1976 L*a*b*]] mieux adapté pour calculer des distances entre couleurs.
* Liens:
** la page de [[https://www.lama.univ-savoie.fr/mediawiki/index.php/Transport_optimal_par_coupe_1D_et_transfert_de_couleurs_entre_images Lucas Chardonnet]]
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

=== Génération fractale de terrains ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La génération procédurale de terrain est très utilisée en modélisation 3D et dans les jeux vidéos, afin de générer rapidement des paysages pseudo-réalistes que l'on étoffera ensuite de façon plus manuelle. On propose d'étudier et d'implémenter un algorithme classique, dit "algorithme Diamant-Carré". Cet algorithme récursif permet de générer une carte d'élévation. Selon les paramètres données, le résultat peut ressembler aux cartes d'altitude de haute montagne ou des collines plus douces.
{| class="wikitable alternance center"
|+ Génération fractale de terrain par algorithme diamand carré
|----
! scope="col" | Elévations générées !! scope="col" | Colorisation !! scope="col" | Visualisation 3D
|----
| [[Fichier:Diamond-Square_texture.png|200px]] || [[Fichier:Diamond-Square_heightmap.png|200px]] || [[Fichier:Terragen.jpg|200px]]
|}

* Objectifs:
*# Comprendre et implémenter l'algorithme Diamant-Carré
*# Comprendre comment paramétrer cet algorithme pour qu'il génère des montagnes bien abrupte à haute altitude ou des collines à basse altitude.
*# Fabriquer une image de couleur/texture qui va associer des couleurs aux altitudes générées (e.g. forcer du bleu sous l'altitude zero, ajouter de la neige, des lacs, de la forêt)
*# Générer un fichier 3D (par exemple OBJ) à partir de ces deux images (l'image des hauteurs et l'image des couleurs) pour pouvoir faire de beau rendu 3D (sous blender par exemple)
* Liens:
** La page [[https://fr.wikipedia.org/wiki/Algorithme_Diamant-Carr%C3%A9 Wikipedia]] de l'algorithme
** La page [[https://en.wikipedia.org/wiki/Wavefront_.obj_file Wikipedia]] du format OBJ

=== Architectures Orientées Micro-Services ===

* Tuteur : David Télisson
* Résumé : Les architectures des applications logicielles distribuées de grandes envergures ont évolué à partir du début des années 2000, d’une application molithique déployée sur un serveur d’application (JEE, TomCat, etc.) vers des solutions fortement répartis déployées sous formes de services. On parle alors d’architectures orientées services qui se traduisent par le développement et le déploiement de services logiciels interrogeables via des protocoles dédiés (par exemple SOAP) et des API (REST). Cette tendance, corrélée aux nouvelles méthodes de management des projets informatiques (méthodes agiles, intégration continue, DevOps1), s’est accentué ces dernières années et a fait émergé un « nouveau » paradigme : le micro-service. Plusieurs aspects caractérisent un micro-service :
** fonctionnalité unique
** flexibilité technologie
** équipe de développement réduite
** déploiement ciblé
** support de la montée en charge (scalabilité)
** tests facilités et intégrés au processus de développement (TDD2)
* Objectifs du projet :
*# Etudier et comprendre les concepts liés aux micro-services (API, conteneurisation, framework, etc.)
*# Implémentez un PoC (proof of concept) qui démontre qu’une application peut se construire dynamiquement par agrégation de micro-services développés avec des langages différents (Python, JS et Java), déployés sur des plateformes différentes (Django, Node et Glassfish) et disponibles sous formes de conteneurs dans le cloud (Azure)
*# Livrable attendu : un tutoriel « à la OpenClassRooms »
* Liens pour démarrer :
** https://mbaron.developpez.com/cours/microservices/introduction-generalites
** https://openclassrooms.com/fr/courses/4668056-construisez-des-microservices


=== Apprentissage automatique ===

* Tuteur : Tom Hirschowitz
* Résumé : L'apprentissage automatique est un ensemble de techniques algorithmiques visant à écrire des programmes qui améliorent leurs performances au cours du temps. Le sujet consiste en une initiation à cette idée par l'exemple, à base de ressources telles que https://colah.github.io/posts/2015-08-Backprop et http://neuralnetworksanddeeplearning.com .


=== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ===

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]


=== Base de données orientées Graphe, similarité et modèles prédictifs ===

* Tuteur : Gérald Cavallini
* Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
* Objectifs :
*# Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
*# Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
*# Proposer un une validation du modèle prédictif.
* Liens pour commencer
** https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard
** https://www.machinelearningplus.com/nlp/cosine-similarity/
** https://neo4j.com/
** https://movielens.org/

[[Fichier:Neo4j.jpg|400px]]

== Sujets proposés 2018-2019 ==

* Transport optimal par coupe 1D et transfert de couleurs entre images
* Génération et résolution de labyrinthes II
* REST + Pub/Sub : protocole hybride pour l’IoT
* La suite de Conway et la classification périodique des "éléments"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
* Dilemme du prisonnier

=== Transport optimal par coupe 1D et transfert de couleurs entre images ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous verrons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.

[[Fichier:Ex-transfert-couleur-OT.png]]

* Objectifs:
*# comprendre ce qu'est une image niveaux couleur, et ce qu'on appelle le transfert de couleurs.
*# comprendre le principe du transport optimal (discret).
*# comprendre et décrire le principe du transport optimal par coupe 1D, et comment se fait le calcul du meilleur transport dans ce cas.
*# Coder un programme de transfert de couleur, qui prend deux images couleurs et réalise le transfert de couleurs.
*# On pourra ensuite réfléchir à quelques améliorations simples (espace couleur YUV, grouper les pixels).
* Liens pour démarrer
** Le vrai "Transport Optimal" est vite très mathématique (ce sont des mesures qui sont transportées), mais on peut l'aborder beaucoup plus simplement dans le cas discret (un nombre fini de valeurs) comme une simple assignation entre deux ensembles.
** [[https://en.wikipedia.org/wiki/Color_mapping Transfert de couleur Wikipedia]]
** [[https://hal.archives-ouvertes.fr/tel-01246096/file/hdr_hal2.pdf Habilitation de N. Papadakis]] (regardez les images plutôt).

=== Génération et résolution de labyrinthes II ===

* Tuteur: François Boussion
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter un labyrinthe avec une structure de données simple
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
*# introduire des poids pour varier le labyrinthe
*# comment faire un labyrinthe sur grille hexagonale avec des tableaux.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

=== REST + Pub/Sub : protocole hybride pour l’IoT ===

* Tuteur: David Télisson
* Résumé: L’avènement de l’Internet des Objets (IoT) depuis une dizaine d’années a fait apparaitre des problématiques propres aux protocoles de communications liées à ces objets. En effet, l’échange de données dans ce contexte nécessite de tenir compte (au moins) des paramètres suivant :
*# Autonomie énergétique souvent limitée
*# Faible puissance des processeurs et taille réduite de la mémoire
*# Disponibilité « aléatoire » de l’accès aux réseaux de communication

De nombreux protocoles cohabitent et la littérature du domaine foisonne d’exemples autour des réseaux dédiées (LORA, Sigfox, etc.) et des protocoles applicatifs (OPC-UA, MQTT, CoaP, XMPP) mais force est de constater que dans la réalité, ces solutions ne répondent pas toujours aux besoins des concepteurs qui leurs préfèrent encore le protocole HTTP. Celui-ci offre l’avantage d’implémenter un protocole applicatif (REST) en même temps qu’un protocole de transport de haut niveau (TCP/IP) permettant de passer les pare-feu. Cependant, la version actuel d’HTTP ne répond pas vraiment aux critères énoncés précédemment.
Depuis quelques années émerge donc l’idée d’enrichir HTTP pour créer un protocole hybride qui mêlerait les avantages de REST avec ceux proposés par les mécanismes de type Publish/Subscribe (MQTT, AMQP, JMS, etc.). En attendant cette éventuelle évolution, peut-on envisager de mettre en place un mécanisme de type Pub/Sub avec le protocole Websocket au-dessus d’HTTP ?

* Objectifs:
*# Etudier et faire une synthèse des deux approches : REST et Pub/Sub
*# Implémentez un PoC (proof of concept) d’une solution hybride qui met en œuvre un mécanisme de Pub/Sub sur Websocket. .
*# Présenter un protocole de test pour valider ou invalider cette solution

* Liens pour démarrer :
** https://nsrc.org/workshops/2018/apricot/iot/presentations/mqttvsrest_v4.pdf
** http://www.tigli.fr/lib/exe/fetch.php?media=cours:tutorial_mqtt_mit_2015_2016.pdf
** https://openclassrooms.com/fr/courses/3449001-utilisez-des-api-rest-dans-vos-projets-web
** http://www.lirmm.fr/~tibermacin/ens/ws/expose.pdf


=== La suite de Conway et la classification périodique des "éléments" ===

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

=== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ===

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

=== Algorithmes probabilistes/déterministes pour tester la primalité d'un entier ===

* Tuteur : Sébastien Tavenas
* Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
* Objectifs :
*# Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
*# Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
*# Programmer quelques uns des ces tests et les comparer
*# Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

* Liens pour commencer
** [[https://en.wikipedia.org/wiki/Primality_test Tests de primalité]]

=== Dilemme du prisonnier ===

* Tuteur: Gerald Cavallini
* Résumé: Le dilemme du prisonnier caractérise en théorie des jeux une situation où deux joueurs auraient
intérêt à coopérer, mais où, en l’absence de communication entre les deux joueurs, chacun choisira
de trahir l'autre si le jeu n'est joué qu'une fois.

On peut informatiquement modéliser ce dilemme à l’aide de matrices de gains et conserver la
mémoire des choix de l’adversaire. Ce modèle appliqué à un grand nombre d’individus peut être
utilisé pour comprendre l’émergence de stratégies stables dans l’économie, l’écologie, l’évolution
des espèces ...

On peut visualiser spatialement les interactions entre individus en les représentants par des pixels et
en leurs associant une couleur en fonction de leurs stratégies.

[[Fichier:Dilemme.png]]


* Objectifs
*# Comprendre le dilemme du prisonnier
*# Comprendre la notion de stratégie
*# Penser un modèle spatiale pour « opposer » des individus qui appliquent des stratégies différentes
*# Développer une interface pour visualiser dans le temps l’évolution d’une population d’individus adoptants des stratégies différentes.

* Lien :
*# [https://fr.wikipedia.org/wiki/Dilemme_du_prisonnier Dilemme du prisonnier Wikipedia]
*# [http://cormas.cirad.fr/fr/applica/dps.htm Site spécifique]

== Sujets proposés 2017-2018 ==

* Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
* Transformées en distance, diagramme de Voronoi et applications en geometry processing
* Pavages de Penrose


=== [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
* Objectifs:
*# comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
*# décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
*# décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
*# Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Watershed_(image_processing) Watershed Wikipedia]]
** Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf PDF]]

=== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ===

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

=== [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] ===

* Tuteur: Laurent Vuillon
* Résumé: L'idée de ce projet est de se familiariser avec les techniques de fouille de données textuelles à partir des "Exercices de style" de R. Queneau (https://fr.wikipedia.org/wiki/Exercices_de_style). On cherchera à comprendre la structure du vocabulaire du corpus de textes, à utiliser les techniques de TF/IDF pour extraire les mots significatifs du corpus puis à tester les techniques de LDA (Allocation de Dirichlet latente) pour extraire automatiquement les thématiques du corpus afin de construire des regroupements par thème. On pourra également proposer des visualisations des résultats afin de rendre accessible visuellement l'analyse de données produite sur le corpus de documents.
* Objectifs: Introduction à la fouille de données au travers d'un cas pratique
* Pour aller plus loin
** http://blogperso.univ-rennes1.fr/stephane.tuffery/
** http://www.editionstechnip.com/en/catalogue-detail/1005/data-mining-et-statistique-decisionnelle.html
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es
** https://fr.wikipedia.org/wiki/TF-IDF
** "Recherche d'information : applications, modèles et algorithmes; Data mining, décisionnel et big data" de Amini et Gaussier aux éditions Eyrolles.


=== [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
*# Identifier le lien avec l'axe médian et les squelettes
*# Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
*# Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
*# Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
** [[https://en.wikipedia.org/wiki/Distance_transform Transformée en distance Wikipedia]]
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
** [[http://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]

=== [[Pavages de Penrose]] ===

* Tuteur : Pierre Hyvernat
* Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

[[Fichier:P2.png]]

* Objectifs
*# comprendre les notion de pavage périodique, non périodique et apériodique,
*# comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
*# comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
*# écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
*# utiliser ces méthodes pour générer d'autres types de pavages apériodique.

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Pavage_de_Penrose pavage de Penrose (wikipedia]]
** [[https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf Penrose Tiling (Marting Gardner, en anglais)]]


=== [[Algorithmes d'analyse syntaxique]] ===

* Tuteur : Pierre Hyvernat

* Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données ''textuelles'' et ''structurées''. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle ''d'analyseur syntaxique'' ou de ''parseur''. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.

* Objectifs :
*# étudier la formalisation du problème à travers la notion de ''langage'' et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
*# comprendre le lien entre les langages et les automates (automates finis / automates à pile)
*# implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
*# comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (''LL*(k)'', ''LR'', etc.)
*# à partir de là, de nombreuses pistes sont ouvertes :
*#* essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
*#* comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
*#* améliorer l'efficacité des parseurs produits
*#* ajouter des fonctionnalités,
*#* ...

* Liens pour démarrer :
** [[https://en.wikipedia.org/wiki/Parsing page wikipedia "parsing"]]
** [[https://en.wikipedia.org/wiki/Recursive_descent_parser page wikipedia "recursive descent parser"]]
** Le livre référence sur le parsing est probablement "Compilers: Principles, Techniques, and Tools" de Aho, Sethi et Ullman (le "dragon book")
** [[https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ exemples de notes cours de compilation]]

== Sujets proposés 2016-2017 ==

=== [[Algorithme de rendu de scène 3D par Z-buffer]] ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
* Objectifs:
*# décrire le principe de la projection 3D vers 2D
*# décrire la rastérisation des triangles sur une image en pixel
*# expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
*# expliquer comment les couleurs sont calculées par pixel
*# indiquer les qualités et limitations de l'algorithme
* Pour aller plus loin
*# mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
*# expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Z-buffer Wikipedia]]
** [[https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/overview-rasterization-algorithm Scratch a pixel]]

=== [[Traitement d'image]] ===

* Tuteur: Jacques-Olivier Lachaud
* Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
* Objectifs:
*# identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
*# identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
*# comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
*# choisir un ou deux algorithmes de traitement et les expliquer en détails
* Pour aller plus loin
*# Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)

* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Traitement_d%27images Wikipedia]]
** [[http://www.ipol.im/ Image Processing on line]] (permet de tester en ligne des algorithmes sur vos images)


=== [[Nim et la théorie des jeux impartiaux]] ===

* Tuteur: Pierre Hyvernat

* Étudiant : Luca Chapelle

* Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
* Objectifs:
*# comprendre la théorie du jeu de Nim (et la programmer)
*# comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
*# regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
*# programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

* Liens pour commencer
** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]
** [https://fr.wikipedia.org/wiki/Jeu_de_Grundy jeu de Grundy]

=== La suite de Conway et la classification périodique des "éléments" ===

* Tuteur : Pierre Hyvernat
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

* Liens pour commencer
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]

=== Initiation à la démonstration sur ordinateur et certification de logiciel ===

* Tuteur: Tom Hirschowitz
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]

=== [[Calculabilité et modèles de calcul]] ===

* Tuteur: Rodolphe Lepigre
* Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
* Objectifs:
*# comprendre la notion de fonction calculable,
*# comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
*# regarder et comparer quelque modèles de calcul,
*# programmer un modèle de calcul et comprendre les limitations pratiques.

* Liens pour commencer:
** https://fr.wikipedia.org/wiki/Calculabilité
** https://fr.wikipedia.org/wiki/Machine_de_Turing
** https://fr.wikipedia.org/wiki/Lambda-calcul
** https://fr.wikipedia.org/wiki/Jeu_de_la_vie

=== [[Génération et résolution de labyrinthes]] ===

* Tuteur: <strike>Jacques-Olivier Lachaud</strike> Xavier Provençal
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter avec une structure de données un labyrinthe
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]

=== Pavages par polyomino ===

* Tuteur: Xavier Provençal
* Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?
On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?
* Objectifs :
*# Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
*# Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
*# Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
* Pour aller plus loin :
*# Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
*# Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Polyomino Polyomino]]
** [[https://en.wikipedia.org/wiki/Polyomino Polyomino (en)]]
** [[https://fr.wikipedia.org/wiki/Pavage_par_des_polygones_r%C3%A9guliers Pavages]]

Dernière version du 28 mai 2024 à 06:57

  • Cours du semestre 2 du parcours CMI Informatique (licence INFO).
  • Responsable pour 2023--2024: Jacques-Olivier Lachaud
  • Responsable 2016--2023 : Jacques-Olivier Lachaud

Descriptif

L'objectif du module est de faire découvrir les laboratoires, le monde de la recherche et les enseignants-chercheurs et chercheurs, ainsi que la réflexion scientifique. Cela se fait de deux manières.

D'abord, une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (environ 5 par an). [Planning séminaires CMI]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet proposé par les enseignants, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail se fait en interaction avec un tuteur académique (5-6 contacts au moins). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé, et du code si le sujet s'y prête.

Projets réalisés (2023-2024)

Sujets proposés (2023-2024)

Calcul approché de l'élément majoritaire, et autres algorithmes approchés

Tuteur : Pierre Hyvernat

Résumé : en informatique, il est parfois préférable d'accepter un résultat "pas complètement correct", si cela permet d'être plus rapide. Un des premiers problèmes de ce genre est le problème du voyageur de commerce : aucune méthode efficace pour calculer le meilleur trajet n'est connue, mais sous certaines conditions, il existe une méthode efficace qui donne un résultat "pas trop éloigné de l'optimum".

Un autre exemple est celui de la recherche de l'élément majoritaire : c'est l'élément qui apparait le plus souvent dans une liste. Ici, il est facile d'écrire une fonction qui le calcule exactement, mais dans le cas du "big data" qui évolue constamment, la méthode naïve prend trop de temps, et trop de mémoire. En 2005, A. Metwally, D. Agrawal et A. El Abbadi on décrit une méthode approchée pour ce problème. Le programme correspondant est beaucoup plus rapide que la méthode naïve et n'a besoin que d'une quantité de mémoire bornée. Le résultat n'est pas toujours le bon, mais l'erreur faite est connue.

Ce qui est surprenant dans cette méthode est qu'elle semble fausse à première lecture !

Objectifs : comprendre la méthode générale en lisant l'article de A. Metwally, D. Agrawal et A. El Abbadi, et l'implémenter en Python (ou un autre langage). Pour valider la méthode, il serait intéressant de voir si cette méthode approchée peut être plus rapide qu'un générateur aléatoire adéquat de valeurs sur lequel on la brancherait.

Référence : Ahmed Metwally, Divyakant Agrawal et Amr El Abbadi, Efficient Computation of Frequent and Top-k Elements in Data Streams, https://www.cse.ust.hk/~raywong/comp5331/References/EfficientComputationOfFrequentAndTop-kElementsInDataStreams.pdf

Surfaces polygonales et surfaces de subdivision

Tuteur : Jacques-Olivier Lachaud

Résumé : Les surfaces polygonales, et notamment les surfaces triangulées ou quadrangulées, sont la brique de base des modèles géométriques 3D, utilisés par exemple dans tous les jeux vidéos 3D, les effets spéciaux pour les films, ou la conception et fabrication assistée par ordinateur. Parfois ces surfaces ont une géométrie un peu trop facettée. Les processus de subdivision de surface permettent de raffiner progressivement une surface polygonale (en subdivisant les faces et en replaçant les sommets) de manière à obtenir une surface de plus en plus lisse. D'ailleurs on peut montrer que la surface limite est bien est une surface lisse.

Suzanne-1.png Suzanne-s1.png Suzanne-s2.png Suzanne-s3.png Suzanne-s4.png
Surface polygonale 1 subdivision 2 subdivisions 3 subdivisions 4 subdivisions

Objectifs : Il s'agira de comprendre comment représenter une surface polygonale en mémoire (pour l'affichage on utilisera polyscope, une bibliothèque python), comment charger une surface à partir d'un format simple (wavefront OBJ). Ensuite on étudiera plus particulièrement les surfaces de subdivision dite Catmull-Clark, que l'on implémentera.

Référence :

  • Catmull-Clark subdivision
  • On utilisera Polyscope pour visualiser les surfaces en 3D avec python.
  • Un tutorial pour créer/charger les surfaces polygonales en python et polyscope.
  • Blender un logiciel open-source pour créer des modèles 3D et calculer des rendus par lancer de rayons.

Calcul des valeurs de Grundy pour des jeux octaux

Tuteur : Valentin Gledel

Résumé : Les jeux combinatoires impartiaux sont des jeux à deux joueurs, à informations parfaites (pas de hasard ni d'information cachée) et dans lesquels dans chaque position les joueurs disposent toujours du même ensemble de coups l'un que l'autre. Par exemple les échecs ne rentrent pas dans cette catégorie car si c'est aux blancs de jouer, ils ne peuvent bouger que les pièces blanches tandis que si c'est au noirs de jouer, ils ne peuvent jouer que les pièces noires. Les ensembles de coups possibles ne sont pas les mêmes. Dans l'étude de ces jeux, la question qu'on se pose est de savoir quel joueur gagnerait si les deux joueurs jouaient parfaitement. Un outil pratique dans la résolution de cette question est la notion de valeur de Grundy d'un jeu. En effet, si on connait la valeur de Grundy d'un jeu J1 et d'un jeu J2 alors on sait quel joueur gagne si on joue en même temps sur J1 et sur J2. Les jeux octaux forment une sous-classe des jeux combinatoires impartiaux qui contient des jeux proches du célèbre jeu de Nim et, en particulier, le "jeu de Fort Boyard" fait partie de cette catégorie. Dans ce sujet on se propose de calculer la valeur de Grundy pour des jeux octaux.

Objectifs : Comprendre ce qu'est la valeur de Grundy d'un jeu et calculer la valeur de Grundy de plusieurs jeux octaux. On pourra ensuite écrire un programme générique qui trouve la valeur de Grundy de jeux octaux sous forme générique, voire même prouver la périodicité des valeurs de Grundy de certains jeux.

Références :


Cryptanalyse informatique de quelques systèmes de chiffrement "historiques"

Tuteur : Pierre Hyvernat

Résumé : pendant longtemps, "craquer" les systèmes de chiffrement ("codes secrets") se faisait essentiellement à la main, et les outils informatiques ont rendu la plupart des systèmes historiques obsolète. Pourtant, sauf dans quelques cas particuliers, l'ordinateur ne peut pas casser un code simplement en testant toutes les possibilités. Il faut trouver une méthode plus efficace.

L'objectif sera d'étudier et d'implémenter quelques uns de ces systèmes simples :

  • chiffrement,
  • déchiffrement,
  • décryptage (càd déchiffrement sans utiliser la clé secrète).

Les systèmes de chiffrement considérés seront

  • substitutions monoalphabétiques, décryptées en utilisant la méthode "aléatoire" du "hill-climbing",
  • le "straddling checkerboard", décrypté par recherche exhaustive sur les positions des "blancs" dans la clé, et en le transformant en substitutions monoalphabétique,
  • le code de Hill, décrypté en utilisant un mot probable, ou la conjonction d'une recherche exhaustive sur les lignes de la clé suivie des tests exhaustifs de toutes leurs permutations.

Suivant le temps et l'intérêt, on pourra soit regarder d'autres systèmes de chiffrement, soit essayer d'améliorer l'analyse du chiffre de Hill en combinant la seconde méthode avec la méthode du Hill-climbing.

Références :


Implémentation d'une IA pour le jeu Puissance 4 à l'aide de l'algorithme alpha-beta

Tuteur : Valentin Gledel

Résumé : Le jeu Puissance 4 est un jeu bien connu dans lequel deux joueurs placent alternativement des jetons dans une grille 7 par 6. Le premier joueur qui réussit à aligner 4 jetons gagne la partie. La simplicité des règles du jeu et le nombre restreint de coups possibles à chaque moment de la partie font de ce jeu un bon candidat pour implémenter les algorithmes de jeux minimax et alpha-beta. Ces algorithmes effectuent une recherche jusqu'à une certaine profondeur dans l'arbre des coups possibles. Ils évaluent ensuite les positions à la profondeur choisie à partir d'une "mesure" choisie par le programmeur. Puis, ils choisissent un coup à jouer en fonction de la position donnant le meilleur résultat.

Objectif : Implémenter le jeu Puissance 4, trouver des mesures pour évaluer des positions de ce jeu, implémenter l'algorithme minimax et l'algorithme alpha-beta, comparer les résultats de ces algorithmes.

Références :

Modélisation de la ruine du joueur

Tuteur : Céline Labart

Résumé : Nous nous intéressons à l'étude des gains d'un joueur à la roulette. Celui-ci arrive au casino avec une certaine somme en poche et joue à la roulette tant qu'il n'est pas ruiné ni que ses gains atteignent une somme qu'il s'est fixée. A chaque fois qu'il joue, le joueur gagne ou perd un euro avec une certaine probabilité.

Objectifs :

  • Simulation d'une partie
  • Calcul de la probabilité de gagner
  • Calcul du temps moyen de jeu
  • Estimation numérique de ces deux quantités à l'aide de la loi des grands nombres

Références :

Planarité de graphes

Tuteur : Sébastien Tavenas

Résumé : Un graphe est dit planaire si on peut le "dessiner" dans le plan de façon à ce que les arêtes ne se croisent pas. Donné un graphe, est-il facile de tester s’il est planaire ? Pour commencer, il est facile de certifier qu’un graphe est planaire en donnant le "dessin" du graphe dans le plan. Mais comment montrer qu’un graphe n’est pas planaire ? Kuratowski a montré qu’un graphe n’est pas planaire si et seulement si il contient un mineur (ie, un sous-graphe) qui est K5 (le graphe complet avec 5 sommets) ou K3,3 (le graphe biparti complet avec chaque partie ayant 3 sommets). Ainsi, pour montrer qu’un graphe n’est pas planaire, il suffit de montrer une subdivision qui est K5 ou K3,3. Il semble alors possible de trouver un algorithme qui donné un graphe, soit retourne un "dessin" du graphe planaire dans le plan, soit trouve une subdivision K5 ou K3,3 garantissant que le graphe n’est pas planaire.

Objectif : Comprendre la notion de graphe planaire et le théorème de Kuratowski. Coder un programme de détection de planarité (plusieurs algorithmes linéaires existent pour ce problème).

Référence :


Calibration de caméra et reconstruction 3D

Tuteur : Stéphane Breuils

Résumé : Nous explorons dans ce projet la calibration de caméras à partir d’un ensemble de points de correspondance et son utilisation pour reconstruire des objets en 3D. L'idée est de pouvoir dimensionner précisément des éléments photographiés.

Objectifs :

  • Comprendre la modélisation d'une caméra (paramètres intrinsèques, extrinsèques)
  • Etudier des méthodes de rectification épipôlaires consistant à transformer des images avec des homographies.
  • Effectuer des calibrations de caméras et discuter des méthodes d'estimation de la profondeur.

Références :

Archive des sujets réalisés

Projets 2023-2024

Projets 2022-2023

Projets 2021-2022

Projets 2020-2021

Projets 2019-2020

Projets 2018-2019

Projets 2017-2018


Projets 2016-2017

Archive des projets proposés

Sujets proposés 2022-2023

  • Programmation du robot Nao
  • Vision en relief, anaglyphes à partir d'images RGB+profondeur
  • Vision en relief, auto-stéréogrammes à partir d'une image de profondeur
  • Tables de hachage et dictionnaires
  • Réductions de problèmes
  • Détection d’anomalies en « temps réel » via la plateforme de streaming d’évènements Kafka
  • Recherche de chemin en temps réel par A*
  • Rendu rapide de scènes 3D
  • Détection de droites dans les images avec la transformée de Hough
  • Stratégies mixtes et programmation linéaire


Programmation du robot Nao

  • Tuteur : Christophe Carmagnac
  • Résumé : Nao est un robot programmable. Il dispose d'une API qui permet de le controler à distance. Il possède divers capteurs qui remontent des données en temps réel. Nao est donc une base intéressante pour faire des projets axés sur la robotique sans avoir à se soucier des contraintes électroniques. Dans ce projet, on cherchera à créer des programmes permettant à Nao d'analyser et d'intéragir avec son environnement.
  • Objectifs :
    1. Implémenter un algorithme permettant à Nao de se déplacer
    2. Reconnaître différents objets tels qu'une tasse de café en utilisant Python
    3. Faire en sorte que Nao prenne un objet
    4. Créer un programme permettant de déplacer un objet de manière autonome
  • Liens pour démarrer

Vision en relief, anaglyphes à partir d'images RGB+profondeur

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La vision en relief nécessite de construire 2 images d'une scène 3D, une pour l'oeil gauche, l'autre pour l'oeil droit. A moins d'avoir des dispositifs particuliers, le procédé le plus simple pour construire et visualiser une image en relief est l'anaglyphe, c'est-à-dire construire une seule image mélangeant les 2 vues, la vue gauche en rouge, la vue droite en cyan, et d'utiliser de simples lunettes colorées rouge-cyan. Nous allons construire de tels anaglyphes, mais à partir d'images couleurs (RGB) qui ont aussi une profondeur par pixel. Ces images sont devenues très courantes avec la Kinect de la Xbox. On verra que l'on peut ainsi donner une impression de relief, mais que ces images ont aussi des défauts.
  • Objectifs:
    1. Comprendre le procédé anaglyphe et la différence de point de vue entre nos deux yeux
    2. Lire les images RGB+Z et fabriquer une image anaglyphe (on utilisera OpenCV avec python)
    3. Faire la même chose en flux video.
    4. Corriger l'entrée en profondeur pour améliorer le rendu.
  • Liens pour démarrer
RGB Profondeur Anaglyphe
Rgb.png Depth.png Anaglyph.png

Vision en relief, auto-stéréogrammes à partir d'une image de profondeur

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La vision en relief nécessite de construire 2 images d'une scène 3D, une pour l'oeil gauche, l'autre pour l'oeil droit. Nous proposons ici d'étudier une technique qui permet d'avoir une vision en relief à partir d'une seule image ! Le procédé, appelé (auto-)stéréogramme encode l'image pour l'oeil gauche et l'image pour l'oeil droit dans la même image. L'idée est d'utiliser une image qui se répète par bandes verticales régulièrement (genre tous les 60 pixels). Ensuite, c'est l'observateur qui, en faisant converger ses yeux au-delà de l'écran, ne fait pas voir les mêmes bandes à ses yeux. En modifiant légèrement les motifs de répétition, nos 2 yeux ne voient pas la même chose et nous voyons la scène en relief !
  • Objectifs:
    1. Comprendre le procédé stéréogramme
    2. Mettre au point l'algorithme de calcul d'une telle image à partir d'un motif (donné ou généré) et d'une image de profondeur.
    3. On pourra utiliser OpenCV avec python
    4. On peut même faire la même chose avec un flux video d'images de profondeur.
  • Liens pour démarrer
Profondeur Stéréogramme 1 Stéréogramme 2 On voit ci-dessous le procédé qui consiste en des décalages de motifs. Malheureusement sous cette forme, notre cerveau a beaucoup de peine à le reconstruire
Stereogram-depth.png Stereogram-1.png Stereogram-2.png Stereogram-3.png

Tables de hachage et dictionnaires

  • tuteur : Pierre Hyvernat
  • Résumé : les ordinateur peuvent facilement représenter un tableau de n cases par une zone de n cases mémoires consécutives. Le plus simple pour représenter un dictionnaire (comme un Python) est d'utiliser un tableau où chaque case contient à la fois la clé et la valeur. Ceci est particulièrement inefficace car savoir si une clé est valide (càd apparait dans le dictionnaire) est lent.
  • Objectifs :
    1. regarder comment implémenter les tables de hachage. Cette structure permet de représenter les dictionnaire de manière plus efficace,
    2. comprendre comment fonctionnent quelques fonctions de hachage. Ces fonctions permettent de transformer chaque clé en indice de case d'un tableau standard. Les clés deviennent donc des nombres entiers, et il alors possible de faire des recherche par dichotomie pour accélérer la recherche.
    3. regarder différentes manières de gérer les collisions, car même avec une fois la fonction de hachage bien choisie, 2 clés différentes peuvent donner le même indice.

Réductions de problèmes

  • Tuteur : Pierre Hyvernat
  • Résumé : en complexité algorithmique, le concept de "réduction de problème" est fondamentale. L'idée est simplement de transformer un type de problèmes que l'on souhaite résoudre en un problème que l'on sait résoudre. Le problème "couverture exacte" est le suivant : étant donné un tableau à 2 dimensions de booléens, on cherche une liste de lignes pour mettre exactement une valeur "vraie" sur chaque colonne. Malgré son apparence abstraite, de nombreux problèmes peuvent être transformés en une instance de "couverture exacte" :
    • les sudokus
    • le recouvrement d'une région par des polyominos
    • le problème des n reines ("comment placer n reines sur un échiquier n*n" sans qu'elles ne s'attaquent)
    • le casse-tête dominosa
  • Objectifs :
    1. comprendre un peu le problème "couverture exacte"
    2. programmer quelques réductions (en python) qui permettront d'utiliser un solveur pour la couverture exacte afin de résoudre d'autres problèmes.

Détection d’anomalies en « temps réel » via la plateforme de streaming d’évènements Kafka

  • Tuteur : David Télisson
  • Résumé : Depuis une dizaine d’années, l’avènement de l’Internet des Objets (IoT) a fait apparaitre de nouvelles problématiques en matière de détection d’anomalies dans un flux de données « temps réel ». En effet, les capteurs disséminés peuvent transmettre des données erronées : dérive de sonde, problème d’alimentation, malveillance, etc. La plupart de ces anomalies sont détectées a posteriori en analysant les données stockées en base. Idéalement, il faudrait détecter ces anomalies dès qu’elles se produisent, avant même d’être insérées en base de données.
  • Objectifs :
    1. Déployer une maquette simple (arduino + capteurs) qui alimente une plateforme de streaming d’événements Kafka et simuler des anomalies (ex : approcher une source de chaleur d'un capteur de température).
    2. Implémenter l'algorithme isolation forest en Python (librairie Scikit-Learn) dans un consommateur Kafka pour de détecter une donnée anormale en « temps réel »
  • Liens utiles

Recherche de chemin en temps réel par A*

  • Tuteur : Lucas Chardonnet
  • Résumé : Il existe plusieurs méthodes de recherche de chemin entre un point d'arrivé et un point de départ, qui se basent sur des données représentées par graphe. L'algorithme A* (A étoile ou A star en anglais) permet de trouver un chemin parmi les plus courts entre ces deux points, en temps réel. On propose ici d'implémenter et de visualiser cet algorithme.
  • Objectifs:
    1. Créer une structure de données pour représenter un graphe.
    2. Implémenter l'algorithme A* en utilisant cette structure.
    3. Visualiser l'algorithme au travers d'une interface graphique.
  • Liens utiles :

Rendu rapide de scènes 3D

  • Tuteur: Colin Weill-Duflos
  • Résumé : On cherche à implémenter des méthodes permettant de faire du rendu de scène 3D. On se base sur la rastérisation de triangles, qui est la méthode employée pour faire du rendu en temps réel (par exemple jeux vidéos). D'autres méthodes existent comme le path tracing, plutôt utilisé dans le rendu différé (pour un film d'animation par exemple). Une implémentation de rastérisation de triangles et de z-buffer (technique de gestion de la profondeur) a déjà été réalisée une année précédente, permettant donc d'afficher des triangles en rendant compte de la profondeur. On cherche à la poursuivre pour afficher une scène illuminée.
  • Objectifs:
    1. comprendre les travaux réalisés autour de la rastérisation et du z-buffer
    2. rajouter une lumière et modifier l'affichage des triangles pour prendre en compte l'illumination
    3. utiliser des textures pour le calcul des couleurs
    4. rajouter des calculs d'ombres à l'aide de shadow maps
  • Pour aller plus loin:
    1. Afficher des modèles 3D
    2. Utiliser une pipeline graphique (type OpenGL) pour faire ces calculs
    3. Contrôles de la caméra
  • Liens:

Détection de droites dans les images avec la transformée de Hough

  • Tuteur : Stéphane Breuils
  • Résumé : La détection de droites est un sujet vaste en traitement d’images et vision par ordinateur. Le problème est de détecter des droites dans une image. Ces droites font en général plus d’un pixel de large, et sont parfois coupées par d’autres objets de l’image. Ce projet consiste à traiter le problème de la détection de lignes avec une implantation de la transformée de Hough, introduite par Paul Hough.
  • Objectifs:
    1. Comprendre et implémenter la transformée de Hough,
    2. Montrer son intérêt et ses limites sur différentes images,
    3. Appliquer le même principe que Hough pour la détection de cercles et d'ellipses.
  • Lien pour démarrer


Stratégies mixtes et programmation linéaire

  • Tuteur : Sébastien Tavenas
  • Résumé : Considérons le jeu à deux joueurs suivant. Chacun des deux joueurs écrivent un nombre entier entre 1 et 10 sur une feuille. Puis ils comparent les deux nombres. Si les deux joueurs ont écrit le même nombre, rien ne se passe. Si les deux nombres se suivent, le joueur ayant inscrit le plus petit donne 5 jetons à l'autre. Dans tous les autres cas, c'est le joueur ayant inscrit le plus grand nombre qui donne 1 jeton à l'autre joueur. Pour la même raison que pour le jeu Pierre-Feuille-Ciseau, jouer tout le temps le même coup ne semble pas optimal. Des stratégies optimales pour ces jeux sont appelées mixtes. En fait, trouver la stratégie optimale d'un tel jeu (plus précisément, d'un jeu à somme nulle) revient à résoudre un problème de programmation linéaire associé.
  • Objectifs:
    1. Comprendre les notions de stratégie mixte, de programmation linéaire et leur lien,
    2. En utilisant une librairie de programmation linéaire, écrire un programme qui calcule les stratégies optimales de différents jeux,
    3. Comprendre (et essayer d'implémenter) la méthode du simplexe.
  • Lien pour démarrer

Sujets proposés 2021-2022

  • Détection d’anomalies par Isolation Forest : application pour l’industrie 4.0
  • Machines de Turing
  • Géométrie discrète, Convexité des polyominos, Combinatoire des mots
  • Origami, axiomes de Huzita/Justin et ReferenceFinder
  • Les "claviers"
  • Fractales de Newton et sensibilité aux conditions initiales
  • Approximation numérique de calculs intégraux
  • Instant Insanity
  • Automates cellulaires
  • Simulation de fluides

Détection d’anomalies par Isolation Forest : application pour l’industrie 4.0

  • Tuteur : David Télisson
  • Résumé : Cette 4ième ère de l’industrie se définit comme la convergence du monde numérique virtuel avec les produits et objets du monde réel. Ainsi, l’Internet of Things (IoT) se diffuse progressivement dans toutes les strates de l’industrie en intégrant des capteurs et des services qui se connectent à d’autres équipements pour échanger des données. Ce déploiement massif d’objets entraine la collecte puis le traitement de données plus ou moins sensibles selon le contexte. Pour diverses raisons (pannes de capteurs, erreurs de paramétrages, évolution de l’environnement,…) un certain nombre de données peuvent être erronées et entrainer des conséquences sur l’usage. Des méthodes d'apprentissage automatique, permettent la détection d'anomalies. Ainsi l’algorithme non supervisé « Isolation Forest » permet de détecter des anomalies dans un jeu de données en isolant les données atypiques (celles qui sont trop différentes de la plupart des autres données). Cet algorithme calcule, pour chaque donnée du jeu, un score qui reflète à quel point la donnée en question est atypique.
  • Objectifs du projet :
    1. Etudier et comprendre l’algorithme « Isolation Forest »
    2. Tester les lib dédiées du framework Scikit-learn sur un jeu de données type
  • Quelques liens :


Machines de Turing

  • Tuteur: François Boussion
  • Résumé : Une machine de Turing est un modèle de calcul, qui représente de manière abstraite le fonctionnement des ordinateurs. Toutes les fonctions calculables (ie. tous les algorithmes qui terminent) peuvent être simulées par une machine de Turing. L'objectif est de comprendre ce modèle théorique, et de l'implémenter dans le langage de son choix.
  • Objectifs :
    1. comprendre les machines de Turing
    2. coder (dans le langage de son choix) une machine de Turing, réalisant une opération basique (ajouter 1, soustraire 1, multiplier par 2...)
    3. coder une machine de Turing universelle
  • Liens pour débuter :


Géométrie discrète, Convexité des polyominos, Combinatoire des mots

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Les régions d'intérêt ou formes dans les images ont une géométrie particulière. Leur contour est un chemin avec seulement 4 directions possibles, car les points du chemin n'ont que des coordonnées entières. Comment faire pour retrouver des éléments de la géométrie Euclidienne classique dans ce cas ? Par exemple, quid de l'aire du périmètre, de la convexité, des tangentes, des points d'inflexion ? Comment reconnaître que la forme est un rectangle tourné de 30 degrés ? Nous verrons comment nous pouvons aborder ce problème au travers d'un outil commun, appelé mot de Christoffel. Il conduit à des algorithmes simples et rapides pour analyser la géométrie des contours dans les images.
  • Objectifs:
    1. Comprendre les difficultés d'appliquer la géométrie classique sur les formes définies dans les images
    2. Comprendre les mots de Christoffel, ses différentes définitions combinatoires et géométriques, la pente d'un tel mot, et lien avec les fractions continues
    3. Déterminer la convexité d'un contour en utilisant les mots de Christoffel.
    4. Si le temps le permet, savoir calculer un mot de contour à partir d'une image noir et blanc
    5. Coder tout ça pour faire un peu d'analyse d'image, genre identifier combien de côtés à un polygone rasterisé dans une image.
  • Liens pour démarrer
Triangle digital Pentagone digital Forme non convexe Diverses définitions de polyominos convexes Mots de Christoffel
Triangle-50-n.png Pentagon-50-n.png Flower-50-3-n.png Convex-polyominos.gif Christoffel-word.png

Origami, axiomes de Huzita/Justin et ReferenceFinder

  • Tuteur : Pierre Hyvernat
  • Résumé : la trisection (exacte) d'un angle quelconque n'est pas possible en utilisant uniquement un compas et une règle (non graduée). Si cet angle est tracé sur une feuille de papier, il existe pourtant une séquence de plis pour le découper en 3 angles égaux ! En étant volontairement provocateur, on peut donc dire que l'origami (pliage depapier) est plus puissant que la géométrie (utilisation du compas et de la règle) !
  • Objectifs : comprendre comment on modélise les plis autorisés (axiomes de Justin/Huzita) et visualiser les (approximation des) points constructibles par un petit nombre de plits. On pourra pour ceci utiliser la base de données générée par le programme ReferenceFinder. Idéalement, il faudrait ensuite développer un programme qui reconstruit une telle base de données.
  • Références :
    1. Jacques Justin, Résolution par le pliage de l'équation du troisième degré et applications géométriques https://publimath.univ-irem.fr/numerisation/ST/IST86008/IST86008.pdf
    2. George Martin, *Geometric Constructions* (partie 10)
    3. Jean-Paul Delahaye, les mathématiques de l'origami https://www.cristal.univ-lille.fr/~jdelahay/pls/255.pdf
    4. Robert Lang, ReferenceFinder https://www.langorigami.com/article/referencefinder/
    5. Roger Alperin et Robert Lang, One- Two- and Multi-Fold Origami Axioms https://langorigami.com/wp-content/uploads/2015/09/o4_multifold_axioms.pdf


Les "claviers"

  • Tuteur : Pierre Hyvernat
  • Résumé : chaque touche d'un clavier affiche un caractère. On peut alors écrire tous les mots possibles en appuyant successivement sur les touches pertinentes. Sur un clavier cassé (par exemple, parce qu'il a reçu du café), les touches n'ont plus forcément le comportement attendu : la première touche peut inscrire "ktjh", le seconde "uta", etc. Il n'est alors plus forcément possible d'écrire tous les mots possibles, mais il est facile de comprendre ce que l'on peut faire. Lorsque le comportement de ces touches peut inclure des déplacement (gauche / droite) et la touche "backspace", la situation peut devenir infernale ! Quatre jeunes étudiants en thèse ont récemment développé cette théorie.
  • Objectifs : l'objectif est de se familiariser avec les notions de théorie des langages et de regarder les premiers résultats de cette théorie, les astuces mises en œuvre pour étudier les langages engendrés et les questions ouvertes. L'implémentation de petits programmes pour faciliter l'étude de ces langages n'est pas obligatoire, mais forcément recommandé !
  • Références :
    1. Yoan Géran, Bastien Laboureix, Corto Mascle, Valentin D. Richard, Keyboards as a New Model of Computation Keyboards as a New Model of Computation https://drops.dagstuhl.de/opus/volltexte/2021/14489/pdf/LIPIcs-MFCS-2021-49.pdf (ou la version longue : https://arxiv.org/abs/2102.10182)
    2. diapos d'un exposé donné au LAMA en décembre 2021

Fractales de Newton et sensibilité aux conditions initiales

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: De modèles en apparence simples peuvent naître des comportements complexes. On parle souvent de Chaos ou d'effet papillon. Nous allons ici étudier un algorithme simple et itératif pour trouver des solutions à l'équation f(z)=0 (où z est un nombre complexe). Comme en général f a plusieurs solutions, cet algorithme qui part d'une position z0 va arriver (s'il arrive) sur une des solutions. Or cet algorithme est sensible aux conditions initiales (pas trop surprenant), mais cette sensibilité est très curieuse et parfois une variation infinitésimale amène sur n'importe quelle solution ! L'image ci-dessous montre cette sensibilité aux conditions initiales, en mettant la couleur de la solution trouvée au point de départ (rappelons que z0 est un nombre complexe, donc un point du plan).
  • Objectifs:
    1. Comprendre l'algorithme de Newton de recherche de solutions à f(z)=0
    2. Implémenter cet algorithme et afficher pour chaque pixel d'un domaine choisi la solution trouvée (avec une couleur) pour faire de jolies images
    3. Si le temps le permet, on verra comment aussi faire des images 3D !
  • Liens pour démarrer

Fractale-newton.png

Approximation numérique de calculs intégraux

  • Tuteur : Dionysios Grapsas
  • Résumé : L’utilisation de l’ordinateur comme une supercalculette est le moyen que nous disposons aujourd’hui pour calculer les solutions des problèmes “compliqués” de la mécanique, dont les solutions exactes ne sont pas connues (aéronautique, météorologie, éléctromagnétisme, …). Le calcul intégral permet de s’initier à cet approche, de se rendre compte de sa puissance (résolution rapide de problèmes difficiles / impossible à calculer manuellement), de ses limitations (les solutions ne sont jamais “exactes”), ainsi que l’importance de tous les choix qu’on fait pendant la construction et l’implémentation des méthodes numériques aux résultats finaux.
  • Objectifs :
    1. Implémenter des méthodes de calcul intégral déterministes (méthodes de quadrature) et probabilistes (Monte-Carlo)
    2. Comparer leurs résultats et leur efficacité sur plusieurs cas de figure
    3. Calcul intégral en plusieurs dimensions

Instant Insanity

  • Tuteur : Sébastien Tavenas
  • Résumé : Instant Insanity est un puzzle qui a été vendu sous différents noms. Le but est, étant donnés 4 cubes dont les faces sont coloriées (par exemple, en rouge, jaune, vert et bleu), on veut empiler les 4 cubes de telle sorte à ce que chaque "côté" de la colonne contienne les 4 couleurs. Par exemple, vous pouvez essayer avec ces 4 patrons de cubes :

Instant insanity Cube.png

Ce puzzle peut facilement être généralisé à n cubes et n couleurs. On cherche à écrire un algorithme qui, si c'est possible trouve un bon empilement. Toutefois, ce jeu a été un des premiers puzzles à avoir été montré NP-complet (par Robertson et Munro en 1978).

  • Objectifs :
    1. Comprendre ce qu'est un problème NP-complet
    2. Comprendre pourquoi ce puzzle est NP-complet
    3. Coder une heuristique ou utiliser un SAT-solveur
    4. Chercher si d'autres puzzles sont aussi NP-complets
  • Références pour commencer :
    1. [Page wikipedia du jeu]
    2. [Page wikipedia sur la NP-complétude]

Automates cellulaires

  • Tuteur : Gérald Cavallini
  • Résumé : La théorie des automates cellulaires est relativement simple, une série de règles permet de modifier l’état spatial et temporel d’une cellule en fonction de son voisinage. Cette théorie se décline en de nombreux cas d’étude, automate circulaire cyclique, 2D, 3D … En théorie, les automates cellulaires permettent aussi de réaliser toutes sortes de calculs.Le jeu de la vie imaginé par John Horton Conway en 1970 est un automate cellulaire.
  • Objectifs : Le but de ce sujet est d’expliquer si possible au moyen de programmes simples :
    1. la classification des automates cellulaires
    2. les automates cellulaires remarquables
    3. l’équivalence avec les machines de Turing
    4. la notion d’universalité
    5. les caractéristiques du jeu de la vie
  • Liens pour démarrer

Automate 1.png

Simuca.gif

Simulation de fluides

  • Tuteur: Colin Weill-Duflos
  • Résumé : Lorsque l'on veut afficher de l'eau sur un écran, on veut généralement représenter son mouvement sans qu'un animateur n'ait à préciser à la main le déplacement de chaque polygone représentant la surface de l'eau. Pour cela, on emploie des modélisation physiques du fluide pour simuler son comportement, puis on effectue un rendu du fluide ainsi modélisé. Les modèles physiques employés pour simuler un fluide sont complexes (voir les équations de Navier-Stokes) et font apparaître des phénomènes comme des vortex, des vagues... Il faut donc des méthodes de simulation fines capturant la complexité de ces phénomènes.
  • Objectifs :
    1. implémenter un simulateur physique de fluide suivant la méthode "SPH" pour des scènes simples
    2. implémenter une méthode pour afficher le fluide ainsi simulé.
  • Références

Sph.png

Sujets proposés 2020-2021

  • Transformée en distance discrète, diagramme de Voronoi discret, axe médian et squelette
  • Clustering par K-means, segmentation d'image
  • Base de données orientées Graphe, similarité et modèles prédictifs
  • Algorithmes d'approximation numérique de la mesure de Mahler
  • Ensemble de Mandelbrot et autres fractales
  • Complexité pratique contre complexité théorique
  • Etude du protocole gRPC
  • Valeurs de Sprague-Grundy pour le jeu de Wythoff
  • Modèle mathématique SIR pour décrire la propagation d'une épidémie
  • Modélisation de réseaux sociaux, base de données orientées graphe
  • Modélisation de la ruine du joueur

Transformée en distance discrète, diagramme de Voronoi discret, axe médian et squelette

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La transformée en distance permet de situer l'éloignement de tout point du plan ou de l'espace à un ensemble donné. C'est un outil de base dans beaucoup d'algorithmes de traitement d'image ou de données 3D. Pour les images, on peut l'utiliser pour filtrer des objets, comparer deux objets, extraire son squelette, mettre en correspondance deux objets. Dans le cas de nuage de points 3D acquis par laser, on peut utiliser cet outil pour reconstruire une surface approchant ces points. Dans ce travail, on se concentrera sur la transformée en distance dans le cas des images 2D (appelé cas discret). Les objets traités seront des ensembles de pixels, par exemple des caractères écrits si on fait de l'analyse de texte scanné. On s'intéressera aux algorithmes spécifiques à ce contexte, ainsi qu'à quelques applications.
  • Objectifs:
    1. Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
    2. Identifier le lien avec l'axe médian et les squelettes
    3. Coder un algorithme de calcul de la transformée en distance et du diagramme de Voronoi dans le cas des images 2D, ainsi que l'extraction de l'axe médian discret.
    4. Si le temps le permet, on s'intéressera aussi à l'extraction d'un squelette "topologique", qui contient l'axe médian discret.
Pixels en entrée Transformée en distance Diagramme de Voronoi Squelette topologique
Dt-input.png Dt-output.png Dt-voronoi.png Skel.png

Base de données orientées Graphe, similarité et modèles prédictifs

  • Tuteur : Gérald Cavallini
  • Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
  • Objectifs :
    1. Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
    2. Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
    3. Proposer un une validation du modèle prédictif.
  • Liens pour commencer

Neo4j.jpg

Clustering par K-means, segmentation d'image

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le partitionnement de données (ou data clustering) est l'opération visant à découper un ensemble de données en des groupes disjoints, tel que chaque groupe est le plus homogène possible. C'est un procédé à la base de nombreux algorithmes d'analyse de données, et reste encore une tâche difficile, avec de nombreuses définitions possibles. Nous nous intéresserons ici à une méthode standard, relativement simple à mettre en oeuvre, et qui permet de découper un ensemble de données en K groupes, où K est donné. on l'appelle K-means ou algorithme des K-moyennes. Elle opère sur des données où nous pouvons calculer une distance entre toute paire de données. On appliquera cet algorithme aux images couleurs. On verra qu'on peut l'utiliser pour réduire considérablement le nombre de couleurs d'une image tout en la préservant au maximum. On verra aussi, en modifiant la distance, comment utiliser cet algorithme pour faire de la segmentation d'image, c'est-à-dire décomposer une image en ses régions homogènes afin d'identifier les objets d'intérêt.
  • Objectifs:
    1. Comprendre l'algorithme des k-moyennes et comment l'appliquer à l'analyse d'images couleurs
    2. Implémenter cet algorithme avec Python/numpy
    3. Tester les distances entre couleurs, et les distances couleur+géométrie
    4. Montrer son intérêt sur différentes images, ainsi que ses limites
  • Liens pour démarrer
Image en entrée Clustering K=256 Clustering K=10 Spatial clustering K=10, c=0.5
Kowloon-small.png Kowloon-k256.png Kowloon-k10.png Kowloon-k10-s0 5.png

Algorithmes d'approximation numérique de la mesure de Mahler

  • Tuteur : Denys DUTYKH (CR CNRS, Denys.Dutykh@univ-smb.fr)
  • Résumé : Le LAboratoire de MAthématiques (LAMA UMR 5127) de l'USMB se distingue par la grande diversité des recherches menées au sein de cette unité ainsi que par des synergies, parfois surprenantes et inattendues, qui existent entre ses membres. Le présent projet s'inscrit parfaitement dans cette optique. Notamment, nous avons une chance au LAMA d'avoir parmi nous un expert international sur la conjecture de Lehmer et qui se trouve involontairement à l'origine du sujet décrit ci-dessous. Plus précisément, la conjecture de Lehmer porte sur certaines propriétés de l'ensemble de toutes les mesures de Mahler des polynômes univariés à coefficients entiers. La résolution de cette conjecture ne figure pas parmi les objectifs premiers de ce stage même si une telle finalité serait très bien vue par l'encadrant. Dans le premier temps nous allons plutôt étudier et comparer les différentes approches numériques qui existent pour le calcul de la mesure de Mahler d'un polynôme (éventuellement de très grand degré) donné. Si le temps le permet, nous pouvons nous intéresser aussi au calcul de la mesure de Mahler pour des polynômes multivariés bien que cette tâche ait un niveau de difficulté bien supérieur. En cas de difficultés imprévues, nous pourrons ponctuellement consulter l'expert local sur la question qui est toujours très généreux pour partager ses connaissances pointues sur le sujet. Enfin, un certain goût mathématique et une passion (même si elle est dormante) pour la théorie des nombres sont absolument nécessaires pour savourer pleinement le travail sur la mesure de Mahler.
  • Liens pour démarrer
    1. https://mathworld.wolfram.com/LehmersMahlerMeasureProblem.html
    2. https://en.wikipedia.org/wiki/Mahler_measure

Mahler-1.gif Mahler-2.gif


Ensemble de Mandelbrot et autres fractales

  • Tuteur : Pierre Hyvernat
  • Résumé : l'ensemble de Mandelbrot est un sous-ensemble des points du plan avec une structure extrêmement complexe. Comme de nombreuses fractales, cet ensemble donne naissance à des visuels surprenants tels que
    Mandelbrot.jpg
    La couleur d'un point c du plan dépend uniquement de la vitesse à laquelle l'itération de la fonction z -> z*z + c diverge et il est donc facile d'écrire un programme qui dessine (une approximation de) l'ensemble de Mandelbrot. Écrire un programme efficace est un peu plus complexe, et ce encore plus dans des langages comme Python !
  • Objectifs :
    1. écrire une version "naïve" du programme en Python pur,
    2. écrire une seconde version du programme en utilisant des bibliothèques de calcul comme numpy afin de comparer les vitesse d'execution,
    3. appliquer certaines optimisation et étudier lors impact sur le temps de calcul,
    4. à des niveaux de zoom extremes, la précision des nombres flottants n'est plus suffisante. Il peut être intéressant de tester un calcul beaucoup plus lent, mais avec une précision supérieure,
    5. étendre ces programmes pour dessiner les ensembles de julia correspondant à un point du plan.


Complexité pratique contre complexité théorique

  • Tuteur : Pierre Hyvernat
  • Résumé : la complexité théorique d'un algorithme est une estimation du nombre d'opérations élémentaires nécessaires pour que l'algorithme termine, en fonction de ses arguments. On ne peut pas donner de réponse exacte, et cette complexité prend typiquement la forme : "le nombre d'opérations élémentaires pour trouver le minimum d'un tableau (avec l'algorithme standard) est proportionnel à la taille du tableau". La complexité pratique d'un programme est simplement le temps qu'il met sur certains arguments. Par exemple "mon programme du tri bulle prend 4 secondes sur un tableau de taille 10000".
    Normalement, une meilleur complexité théorique se traduit par une meilleur complexité pratique, mais ce n'est pas toujours le cas. Nous allons implémenter et comparer plusieurs programmes et étudier la différence entre ces deux notions de complexité. Python sera le langage initial, mais suivant l'étudiant, d'autres langages plus bas niveau pourront être utilisés.
  • Objectif :
    1. comprendre la définition de complexité théorique
    2. implémenter des algorithmes pour le même problème et comparer les complexités pratiques et théoriques, comme par exemple
      • multiplication naive / méthode de Karatsuba / méthode de Toom-Cook
      • recherche de la mediane naive / méthode quickselect / méthode linéaire
      • tri par insertion / tri rapide / tri fusion
    3. expliquer d'où peuvent venir les différences constatées, et chercher comment améliorer la complexité "pratique" des programmes correspondants.

Etude du protocole gRPC

  • Tuteur : David Télisson
  • Résumé : « gRPC est un framework RPC (Remote procedure call) open source initialement développé par Google. Il utilise le protocole HTTP/2 pour le transport, Protocol Buffers comme langage de description d'interface (IDL : interface description language), et offre des fonctionnalités telles que l'authentification, la transmission bidirectionnelle et le contrôle de flux, par le blocage ou non des communications par annulation ou délais d'attente. Il permet la construction de liaisons client/serveur multiplateforme pour de nombreux langages » [source wikipedia]
  • Objectifs du projet :
    1. Etudier et comprendre ce protocole
    2. Comparer avec les protocoles RPC historiques : XML-RPC ou JSON-RPC
    3. Implémentez un PoC (preuve de concept) simple qui montre le fonctionnement du protocole entre deux applications développées dans des langages différents (Python et JavaScript).
  • Liens pour démarrer :

Valeurs de Sprague-Grundy pour le jeu de Wythoff

  • Tuteur : Sébastien Tavenas
  • Résumé : Le jeu de Wythoff est un jeu à deux joueurs nécessitant deux piles de pièces. Chacun à leur tour, les joueurs retirent des pièces d’une des deux piles ou des deux piles en même temps. Il y a toutefois une contrainte : si le joueur choisit de retirer des pièces des deux piles en même temps, alors il doit retirer le même nombre de pièces dans chacune des deux piles. Le joueur ramassant la dernière pièce est déclaré vainqueur. Une description équivalente du jeu est la suivante. Une dame d’échecs est placée quelque part sur une un grand échiquier. À tour de roles, chaque joueur déplace la reine vers l’angle bas-gauche du plateau : soit vers le bas, soit en diagonal (bas-gauche), soit vers la gauche du nombre de cases désiré. Le joueur mettant la dame dans la case à l’angle de l’échiquier est déclaré vainqueur. Ce jeu est une variation du célèbre jeu de Nim. Comme ce dernier on connait aujourd’hui l’ensemble des positions perdantes et gagnantes. Toutefois ce jeu devient vite plus compliqué que le jeu de Nim  : la stratégie optimale est basée sur les suites de Beatty et l'on ne connait pas d'algorithme pour calculer les valeurs de Sprague-Grundy pour ce jeu en temps polynomial.
  • Objectifs du projet :
    1. Etudier et comprendre les stratégies pour le jeu de Wythoff
    2. Implémenter un algorithme jouant parfaitement
    3. Implémenter un algorithme calculant les valeurs de Sprague-Grundy des positions (sans trop se soucier de son efficacité)
    4. Si le temps le permet, on pourra s'intéresser à la périodicité additive des valeurs de Sprague-Grundy dans les position de ce jeu.
  • Quelques liens :


Modèle mathématique SIR pour décrire la propagation d'une épidémie

  • Tuteur : Jimmy Garnier
  • Résumé : Pour les États et pour les organisations internationales, connaître l’évolution d’une épidémie humaine (grippe H1N1, virus Ebola, coronavirus), animale ou végétale est primordial. Un des outils de gestion est la modélisation mathématiques. Il convient dès à présent de préciser que les modèles mathématiques sont des modèles simplifiés, ayant des limites dont il faut être conscient. Dans ce travail, on s'intéressera au modèle SIR qui est un exemple de modèle à compartiments, c’est à dire que l’on divise la population en plusieurs catégories. Pour une population donnée, on étudie la taille de trois sous-populations au cours du temps t :
    • S(t) représente les personnes saines (susceptible en anglais) au temps t,
    • I(t) les personnes infectées (infected), et
    • R(t) les personnes guéries (recovered);
    • N=S(t)+I(t)+R(t) représente alors la population constante totale au cours du temps.
  • Objectif:
    1. Écrire mathématiquement ce modèle d'équations différentielles ordinaires (ODE). Comprendre et intérpréter chaque terme et paramètre du modèles.
    2. Analyser mathématiquement ce modèle (existence et unicité des solutions), taux de reproduction et théorème du seuil.
    3. Implémenter ce modèle en python à l'aide des librairies mathématiques (numpy, odeint).
    4. Représenter graphiquement les résultats du modèle.
  • Liens pour démarrer
Sir-1.png Sir-2.png Sir-3.jpg

Modélisation de réseaux sociaux, base de données orientées graphe

  • Tuteur : Gérald Cavallini
  • Résumé : Les réseaux sociaux sont devenus des cas d'études extrêmement importants dans de nombreux domaines, communication, médecine ... Ce sont des graphes qui présentent des caractéristiques particulières : coéfficient d'agglomération (clustering), longeur moyen des chemins. Des algorithmes existent pour générer ces graphes et obtenir des modéles proches des réseaux sociaux réels. Un type particulier de réseau social et le réseau « petit

monde » ou chaque individu est relié à un autre par un nombre maximum de relations faible.

Smallworld.png Smallworld-2.jpg

Modélisation de la ruine du joueur

  • Tuteur : Céline Labart
  • Résumé : nous nous intéressons à l'étude des gains d'un joueur à la roulette. Celui-ci arrive au casino avec une certaine somme en poche et joue à la roulette tant qu'il n'est pas ruiné ni que ses gains atteignent une somme qu'il s'est fixée. A chaque fois qu'il joue, le joueur gagne ou perd un euro avec une certaine probabilité.
  • Objectifs :
    1. Simulation d'une partie
    2. Calcul de la probabilité de gagner
    3. Calcul du temps moyen de jeu
    4. Estimation numérique de ces deux quantités à l'aide de la loi des grands nombres
  • Lien pour commencer :
    1. Modélisation aléatoire

Sujets proposés 2019-2020

  • Compression et transformée de Burrow-Wheeler
  • Backtracking
  • Transfert de couleur (version 2)
  • Génération fractale de terrains
  • Architectures Orientées Micro-Services
  • Apprentissage automatique
  • Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
  • Base de données orientées Graphe, similarité et modèles prédictifs

Compression et transformée de Burrow-Wheeler (lien : Transformée Burrows Wheeler)

  • Tuteur : Pierre Hyvernat
  • Résumé : La transformée de Burrow-Wheeler est l'étape clé de l'algorithme de compression bzip2. C'est une transformation de texte (suite d'octet) qui ne modifie pas la taille, mais ajoute suffisamment de motifs redondants pour améliorer un autre algorithme de compression (algorithme de Huffman dans le cas de bzip2)
  • Objectif : L'objectif est de comprendre le fonctionnement de cette transformation (et de son inverse) et d'implémenter une version naïve de l'algorithme de compression / décompression et de tester sur quelques exemples. Les améliorations de l'algorithme seront ensuite abordées.
  • Liens : Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation [PDF]

Backtracking (lien : VISI201 Backtracking (PICHENOT Simon))

  • Tuteur : Pierre Hyvernat
  • Résumé et objectif : La notion de "backtracking" est fondamentale en algorithmique : il s'agit essentiellement de tester des solutions partielles à un problème, en revenant en arrière dès qu'une incohérence est découverte. Le point de départ sera le fascicule 4.5b de D. Knuth "Introduction to backtracking" et permettra de se familiariser avec les concepts, la terminology et des exemples, qu'il faudra implémenter. Une suite possible sera la notion de réduction de problèmes et l'algorithme-X qui permet de "factoriser" de nombreux problèmes de backtracking en un seul algorithme.
  • Liens : D. Knuth, "the art of computer programming introduction to backtracking" [PS]

Transfert de couleur (version 2)

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous étudierons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.
Transfert de couleur
Input Output
Horseshoe.jpg Horseshoe-fjord-n40.jpg
Fjord.jpg Fjord-horseshoe-n40.jpg
  • Objectifs:
    1. Comprendre la version 1 fait par [Lucas Chardonnet], comprendre les qualités et limites de l'approche (sur quelle type d'image ça marche assez bien par exemple)
    2. Adapter l'algorithme pour qu'il puisse traiter des images de tailles différentes
    3. Réécrire le code en utilisant la bibliothèque python NUMPY pour accélérer les calculs
    4. Changer les espaces de couleurs utilisés: RGB ne convient pas très bien pour mesurer le coût du transport. Transformer le code pour qu'il puisse utiliser plutôt l'espace [L*a*b*] mieux adapté pour calculer des distances entre couleurs.
  • Liens:

Génération fractale de terrains

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La génération procédurale de terrain est très utilisée en modélisation 3D et dans les jeux vidéos, afin de générer rapidement des paysages pseudo-réalistes que l'on étoffera ensuite de façon plus manuelle. On propose d'étudier et d'implémenter un algorithme classique, dit "algorithme Diamant-Carré". Cet algorithme récursif permet de générer une carte d'élévation. Selon les paramètres données, le résultat peut ressembler aux cartes d'altitude de haute montagne ou des collines plus douces.
Génération fractale de terrain par algorithme diamand carré
Elévations générées Colorisation Visualisation 3D
Diamond-Square texture.png Diamond-Square heightmap.png Terragen.jpg
  • Objectifs:
    1. Comprendre et implémenter l'algorithme Diamant-Carré
    2. Comprendre comment paramétrer cet algorithme pour qu'il génère des montagnes bien abrupte à haute altitude ou des collines à basse altitude.
    3. Fabriquer une image de couleur/texture qui va associer des couleurs aux altitudes générées (e.g. forcer du bleu sous l'altitude zero, ajouter de la neige, des lacs, de la forêt)
    4. Générer un fichier 3D (par exemple OBJ) à partir de ces deux images (l'image des hauteurs et l'image des couleurs) pour pouvoir faire de beau rendu 3D (sous blender par exemple)
  • Liens:

Architectures Orientées Micro-Services

  • Tuteur : David Télisson
  • Résumé : Les architectures des applications logicielles distribuées de grandes envergures ont évolué à partir du début des années 2000, d’une application molithique déployée sur un serveur d’application (JEE, TomCat, etc.) vers des solutions fortement répartis déployées sous formes de services. On parle alors d’architectures orientées services qui se traduisent par le développement et le déploiement de services logiciels interrogeables via des protocoles dédiés (par exemple SOAP) et des API (REST). Cette tendance, corrélée aux nouvelles méthodes de management des projets informatiques (méthodes agiles, intégration continue, DevOps1), s’est accentué ces dernières années et a fait émergé un « nouveau » paradigme : le micro-service. Plusieurs aspects caractérisent un micro-service :
    • fonctionnalité unique
    • flexibilité technologie
    • équipe de développement réduite
    • déploiement ciblé
    • support de la montée en charge (scalabilité)
    • tests facilités et intégrés au processus de développement (TDD2)
  • Objectifs du projet :
    1. Etudier et comprendre les concepts liés aux micro-services (API, conteneurisation, framework, etc.)
    2. Implémentez un PoC (proof of concept) qui démontre qu’une application peut se construire dynamiquement par agrégation de micro-services développés avec des langages différents (Python, JS et Java), déployés sur des plateformes différentes (Django, Node et Glassfish) et disponibles sous formes de conteneurs dans le cloud (Azure)
    3. Livrable attendu : un tutoriel « à la OpenClassRooms »
  • Liens pour démarrer :


Apprentissage automatique


Algorithmes probabilistes/déterministes pour tester la primalité d'un entier

  • Tuteur : Sébastien Tavenas
  • Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
  • Objectifs :
    1. Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
    2. Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
    3. Programmer quelques uns des ces tests et les comparer
    4. Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés


Base de données orientées Graphe, similarité et modèles prédictifs

  • Tuteur : Gérald Cavallini
  • Résumé : Avec l’avènement du BigDatas, dans bien des cas le choix d’un produit, d’un média, d’un voyage ... ne peut plus être direct. Il s’appuie sur des systèmes de recommandations. L’importance financière de ces systèmes est énorme Amazon estime à 30% les ventes supplémentaires dues à son système de recommandation. Ces systèmes s’appuient sur des calculs statistiques et des algorithmes de recherche de similarité. Ces algorithmes expriment la distance entre des objets, ce qui permet par exemple d’identifier des utilisateurs(consommateurs, électeur ...) similaire et de recommander leurs choix.
  • Objectifs :
    1. Mettre en œuvre différents algorithmes de recherche de similarité ( similarité de Jaquard, similarité cosinus...) dans une base de donnée orientées Graphe Neo4j.
    2. Proposer un système de recommandation de film à partir de la base MovieLens (Notation de films par des utilisateurs).
    3. Proposer un une validation du modèle prédictif.
  • Liens pour commencer

Neo4j.jpg

Sujets proposés 2018-2019

  • Transport optimal par coupe 1D et transfert de couleurs entre images
  • Génération et résolution de labyrinthes II
  • REST + Pub/Sub : protocole hybride pour l’IoT
  • La suite de Conway et la classification périodique des "éléments"
  • Initiation à la démonstration sur ordinateur et certification de logiciel
  • Algorithmes probabilistes/déterministes pour tester la primalité d'un entier
  • Dilemme du prisonnier

Transport optimal par coupe 1D et transfert de couleurs entre images

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le transfert de couleurs de l'image Y vers l'image X consiste à repeindre "au mieux" l'image X avec la palette de couleurs de l'image Y. L'image repeinte X' a alors les mêmes couleurs que l'image Y (mais les pixels ne sont pas répartis pareils). Voir l'exemple de transfert ci-dessous. Il existe plusieurs techniques de transfert de couleurs, mais nous étudierons une technique basée sur le transport optimal. Comme c'est un problème assez difficile dans le cas général, nous verrons une variante dite par coupe 1D, qui simplifiera considérablement le problème de transport.

Ex-transfert-couleur-OT.png

  • Objectifs:
    1. comprendre ce qu'est une image niveaux couleur, et ce qu'on appelle le transfert de couleurs.
    2. comprendre le principe du transport optimal (discret).
    3. comprendre et décrire le principe du transport optimal par coupe 1D, et comment se fait le calcul du meilleur transport dans ce cas.
    4. Coder un programme de transfert de couleur, qui prend deux images couleurs et réalise le transfert de couleurs.
    5. On pourra ensuite réfléchir à quelques améliorations simples (espace couleur YUV, grouper les pixels).
  • Liens pour démarrer
    • Le vrai "Transport Optimal" est vite très mathématique (ce sont des mesures qui sont transportées), mais on peut l'aborder beaucoup plus simplement dans le cas discret (un nombre fini de valeurs) comme une simple assignation entre deux ensembles.
    • [Transfert de couleur Wikipedia]
    • [Habilitation de N. Papadakis] (regardez les images plutôt).

Génération et résolution de labyrinthes II

  • Tuteur: François Boussion
  • Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
  • Objectifs:
    1. Comprendre comment représenter un labyrinthe avec une structure de données simple
    2. Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
    3. Comprendre l'algorithme d'arbre couvrant minimum
    4. Comprendre le principe du parcours en profondeur et de la récursivité
  • Pour aller plus loin
    1. coder la génération d'un labyrinthe et sa visualisation
    2. introduire des poids pour varier le labyrinthe
    3. comment faire un labyrinthe sur grille hexagonale avec des tableaux.
  • Liens pour démarrer

REST + Pub/Sub : protocole hybride pour l’IoT

  • Tuteur: David Télisson
  • Résumé: L’avènement de l’Internet des Objets (IoT) depuis une dizaine d’années a fait apparaitre des problématiques propres aux protocoles de communications liées à ces objets. En effet, l’échange de données dans ce contexte nécessite de tenir compte (au moins) des paramètres suivant :
    1. Autonomie énergétique souvent limitée
    2. Faible puissance des processeurs et taille réduite de la mémoire
    3. Disponibilité « aléatoire » de l’accès aux réseaux de communication

De nombreux protocoles cohabitent et la littérature du domaine foisonne d’exemples autour des réseaux dédiées (LORA, Sigfox, etc.) et des protocoles applicatifs (OPC-UA, MQTT, CoaP, XMPP) mais force est de constater que dans la réalité, ces solutions ne répondent pas toujours aux besoins des concepteurs qui leurs préfèrent encore le protocole HTTP. Celui-ci offre l’avantage d’implémenter un protocole applicatif (REST) en même temps qu’un protocole de transport de haut niveau (TCP/IP) permettant de passer les pare-feu. Cependant, la version actuel d’HTTP ne répond pas vraiment aux critères énoncés précédemment. Depuis quelques années émerge donc l’idée d’enrichir HTTP pour créer un protocole hybride qui mêlerait les avantages de REST avec ceux proposés par les mécanismes de type Publish/Subscribe (MQTT, AMQP, JMS, etc.). En attendant cette éventuelle évolution, peut-on envisager de mettre en place un mécanisme de type Pub/Sub avec le protocole Websocket au-dessus d’HTTP ?

  • Objectifs:
    1. Etudier et faire une synthèse des deux approches : REST et Pub/Sub
    2. Implémentez un PoC (proof of concept) d’une solution hybride qui met en œuvre un mécanisme de Pub/Sub sur Websocket. .
    3. Présenter un protocole de test pour valider ou invalider cette solution


La suite de Conway et la classification périodique des "éléments"

  • Tuteur : Pierre Hyvernat
  • La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
    • "1" : un "1" -> 11
    • "11" : deux "1" -> 21
    • "21" : un "2", un "1" -> 1211
    • "1211" : un "1", un "2", deux "1" -> 111221
    • etc.

Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".

  • Objectifs :
    1. comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
    2. programmer la suite de Conway pour retrouver la classification des "atomes"
    3. écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
    4. écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

Initiation à la démonstration sur ordinateur et certification de logiciel

  • Tuteur: Tom Hirschowitz
  • Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
  • Objectifs:
    1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
    2. programmer certaines démonstrations basiques en Coq,
    3. suivre le début du cours [Software Foundations],
  • Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
  • Liens pour démarrer

Algorithmes probabilistes/déterministes pour tester la primalité d'un entier

  • Tuteur : Sébastien Tavenas
  • Pouvoir tester si un entier est un nombre premier semble être une brique de base si l'on souhaite faire de l'arithmétique sur un ordinateur. Le crible d'Érathostène enseigné dans les petites classes se montre beaucoup trop lent en pratique. L'algorithme probabiliste utilisé le plus rapide est le test de Fermat. Or, si on regarde les algorithmes des librairies "génériques", on peut s'apercevoir que la fonction 'mpz_probab_prime_p' de la librairie 'gmp' sur c++ utilise un test probabiliste de Miller-Rabin, la fonction 'isPrime' de la classe 'Prime' dans java utilise aussi un test de Miller-Rabin mais qui est déterminisé, alors que la fonction 'isprime' de la librairie 'sympy' dans python effectue un test de Miller-Rabin si l'entier est plus petit que 2^64 et un test BPSW fort si l'entier est plus grand. Ainsi, une fonction déjà implémentée de test de primalité peut se tromper ou non, être instantanée ou moins. Que dire alors de l'algorithme polynomial déterministe et toujours correct proposé par AKS?
  • Objectifs :
    1. Comprendre quelques tests de primalité et comment l'aléatoire est utilisé dans ces algorithmes
    2. Comprendre la notion de nombre pseudopremier qui explique, entre autre, quand il vaut mieux utiliser le test de Fermat ou celui de Miller-Rabin
    3. Programmer quelques uns des ces tests et les comparer
    4. Essayer de dérandomiser ces tests à l'aide de hitting-sets précalculés

Dilemme du prisonnier

  • Tuteur: Gerald Cavallini
  • Résumé: Le dilemme du prisonnier caractérise en théorie des jeux une situation où deux joueurs auraient

intérêt à coopérer, mais où, en l’absence de communication entre les deux joueurs, chacun choisira de trahir l'autre si le jeu n'est joué qu'une fois.

On peut informatiquement modéliser ce dilemme à l’aide de matrices de gains et conserver la mémoire des choix de l’adversaire. Ce modèle appliqué à un grand nombre d’individus peut être utilisé pour comprendre l’émergence de stratégies stables dans l’économie, l’écologie, l’évolution des espèces ...

On peut visualiser spatialement les interactions entre individus en les représentants par des pixels et en leurs associant une couleur en fonction de leurs stratégies.

Dilemme.png


  • Objectifs
    1. Comprendre le dilemme du prisonnier
    2. Comprendre la notion de stratégie
    3. Penser un modèle spatiale pour « opposer » des individus qui appliquent des stratégies différentes
    4. Développer une interface pour visualiser dans le temps l’évolution d’une population d’individus adoptants des stratégies différentes.

Sujets proposés 2017-2018

  • Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
  • Initiation à la démonstration sur ordinateur et certification de logiciel
  • Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
  • Transformées en distance, diagramme de Voronoi et applications en geometry processing
  • Pavages de Penrose


Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
  • Objectifs:
    1. comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
    2. décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
    3. décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
    4. Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
  • Liens pour démarrer
    • [Watershed Wikipedia]
    • Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [PDF]

Initiation à la démonstration sur ordinateur et certification de logiciel

  • Tuteur: Tom Hirschowitz
  • Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
  • Objectifs:
    1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
    2. programmer certaines démonstrations basiques en Coq,
    3. suivre le début du cours [Software Foundations],
  • Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
  • Liens pour démarrer

Fouille de données textuelles à partir des "Exercices de style" de R. Queneau


Transformées en distance, diagramme de Voronoi et applications en geometry processing

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
  • Objectifs:
    1. Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
    2. Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
    3. Identifier le lien avec l'axe médian et les squelettes
    4. Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
    5. Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
    6. Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

Pavages de Penrose

  • Tuteur : Pierre Hyvernat
  • Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

P2.png

  • Objectifs
    1. comprendre les notion de pavage périodique, non périodique et apériodique,
    2. comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
    3. comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
    4. écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
    5. utiliser ces méthodes pour générer d'autres types de pavages apériodique.


Algorithmes d'analyse syntaxique

  • Tuteur : Pierre Hyvernat
  • Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données textuelles et structurées. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle d'analyseur syntaxique ou de parseur. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.
  • Objectifs :
    1. étudier la formalisation du problème à travers la notion de langage et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
    2. comprendre le lien entre les langages et les automates (automates finis / automates à pile)
    3. implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
    4. comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (LL*(k), LR, etc.)
    5. à partir de là, de nombreuses pistes sont ouvertes :
      • essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
      • comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
      • améliorer l'efficacité des parseurs produits
      • ajouter des fonctionnalités,
      • ...

Sujets proposés 2016-2017

Algorithme de rendu de scène 3D par Z-buffer

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
  • Objectifs:
    1. décrire le principe de la projection 3D vers 2D
    2. décrire la rastérisation des triangles sur une image en pixel
    3. expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
    4. expliquer comment les couleurs sont calculées par pixel
    5. indiquer les qualités et limitations de l'algorithme
  • Pour aller plus loin
    1. mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
    2. expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
  • Liens pour démarrer

Traitement d'image

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
  • Objectifs:
    1. identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
    2. identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
    3. comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
    4. choisir un ou deux algorithmes de traitement et les expliquer en détails
  • Pour aller plus loin
    1. Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)


Nim et la théorie des jeux impartiaux

  • Tuteur: Pierre Hyvernat
  • Étudiant : Luca Chapelle
  • Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
  • Objectifs:
    1. comprendre la théorie du jeu de Nim (et la programmer)
    2. comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
    3. regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
    4. programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

La suite de Conway et la classification périodique des "éléments"

  • Tuteur : Pierre Hyvernat
  • La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
    • "1" : un "1" -> 11
    • "11" : deux "1" -> 21
    • "21" : un "2", un "1" -> 1211
    • "1211" : un "1", un "2", deux "1" -> 111221
    • etc.

Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".

  • Objectifs :
    1. comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
    2. programmer la suite de Conway pour retrouver la classification des "atomes"
    3. écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
    4. écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

Initiation à la démonstration sur ordinateur et certification de logiciel

  • Tuteur: Tom Hirschowitz
  • Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
  • Objectifs:
    1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
    2. programmer certaines démonstrations basiques en Coq,
    3. suivre le début du cours [Software Foundations],
  • Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
  • Liens pour démarrer

Calculabilité et modèles de calcul

  • Tuteur: Rodolphe Lepigre
  • Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
  • Objectifs:
    1. comprendre la notion de fonction calculable,
    2. comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
    3. regarder et comparer quelque modèles de calcul,
    4. programmer un modèle de calcul et comprendre les limitations pratiques.

Génération et résolution de labyrinthes

  • Tuteur: Jacques-Olivier Lachaud Xavier Provençal
  • Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
  • Objectifs:
    1. Comprendre comment représenter avec une structure de données un labyrinthe
    2. Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
    3. Comprendre l'algorithme d'arbre couvrant minimum
    4. Comprendre le principe du parcours en profondeur et de la récursivité
  • Pour aller plus loin
    1. coder la génération d'un labyrinthe et sa visualisation
  • Liens pour démarrer

Pavages par polyomino

  • Tuteur: Xavier Provençal
  • Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?

On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?

  • Objectifs :
    1. Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
    2. Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
    3. Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
  • Pour aller plus loin :
    1. Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
    2. Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
  • Liens pour démarrer
Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=VISI201_CMI_:_visite_de_laboratoire&oldid=15645 »