Algorithme de Dijkstra

samok0
samok0
dans Les-mathématiques
Bonsoir

j'ai regardé plusieurs livres de Terminale ES, je n'arrive pas à me convaincre que l'algorithme de Dijkstra marche.

Merci de l'aide et des arguments que vous pourrez m'apporter

S

Réponses

  • Logicien
    Logicien
    Bonsoir,

    Et pourtant il marche !
    Puisqu'à chaque étape, on met à jour les distances partielles en prenant le minimum des distances parcourues depuis le sommet de départ jusqu'au sommet courant .

    Cordialement
  • samok0
    samok0
    Je vais faire plus d'exemples pour m'en convaincre, car l'argument que vous me donnez ne me convainc pas mais me donne à réfléchir, merci.

    Je trouve étrange qu'il n'y ait pas une petite phrase en français pour expliquer l'idée de l'algorithme dans les cours de T ES que j'ai vu. Je serais ravi qu'un candidat au bac m'explique.

    Aimablement,
    S
  • J2L21
    J2L21
    ... ça marche aussi bien pour les graphes non orientés que pour les graphes orientés.
  • Logicien
    Logicien
    Bonsoir

    Dans le cours de Vincent Bouchitté figure une démonstration par récurrence.
    Lien : <http://wwwens.uqac.ca/~nlandry/reseaux/note_graphes.pdf&gt;

    Voici une présentation sympa de la mise en oeuvre de l'algorithme faite par une équipe de Bordeaux
    Lien : <http://mathematiques.ac-bordeaux.fr/peda/lyc/seqdocped/graphes/paf_02-03/dijkstra.pdf&gt;

    Cordialement
  • samok0
    samok0
    Merci

    S
  • CédricTjrsPasLoggué
    CédricTjrsPasLoggué
    hehe ce cours me rappelle quelques choses :)
    Plus sérieusement, à quelle occasion fait-on des graphes en Terminale ?
    J'imagine qu'on ne doit pas faire de preuve des algorithme (terminaison, correction ...), on nous donne simplement l'algorithme en demandant de croire très très fort que le prof ne ment pas quand il dit que ça marche ?
  • Yama
    Yama
    Les graphes sont au programme de terminale ES depuis 3 ou 4 ans je pense.
  • FrançoisD
    FrançoisD
    salut,

    les graphes sont au programme de spécialité de TES depuis 2002

    raison? bassement individualiste, l'un des "experts" de la commission voulait placer ses poulains en fac et trouver des spécialistes de graphes en maths c'est pas si facile...

    (il l'a reconnu à mots couverts dans une conférence)

    amicalement,

    F.D.

    PS: son idée a fonctionné pouisque les graphes sont au CAPES... :-)
  • Domi
    Domi
    Personnellement , je trouve la théorie des graphes ( longtemps ignorée en france ) particulièrement intéressante et en plein essor . Il ne faut pas se plaindre de son apparition dans les programmes de lycée .

    Domi
  • CédricTjrsPasLoggué
    CédricTjrsPasLoggué
    Oui, c'est un domaine important de l'informatique, or c'est certainement une autre discipline qui tend à prendre de l'importance... sinon en effet il y a beaucoup de jolies choses à faire avec des graphes.

    D'ailleurs le bagage pour faire des choses interessantes avec les graphes est plus réduit... donc ça doit donner moyen aux profs (et donc aux élèves) de faire des choses qui sortent un peu de l'ordinaire.
  • Fionat1
    Fionat1
    Une petite précision sur Dijkstra...
    Il ne fonctionne que sur des graphes sans cycle de poid négatif...
  • Eric Lafosse1
    Eric Lafosse1
    C'est quand même regrettable qu'il ait fallu attendre qu'un fana des graphes soit dans les décideurs pour avoir des graphes au lycée. Les stats sont apparues de la même manière, parce qu'une statisticienne fait partie d'un groupe d'experts... Vision moins utile qu'opportuniste... Regrettable.
  • FrançoisD
    FrançoisD
    Salut,

    tout à fait d'accord,

    il n'y a pas, au départ, d'intérêt pédagogique à enseigner les graphes mais l'expert y voyait son intérêt direct, les "coups" de ce genre me lassent...

    et puis DDC n'est pas pour rien dans l'enseignement des stats... (sacré pol pot)

    en même temps, je suis serein, si les graphes tombent demain matin, tous mes élèves réussiront dans le cas contraire, ça va être lourd... par exemple la récurrence est au programme et j'ai pû constater 2 ans d'affilée à quel point ça ne fonctionnait pas!

    amicalement,

    F.D.
  • Eric Lafosse1
    Eric Lafosse1
    Je te trouve bien sévère sur le manque d'intérêt pédagogique des graphes. Pour moi, ça permet entre autres à certains pas forcément à l'aise avec les maths de trouver un domaine complètement nouveau et pour lequel ils auront peut-être plus d'inspiration...
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français