Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 19-11-2016 00:44:22
- capesman
- Modérateur
- Inscription : 15-08-2016
- Messages : 152
[Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,
Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'algorithmes opérant sur un graphe. Applications.
Capesman.
Hors ligne
#2 03-02-2017 21:25:45
- Capeswomen
- Invité
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonsoir, je souhaiterai savoir si quelqu'un sait ce qui est attendu dans cette leçon? Merci
#3 04-02-2017 11:51:59
- capesman
- Modérateur
- Inscription : 15-08-2016
- Messages : 152
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,
Je pense (sans en être tout à fait sûr...) que l'on attend des algorithmes du type de ceux que l'on met en place en Terminale ES (spécialité) et dans une moindre mesure en Terminale S sur les graphes, comme par exemple :
* recherche de plus court chemin dans un graphe (algorithme de Dijkstra)
* coloration d'un graphe
* recherche de chaines ou de cycles eulériens
* simuler une marche aléatoire dans un graphe probabiliste
* ....
Je pense aussi qu'il faut montrer que l'on sait utiliser des outils adaptés : tableur, python,.....
Capesman.
Hors ligne
#4 18-04-2017 13:56:38
- 171Caralone
- Invité
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,57
Pensez vous que l'on demande uniquement de présenter ce genre d'algorithme et leurs éventuelles implémentations informatiques ? ou bien attend-on également que l'on reprenne le cours théorique sur les graphes (définition de la notion de graphe, de graphe orienté, de graphe connexe, de chemin, de cycle etc.) ? La deuxième option me paraît un peu longue.
Merci pour vos avis,
Bonne journée
#5 18-04-2017 21:22:22
- capesman
- Modérateur
- Inscription : 15-08-2016
- Messages : 152
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,
Refaire le cours théorique sur les graphes me semblerait hors-sujet. En revanche, on peut (doit?) rappeler pour chaque algorithme la notion que l'on cherche à implémenter. Par exemple, définir ce qu'est une coloration, etc...
Capesman.
Dernière modification par capesman (18-04-2017 21:22:34)
Hors ligne
#6 19-04-2017 09:33:52
- Caralone
- Invité
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,
Merci pour la réponse, c'est ce que je pensais aussi mais un deuxième avis est toujours bon à prendre !
#7 27-11-2018 21:24:23
- capesman
- Modérateur
- Inscription : 15-08-2016
- Messages : 152
Re : [Info 8] - Exemples d'algorithmes opérant sur un graphe. Applications.
Bonjour,
Le rapport du jury 2018 précise les attendus pour cette leçon :
"L'objectif de cette leçon est la présentation des algorithmes classiques sur les graphes. Aucune connaissance théorique sur les objets manipulés ne sera 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 graphes orientés ou non orientés.
On pourra considérer plusieurs implémentations des arbres : à l'aide de matrices d'adjacence, à l'aide de liste d'adjacence entrantes ou sortantes, etc.
Comme pour les arbres, on pourra s'intéresser aux algorithmes de parcours : en profondeur, en largeur, etc.
On pourra aussi s'intéresser aux problèmes de détermination de chemins optimaux dans des graphes valués. L'algorithme le plus
célèbre est certainement celui de Dijkstra. Il en existe d'autres, par exemple l'algorithme de Floyd-Warshall qui ramène le problème au calcul des exposants d'une matrice. On pourra aussi s'intéresser à des problèmes de recherche de flot maximal dans un graphe
valué, quoiqu'ils soient un peu plus complexes.
On pourra aussi envisager des problèmes d'étude de la structure d'un graphe, par exemple déterminer la composante simplement (ou fortement) connexe d'un nœud, le nombre de composantes connexes, l'arbre des composantes connexes, ou encore calculer des paramètres structurels comme le nombre chromatique, la taille de la plus grande clique, etc.
Un algorithme facilement programmable en Python est le parcours en profondeur ou en largeur, qui peut être ensuite utilisé pour compter le nombre de composantes connexes.
Capesman
Hors ligne