Instance

Voilà, le projet SPIRIT est terminé. Nous avons présenté le résultat ce lundi 7 mars et je vais vous résumer ce projet en différentes parties :

Rappel du projet
Les difficultés du projet
Ce qui a fonctionné
Bilan
Remerciement

Rappel du projet

L’acronyme SPIRIT signifie Système Prototype d’Interrogation et de Recherche d’Images par Téléphone. Le but était donc de créer un logiciel prototype montrant la possibilité de reconnaitre automatiquement un monument/bâtiment connu sur une image et d’en fournir une documentation. Ceci devait être possible via un navigateur web ou un smartphone. Ce projet permettait donc également de juger des connexions possibles entre les smartphones et les services WebLab.
Pour plus de détails, je vous renvoie vers les anciens articles : Cliquez ici

Pour ceux qui désirent voir le cahier des charges : Cliquez ici

Les difficultés du projet

Durant ce projet, nous avons subit tout un ensemble de difficultés plus ou moins importantes et handicapantes. Cette analyse des difficultés du projet n’engage que moi. Certains points de cette analyse ne sont peut-être pas partagés par les autres membres du projet.

Comprendre les besoins

Ce problème est typiquement un problème de communication. Le projet était organisé en 3 niveaux :

La maitrise d’ouvrage (MOA) représenté par M. Giroux (professeur de gestion de projet et cadre dirigeant de Cassidian)
La maitrise d’œuvre (MOE) représenté par mon équipe
Les équipes de développement, c’est à dire les autres équipes des M2GIL

Il faut donc une communication solide pour un tel projet. Or, il y a justement eu des failles de communication entre la MOE et la MOA, puis entre la MOE et les équipes de développement. Par manque d’expérience dans ce domaine, nous avons eu des difficultés à formaliser les besoins de la MOA, mais avec les révisions qui se sont succédées, les spécifications du besoin ont pu prendre une forme convenable et être validées par la MOA, malgré que cette validation soit arrivée assez tard.

Ce retard de formalisation a également été gênante pour les équipes de développement qui ont donc eu des difficultés à comprendre le travail qu’ils devaient accomplir. Les révisions des spécifications ont eu comme conséquence des changements des composants développés. Cela a donc provoqué des retards et des tensions entre les équipes de développement et la MOE.

Pour éviter également que des décisions ne soient oubliées par certains, un registre de décisions a été mis en place, permettant une référence en cas de litige.

Méconnaissance technique

Nous avons travaillé quasi-uniquement sur des technologies nouvelles pour nous. En effet, sur les 3 équipes de développement, nous avions une équipe responsable des services web, une autre équipe sur les portlets et une dernière équipe sur l’application Android. Je vais donc vous détailler les difficultés de chacun de ces points.

Services Web

Jusqu’ici, nous n’avions jamais créé de service web. Notre connaissance se limitait à des notions théoriques sur les architectures orientées services et distribuées. De plus, dans le cadre du projet SPRIT, nous devions adapter nos services web au socle WebLab utilisé par Cassidian (Anciennement EADS Defence & Security). Cette contrainte n’était pas une difficulté négligeable puisque nous avions eu beaucoup de mal à nous informer (et donc à comprendre) le fonctionnement et la philosophie de l’architecture de WebLab. Je ne détaillerais pas ici le fonctionnement technique de WebLab, mais nous avons été contraint à modifier plusieurs fois l’architecture de SPIRIT lorsque nous comprenions un point supplémentaire de WebLab. Cela a donc provoquer des retards assez importants.

Le plus gros retard concernant les services web concerne l’appel des services web. Nous savions que nous avions besoin de “WebServiceClient” que nous devions utiliser pour appeler un service web. Nous avons donc généré nos propres “WebServiceClient” via Eclipse et nous l’exportions ensuite en format JAR. Nous avions eu beaucoup de dysfonctionnements avec ces JAR, ce qui était complètement bloquant puisque sans appel de services web, il n’y a aucun traitement et donc le prototype ne fonctionne pas. C’est seulement une semaine plus tard que nous avons appris que WabLab possède un JAR qui permet d’appeler les services web qui implémentent les interfaces WebLab, ce qui est notre cas. Un certain désespoir nous est tombé dessus lorsque nous nous sommes rendu compte que nous avions perdu une semaine du projet sur un total d’un mois… ensuite, un dernier dysfonctionnement a été réglé par les intervenants Cassidian qui sont venu nous aider bénévolement. Ce dysfonctionnement concernait les services web qui implémentent plusieurs interfaces WebLab, ce qui n’était pas très courant dans les projet WebLab et nécessitait une légère modification de la configuration du déploiement des services web.

