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).

Répondre

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 neuf moins cinq
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.

Retour

Résumé de la discussion (messages les plus récents en premier)

capesman
27-11-2018 21:21:27

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.

Fred
06-05-2017 13:25:05

Hello,

  Je pense que c'est effectivement hors-sujet.

F.

Enalo
06-05-2017 12:35:15

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

Fred
05-05-2017 12:45:22

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.

Enalo
05-05-2017 11:52:03

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

capesman
22-04-2017 21:04:25

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.

quentinrt
22-04-2017 16:21:17

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...

capesman
21-04-2017 21:36:58

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

Enalo
21-04-2017 17:59:42

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 !

capesman
19-11-2016 00:43:38

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.

Pied de page des forums