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)?
vingt deux plus dix
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:24:23

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

Caralone
19-04-2017 09:33:52

Bonjour,

Merci pour la réponse, c'est ce que je pensais aussi mais un deuxième avis est toujours bon à prendre !

capesman
18-04-2017 21:22:22

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.

171Caralone
18-04-2017 13:56:38

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

capesman
04-02-2017 11:51:59

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.

Capeswomen
03-02-2017 21:25:45

Bonsoir, je souhaiterai savoir si quelqu'un sait ce qui est attendu dans cette leçon? Merci

capesman
19-11-2016 00:44:22

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.

Pied de page des forums