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

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 moins soixante neuf
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