SIMS (SIMS Is a Machine Simulator)
Publié le jeudi 27 janvier 2005, 16:34 - modifié le 11/10/12 - Projets - Lien permanent
- Article
- |
- Commentaires (1)
- |
- Annexes (3)
SIMS est un autre projet qui a dû être fait pour l'Université de Cergy. Plus gros projet jamais réalisé par moi à cette époque (nous étions quatre bien que l'une des quatre ne trouva rien de mieux que de partir en Normandie faire du cheval alors que tous trimaient) ; il s'agit d'un projet d'envergure pour l'affichage, au départ, de graphes orientés, puis finalement de machines de Turing et machines à registres.
Le projet demandé consistait à créer une interface graphique facile à utiliser qui puisse créer des machines à registres et de Turing et afficher leur contenu, graphes et bandes. Par la suite, un éditeur de machines a été rajouté permettant d'afficher le déplacement en temps réel de l'instruction lue par la machine et de modifier facilement les données de la machine en cours. Cet éditeur fut aussi utile dans le sujet du projet dont le but était de simuler le déplacement du curseur pour suivre l'état courant de la machine. Le sommet actif du graphe et l'état actif de la bande s'affichait ainsi en rouge. Une des grosses difficultés du problème était le principe de placement des sommets d'un graphe. En effet, il s'agit là d'un problème NP-Complet i.e. un problème sans réelle solution donnée par un ordinateur et que seul l'humain à force d'approximation peu résoudre. Le principe était donc de créer un algorithme valable de placement d'états assez fiable pour qu'on puisse croire qu'un humain avait lui-même placé les états. Je m'occupai de cet aspect du problème et le principe du placement utilisé, non seulement fiable et plutôt correct, est unique car je l'ai créé sans aucune inspiration en provenance de travaux déjà existant. Cet algorithme et ce simulateur semblait être bon car ils nous ont valu la meilleure note (19/20).
Pour ceux qui ne savent pas qui était Turing ou qui aimerait en savoir plus sur ce projet, je vous propose de télécharger les diapos (format OpenOffice.org) attachés avec l'application à ce billet.