À la recherche du plus court chemin
De Sciencinfolycee
| 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 ; François Passebon |
| Fonction(s) | éditeur ; auteur |
| 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 | |
| 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.