Après ce dernier point, les services web avançaient sans trop de difficulté.

Portlets

Nos portlets ont utilisé le portail Liferay puisqu’il est également utilisé par les projets WebLab. Au début du projet, les portlets se portaient bien, mais au fur et à mesure des modifications du fonctionnement de l’architecture (et des services web bien sûr), des retards et difficultés techniques sont évidemment apparus. La plus grosse difficulté est liée aux services web puisqu’il s’agit des “WebServiceClient” pour appeler les services web. Ce point a été développé dans le paragraphe précédent, je ne le détaillerai donc pas ici.

Smartphone

Notre application smartphone était prévu pour fonctionner sous Android et devait pouvoir appeler les services web. Cependant, nous avons découvert qu’une application Android ne possède pas tous les outils qu’offre le langage Java et ne permet pas non plus de manipuler les classes WebLab. L’impossibilité de manipuler les objets WebLab nous empêche donc de créer les paramètres envoyés aux services web implémentant les interfaces WebLab. Ceci nous a obligé à ajouter une couche middleware permettant de “pousser” des données sous forme de tableau d’octets que le middleware peut utiliser pour créer les objets WebLab nécessaires aux service web. Lorsque nous avons présenté cette idée à la MOA, nous avons appris que “pousser” les données est justement une des fonctionnalités des ESB, qui font la liaison entre les services web et les applications clients.

L’autre difficulté sur l’application Android est l’appel des services web déployé sur le réseau local. Nous avons du mettre en place un routeur sur le réseau local de l’université qui ne permet pas si facilement d’ajouter ce système. Nous avons donc réussit, très tardivement, à connecter le smartphone sur le réseau local, ce qui a retardé les tests en situations réelles et donc les corrections qui en découlent.

Promiscuité

Nous étions une vingtaine d’étudiants à travailler à temps complet sur ce projet, dans une seule salle. Nous étions donc assez entassés et nous travaillions dans un bruit constant puisque ce travail implique qu’il y ait constamment des discussions dans la salle commune. Un travail correct et une bonne ambiance nécessite d’avoir un lieu de travail pour chaque équipe. Ces conditions ont donc provoquées certaines tensions entre les équipes.

Ce qui a fonctionné

Durant la présentation final du prototype, nous avons pu montrer les fonctionnalités réussies de SPIRIT. Voici la liste de ces fonctionnalités :

Collecte automatique (via GoogleImage et FlickR) et manuelle (depuis un zip) d’images de monuments/bâtiments.
Collecte automatique (via DBpedia) et manuelle (via un formulaire) de fiches descriptives sur un monument/bâtiment.
Liaison image/fiche descriptive permettant de retrouver la documentation d’un monument d’une photographie.
Indexation des images afin de pouvoir être utilisées lors des prochaines recherches d’images par le contenu. Cependant, l’indexation ne s’effectue bizarrement que sur la moitié des photographies, il faut donc effectuer log₂(n) indexation, avec n le nombre d’images disponibles à indexer.
Lancer une recherche depuis un navigateur internet via un portlet.
Lancer une recherche depuis un smartphone via l’application Android.
Lancer une recherche depuis un smartphone via une application mail. (Cette fonctionnalité n’a pas pu être présenté lors de la démonstration finale puisque le smartphone ne permettait pas d’envoyer de mail sur le réseau local. Cependant, si le service mail était déployé sur internet, le smartphone pourrait appeler ce service mail.)

Bilan

Ce bilan ne concerne que la maitrise d’œuvre, les membres de chaque équipe de développement ont fait leurs propres bilan et leurs propres conclusions.

Nouveaux postes pour les membres de la MOE

Chaque membre de la MOE a découvert un nouveau poste et ses responsabilités durant le projet SPIRIT. Je rappel la composition de l’équipe et les rôles :

