Algorithme de Dijkstra
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
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
-
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 -
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 -
... ça marche aussi bien pour les graphes non orientés que pour les graphes orientés.
-
Bonsoir
Dans le cours de Vincent Bouchitté figure une démonstration par récurrence.
Lien : <http://wwwens.uqac.ca/~nlandry/reseaux/note_graphes.pdf>
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>
Cordialement -
Merci
S -
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 ? -
Les graphes sont au programme de terminale ES depuis 3 ou 4 ans je pense.
-
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... :-) -
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 -
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. -
Une petite précision sur Dijkstra...
Il ne fonctionne que sur des graphes sans cycle de poid négatif... -
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.
-
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. -
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!
Catégories
- 164.9K Toutes les catégories
- 52 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 57 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 50 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 82 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 77 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 334 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 794 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres