Aller au contenu
Sup et Spé
Télécharger l'application

Accueil › ECG › Maths appliquées

ECG1 · Maths appliquées · semaine 33

Informatique et algorithmique du second semestre

Représentation des graphes finis et recherche d'un plus court chemin dans un graphe pondéré à poids positifs avec l'algorithme de Dijkstra. Simulation d'expériences aléatoires élémentaires conduisant aux lois usuelles. Les commandes Python exigibles sont listées en annexe du programme, notamment numpy, numpy.random, matplotlib et pandas.

Sommaire

Le cours

Résumé en cinq points

  1. Un graphe se représente par sa matrice d'adjacence, adaptée au calcul matriciel, ou par des listes d'adjacence, adaptées au parcours des voisins et plus économiques pour un graphe creux.
  2. L'algorithme de Dijkstra calcule les plus courts chemins depuis un sommet dans un graphe pondéré à poids positifs, par choix glouton du sommet le plus proche puis relaxation de ses voisins.
  3. Son coût est de l'ordre du carré du nombre de sommets avec la version simple, et l'hypothèse de poids positifs est indispensable.
  4. Toute simulation part de rd.random, qui tire un réel uniformément entre 00 et 11, et les lois usuelles se simulent en traduisant leur définition, ou avec rd.binomial, rd.randint, rd.geometric et rd.poisson.
  5. Simuler un grand échantillon puis comparer sa moyenne et sa variance aux valeurs théoriques est la méthode de vérification standard, et matplotlib permet d'en visualiser la forme.
Pourquoi ce chapitre

Le second semestre met l'informatique au service de deux objets du cours de mathématiques.

  • Les graphes, introduits au premier semestre par leur matrice d'adjacence, que l'on reprend ici du point de vue algorithmique, avec le problème du plus court chemin et l'algorithme de Dijkstra.
  • Les variables aléatoires, que l'on simule pour vérifier une loi, estimer une espérance, ou étudier un phénomène trop complexe pour le calcul exact.

Un graphe pondéré modélise un réseau de transport, un enchaînement de tâches, un réseau social, et le plus court chemin est le trajet le moins coûteux.

Le programme demande explicitement que l'étude des lois usuelles se fasse en lien étroit avec cette partie. Les questions d'épreuve portent le plus souvent sur la lecture ou le complètement d'un programme court.

Fin de l'aperçu gratuit

Encore 10 parties de cours et 9 corrigés.

Essayer 7 jours gratuitement Sans engagement · cours, exercices et fiches complets

Méthodes et exercices

Exercices classiques corrigés

Rangés par thème, du plus simple au plus exigeant. Difficulté et durée indicatives.

Représentation de graphes 2

Exercice 1. Matrice d'adjacence et chemins ★

Application du cours · 15 min · Niveau khôlle

Graphe orienté à quatre sommets, d'arcs 0→1,0→2,1→2,2→0,2→3.0 \to 1, \quad 0 \to 2, \quad 1 \to 2, \quad 2 \to 0, \quad 2 \to 3. Écrire ses listes d'adjacence et sa matrice AA, calculer A2A^2, puis le nombre de chemins de longueur 33 de 00 à 00.

Voir l'indice

Technique la ligne ii de A2A^2 est la somme des lignes de AA indexées par les successeurs de ii.

Voir le corrigé offert
  1. G=[[1,2],[2],[0,3],[]]G = [[1, 2], [2], [0, 3], []].
  2. Les lignes de AA sont [0,1,1,0][0, 1, 1, 0], [0,0,1,0][0, 0, 1, 0], [1,0,0,1][1, 0, 0, 1], [0,0,0,0][0, 0, 0, 0]. Elle n'est pas symétrique.
  3. Ligne 00 de A2A^2, lignes 11 et 22 de AA sommées, soit [1,0,1,1][1, 0, 1, 1]. Ligne 11, la ligne 22, soit [1,0,0,1][1, 0, 0, 1]. Ligne 22, lignes 00 et 33 sommées, soit [0,1,1,0][0, 1, 1, 0]. Ligne 33 nulle.
  4. Le coefficient (0,0)(0, 0) de A3A^3 vaut ∑\sum sur ll de (A2)0lAl0(A^2)_{0l} A_{l0}. Seul l=2l = 2 contribue, avec 1×11 \times 1. Un seul chemin, 0→1→2→00 \to 1 \to 2 \to 0.

piège : Lire AA en colonnes, ce qui inverse le sens des arcs.

Exercice 2. Conversions et degrés ★