Audrey SACARABANY (Responsable qualité) a découvert la formalisation des spécifications techniques du besoin.
Vincent ETIENNE (Architecte principale) a reçu la tâche de créer une architecture et d’en déduire des workpackages pour une sous-traitance de développement.
Hisham ENNAJIH (Responsable intégration) devait intégrer les composants et effectuer des tests afin de valider la conformité du projet par rapport au spécification du responsable qualité.
Rachid BEN HAMMOU (Responsable évaluation) a reçu la responsabilité d’évaluer l’efficacité de la recherche d’images par le contenue via un protocole scientifique précis qu’il a défini.
Moi-même, Jonathan GERMOND (Maitre d’œuvre), mon travail était d’organiser les réunions, de définir le planning général et de m’occuper du suivi du projet.

La découverte de ces postes, et les erreurs qui en découlent, ont donc provoquer un ensemble de trous dans le déroulement du projet, impliquant un effet passoire par laquelle s’est échapper la réussite total du projet.

En revanche, ceci nous a permis d’avoir une meilleur connaissance de soi-même, en nous apportant des précisions sur les capacités et les possibilités de carrière de chacun.

Dans mon propre cas, j’ai eu la confirmation d’un fait que je soupçonnais : J’ai bien plus de chance de réussir une carrière technique (Architecte logiciel, par exemple) qu’une carrière de gestion de projet. Cette confirmation vient du fait que j’ai régulièrement vu des défauts d’architectures et que mon aide était apprécié. De plus, ma gestion du projet a régulièrement été critiquée, donc soit ma gestion du projet était effectivement insuffisante, soit les personnes se plaignent toujours!

Cependant, j’ai effectivement eu l’impression que les autres étudiants me demandais l’efficacité d’un chef de projet confirmé (en particulier à propos des prises de décisions), ce qui est évidement pas mon cas. Je ne risquait donc pas de les satisfaire sur le point.

Je verrais bien si la suite de ma carrière confirme (ou pas) ma préférence du monde technique par rapport à la gestion de projet.

Attente de composants prêt à l’intégration

La MOA nous a fourni plusieurs services web pour le projet SPIRIT. Nous nous attendions à des services tout prêt à être intégrés qu’il suffisait d’appeler simplement, ce qui n’était pas du tout le cas puisque les services web fournis nécessitaient un ensemble de configurations et d’adaptation pour pouvoir être intégrés au projet SPIRIT. Il y a donc eu une incompréhension entre la MOE et la MOA.

Nous avons donc appris à avoir une certaine réserve vis-à-vis du client afin que nos espérances ne soient pas considérées comme dû, ce qui provoque des imprévus et donc du retard.

Dans notre cas, nos espérances étaient la présence de schéma pré-post pour chaque méthode des services web fournis. Ce manque nous a obligé à mettre en place des séances de rétro-ingénierie qui n’étaient pas prévu initialement. Nous avons donc appris à prévoir ces séances.

Méconnaissances techniques

Les méconnaissances techniques décrites précédemment ont provoqué des retards sur la rédaction des spécifications technique du besoin et de l’architecture. Par conséquence, nous avons pu observer l’importance d’une conception propre avant la phase de développement. Il est très dangereux de commencer le développement d’un projet avant d’avoir terminer la rédaction des spécifications technique du besoin et la définition de l’architecture car cela provoque des modifications sur ce qui est déjà développé, ce qui indique donc un gâchis de ressources humaines et du temps perdu qui ne sera pas rattrapé.

Nous avons donc maintenant connaissance de ce qu’est un projet en difficulté avec l’organisation qui va avec : Développement en urgence, réunion de crise, risque de non-conformité, …

Différences d’implications personnelles

Régulièrement, pendant le développement du projet, certains étudiants se sont limités strictement à leurs responsabilités sans se soucier de la réussite du travail des autres équipes. Typiquement, les phrases suivantes ont régulièrement été dites : “Ce n’est pas mon travail”, “J’ai fait ma partie, après, ce n’est plus mon problème”.

Environ une semaine avant la fin du projet, le professeur de gestion de projet est intervenu en indiquant que tout le monde était concerné et que si le projet coule, tout le monde coule, même les équipes qui ont réussies leurs parties. C’est à ce moment qu’on a pu voir une bien meilleurs implication de la part d’une bonne partie des étudiants. Il y a eu des prêts de membres entre les équipes, et cette entraide à largement accéléré l’avancé du projet. Nous pouvons donc facilement déduire l’importance de la solidarité et de la fédération inter et intra-équipe.

Dans l’idéal, chaque membre doit porter un intérêt envers le résultat final du projet, car la passion apporte les plus grande réussite, logiciel ou non. Nous aurions peut-être dû faire un effort sur ce point afin que chacun porte plus d’intérêt envers ce projet, au lieu de faire ce travail simplement parce qu’il doit être fait…

