Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
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.