Représentations (arbres, mots, chemins) : vrai ou faux, Memory, texte à trous et remets dans l'ordre
Tle › Mathematiques › Combinatoire et dénombrement. Teste tes connaissances en quelques minutes, sans inscription : la correction s'affiche à chaque réponse.
Révision : les 20 affirmations corrigées
Un arbre de construction représente des choix successifs.
Vrai — Un arbre modélise exactement les choix effectués étape par étape.
Un mot est une suite d'éléments représentant une séquence.
Vrai — La définition du cours précise qu'un mot est une suite d'éléments (lettres, chiffres).
Un chemin est une suite de sommets reliés par des arcs.
Vrai — Le cours définit un chemin comme un parcours de sommets connectés par des arcs.
La racine se situe au niveau 0, sans lettre choisie.
Vrai — L'exemple indique que le niveau 0 est la racine, avant tout choix de lettre.
Dans l'exemple, le nombre de mots de longueur 3 sur {A, B} est \(2^3 = 8\).
Vrai — Avec 2 choix à chaque étape et 3 étapes, on a bien \(2^3=8\) mots possibles.
Le nombre de mots de longueur 4 sur {A, B, C} est \(3^4 = 81\).
Vrai — Il y a 3 choix à chaque étape pour 4 étapes, donc \(3^4=81\) possibilités.
Les arbres aident à visualiser toutes les combinaisons possibles.
Vrai — Le cours explique que suivre les branches d'un arbre montre toutes les combinaisons.
Le nombre total de chemins dépend du nombre de choix à chaque étape.
Vrai — Le cours rappelle que le dénombrement dépend du nombre de choix successifs.
On représente la construction des mots par un arbre avec un niveau par lettre.
Vrai — L'exemple montre un niveau par lettre choisie pour construire des mots.
Les mots peuvent représenter des séquences d'actions ou d'états.
Vrai — Le cours indique que les mots symbolisent des séquences d'actions ou d'états.
Le niveau 1 d'un arbre correspond à la racine.
Faux — La racine est au niveau 0; le niveau 1 suit la racine et contient le premier choix.
Pour compter les mots, on additionne les choix à chaque étape.
Faux — Le dénombrement se fait par produit des choix successifs, pas par addition.
Le nombre de mots de longueur 3 sur {A, B} est \(3^2 = 9\).
Faux — L'alphabet a taille 2, donc on calcule \(2^3\), pas \(3^2\).
Le nombre de mots de longueur 4 sur {A, B, C} est \(3^3 = 27\).
Faux — Avec 4 étapes il faut \(3^4\), donc \(3^3\) est incorrect pour 4 lettres.
Un chemin est toujours une suite de lettres dans un mot.
Faux — Un chemin parcourt des sommets et arcs; ce n'est pas nécessairement une suite de lettres.
Les arbres et les arborescences sont identiques sans nuance.
Faux — Le cours signale que confondre arbre de construction et arborescence structurée est une erreur.
Chaque nœud d'un arbre doit avoir le même nombre d'enfants.
Faux — Rien n'impose un nombre d'enfants identique pour chaque nœud dans le cours.
Visualiser par un arbre néglige la multiplicité des choix.
Faux — Au contraire, l'arbre met en évidence la multiplicité en suivant toutes les branches.
Le produit des choix successifs ne s'applique pas aux chemins.
Faux — Le cours indique que le nombre de chemins est déterminé par le produit des choix successifs.
Un mot est défini uniquement par les sommets d'un graphe.
Faux — Un mot est une suite d'éléments; il n'est pas défini uniquement par des sommets de graphe.
Les 10 notions à retenir
- Arbre
- Structure hiérarchique et orientée
- Mot
- Suite d'éléments représentant une séquence
- Chemin
- Parcours de sommets reliés par des arcs
- Racine
- Niveau 0, pas de lettre choisie
- Niveau
- Étape correspondant à un choix dans l'arbre
- Alphabet
- Ensemble de lettres disponibles pour les mots
- Arbre de construction
- Arbre montrant toutes les combinaisons possibles
- Nombre de mots
- Produit des choix successifs, soit \(k^n\)
- Visualisation
- Permet de suivre toutes les branches possibles
- Erreur fréquente
- Confondre niveaux ou oublier la multiplication
Les 15 phrases à connaître
Un arbre est une structure hiérarchique et orientée.
Un arbre organise les éléments selon des niveaux et des relations de parenté, d'où 'hiérarchique'.
La racine correspond au niveau 0 où aucune lettre n'est choisie.
Le cours précise 'Niveau 0 : racine' comme point de départ sans choix.
Dans un arbre de construction, chaque niveau correspond à un choix de lettre.
L'exemple utilise des lettres pour chaque choix à chaque niveau de l'arbre.
Un mot est une suite d'éléments représentant une séquence d'actions ou d'états.
Le cours définit un mot comme une suite d'éléments (lettres, chiffres) formant une séquence.
Le nombre de mots de longueur 4 sur l'alphabet \{A,B,C\} est \(3^4 = 81\).
Il y a 3 choix à chaque étape sur 4 étapes, d'où \(3^4 = 81\).
Dans l'exemple, le nombre total de mots de longueur 3 sur \{A,B\} vaut \(2^3 = 8\).
Avec 2 choix à chaque étape et 3 étapes, le nombre total est \(2^3 = 8\).
Un chemin dans un graphe est une suite de sommets reliés par des arcs.
Un chemin est décrit comme une suite de sommets successifs reliés par des arcs.
Pour compter les combinaisons, il faut multiplier le nombre de choix à chaque étape.
Le principe multiplicatif s'applique en multipliant les choix disponibles à chaque étape.
Les arbres permettent de visualiser toutes les combinaisons possibles en suivant des branches successives.
L'arbre illustre graphiquement toutes les combinaisons obtenues en suivant les branches.
Confondre arbre de construction et arborescence structurée est une erreur fréquente.
Le cours signale qu'on doit distinguer l'arbre de construction de l'arborescence structurée.
Les mots sont des suites d'éléments utilisées pour représenter une séquence ou une procédure.
Un mot représente une séquence d'actions ou d'états, comme expliqué dans la fiche.
Au niveau 1 de l'arbre de l'exemple, il y a des branches pour A et B.
L'exemple précise qu'au niveau 1 les branches correspondent aux lettres A et B.
La représentation par un mot transforme un parcours en une suite de symboles.
Transformer un parcours en mot revient à noter la suite ordonnée des symboles correspondants.
Le nombre de mots ou chemins dépend du nombre de choix à chaque niveau, pas seulement de la longueur.
Le cours insiste sur le fait que le total dépend du nombre de choix à chaque niveau.
Dans un arbre binaire, chaque niveau double le nombre de branches possibles si deux choix par étape.
Avec deux choix par étape (arbre binaire), le nombre de branches possibles double à chaque niveau.
Les 6 séries dans le bon ordre
Ordonner les niveaux d'un arbre de construction du début (racine) jusqu'aux mots finaux.
- Racine (niveau 0)
- Niveau 1 : premier choix
- Niveau 2 : deuxième choix
- Niveau 3 : résultats finaux
L'ordre suit la construction de l'arbre du niveau 0 (racine) vers les niveaux successifs aboutissant aux mots.
Ordonner les étapes pour compter le nombre total de mots en appliquant le principe multiplicatif.
- Identifier le nombre de choix à chaque étape
- Multiplier ces nombres
- Interpréter le produit comme le nombre total de mots
On commence par déterminer les choix, on multiplie ces quantités puis on lit le produit comme le total.
Ordonner les étapes pour représenter un chemin par un mot.
- Choisir un parcours dans le graphe
- Noter la suite de sommets traversés
- Écrire le mot correspondant à cette suite
On prend d'abord le parcours, on note la suite de sommets, puis on traduit cette suite en mot.
Ordonner les opérations pour calculer le nombre de mots de longueur 4 sur \{A,B,C\}.
- Constater qu'il y a 3 choix par étape
- Reconnaître qu'il y a 4 étapes successives
- Écrire la formule \(3^4\)
- Calculer \(3^4 = 81\)
On identifie le nombre de choix et d'étapes, on écrit la puissance correspondante puis on calcule le résultat.
Ordonner les vérifications pour éviter la confusion entre arbre de construction et arborescence.
- Vérifier la distinction entre niveaux
- Vérifier les choix disponibles à chaque niveau
- Vérifier la multiplicité et les contraintes
Il faut d'abord distinguer les niveaux, puis contrôler les choix par niveau et enfin les contraintes qui affectent le dénombrement.
Ordonner les choix successifs pour construire un mot de longueur 3.
- Choisir la 1ère lettre
- Choisir la 2ème lettre
- Choisir la 3ème lettre
- Obtenir le mot de longueur 3
La construction d'un mot se fait lettre par lettre dans l'ordre des étapes jusqu'à obtenir le mot final.