Un petit exemple cinématographique, Spielberg et Burton sont des passionnés et vous connaissez sûrement le résultat de leurs œuvres

Remerciement

Voila ce projet est maintenant terminé. Je tiens à remercier un ensemble de personnes pour ce projet :

A M. Giroux qui a effectué le double rôle de MOA et de professeur de gestion de projet.
Aux deux intervenants Cassidian qui sont venus bénévolement nous aider plusieurs fois :
- M. Emilien BONDU
- M. Nicolas MARTIN
A la communauté WebLab qui nous a répondu sur le forum de WebLab.
Aux équipes de développement qui ont fait un bon travail de développement

Merci de m’avoir lu jusqu’au bout. J’espère que cet article sera utile à d’autres membres d’un projet similaire.

Tags: Android, Architecte logiciel, CBIR, Chef de projet, EADS, Informatique, Liferay, Master, Middleware, Portlet, Recherche d'images par le contenu, Service web, Smartphone, SPIRIT, Technologie, WebLab

Dec 11

Conditions d’utilisation des sources

Categories:

Blog Instance

Depuis quelques mois, il y a apparemment de plus en plus de personnes (surtout de la fac) qui viennent lire régulièrement mes articles, donc tout d’abord merci à tous ces lecteurs.

A propos des codes sources partagés dans les différents articles, je vais préciser les utilisations que j’accepte.

Tout d’abord, toute copie est autorisée sans conditions. J’autorise également d’étudier les sources si ca peut permettre d’aider certaines personnes dans leur travail de développement. En revanche, j’interdis formellement le copier/coller de mes codes sources dans des projets étudiants… dommage pour certains

Les conditions d’utilisation des codes sources sont donc très proche d’une licence libre mis à part ce dernier point. Je veux juste éviter que des étudiants présentent mon code source dans leurs projets afin de recevoir une bonne note sans travail. Je rappelle également que, selon la loi française, il est strictement interdit d’ajouter mon code source dans un projet sans y ajouter aussi mon nom, quelque soit la licence du code source… encore dommage pour certains

Je demande donc aux étudiants, qui auraient l’envie d’utiliser mes sources, de réfléchir par eux même. Ils peuvent utiliser mon travail pour comprendre les algorithmes, l’organisation des composants, etc… mais pas de copier/coller mes lignes dans leurs projets.

Merci

This post has no tag

Nov 25

Tout est relatif… le vocabulaire aussi!

Categories:

Aucune

Depuis quelque jours, j’ai appris que des personnes n’ont pas apprécié certains propos de mes articles, en particulier des étudiants en Master GIL ou SSI.

Un exemple de ces phrases avec la partie gênante en gras :

Mais je ne perd pas espoir car le reste de leur équipe possède un niveau plus médiocre alors que la mienne est bien plus équilibré.

Je comprend que cette phrase ne soit pas agréable à lire par tout le monde, c’est pourquoi elle a été modifiée. De plus, je ferais un effort d’écriture afin que cela ne se reproduise plus. D’ailleurs, cela me fera un exercice supplémentaire dans le domaine de la communication et du relationnel .

Mais en échange, j’aimerais être prévenu directement par les personnes blessées ou gênées, au lieu de rumeurs trainant dans les couloirs… Cela me permettra de réagir plus rapidement dans mes articles, mais ça sera également une preuve de franchise. Le système de commentaires est là pour ça

Au final, je voudrais qu’il soit clair qu’il n’y a aucun sentiment méchant ou hautain derrière ces mots. C’est tout simplement mon caractère et mon vocabulaire habituel qui s’exprime ainsi.

Merci.

This post has no tag

3 comments

Oct 26

[Projet Universitaire] Théorie des codes – début 2010

Categories:

Wikipédia :

En théorie de l’information, la théorie des codes traite des codes et de leurs propriétés et leurs aptitudes à servir sur différents canaux de communication. On distingue deux modèles de communication : avec et sans bruit. Sans bruit, le codage de source suffit à la communication. Avec bruit, la communication est possible avec les codes correcteurs.

Cette matière nous a été enseignée pendant notre 1ère année du Master Génie de l’Informatique Logicielle. Nous avons également eu un projet à programmer. Voici le sujet : sujet_projet_codes.pdf

