Remerciez-le!

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

Ministère de l’enseignement supérieur et Recherche scientifique Université de l

Ministère de l’enseignement supérieur et Recherche scientifique Université de la Manouba Ecole Nationale des Sciences Informatique Simulation Graphique des traitements sur les Arbres Binaires Rapport de stage de programmation élaboré par : EDDAHECH Soumaya KHAYAT Arwa Année Universitaire : 2010 - 2011 Remerciement En préambule à ce rapport, nous souhaitions adresser nos remerciements les plus sincères aux personnes qui nous ont apportées leur aide et qui ont contribué à l'élaboration de projet. Nous tenons à remercier dans un premier temps, toute l’équipe pédagogique de l’Ecole Nationale des Sciences Informatiques, pour nous avoir donné l’occasion d’effectuer ce stage d’été dans les meilleures conditions possibles. Nous remercions également Mademoiselle Ben Ali et Madame Souileh pour l’aide et les conseils concernant les missions évoquées dans ce rapport, qu’ils nous ont apportés lors des différents suivis. Nous espérons que ce travail soit au niveau de leurs attentes et de la confiance qu’ils ont bien voulu nous donner. Nous n'oublions pas nos parents pour leur contribution, leur soutien et leur patience. Enfin, nous adressons nos plus sincères remerciements à tous nos proches et amis, qui nos ont toujours soutenues et encouragées au cours de la réalisation de ce projet. Merci à tous et à toutes. Table des figures Figure1.1 Le parcours en largeur ……………….......................................................................8 Figure1.2 Le parcours préfixe ………………………………….……….………………..…....8 Figure1.3Le parcours infixe …………………………………….………………………….….8 Figure1.4 Le parcours post fixe …………………………………...…………...…….……..…8 Figure1.5 Les fonctionnalités offertes par l’application……………….………………….….11 Figure2.1 Le splashscreen de l’application………………………...…….…………………..14 Figure2.2 La fenêtre principale …………...…………………………….…………………....15 Figure2.3 La fenêtre de dialogue de l’opération de création……...…………….…….…..….17 Figure2.4 La fenêtre de dialogue de l’opération de recherche d’un élément dans l’arbre…....18 Figure2.5 La fenêtre de dialogue de l’opération de calcul de la taille.……………….……....20 Figure2.6 La fenêtre de dialogue de l’opération de calcul de nombre de feuilles……..……..21 Figure2.7 La fenêtre de dialogue de l’opération de transformation..………..……..…....……22 Figure2.8 La fenêtre de dialogue de l’opération d’ajout………….. ………………...……….23 Figure2.9 La fenêtre de dialogue de l’opération de suppression..…………………..….….....24 Figure3.1 Modularité de l’application……………………..……………… ..…….…..…......27 Figure3.2 Format d’un fichier représentant un arbre binaire……………… ..…….…..…......34 Table des matières Introduction .................................................................................... 5 Chapitre1: Présentation du projet ............................................. 6 1.2 Motivation du travail .......................................................................................................................... 6 1.1 Intégration du TIC dans l’enseignement .............................................................................................. 6 1.3 Les arbres binaires .............................................................................................................................. 7 1.4 Travail demandé ............................................................................................................................... 10 2.1 Fonctionnalités à implémenter .......................................................................................................... 10 2.2 Critères d’évaluation ......................................................................................................................... 11 2. Langage de programmation ....................................................................................... 12 3.1 Solutions envisageables .................................................................................................................... 12 2.2 Solution retenue ............................................................................................................................... 12 2.3 Conclusion ........................................................................................................................................ 13 Chapitre2 :Conception de l’interface ....................................... 14 1. Le splashscreen .................................................................................................................................... 14 2. La fenêtre principale ............................................................................................................................ 15 3. les fenêtres de dialogues ...................................................................................................................... 16 3.1 Création d’un arbre binaire ............................................................................................................... 17 3.2 Recherche d'un élément dans un arbre binaire .................................................................................. 18 3.3 Calcul de la taille .............................................................................................................................. 20 3.4 Calcul du nombre de feuille .............................................................................................................. 21 3.5 Création d'un arbre binaire de recherche .......................................................................................... 22 3.6 Adjonction d'un élément .................................................................................................................. 23 3.7 Suppression d'un élément .................................................................................................................. 24 4. Conclusion ................................................................................................................... 25 Chapitre3: Implémentation des fonctionnalités…… ............. 26 1. Modularité ............................................................................................................................................ 26 2. Présentation des principales classes ...................................................................................................... 27 2.1 Module affichage ............................................................................................................................... 27 2.2 Module traitement .............................................................................................................................. 28 2.3 Module de gestion de fichiers ........................................................................................................... 33 3. Améliorations possibles ........................................................................................................................ 35 3.1 Utiliser les onglets ............................................................................................................................ 35 3.2 Pouvoir imprimer les arbres ............................................................................................................ 35 3.3 Intégration d’autres fonctionnalités ................................................................................................. 35 3.4 Discussion en ligne........................................................................................................................... 36 4. Conclusion ............................................................................................................................................ 36 Conclusion…. ................................................................................. 37 Annexe…. ........................................................................................ 38 Département Informatique 5 EDDAHECH.S & KHAYAT.A /2010 Introduction L’évolution des technologies de la communication d’une part et l’analyse des besoins en matière de formation après les reformes des enseignements supérieurs d’autre part amènent la communauté universitaire à s’intéresser à l’intégration des technologies de l’information et de la communication dans l’enseignement. Mais l’utilisation des nouvelles technologies n’est pas en elle-même un objectif, néanmoins c’est un support sur lequel on peut se baser afin de proposer une nouvelle approche méthodologique dans l’enseignement. En algorithmique, l’exploitation de tel technologie a pour objectif fondamental de résoudre un problème majeur rencontrant les étudiants qui est la compréhension. C’est dans ce contexte que se situe ce travail qui consiste à la réalisation d’une application pédagogique à l’usage des enseignants et leurs étudiants. Celle-ci doit être un support de cours d’algorithmique sur les arbres ainsi qu’une base de travail individuel pour chaque étudiant. Cette application s’appuie particulièrement sur la visualisation d’algorithmes. Elle doit faciliter la compréhension de ces algorithmes en déroulant ceux-ci tout en montrant les modifications subies par l’arbre. Ce rapport s’articule ainsi en trois parties. Le premier chapitre est consacré à la présentation du projet, l’analyse et à la spécification des besoins, il contient une explication détaillée des exigences auxquelles notre application doit répondre. Le chapitre suivant développe la conception de l’application et décrit l’environnement de développement et les différentes techniques utilisées lors du développement de l’application. Projet d’été Présentation du projet Département Informatique 6 EDDAHECH.S & KHAYAT.A /2010 Chapitre I Présentation du projet Dans le cadre de notre formation d’ingénieurs informaticiens à l’Ecole Nationale des Sciences de l’Informatique, nous avons eu l’occasion d’effectuer notre projet d’été qui consiste à la réalisation d’une application pédagogique facilitant la manipulation d’arbres binaires. Dans ce chapitre, nous présentons le cadre général de notre projet. En effet, nous commençons par découvrir le sujet du projet. Ensuite nous présentons les diverses fonctionnalités à implémenter. I. Motivation du travail La compréhension des algorithmes constitue un problème qui se pose à chacun de l’étudiant en informatique, à l’enseignant d’algorithmes, et encore au concepteur d’algorithme. Ce problème est complexe car il demande d’établir une relation entre un objet statique algorithme et un objet dynamique qui est son exécution. Afin d’assurer la compréhension de ce dernier, la meilleure solution était de le visualiser et de le voir s’exécuter suivant la citation de Donald Ervin Knuth : « An algorithm must be seen to be believed. » et en exploitant l’intégration des technologies de l’information et de la communication dans l’enseignement. 1. Intégration de TIC dans l'enseignement Les TIC1s sont à l’origine de grandes innovations dans tous les secteurs d’activité à travers le monde entier. Cette révolution inclue aussi le domaine éducatif qui s’est évolué grâce à elle. La question qui se pose maintenant est : Comment peut-on profiter des facilités apportées par les TICs et améliorer la qualité de l’enseignement et de l’apprentissage? Les TICs s’imposent de plus en plus comme support incontournable dans l’apprentissage des différents savoirs et comme moyen d’exécution pratique en même temps ce qui justifie la 1 Les technologies de l’information et de la communication Projet d’été Présentation du projet Département Informatique 7 EDDAHECH.S & KHAYAT.A /2010 citation de Debray : «Si les technologies ne permettent pas d’accomplir le processus de transmission de connaissances dans son intégralité, elles en facilitent certains mécanismes». En effet, l’étudiant apprend à être autonome et à s’ouvrir sur différents ressources pédagogiques. En plus, ils lui offrent une illustration pratique de toutes connaissances théorique : en algorithmique par exemple, la visualisation des algorithmes est l’une des meilleures méthodes facilitant leurs compréhension. Les arbres binaires constituent l’une des plus importantes structures de données d’une part et l’une des plus difficiles à apprendre et à enseigner de l’autre ce qui amènent beaucoup d’informaticien à penser à résoudre ce problème en réalisant des applications pédagogiques traitant cette structure. 2. Les arbres binaires Dans cette section on va s’intéresser à présenter les arbres binaire en tant structures de donné se caractérisant par un ensemble d’opérations élémentaires facilitant leurs manipulation en vue de présenter par la suite leurs utilités. 2.1. Définition et Opérations élémentaires 2.1.1 Définition Un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit. 2.1.2 Opérations élémentaires Les arbres binaires représentent une structure de données très utilisée. En effet, ce type de structure si elle est bien utilisée donne de très bonnes performances. Afin de bien manipuler la structure arborescente on doit d’abord la maitriser. Création d’un arbre binaire On peut distinguer deux types de création d’un arbre : création d'un arbre vide, et création d'un arbre à partir d'un élément et de deux sous arbres. Calcul de la taille Pour compter la taille d'un arbre, on calcule, pour chaque nœud qui existe, une somme égale à un à laquelle on additionne la somme des nœuds du fils gauche et la somme des nœuds du fils droit. Calcul de nombre de feuilles Projet d’été Présentation du projet Département Informatique 8 EDDAHECH.S & KHAYAT.A /2010 Le calcul du nombre de feuille repose sur la définition récursive suivante: - un arbre vide n'a pas de feuille. - un arbre non vide a son nombre de feuille défini de la façon suivante : - si le nœud est une feuille alors on renvoie 1 - si c'est un nœud interne alors le nombre de feuille est la somme du nombre de feuille de chacun de ses fils. Parcours en largeur et parcours en profondeur Parcours en largeur Le uploads/Science et Technologie/ simulation-graphique-des-traitements-sur-les-arbres-binaires.pdf