Projet

Vous allez être impliqué dans la réalisation d'un projet de programmation de votre choix par groupe de deux ou trois (deux préférables) personnes. Le choix du projet est libre mais la suite donne quelques idées de projets. Tous les langages sont autorisées (C, C++, Rust, Python, etc.).

Rapidly exploring random tree et le voyageur de piano

Interpréteur Scheme

Scheme est un dialecte de Lisp, un langage fonctionnel à typage fort et 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/Rust 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. Implémenter l'algorithme de [https://ojs.aaai.org/index.php/AAAI/article/view/8140]
  4. Implémenter les améliorations de CBS

Implémentation d'un algorithme pour CLIQUE COVER

Implémenter l'algorithme proposée dans https://arxiv.org/abs/2410.03609

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. J'ai commencé un prototype existant. Je pourrais vous montrer.

Apprentissage et MINST (projet très libre)

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

Quelques idées en vrac

  • programmer un jeu comme :
    • block blast
    • un jeu en mode terminal
    • un jeu quelconque
  • entiers arbitrairement grands
    • algorithme de Rho de Polard
    • test de Fermat
    • génération de nombres premiers grands
  • interpréteur LISP/langage de leur choix à écrire en C
  • Diagramme de Voronoi et Delaunay
  • Fractales (d'autres choses, à définir ?)
  • Raytracing?
  • Dancing links et backtracking
  • MCTS et résolution de jeux
  • Génération de niveau de Sokoban
  • Génération de labyrinthes (variantes, sur une sphère etc.)
  • quelque chose avec des quadtrees, quoi ?
  • Voyageur de commerce et recuit simulé
  • Apprentissage par renforcement
  • https://fr.wikipedia.org/wiki/Algorithme_de_Bron-Kerbosch
  • https://adriann.github.io/Ullman%20subgraph%20isomorphism.html
  • https://nbviewer.org/urls/staff.science.uva.nl/u.endriss/teaching/ijcai-2024/sat4sct.ipynb problème de vote du tutorial de Ulle Endriss
  • Composantes dans un graphe randomisé de Erdos avec faible proba, phénomène de seuil, avec algo de Kruskal (voir avec Stephan Thomassé)
  • Génération d'arbres uniforme avec n sommets
    • Codage de Pruffer ? Il y a une bijection entre code et arbre. On génère une suite aléatoire uniforme puis on décode
    • Kruskal. Puis le diamètre de l'arbre est de taille n^{2/3}
  • Génération d'arbres uniforme couvrant dans un arbre
    • Marche aléatoire dans le graphe original
    • on ajoute une arête dès qu'on est sur un nouveau sommet
    • On prend le graphe et chaque arête c'est une résistance de 1 ohm. La résistance entre deux aretes e c'est #nb arbre courant contenant e / #nb arbre couvrant.
  • Galey-Shapley
    • constater les différences de choix quand c'est les hommes ou les femmes qui proposent
    • lancer en moyenne
  • triangulation : on peut toujours passer d'une triangulation coloriée avec des + et - à une autre avec des flips
  • des algos pour trouver des vecteurs proches https://en.wikipedia.org/wiki/Vector_database
  • jeu de la vie, simulation de particules (rouge s'assemble avec rouge, rouge aime vert, vert aime pas rouge etc.)