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

Accueil › ECG › Maths appliquées

ECG1 · Maths appliquées · semaine 32

Informatique et algorithmique du premier semestre

Algorithmique des listes avec recherche séquentielle, boucles imbriquées, algorithmes dichotomiques et gloutons. Statistiques descriptives et analyse de données à partir de fichiers csv, représentations en diagrammes en bâtons et histogrammes. Approximation numérique de la racine d'une équation, la programmation se fait en Python.

Sommaire

Le cours

Résumé en cinq points

  1. Le programme fixe une liste limitative de commandes Python, et il faut s'y tenir :
    • structures de contrôle ;
    • listes avec append, len, in, del, count ;
    • bibliothèques numpy, matplotlib et pandas avec documentation fournie.
  2. La recherche séquentielle a un coût linéaire, les boucles imbriquées un coût quadratique, la dichotomie un coût logarithmique mais exige une liste triée.
  3. Un algorithme glouton choisit le meilleur à chaque étape sans revenir en arrière, il est rapide et n'est pas toujours optimal.
  4. L'analyse de données se fait sur un fichier csv avec pandas, avec :
    • des indicateurs de position et de dispersion à choisir pour leur pertinence ;
    • des représentations en bâtons ou en histogrammes.
  5. Une racine de f(x)=0f(x)=0 s'approche :
    • par dichotomie ;
    • par balayage ;
    • par une suite récurrente dont la convergence vient de l'inégalité des accroissements finis.
Pourquoi ce chapitre

L'informatique est une manière de pratiquer les mathématiques :

  • une liste de nombres est une série statistique ;
  • un algorithme de dichotomie est une preuve de convergence rendue exécutable ;
  • une simulation est une expérience aléatoire répétée.

Le premier semestre poursuit trois objectifs affichés par le programme :

  • consolider la programmation vue au lycée ;
  • installer une discipline de travail avec des fonctions, des commentaires et des tests ;
  • mettre en pratique des algorithmes utiles au traitement de l'information.

Les trois thèmes sont :

  • les listes ;
  • l'analyse de données réelles issues de l'économie ;
  • l'approximation numérique d'une racine.

RemarqueAux concours

Ces notions apparaissent sous forme de courts programmes à compléter ou à commenter, plus rarement à écrire entièrement.

Classiques et HP

Méthodes et approfondissements du chapitre · le statut est précisé pour ECG1.

Classiques et HP réservés

Prolongements et démonstrations de Maths appliquées.

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

Fin de l'aperçu gratuit

Encore 12 parties de cours et 10 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.

Statistiques descriptives 2

Exercice 1. Moyenne et variance sans bibliothèque ★

Application du cours · 10 min · Niveau khôlle

Écrire une fonction qui renvoie la moyenne et la variance empirique d'une liste non vide de nombres, sans numpy.

Voir l'indice

Technique deux accumulateurs, ou un seul avec la formule de König-Huygens.

Voir le corrigé offert
  1. On initialise s=0s = 0 et q=0q = 0.
  2. Pour chaque xx de LL, on fait s=s+xs = s + x et q=q+x∗∗2q = q + x ** 2.
  3. On pose m=s/len⁡(L)m = s / \operatorname{len}(L) et v=q/len⁡(L)−m∗∗2v = q / \operatorname{len}(L) - m ** 2.
  4. On renvoie mm et vv.
  5. Contrôle sur [1,3][1, 3] : m=2m = 2 et v=5−4=1v = 5 - 4 = 1.

piège : Diviser par n−1n - 1 par habitude. La variance empirique du programme divise par nn.

Exercice 10. Médiane et esprit critique ★

Application du cours · 10 min · Niveau écrit Ecricome

Écrire une fonction qui renvoie la médiane d'une liste triée LL non vide, en prenant la moyenne des deux valeurs centrales si la longueur est paire.

Appliquer à [1,1,1,1,1,10][1, 1, 1, 1, 1, 10] et commenter.

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

Parcours de listes 3

