Idées de projets pour experts

Voici des idées de projets pour les experts en programmation. Langages autorisées : C, C++ ou Rust.

Point dans polygone - version ++

  1. Corriger la version du cours pour que les cas dégénérées fonctionnent
  2. L'algorithme du cours est en THETA(n) où n est le nombre de points dans le polygone. Ce n'est pas acceptable pour des grands polygones. Développer une structure de données (que l'on peut appeler polygon) arborescentes que l'on précalcule depuis le polygone afin que les requêtes d'appartenance d'un point dans ce polygone soit plus efficace. Développer une API claire comme:
    • polygon createPolygon(tPoint[] A, int n) qui crée cette structure de données
    • bool isPointInPolygon(tPoint point, polygon P) qui renvoie vrai si le point est dans le polygone P
  3. Implémenter un bidding Python/C pour appeler votre fonction C en Python

Interpréteur Scheme

Scheme est un langage fonctionnelle à typage fort dynamique. L'avantage est que les expressions sont faciles à analyser syntaxiquement (à parser) car ce sont des expressions préfixes parenthésées.

  1. Ecrire un interpréteur pour des expressions simples (+ 1 2) etc.
  2. Etendre aux définitions de fonction etc.
  3. Implémenter une gestion d'exception, le call/cc
  4. Implémenter un bidding Python/C pour appeler votre fonction C d'évaluation d'expression Scheme en Python

Multi-agent path finding

On considère un environnement qui est une grille où certaines cases contiennent des obstacles (immobiles). Un nombre n de robots occupent des positions initiales (des cases libres) et doivent se rendre à des positions finales (des cases libres aussi).

L'objectif est de construire un chemin pour chaque robot (qui se déplace horizontalement ou verticalement d'une case à chaque étape, ou reste sur place) qui l'amène de sa position initiale à sa position finale telle que :

  • les robots n'entrent pas en collision
  • la durée totale de la mission (le max des longueurs des chemins) soit minimale.
  1. Construire un programme qui permet de charger des environnements et des instances
  2. Développer un algorithme basé sur A*
  3. Lire le papier sur CBS [1] et l'implémenter
  4. Implémenter les améliorations de CBS
  5. Implémenter un bidding Python/C pour utiliser votre programme depuis Python

[1] Guni Sharon, Roni Stern, Ariel Felner, Nathan R. Sturtevant: Conflict-based search for optimal multi-agent pathfinding. Artif. Intell. 219: 40-66 (2015)

## Débugueur en raylib (projet très libre)

L'idée est de faire un programme qui discute avec gdb et affiche le contenu de la mémoire graphiquement.

Sokoban (projet très libre)

  1. Ecrire un solveur de Sokoban
  2. Ecrire un générateur de niveau de Sokoban.

Apprentissage et MINST (projet très libre)

Réimplémenter l'architecture utilisé par Yann LeCun pour apprendre à reconnaître des chiffres.