J’ai travaillé sur ce projet avec Vincent ETIENNE et je me suis surtout occupé de la partie algorithmique pendant que Vincent s’est occupé de toute l’IHM.

J’ai passé beaucoup de temps à améliorer la performance algorithmique, en particulier pour la génération du graphe de Sardinas et Patterson du code. Au lieu de recalculer le graphe à chaque modification du code, ce graphe se met dynamiquement à jour. Tout les détails de cette amélioration algorithmique sont dans le rapport du projet, avec des supers dessins et tout et tout.

J’ai écrit totalement le rapport, je me suis forcé à expliquer au maximum chaque chapitre avec les descriptions des algorithmes et structures de données. Pendant ce projet, j’ai eu l’impression de faire une mini-thèse. En effet, les améliorations algorithmiques que je recherche moi-même, les explications de ma démarche, l’analyse de complexité et les jolies dessins… tout est présent mis à part que le projet est bien plus petit qu’une thèse. Si on oublie le peu de temps que nous avions, c’était un pur plaisir

Lien du projet complet : projet_de_codes.zip (~5Mio)

Tags: Algorithme, GIL, Graphe de Sardinas et Patterson, Informatique, Langage C, Licence Informatique, Liste chainée, Optimisation algorithmique, Rouen, Structure de données dynamique, Théorie des codes

Oct 25

[Projet Universitaire] Algorithmique du texte et Aho-Corasick – fin 2009

Categories:

Cette matière comprenait un projet dont voici le sujet :

Vous rendrez au plus tard le jour de l’examen une archive contenant un dossier comprenant les sources de vos programmes, une description des structures de données utilisées et un commentaire détaillé de vos résultats.

Travail demandé

Implanter l’algorithme de recherche exacte d’un ensemble de k mots dans un texte d’Aho-corasick.
Utiliser trois méthodes pour représenter l’arbre :

un matrice de transitions;

des listes d’adjacence;

une table de transitions pour la racine et des listes d’adjacence pour les autres nœuds de l’arbre.

Générer pseudo-aléatoirement des textes de longueur 500 000 sur des alphabets de taille 2, 4, 20 et 70. Pour chacun de ces alphabets générer pseudo-aléatoirement 3 ensembles de 50 mots de longueur entre 5 et 12, entre 13 et 20 et entre 21 et 30 respectivement.
Pour chacun des textes effectuer la recherche des 3 ensembles.
Relever les temps d’exécution de chacune de ces recherches, faire des courbes et commenter.

Les détails des 3 structures de données sont dans le rapport du projet. J’ai pris la peine de faire des jolies dessins pour être facilement compris, alors profitez en.

Les résultats de l’étude statistique sont également dans le rapport du projet. Voici un résumé :

La matrice est la structure de données la plus rapide mais elle gâche également beaucoup de mémoire.
La liste de listes ne gâche pas de mémoire, mais est bien plus lente d’exécution que la matrice.
La troisième structure de données était presque aussi rapide que la matrice, mais ne gâchait pas de mémoire.

Tout l’intérêt de l’étude statistique est sur ce dernier point. Elle montre qu’un petit détail peut considérablement modifier les performances d’une structure de données (dans notre cas, le simple tableau qui remplace la 1ère liste). Vous pouvez voir qu’il n’existe que très peu de différence entre les dessins de la liste de listes et les dessins de la 3ème structure de données.

Ce rapport explique ensuite le pourquoi des performances de chaque structure de données grâce à une analyse de la complexité en temps d’exécution de chaque structure de données.

Le travail que j’ai effectué dans ce projet est la programmation de la matrice, la participation au débogage des autres structures de données, les études statistiques et l’écriture du rapport. Ce projet m’a appris à utiliser le logiciel “Valgrind” afin de trouver l’origine d’une fuite mémoire. Dans notre cas, un string (donc un tableau) était alloué pour chaque caractère du texte et n’était pas libéré. Sachant que le programme a été testé dans un texte de 10 millions de caractères, il faudrait être aveugle pour ne pas s’apercevoir de l’existence d’une fuite mémoire…

Ce qui a été également très formateur dans ce projet, c’est le travail en urgence. Nous avions peu de temps pour effectuer ce projet, j’ai donc sacrifié plusieurs nuits. Ce n’était pas la 1ère fois qu’un projet me l’imposait, mais grâce à l’accumulation de ces nuits sacrifiées, je n’ai plus peur du travail long et difficile. N’aimant pas le café, j’ai du trouvé d’autre booster. Pour moi, le red bull fonctionne bien.

