Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Universit´ e de Moncton D´ EPARTEMENT D’INFORMATIQUE DEVOIR 1 INFO 4009 FONCTIO

Universit´ e de Moncton D´ EPARTEMENT D’INFORMATIQUE DEVOIR 1 INFO 4009 FONCTIONNALIT´ E DE LA M´ ETHODE N-VERSIONS NI ´ ETUDIANT : PATRICK GODIN A00188402 MATHIEU ALLAIN A00188843 Table des mati` eres 1 CONTEXTE 2 2 INTRODUCTION 2 3 MOTIVATION 2 4 FONCTIONNALIT´ E 3 5 DESCRIPTION DES FONCTIONS 3 6 IMPL´ EMENTION DE LA M´ ETHODE N-VERSIONS 4 6.1 N-VERSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 6.2 DRIVER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 7 PORT´ EE FUTURE 6 8 CONCLUSION 6 Table des mati` eres 1 1 CONTEXTE La programmation N-versions (NVP) est une m´ ethode de d´ eveloppent de logiciel o` u plusieurs programmes ´ equivalents sont cr´ e´ ees ` a partir des mˆ emes sp´ eciﬁcations initiales. ` A partir de ces sp´ eciﬁcations, deux versions ou plus du programme sont d´ evelopp´ ees. Id´ ealement, chaque version utilise un diﬀ´ erent algorithme, un diﬀ´ erent langage de programmation ou est programm´ ee par diﬀ´ erentes ´ equipes. Ensuite on ´ evalue ces N-versions avec un algorithme de d´ ecision. 2 INTRODUCTION Ce premier devoir a pour but de r´ ediger un programme qui d´ emontre la m´ ethode N versions. Comme appris dans le cours, celle-ci peut aider avec la conception d’un syst` eme ; plus sp´ eciﬁquement, sa ﬁabilit´ e. En comparant diﬀ´ erentes m´ ethodologies et algorithmes ` a l’aide de points sp´ eciﬁques, on peut trouver l’impl´ ementation parfaite pour notre syst` eme. Pour d´ emontrer la fonctionnalit´ e de la m´ ethode N versions, nous avons d´ ecid´ e de cr´ eer un programme de recherche de chemins. 3 MOTIVATION Comme ce devoir nous donne la libert´ e de choisir notre sujet, nous ´ etions motiv´ es ` a cr´ eer quelque chose d’int´ eressant avec un aspect visuel. Nous avons l’id´ ee de recherche de chemin et nous avons pouss´ e plus loin pour y impl´ ementer les aspects de N- Versions. 2 4 FONCTIONNALIT´ E Le programme a ´ et´ e ´ ecrit dans Python, avec plusieurs fonctions de la librairie Py- game. Cette librairie permet de coder des aspects visuels portables ` a plusieurs pla- teformes assez facilement. Python comme tel n’est pas tr` es utile pour des syst` emes temps r´ eel, mais fonctionne tr` es bien pour coder un genre de programme comme celui-ci. Lorsque vous lancez le programme, un onglet Pygame ouvrira. Vous pouvez choisir un des trois modes avec votre souris et mˆ eme changer de langue vers l’anglais. Dans la langue respective, les instructions vont ˆ etre clairement indiqu´ ees. Assurez-vous que le programme et le dossier photos sont dans le mˆ eme r´ epertoire lors de l’ex´ ecution, sinon le programme ne pourra pas ex´ ecuter. 5 DESCRIPTION DES FONCTIONS i.main menu() La fonction main menu() agit comme notre main. Si on active la touche escape n’im- porte o` u dans le programme, on se fait ramener ici. On a un bouton anglais/fran¸ cais ainsi que trois options pour visualiser les algorithmes. ii.game(SELECTION,francais) Selon le choix de langue et de tableau, cette fonction fait appel aux instructions et au tableau respectif. Par suite, cette fonction appelle nos 4 algorithmes. On ex´ ecute les algorithmes une premi` ere fois avec une animation, ensuite chaque algorithme ex´ ecute 4 fois sans animation. Une moyenne est prise pour chaque algorithme. iii.reponses(arrReponses, francais) Cette fonction prend les r´ esultats de la fonction pr´ ec´ edente, s´ electionne le meilleur algorithme selon notre heuristique et ensuite aﬃche les r´ esultats. En fait, cette fonc- tion agit comme le driver, tous les calculs de la r´ eponse ﬁnale sont faits ici. 3 iv.aStar(draw, grid, start, end,num, FR) Cette fonction s’agite de notre impl´ ementation de l’algorithme A*. Il garantit tou- jours le meilleur chemin en utilisant une combinaison de distance Manhattan et de poids des noeuds. Il retourne la longueur du chemin, le temps requis et le nombre de noeuds visit´ es. v.dijkstra(draw, grid, start, end,num) Cette fonction s’agite de notre impl´ ementation de l’algorithme Dijkstra. Il garantit toujours le meilleur chemin en utilisant le poids des noeuds. Il retourne la longueur du chemin, le temps requis et le nombre de noeuds visit´ es. vi.bfs(draw, grid, start, end,num) Cette fonction s’agite de notre impl´ ementation de l’algorithme Breadth First Search ou recherche en largeur. Il garantit toujours le meilleur chemin, cependant il ne suit aucune heuristique pour arriver ` a cette r´ eponse. Il retourne la longueur du chemin, le temps requis et le nombre de noeuds visit´ es. vii.dfs(draw, grid, start, end,num) Cette fonction s’agite de notre impl´ ementation de l’algorithme Depth First Search ou recherche en profondeur. Il ne garantit pas toujours le meilleur chemin,comparativement aux autres algorithmes il peut ˆ etre tr` es lent. Il retourne la longueur du chemin, le temps requis et le nombre de noeuds visit´ es. 6 IMPL´ EMENTION DE LA M´ ETHODE N-VERSIONS 6.1 N-VERSION Nous respections les principes de N-Versions, on a A*, Dijkstra, Breadth-ﬁrst search et Depth-ﬁrst search qui retrouvent tous un parcours. Leur choix est tr` es simple ; premi` erement, ce sont des algorithmes qui ont d´ ej` a ´ et´ e couverts dans autres cours du d´ epartement, alors leurs impl´ ementations ´ etaient famili` ere. Deuxi` emement, on peut dire que chaque algorithme a ses avantages ainsi que ses d´ esavantages. A*, Dijkstra et BFS donnent toujours le chemin le plus court. 4 Cependant, leurs m´ ethodes de recherches diﬀ` erent l’un ` a l’autre. DFS n’a pas tou- jours le chemin le plus court, mais peut ˆ etre tr` es rapide dans certaines situations. Ces diﬀ´ erents points m` enent ` a des comparaisons plus int´ eressantes, ainsi que des sc´ enarios qui testent plus le driver. 6.2 DRIVER Chaque algorithme est tourn´ e 5 fois. Cependant, la d´ emonstration visuelle de son chemin est seulement faite durant son premier appel. Trois aspects de nos pro- grammes sont v´ eriﬁ´ es durant l’ex´ ecution du programme. Le plus important pour nous est la longueur du chemin. Pour ce devoir, nous voulant le chemin le plus court entre le point A et le point B. Trois des quatre algorithmes nous donne le chemin le plus court chaque fois. DFS est tr` es souvent plus long, mais dans certaines situations, il peut avoir la mˆ eme longueur de chemin que les autres. On v´ eriﬁe ensuite le temps pris par chaque algorithme. On tourne 5 fois pour avoir une moyenne des temps. Ceci oﬀre un niveau de pr´ ecision un peu plus haut compar´ e ` a un seul calcul. Dans une situation plus avanc´ ee, on pourrait facilement tourner plus que 5 fois pour avoir un temps encore plus pr´ ecis, mais ce niveau de pr´ ecision est bon assez pour un devoir. Le temps est en secondes, arrondi ` a 7 points apr` es la virgule. Il est rare qu’un algorithme prenne plus qu’une seconde, mais ceci pourrait facilement arriver sur une vieille machine. G´ en´ eralement, le choix du meilleur algorithme serait fait ` a l’´ etape du temps. Celui avec le chemin le plus court et qui prend le moins de temps ` a trouver celui-ci est ´ evidemment le meilleur. Cependant, qu’est-ce qui arrive si les temps sont identiques ? Ce cas s’est r´ eellement arriv´ e durant les tests. Pour avoir un dernier ≪tie-breaker ≫, nous v´ eriﬁons le nombre de nœuds visit´ es par chaque algorithme. Ce facteur ´ etudie la complexit´ e spatiale, ce qui est moins important pour nous dans ce cas. G´ en´ eralement, ce chiﬀre sera diﬀ´ erent pour A* et DFS. Cependant, dans le cas de Dijkstra et BFS, ils auront toujours l’exact mˆ eme nombre. Heureusement, il est presque sˆ ur que cette comparaison ne sera pas n´ ecessaire. Ces deux sont tr` es similaires visuellement, mais leur eﬃcacit´ e est diﬀ´ erente, alors leurs temps devraient toujours varier. Lorsque les calculs sont faits, le meilleur algorithme est soulign´ e, ainsi que toutes ses valeurs. 5 7 PORT´ EE FUTURE Seulement une erreur a ´ et´ e trouv´ ee pendant nos tests. Parfois, lorsqu’un chemin est trop court ( 9 blocs de distance entre le d´ ebut et la ﬁn), le temps pris par l’algorithme est aﬃch´ e comme 0.0. Ceci semble arriver exclusivement lorsque le programme est tourn´ e sur Windows. Puisque nous avons compl` etement r´ edig´ e ce programme en travaillant sur Linux, ce probl` eme est seulement apparu vers la ﬁn du d´ eveloppement, lorsque nous avons ﬁnalement test´ e notre programme sur un autre syst` eme d’op´ eration. Avec plus de temps, une v´ eriﬁcation en d´ etail du bogue pourrait uploads/Litterature/ devoir-1-info4009.pdf