Application du cours · 10 min · Niveau khôlle

Écrire une fonction transformant des listes d'adjacence en matrice. Pour un graphe non orienté, en déduire les degrés et le nombre d'arêtes.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Plus courts chemins 3

Exercice 3. Dijkstra à la main avec chemin ★★

Classiques de khôlle et concours · 20 min · Niveau khôlle

Graphe non orienté sur 00 à 44, d'arêtes 0-1 de poids 7,0-2 de poids 2,1-2 de poids 3,2-3 de poids 8,1-3 de poids 1,3-4 de poids 2,1-4 de poids 6.\begin{aligned} 0\text{-}1 &\text{ de poids } 7, \\ 0\text{-}2 &\text{ de poids } 2, \\ 1\text{-}2 &\text{ de poids } 3, \\ 2\text{-}3 &\text{ de poids } 8, \\ 1\text{-}3 &\text{ de poids } 1, \\ 3\text{-}4 &\text{ de poids } 2, \\ 1\text{-}4 &\text{ de poids } 6. \end{aligned}

Distances depuis 00 et plus court chemin de 00 à 44.

Voir le début du corrigé
  1. Départ : 0, INF, INF, INF, INF. …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 4. Reconstituer le chemin ★★

Classiques de khôlle et concours · 20 min · Niveau écrit EDHEC ou Ecricome

On ajoute au programme de la fiche une liste pred initialisée à [-1] * n et l'instruction pred[v] = u dans la relaxation.

Écrire une fonction renvoyant les sommets d'un plus court chemin de ss à tt.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 5. Nombre minimal d'arêtes ★★★

Approfondissement · 35 min · Niveau écrit EDHEC ou Ecricome

Si tt est accessible depuis s≠ts \neq t, montrer que le nombre minimal d'arêtes d'un chemin de ss à tt est le plus petit k≥1k \geq 1 tel que (Ak)st(A^k)_{st} soit non nul, et que k≤n−1k \leq n - 1.

Écrire la fonction et comparer avec Dijkstra.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Simulation de lois 2

Exercice 6. Contrôler une binomiale ★

Application du cours · 10 min · Niveau khôlle

Avec la fonction binomiale de la fiche, simuler 10 00010\,000 réalisations de la loi binomiale de paramètres 2020 et 0,30{,}3.

Comparer moyenne, variance et fréquence de la valeur 66 aux valeurs théoriques.

Voir le début du corrigé
  1. X = np.array([binomiale(20, 0.3) for k in range(10000)]). …

La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 7. Loi finie par un seul tirage ★★

Classiques de khôlle et concours · 15 min · Niveau khôlle

Simuler XX telle que P(X=1)=12,P(X=2)=13,P(X=3)=16.\begin{aligned} P(X = 1) &= \frac{1}{2}, \\ P(X = 2) &= \frac{1}{3}, \\ P(X = 3) &= \frac{1}{6}. \end{aligned}

Expliquer pourquoi rappeler rd.random() dans chaque test est faux.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Estimation par simulation 3

Exercice 8. Collectionner les six faces ★★

Classiques de khôlle et concours · 30 min · Niveau écrit EDHEC ou Ecricome

On lance un dé jusqu'à avoir vu les six faces. Simuler le nombre T de lancers, estimer puis calculer E(T).

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 9. Retour à l'origine d'une marche aléatoire ★★

Classiques de khôlle et concours · 20 min · Niveau écrit ESSEC ou HEC

Un point part de 00 et fait des pas indépendants de +1+1 ou −1-1 avec probabilité 12\frac{1}{2}.

Estimer puis calculer la probabilité d'être en 00 après 2020 pas.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Exercice 10. Connexité d'un graphe aléatoire ★★★

Approfondissement · 40 min · Niveau écrit ESSEC ou HEC

Sur quatre sommets, chacune des six arêtes possibles est présente avec probabilité 12\frac{1}{2}, indépendamment.

Estimer la probabilité que le graphe soit connexe en réutilisant Dijkstra, puis la calculer.

Corrigé détaillé dans Sup et Spé+ : essai gratuit 7 jours.

Fiche de cours rédigée à partir du programme officiel d'ECG première année, enseignement annuel d'informatique et algorithmique, partie II « Programme du deuxième semestre », paragraphes « Graphes finis, plus courts chemins » et « Simulation de phénomènes aléatoires », complétée par l'annexe « Langage Python » qui liste limitativement les commandes exigibles, notamment celles de numpy, numpy.linalg, numpy.random, matplotlib.pyplot et pandas.