Pour télécharger le projet : Aho_Corasick.zip (~1.1Mio)

Tags: Aho-Corasick, Algorithme de recherche, Analyse de complexité, Informatique, Langage C, Liste chainée, Master, Rouen, Théorie des codes

Oct 16

[Projet Universitaire] Tigwai : Jeux et Stratégies – début 2009

Categories:

Tigwai (Tigwai Is Games With Artificial Intelligence) est le résultat du projet annuel de ma 3ème année de Licence. Ce projet est qualifié d’annuel car il est totalement indépendant des matières des deux semestres. Des professeurs du département Informatique ont proposé un ensemble de sujet et chaque groupe choisit un sujet, de façon qu’il n’y ait pas deux groupes sur le même sujet.

Mon coéquipier était Loic Broche (le même que pour le projet d’éditeur/colorateur de graphe) et nous avons choisi le projet nommé “Jeux et Stratégies”. Voici le sujet exact :

L’objectif de ce T.E.R est d’implanter les principaux algorithmes de recherche des stratégies gagnantes pour des jeux à deux joueurs, répétés, séquentiels, ﬁnis et à information complète.
Le jeu du morpion est un exemple de ce type de jeu :

à deux joueurs : il se joue à deux,

répété : les joueurs jouent plusieurs fois,

séquentiel : les décisions des joueurs sont prises à des moments différents,

ﬁni : la partie se termine après un nombre ﬁni des coups,

à information complète : chaque joueur connaît les coups joués par son adversaire et toute l’histoire de la partie (un jeu de carte comme le Poker n’est pas à information complète puisque les cartes des deux joueurs sont cachées).

Le modèle utilisé pour des tels jeux est un arbre orienté. Dans cet arbre, appelé arbre de jeu ou de décision,

les sommets sont divisés en deux sous-ensembles : les sommets qui appartiennent au joueur 1 et les sommets qui appartiennent au joueur 2,

les ﬂèches qui partent d’un sommet qui appartient au joueur 1, par exemple, représentent les coups qui peuvent être joués par ce joueur.

L’objectif de ce T.E.R. est d’étudier les notions de stratégie et de stratégie gagnante en termes de sous-arbres particuliers de l’arbre de jeu et d’implanter les principaux algorithmes de recherche de stratégies gagnantes, Minimax, Apha-Beta, SSS etc. Des simulations des algorithmes implantés sont aussi demandées. Elles se feront sur des jeux choisis par l’équipe qui réalise ce projet.

Sachant que nous n’avions encore jamais eu de cours sur la théorie des jeux (Ce cours était prévu pour la 1ère année de Master), nous devions tout apprendre par nous même. Nous avons donc découvert les algorithmes suivants :

Minimax
Négamax
Minimax avec élagage alpha-béta
Négamax avec élagage alpha-béta

Ce projet m’a énormément appris sur les intelligences artificielles. Nous avons fait un grand effort d’architecture afin de pouvoir implanter plusieurs jeux et plusieurs algorithmes en même temps. Ainsi, l’utilisateur peut choisir le jeu et l’algorithme conte lequel il joue. De plus, si un développeur veut ajouter un jeu ou un algorithme, en respectant les interfaces Java prévues, tous les jeux pourront se jouer avec tous les algorithmes.
Cependant, cet architecture, permettant le produit cartésien entre les jeux et les algorithmes, sacrifie un peu la performance. Mais la performance reste suffisante car :

Pour le Morpion (le jeux le plus simple qui a été implanté), tous les algo sont capable de prévoir TOUTE la partie. Il est donc impossible de gagner contre le plus haut niveau de difficulté de chaque algorithme implanté.
Pour le Awalé (le jeux le plus complexe qui a été implanté), dans le meilleur des cas, l’algorithme sera capable de prévoir 9 coups à l’avance. Je doute sincèrement qu’un utilisateur du Tigwai soit capable de prévoir plus de 9 coups à l’avance dans le Awalé, sachant les calculs que cela impose

Ce projet m’a réellement donné l’envie d’en savoir plus sur les intelligences artificielles pour les jeux vidéos. De plus, je pense que si un jour je trouve un emploi dans un éditeur de jeux vidéo, cela pourra m’être utile.
Cependant, Tigwai n’est pas très agréable graphiquement car ce n’est pas du tout le but recherché. N’oublions pas que c’est principalement un projet à but pédagogique sur la théorie des jeux.

