Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 19-11-2016 00:43:38

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

[Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'algorithmes opérant sur un arbre. Applications.

Capesman.

Dernière modification par capesman (27-11-2018 21:00:52)

Hors ligne

#2 21-04-2017 17:59:42

Enalo
Invité

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

Quelqu'un aurait-il des idées d’algorithmes opérant sur des graphes ?
J'ai pensé aux algorithmes de recherche de maximum ou minimum sur des arbres binaires de recherche.
Les arbres étant des cas particuliers de graphe les même algorithmes s'y appliquent mais je ne vois pas bien pourquoi mettre deux intitulés de leçon dans ce cas (une sur les graphe et un sur les arbres).

Merci d'avance si vous avez des conseils !

#3 21-04-2017 21:36:58

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

  J'imagine que tu parles d'algorithmes sur les arbres. Je crois qu'il y en a beaucoup :
* savoir si un élément est dans un arbre (ordonné) ou non
* la recherche d'un arbre recouvrant de poids minimal pour un graphe connexe (c'est beaucoup plus sophistiqué!). Voir par exemple http://www.irem.univ-bpclermont.fr/IMG/ … uvrant.pdf
* le tri par tas construit un arbre pour fonctionner (à mon avis, très intéressant à mettre dans cette leçon)
* concernant les arbres binaires de recherche, on peut encore penser aux algorithmes d'ajout d'un élément ou de suppression d'un élément
* peut-être qu'on peut parler aussi du calcul de la hauteur d'un arbre, des problèmes de parcours....

En tous les cas, il faut penser à des algorithmes spécifiques aux arbres et pas à des algorithmes sur les graphes.

Capesman

Hors ligne

#4 22-04-2017 16:21:17

quentinrt
Invité

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour, Les lecons s’appuient sur les programmes scolaires suivants :
– le thème E (algorithmique et programmation) du programme de cycle 4 ;
– le programme d’algorithmique de la classe de Seconde (et suivantes) ;
– le programme de l’enseignement de spécialité ISN (classes terminales S) ;
– le programme d’algorithmique appliquée du BTS SIO.
Mais il me semble qu'aucun de ses programmes ne parlent des arbres?! Du coup je ne comprends pas quelles sont les attentes pour cette leçon...

#5 22-04-2017 21:04:25

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

  Je suis presque d'accord avec toi. Dans le programme de BTS, il est fait mention d' "arborescence", avec le commentaire suivant "La notion de connexité étant hors programme, on se limite à la présentation d’exemples simples d’arborescences à partir de leur représentation géométrique, sans recherche d’une caractérisation générale. " (ceci apparaît dans le thème graphes).
Dans le programme d'ISN, on parle aussi d'arborescence dans "Structuration et organisation des données" en disant "Classer des informations, notamment sous forme d'arborescence" et les commentaires parlent notamment des systèmes de fichiers. On en parle enfin dans le Routage (réseaux) : "on explique la différence entre les réseaux de type arborescent et de type graphe".
Les algorithmes associés à tous ces problèmes sont donc plus ou moins réellement au programme. Et puis, il ne faut pas oublier que "Cependant, le candidat doit pouvoir traiter ces questions avec le recul correspondant au niveau M1 du cycle Master."

Capesman.

Hors ligne

#6 05-05-2017 11:52:03

Enalo
Invité

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

Je ne vois pas bien ce qu'on veut dire par "la différence entre les réseaux de type arborescent et de type graphe".
J'ai l'impression que tous les réseaux peuvent contenir des cycles et donc être de type graphe. Je ne vois pas quels sont les réseaux de type arborescent. Quelqu'un peut-il m'éclairer ?

Merci d'avance

#7 05-05-2017 12:45:22

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Hello,

  Je n'y connais absolument rien, mais j'ai l'impression que chez moi, j'ai un réseau en arbre : c'est ma box qui gère le réseau, mon portable et mon imprimante sont liés à ma box mais ne communiquent pas directement entre eux.
Après une petite recherche google, il semble que l'autre nom est "réseau hiérarchique".

J'espère que cela t'éclaire un peu,
Fred.

Hors ligne

#8 06-05-2017 12:35:15

Enalo
Invité

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

Merci pour ta réponse Fred, effectivement je vois un peu mieux comment présenter ça avec ton exemple.

Je me pose une autre question par rapport à la recherche d'un arbre recouvrant de poids minimal pour un graphe. Cet algorithme s'opère sur un graphe pour obtenir un arbre. Est ce que ce n'est pas hors sujet sachant que le titre de la leçon est "Exemple d'algorithme opérant sur un arbre" ?
Je parle de ce type d'algorithme dans la leçon sur les graphe mais je me demande si je peux également l'introduire dans la leçon sur les arbres.

Merci d'avance pour vos avis sur la question

#9 06-05-2017 13:25:05

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Hello,

  Je pense que c'est effectivement hors-sujet.

F.

Hors ligne

#10 27-11-2018 21:21:27

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

Re : [Info 6] - Exemples d'algorithmes opérant sur un arbre. Applications.

Bonjour,

  Le rapport de jury 2018 comporte quelques éclaircissements sur les attendus de cette leçon :

"L'objectif  de  cette  leçon  est  la  présentation  des  algorithmes  classiques  sur  les  arbres.  Aucune connaissance théorique sur les objets manipulés ne pourra être demandée, mais le recul de niveau M1 doit permettre aux candidats de discuter du coût des algorithmes présentés.

On pourra s'intéresser aux algorithmes de parcours: en profondeur, en largeur, etc. On insistera sur les  liens  entre  le  parcours  en  profondeur  et  l'utilisation  d'une  pile,  le  parcours  en  largeur  et l'utilisation d'une file.

On pourra envisager les arbres étiquetés pour gérer arbres de recherche, et poser la question de leur équilibrage.
On pourra aussi faire le lien entre les arbres et la représentation des expressions arithmétiques, par  exemple.  On  pourra  discuter  de  l'interprétation  des  divers  ordres  de  parcours  d'arbres  par rapport à la présentation préfixée, infixée ou postfixée des expressions.

Pour une implémentation en Python, on pourra coder un arbre sous forme d'une liste de listes. Un
nœud est alors une liste contenant une étiquette et une liste de fils, éventuellement vide.

Un  algorithme  facilement  programmable  en  Python  dans  cette  approche  est
le  parcours  en  profondeur. Le parcours en largeur est plus complexe car il fait nécessairement appel à une file.
On  pourra  aussi  facilement  implémenter  les  opérations  sur  les  arbres  de  recherche  (sans rechercher l'équilibrage).

Capesman.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante six plus quarantesix
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums