Le principe de cette SAE est de réaliser plusieurs versions d'un algorithme du jeu de Grundy, de plus en plus optimisées. Le but de ce jeu est de diviser un tas en deux tas inégaux, ce jeu se joue sur un nombre choisi d'allumettes.
La deuxième partie de cette SAE consiste à comparer les différents algorithmes en calculant leur efficacité et leur performance.
1. AC12.01 | Analyser un problème avec méthode
Lors de cette SAE, nous avons proposé cinq algorithmes du jeu de Grundy, en allant du plus simple (le naïf) au plus optimisé. En implémentant un algorithme après l'autre, notre jeu devient de plus en plus optimal, le temps de jeu devient donc raisonnable.
La première version est naïve, elle explore toutes les possibilités de jeu et choisit celle qui est gagnante.
La deuxième version sauvegarde les situations perdantes afin de ne pas avoir à les explorer à chaque tour.
La troisième version sauvegarde les situations perdantes et gagnantes afin de limiter encore plus l'exploration puisque chaque situation déjà vue est maintenant conservée.
La quatrième version permet de faire une généralisation des états, avec le théorème 3.4 qui dit que l'ajout d'un tas ne change pas son état.
La cinquième version, la plus optimale, analyse directement le type des tas afin de détecter si la situation est perdante.
2. AC12.02 | Comparer des algorithme pour des problèmes classiques
Afin de comparer l'efficacité de chaque algorithme, on va compter le nombre d'appels récursifs de chaque algorithme ainsi que leur temps d'exécution en fonction du nombre d'allumettes avec lequel on joue. Le compteur, placé dans la méthode récursive principale, nous permet de compter le nombre d'opérations effectuées pour différentes tailles de configuration du jeu. En observant l'évolution de ce compteur en fonction du nombre d'allumettes, nous pouvons en déduire une estimation de la complexité de l'algorithme. En plus du nombre d'appels récursifs, nous avons également mesuré le temps d'exécution de chaque algorithme.
Ces deux critères nous permettent de comparer l’efficacité et l’optimisation entre chaque algorithe developper.
3. AC12.03 | Formaliser et mettre en œuvre des outils mathématiques pour l’informatique
Lors de cette SAE, nous utilisons plusieurs outils mathématiques, notamment la logique et la complexité. Le raisonnement sur les positions gagnantes ou perdantes repose sur des principes de logique booléenne, tandis que l'arborescence des décompositions s'appuie sur la notion d'arbres et de récursivité. Les optimisations par mémorisation utilisent des concepts liés aux ensembles et à la recherche d'équivalents.