Bref, je conseil ce projet pour ceux qui désire débuter dans la théorie des jeux et les algorithmes d’IA qui vont avec.

Liens :
L’ensemble des sujets proposés en L3 : sujets_projets_L3.pdf (~70Ko)
Le résultat du projet : Tigwai.zip (~1Mo)

Tags: Informatique, Intelligence Artificielle, Licence Informatique, Stratégies, Théorie des jeux

Oct 16

[Projet Universitaire] Editeur/Colorateur de graphes – fin 2008

Categories:

Ce projet nous a été donné en fin 2008 (J’étais donc en 3ème année de Licence) par le professeur responsable des cours de “Théorie des graphes”. Nous étions 2 dans le groupe (Loic Broche et moi). Le sujet était (en résumé) le suivant :

Le logiciel doit permettre à l’utilisateur de créer un graphe via une interface graphique. L’utilisateur peut donc manipuler les sommets et les arrêtes du graphe.
Ensuite, le logiciel doit être capable de colorer le graphe. Je rappelle la règles de coloration d’un graphe : “Chaque sommet possède une couleur différente de tous ses sommets voisins.” Logiciel doit pouvoir colorer le graphe avec au moins 4 algorithmes dont l’algorithme du Back-tracking (résolution par rebroussement). L’utilisateur peut donc choisir l’algorithme de coloration. En plus de cela, le logiciel doit montrer la coloration étape par étape. L’utilisateur peut donc voir les “retours en arrière” de l’algorithme Back-tracking.

Le logiciel doit être entièrement programmé en Java.

Ce projet avait plusieurs buts :

Apprendre seul : Le projet devait posséder une interface graphique en Java, or le cour sur ce domaine était prévu pour le semestre suivant. Nous avons donc du découvrir seul Swing, la gestion du clavier et de la souris, le multi-thread, etc.
Un gros travail algorithmique : Le projet imposait au moins 4 algorithmes dont un seul est imposé. Les étudiants devaient donc découvrir seul les autres, soit en les inventant, soit dans des documentations. Notre capacité à comprendre un nouvel algorithme était donc mis à l’épreuve.

De mon coté, ce projet m’a beaucoup apporter, et même au delà des buts précédemment exprimés :

Maitrise de Swing.
Maitrise de la gestion des évènements clavier et souris.
Maitrise du multi-threads (indispensable pour l’affichage de la coloration étape par étape).
Amélioration de mes compétences algorithmiques. (Théorie des graphes)
Entrainement sur l’ergonomie du logiciel afin de le rendre intuitif.
Nous avons ajouter l’exportation du graphe au format image.

Ce projet est donc principalement un bon entrainement pour le langage Java et la manipulation de graphes.
Le résultat du projet : GraphEditor.zip (~800Ko)

Tags: Algorithme, Coloration de graphe, Informatique, Java, Langage informatique, Licence Informatique, Multi-threads, Swing, Théorie des graphes

Oct 15

[Projet Universitaire] Calcul Symbolique et caml – début 2008

Categories:

Dans le 2ème semestre de la 2ème année de Licence Informatique (début de l’année 2008), l’une des option est le “calcul symbolique”. Cette matière comprend un projet dans le langage caml qui est un langage de programmation fonctionnel français particulièrement adapté au calcul symbolique.

Le sujet du projet était, de mémoire, le suivant :

Première partie :

Le projet doit offrir un ensemble d’outils permettant de manipuler des entiers relatifs de taille illimité, donc sans aucun débordement de capacité. Ces grands nombres seront implantés sous forme de liste d’entiers et le logiciel doit permettre les opérations suivantes sur ces grand nombres :

Négation d’un grand nombre

Addition de deux grands nombres

Soustraction de deux grands nombres

Multiplication de deux grands nombres (avec un algorithme naïf puis l’algorithme de Karatsuba)

Division entière de deux grands nombres

Modulo de deux grands nombres

PGCD de deux grands nombres

Générateur aléatoire d’un grand nombre

Deuxième partie :
Le projet doit offrir un ensemble d’outils permettant de manipuler des polynômes dont les coefficients sont les grands nombres précédemment implantés en implantant les opérations suivantes :

Négation d’un grand polynôme

Addition de deux grands polynômes

Soustraction de deux grands polynômes

Multiplication de deux grands polynômes (avec un algorithme naïf puis l’algorithme de Karatsuba)

