tc_info:2023-tp-texte

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
tc_info:2023-tp-texte [2023/12/05 09:37] – edaucetc_info:2023-tp-texte [2024/12/03 23:53] (Version actuelle) – edauce
Ligne 1: Ligne 1:
 +==== Arbre lexicographique ====
  
 +Un algorithme de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple.
 +
 +On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si celui-ci est final ou non (le nœud est final si le compteur est >0).
 +
 +Le but de cet exercice est de construire un arbre lexicographique à partir de mots de vocabulaire, puis de l'utiliser pour compléter un début de mot proposé par l'utilisateur.
 +
 +Vous devez implémenter un arbre lexicographique en Java pour gérer une base de mots et répondre à différentes requêtes, telles que l'insertion de mots, l'affichage de l'arbre, la suggestion de mots complets à partir d'un préfixe donné, etc.
 +
 +<note tip>
 +V = {art, arbre, des, dessin}
 +
 +{{:tc_info:arbre_completion.png|700}}
 +</note>
 +
 +=== 1. Définition des Classes ===
 +
 +a. Définissez une classe ''Noeud'' avec les attributs suivants :
 +      - ''terminal'' : un booléen indiquant si le nœud représente la fin d'un mot.
 +      - ''compteur'' : un entier indiquant le nombre d'occurrences du mot.
 +      - ''aretes'' : une liste d'objets de type ''Arete''.
 +
 +b. Définissez une classe ''Arete'' avec les attributs suivants :   
 +      - ''caractere'' : un caractère représentant la relation entre deux nœuds.
 +      - ''noeud'' : un objet de type ''Noeud'' représentant le nœud suivant.
 +
 +c. Pour initialiser un arbre lexicographique, créer un nœud vide dont le ''compteur'' vaut 0 et dont la liste des arêtes est une liste (''ArrayList'') vide. 
 +
 +=== 2. Fonction d'Insertion ===
 +
 +Écrivez une méthode ''insererMot'' dans la classe ''Noeud'' pour insérer un mot dans l'arbre. 
 +  * La fonction est récursive
 +  * Elle prend comme argument une chaîne de caractères
 +
 +<note tip>
 +  * **Cas terminal** :
 +Si le mot est vide, cela signifie que tous les caractères du mot ont été insérés. Dans ce cas, on met à jour l'attribut ''terminal'' du nœud actuel à ''true'' (pour indiquer que c'est la fin d'un mot) et on incrémente le compteur associé.
 +
 +  * **Cas Récursif** :
 +On prend le premier caractère du mot (la première lettre) et on cherche une arête dans le nœud actuel qui a ce caractère.
 +    * S'il existe une telle arête, on appelle récursivement ''insererMot'' avec le nœud correspondant à cette arête et le reste du mot (tous les caractères sauf le premier).
 +    * Si l'arête n'existe pas, on crée une nouvelle arête avec ce caractère et un nouveau nœud associé. Ensuite, on appelle récursivement ''insererMot'' avec le nouveau nœud et le reste du mot.
 +</note>
 +
 +<note>
 +**Extraire le Premier Caractère :**
 +Utilisez la méthode ''charAt(index)'' de la classe ''String'' pour obtenir le caractère à l'index spécifié.
 +
 +Exemple :
 +<code java>
 +String mot = "bonjour";
 +char premierCaractere = mot.charAt(0);
 +</code>
 +
 +**Obtenir la Chaîne Initiale Privée du Premier Caractère :**
 +Utilisez la méthode ''substring(beginIndex)'' de la classe ''String'' pour obtenir la sous-chaîne à partir de l'index spécifié.
 +
 +Exemple
 +<code java>
 +String mot = "bonjour";
 +String resteDuMot = mot.substring(1);
 +</code>
 +</note>
 +
 +
 +
 +=== 3. Fonction d'Affichage ===
 +
 +3.1 Écrivez une méthode ''affiche'' dans la classe ''Noeud'' pour afficher la totalité de l'arbre de complétion. La fonction doit respecter les conditions suivantes :  
 +  * Elle doit parcourir l'arbre de manière récursive.
 +  * Elle doit afficher chaque mot complet trouvé ainsi que son compteur.
 +
 +3.2 Tests
 +
 +a. Créez un arbre de complétion vide.
 +   
 +b. Insérez les mots ''"chat"'', ''"chien"'', ''"chapeau"'', ''"bonjour"'', ''"bonsoir"'', ''"bon"'', ''"jour"'', ''"soir"'' dans l'arbre de complétion.
 +   
 +c. Affichez l'arbre pour vérifier que les mots sont correctement insérés.
 +
 +<note tip> **Concaténation**
 +
 +Vous pouvez créer une nouvelle chaîne qui combine le contenu de l'ancienne chaîne avec un nouveau caractère que vous souhaitez ajouter à la fin.
 +<code java>
 +String maChaine = "Hello";
 +char nouveauCaractere = '!';
 +maChaine = maChaine + nouveauCaractere;  // Crée une nouvelle chaîne
 +</code>
 +</note>
 +
 +
 +=== 4. Fonction d'Appartenance ===
 +
 +a. Écrivez une méthode ''appartient'' dans la classe ''Noeud'' qui retourne ''true'' si le mot est présent dans l'arbre de complétion et ''false'' sinon. La fonction doit respecter les conditions suivantes :  
 +  * Vous pouvez au choix utiliser une approche itérative ou récursive pour parcourir l'arbre.
 +  * La fonction doit retourner ''true'' uniquement si le mot complet est présent dans l'arbre (c'est à dire si la lecture de la dernière lettre conduit à un noeud terminal).
 +
 +b. Testez la fonction ''appartient'' avec les mots ''"chat"'', ''"maison"'', ''"soirée"'' et ''"bon"'', et affichez le résultat pour chaque test.
 +
 +<note> **la méthode ''toCharArray''**
 +
 +La méthode ''toCharArray()'' de la classe ''String'' en Java retourne un tableau de caractères qui représente la séquence de caractères de la chaîne.
 +<code java>
 +String maChaine = "Java";
 +char[] tableauDeCaracteres = maChaine.toCharArray();
 +</code>
 +ce qui peut être utile lorsque l'on veut examiner les caractères d'une chaîne de caractères un à un.
 +
 +exemple:
 +<code java>
 +for (char c : maChaine.toCharArray()) {
 +...
 +}
 +</code>
 +est une boucle permettant de parcourir un à un tous les caractères d'une chaîne.
 +</note>
 +
 +
 +=== 5. Fonction de Suggestion ===
 +
 +a. Écrivez une méthode ''suivant'' dans la classe ''Noeud'' pour retourner une liste de mots complets à partir d'un préfixe donné. La fonction doit respecter les conditions suivantes :
 +  * Elle doit utiliser une approche itérative de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
 +  * Elle doit faire appel à la fonction d'affichage du noeud atteint pour afficher l'ensemble des noeuds suivants
 +
 +b. Testez la fonction ''suivant'' avec les préfixe ''"bon"'', ''"ch"'', ''"pre"'', et affichez les résultats. 
 +
 +
 +   
 +
 +   
 +
 +
 +---