Exercice 3. Tester si une liste est triée ★

Application du cours · 10 min · Niveau khôlle

Écrire une fonction qui dit si une liste est triée par ordre croissant, puis l'utiliser pour sécuriser une recherche dichotomique.

Voir le début du corrigé
  1. Pour i de 0 à len(L) − 2, si L[i] > L[i + 1], on renvoie False. …

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

Exercice 2. Position et multiplicité du maximum ★★

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

Écrire une fonction qui renvoie le premier indice où le maximum est atteint et le nombre de fois où il est atteint.

Voir le début du corrigé
  1. On initialise m=L[0]m = L[0], p=0p = 0 et c=1c = 1.

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

Exercice 4. Les deux valeurs les plus proches d'une liste triée ★★

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

On suppose LL triée par ordre croissant, de longueur au moins 2.

Montrer que l'écart minimal est atteint entre deux voisins, en déduire un algorithme linéaire et comparer les coûts.

Voir le début du corrigé
  1. Si i<ji < j, alors L[j]−L[i]≥L[i+1]−L[i]L[j] - L[i] \geq L[i + 1] - L[i], car L[j]≥L[i+1]L[j] \geq L[i + 1].

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

Recherche dichotomique 2

Exercice 8. √2 par dichotomie ★

Application du cours · 15 min · Niveau écrit e3a

Justifier l'emploi de la dichotomie pour f(x)=x2−2f(x) = x^2 - 2 sur [1,2][1, 2].

Modifier la fonction pour qu'elle renvoie aussi le nombre de tours.

Prévoir ce nombre pour une précision 10−310^{-3} sur la longueur.

Voir le début du corrigé
  1. ff est continue, f(1)=−1f(1) = -1 et f(2)=2f(2) = 2, donc f(1)f(2)<0f(1)f(2) < 0.

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

Exercice 5. Nombre de tours de la recherche dichotomique ★★

Classiques de khôlle et concours · 30 min · Niveau écrit CCINP

Montrer que la recherche dichotomique de la fiche fait au plus ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 tours sur une liste de longueur n≥1n \geq 1.

Application à n=1000n = 1000.

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

Algorithme glouton 2

Exercice 6. Rendu de monnaie avec comptage ★★

Classiques de khôlle et concours · 25 min · Niveau écrit CCINP

Écrire une fonction qui renvoie le nombre de pièces du rendu glouton, les valeurs étant données par ordre décroissant et contenant 11.

Comparer avec l'optimum pour les pièces 44, 33, 11 et les sommes de 11 à 77.

Voir le début du corrigé
  1. On initialise nb = 0 et reste = somme. …

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

Exercice 7. Allocation de salles ★★

Classiques de khôlle et concours · 25 min · Niveau écrit CCINP

Chaque cours est une liste [début, fin].

La liste cours est non vide et triée par heure de fin croissante.

Un cours peut commencer à l'heure où un autre finit.

Écrire le glouton et le faire tourner sur [[1,3],[2,5],[3,6],[5,8],[7,9]].[[1, 3], [2, 5], [3, 6], [5, 8], [7, 9]].

Voir le début du corrigé
  1. On initialise retenus = [cours[0]] et fin = cours[0][1]. …

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

Point fixe 1

Exercice 9. Point fixe et critère d'arrêt ★★★

Approfondissement · 60 min · Niveau écrit Mines ou Centrale

Soit g(x) = (x + 2/x)/2, I = [1, 2], et (uₙ) la suite définie par u₀ ∈ I et u₍ₙ₊₁₎ = g(uₙ). Montrer que I est stable, que |g′| ≤ 1/2 sur I, que (uₙ) converge vers √2, et que le critère |u₍ₙ₊₁₎ − uₙ| ≤ ε de la fiche garantit une erreur au plus ε.

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 I « Programme du premier semestre », paragraphes « Algorithmique des listes », « Statistiques descriptives et analyse de données » et « Approximation numérique », complétée par l'annexe « Langage Python » qui liste limitativement les éléments du langage exigibles.