[Info 7] - Exemples d'algorithmes opérant sur un arbre. Applications. (Page 1) / Leçons de Capes / Forum de mathématiques - Bibm@th.net

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 : 88

[Info 7] - 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.

Hors ligne

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

Enalo
Invité

Re : [Info 7] - 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 : 88

Re : [Info 7] - 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 7] - 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 : 88

Re : [Info 7] - 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 7] - 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 : 4 394

Re : [Info 7] - 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 7] - 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 : 4 394

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

Hello,

  Je pense que c'est effectivement hors-sujet.

F.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer

Les questions suivantes sont faites pour éviter le spam. Si vous voulez ne plus les avoir, inscrivez-vous!

Quel est le résultat de 27+78?

Quel est le 2 ième chiffre de 2980335?

Pied de page des forums

[ Générées en 0.056 secondes, 11 requêtes exécutées - Utilisation de la mémoire : 2.12 MiB (pic d'utilisation : 2.41 MiB) ]