À la recherche du plus court chemin

De Sciencinfolycee
Aller à : navigation, rechercher
Section Description
URL http://media.eduscol.education.fr/file/ISN Tle S/26/7/lyceeGT ressource ISN 20 06 Tle S 26 Plus court chemin 218267.pdf
Titre À la recherche du plus court chemin
Auteur(s) MEN/DGESCO/éduscol
Fonction(s) éditeur
Notes 10 p.
Section Analyse
Langue fre
Résumé Les applications utilisant les signaux des satellites GPS sont en plein essor, avec le calcul de l’itinéraire optimal entre deux lieux géographiques - optimal au regard de critères tels que distance, temps ou coût total. Ce calcul fait appel à la théorie des graphes et utilise différents algorithmes dont celui de Dijkstra, qui est un algorithme du type parcours en largeur ou BFS (Breadth First Search). À la différence d’un algorithme DFS

(Depth First Search) où l’on explore un sommet adjacent à celui de départ, puis un autre adjacent au précédent, et ainsi de suite jusqu’à se retrouver bloqué et revenir en arrière, on examine ici dès le départ tous les sommets adjacents au premier. L’algorithme de Dijkstra est actuellement enseigné en spécialité maths en terminale ES.

Sélection(s) thématique(s) Algorithmes classiques
Mots-clés normalisés théorie des graphes ; problème du plus court chemin ; algorithme de parcours en largeur ; algorithme de parcours en profondeur ; algorithme de Dijkstra
Proposition autres mots-clés
Type documentaire texte
Typologie Générale note
Date de publication 2012/06/01
Structure du document atomique
Niveau d'agrégation 2.une collection de ressources de niveau 1
Exigences techniques PDF
Section Pédagogie
Type pédagogique scénario pédagogique
Public cible enseignant
Utilisation pédagogique Ces documents peuvent être utilisés et modifiés librement dans le cadre des activités d'enseignement scolaire, hors exploitation commerciale.
Section Droits
Droits du document © Ministère de l’éducation nationale (DGESCO – IGEN) toute reproduction totale ou partielle à d’autres fins est soumise à une autorisation préalable du Directeur général de l’enseignement scolaire. La violation de ces dispositions est passible des sanctions édictées à l’article L.335-2 du Code la propriété intellectuelle.
Section processus de validation (workflow)
Intervenants Robert Cabane (demandeur + validateur) ; DB
Statut du workflow publiée

Signaler cette ressource. Si ce lien de signalement ne fonctionne pas (ouverture intempestive d'un mailer alors que vous utilisez un webmail) c'est qu'il vous manque l'extension idoine dans votre navigateur (par exemple l'extension send-mail pour firefox); c'est une bonne occasion de l'installer.