Division entière de deux grands polynômes

Modulo de deux grands polynômes

Générateur aléatoire d’un grand polynôme

Ce résumé du sujet est loin d’être exhaustif mais indique le plus intéressant pédagogiquement et techniquement. Ce projet m’a clairement apporté des connaissances mathématiques et algorithmique. De plus, l’utilisation d’un langage de programmation fonctionnelle m’a parfaitement habitué aux algorithmes récursifs. Parfois, un algorithme récursif peut me paraitre bien plus intuitif qu’une itération.

C’est donc un bon exercice pour ceux qui désirent travailler la récursivité et les algorithmes mathématiques de bases.

Pour les intéressés : projet_cs.zip (~50Ko)

Tags: caml, Grand nombre, Informatique, Langage de programmation fonctionnel, Langage informatique, Licence Informatique, Polynôme, Récursivité

Oct 15

[Projet Universitaire] Structure de Données et Algorithme Fondamental – fin 2007

Categories:

Lors de ma 2ène année de Licence Informatique (fin de l’année 2007), nous avions une matière sur la récursivité et structures des données qui vont avec (liste chainée, arbre binaire, table de hachage, …). Comme dans d’autres matières, nous avions un projet pour appliquer ces concepts. Le sujet que j’ai reçu était donc (de mémoire, car je n’ai plus le sujet exact ) le suivant :

Le logiciel doit pouvoir recevoir un fichier texte en entrée. Le logiciel va parcourir ensuite le texte afin de référencer tous les mots dans une table de hachage. Pour chaque mot, le logiciel doit enregistrer en mémoire la position de la première occurrence, la dernière occurrence et le nombre d’occurrences.

Enfin après avoir parcouru le texte, toutes ces informations doivent être affichées sur la sortie standard avec une ligne par mot (et les informations sur ses occurrences) et par ordre alphabétique des mots.

Le logiciel doit être programmé en Pascal et fonctionne en ligne de commande (pas d’interface graphique).

Le rapport de projet doit contenir une analyse de complexité du programme en temps d’exécution et en mémoire.

On remarque assez facilement les objectifs pédagogiques :

Manipulation de fichier texte.
Création et manipulation d’une table de hachage.
Création et manipulation de listes chainées.
Manipulation de pointeurs.
Application d’un algorithme de tri.
Entrainement à l’analyse de complexité.

J’étais assez satisfait de mon résultat à l’époque. Mon programme était capable de traiter quasi-instantanément un fichier texte contenant les deux œuvres de Molière “Le Bourgeois Gentilhomme” et “Tartuffe”. Ce qui donne en tout 4485 mots en plus de 5200 lignes.

Ce fichier est disponible ici, et le résultat est ici, qui affiche chaque mot de la forme suivant : “mot” ; nombre d’occurrence ; (première occurrence) ; (dernière occurrence)

L’analyse complète de chaque fonction et procédure m’a permis de me rendre compte à quel point la complexité est importante lors de l’optimisation algorithmique d’un programme. De même, pour la fonction de hachage, l’analyse du fichier est passer d’une dizaine de secondes à un résultat quasi-instantané en passant d’une mauvaise à une bonne fonction de hachage.

En plus de cela, pour pimenter un peu ma table de hachage, j’ai voulu créer une table de hachage de taille dynamique. Elle commence donc avec 16 index et, lorsqu’il y a plus de 5 éléments par index en moyenne (donc 16 * 5 = 80 éléments), la table de hachage double sa dimension. Elle peut continuer à doubler sa dimension jusqu’à atteindre une taille maximal de 1024 index. Ceci n’était pas du tout imposer par le sujet (je suis donc le seul a l’avoir implanté) mais c’est un petite défi que je m’étais posé à l’époque. Cela permet donc de borner la taille des listes de la table de hachage et augmente donc les performances.

Pour ceux qui veulent s’entrainer sur ces domaines, je conseille donc ce projet.

Voici l’archive de mon projet entier pour ceux qui sont intéressé : Projet_SDAF.zip (~280Ko)

Tags: Algorithme de tri, Analyse de complexité, Informatique, Langage informatique, Licence Informatique, Liste chainée, Pascal, Pointeur, Table de hachage

Oct 07

[Projet M2GIL / EADS] Etape 3 : Un aperçu du sujet en attendant le cahier des charges

Categories:

Projet M2GIL / EADS