Combien de temps faut-il au minimum pour mener un projet dont les tâches dépendent les unes des autres ?
On représente les tâches et leurs dépendances par un graphe orienté sans cycle. La durée minimale du projet est la longueur du plus long chemin : pour A (3 j), B (2 j) et C (4 j) après A, D (1 j) après B et C, E (2 j) après D, le chemin A-C-D-E impose 10 jours, et B dispose de 2 jours de marge.
Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.
Pourquoi cette question : un modèle d'introduction
Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.
Pour notre projet de NSI en groupe, nous avons dû répartir les tâches : certaines ne pouvaient commencer qu'après d'autres. Nous avons pris du retard parce qu'une tâche dont tout dépendait avait été négligée. J'ai découvert ensuite la méthode du chemin critique, utilisée pour les chantiers et les lancements de fusées, et je voulais comprendre son calcul.
L'enjeu et les notions du programme
Modéliser des dépendances par un graphe orienté sans cycle et calculer des dates au plus tôt par une récurrence avec un maximum.
Mathématiques
- Maximum d'un ensemble fini, inégalités (seconde)
- Suites et relations de récurrence (première)
- Raisonnement logique sur les dépendances (seconde)
Numérique et sciences informatiques
- Graphes orientés, parcours, détection de cycle (terminale)
- Tri topologique (terminale)
Le plan de l'exposé en 9,5 min
1. Introduction
1 minUn projet comporte des tâches de durées connues, dont certaines doivent attendre la fin d'autres. Plusieurs tâches peuvent avancer en parallèle. Problématique : quelle est la durée minimale du projet, et quelles tâches ne doivent surtout pas prendre de retard ?
2. Mathématiques : dates au plus tôt
4 minTâches : A (3 jours) ; B (2 j) et C (4 j), après A ; D (1 j), après B et C ; E (2 j), après D. On note t(X) la date de début au plus tôt de X.
Une tâche ne peut commencer que lorsque toutes ses prédécesseures sont finies : t(X)=max(t(Y)+ durée (Y)) sur ses prédécesseures Y. On calcule : t(A)=0 ; t(B)=t(C)=3 ; t(D)=max(3+2,3+4)=7 ; t(E)=7+1=8. Fin du projet : 8+2=10 jours.
Les 10 jours correspondent au plus long chemin A → C → D → E : 3+4+1+2=10. C'est le chemin critique : tout retard sur l'une de ces tâches retarde le projet. B, lui, peut commencer au plus tard le jour 5 sans rien retarder (il doit finir le jour 7) : sa marge est 7-(3+2)=2 jours.
Le projet ne peut pas durer moins : la chaîne A, C, D, E doit être exécutée dans cet ordre, et elle dure 10 jours.
3. NSI : graphe sans cycle et tri topologique
3 minOn représente le projet par un graphe orienté : un arc de Y vers X si X dépend de Y. Il ne doit pas y avoir de cycle, sinon des tâches s'attendraient mutuellement ; on le vérifie par un parcours en profondeur.
Pour calculer les dates, il faut traiter chaque tâche après ses prédécesseures : c'est un tri topologique, obtenu par un parcours en profondeur. Le calcul complet coûte de l'ordre du nombre de tâches et de dépendances. Cette méthode, appelée PERT, a été développée dans les années 1950 pour le programme de missiles Polaris de la marine américaine.
4. Conclusion
1,5 minLa durée minimale d'un projet est la longueur du plus long chemin dans le graphe des dépendances : 10 jours ici, par A, C, D, E. Les autres tâches ont une marge. Savoir lesquelles sont critiques indique où concentrer les efforts. J'ouvre sur l'affectation des tâches quand le nombre de personnes est limité, beaucoup plus difficile.
Ce que j'écris au tableau
Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.
chemin critique A–C–D–E : 3+4+1+2=10 jours marge de B =7-5=2
Conclusion : la réponse à la question
Le temps minimal d'un projet se calcule par une récurrence avec un maximum le long du graphe des dépendances. Le chemin critique en est le plus long chemin : c'est lui, et non la somme des durées, qui fixe la date de fin.
Les questions probables du jury
Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.
Pourquoi un maximum et pas une somme ?
Les prédécesseures se déroulent en parallèle : on attend la dernière à finir.
Quelle serait la durée si toutes les tâches étaient faites l'une après l'autre ?
3 + 2 + 4 + 1 + 2 = 12 jours.
Que se passe-t-il si C prend un jour de retard ?
C est critique : le projet dure 11 jours.
Pourquoi le graphe ne doit-il pas avoir de cycle ?
Un cycle signifierait qu'une tâche attend, indirectement, sa propre fin : le projet serait impossible.
Le plus long chemin est-il difficile à trouver ?
Dans un graphe sans cycle, non : le tri topologique permet de le calculer rapidement.
Les pièges qui coûtent des points
- Additionner toutes les durées.
- Prendre le minimum au lieu du maximum des dates de fin des prédécesseures.
- Confondre durée d'une tâche et date de début.
Revoir les notions
Autres questions : graphes et réseaux
- Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
- Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
- Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
- Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
Préparer l'oral, pas seulement le contenu
Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.
Méthode : traiter une question de Grand oral →