Informatique et algorithmique

Cours complet · mathématiques (ECT 1re année), chapitre 13 · prépa ECT, 1re année

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

L'informatique n'est pas une matière à part : l'intitulé officiel de l'enseignement est « mathématiques – informatique », et la machine sert ici à voir ce que les chapitres précédents ont écrit. On calcule les termes d'une suite au lieu de les imaginer, on trace un nuage de ventes au lieu de le décrire, on simule un tirage au lieu de le supposer. Le programme organise l'année autour de quatre thèmes — suites, statistiques descriptives, bases de données, probabilités — et d'une liste très courte de commandes, que ce chapitre suit sans jamais la dépasser en silence.

AttentionCe que le programme attend, mot pour mot

Sur le rôle de l'ordinateur : « L'objectif principal de l'activité informatique reste la mise en pratique de connaissances mathématiques. » Il ne s'agit donc pas d'écrire de longs programmes, mais d'assimiler des savoir-faire.

Sur les commandes : « Seules celles dans la colonne de gauche sont exigibles, et leur syntaxe précise doit être rappelée. » Et, pour tout le reste : « Toute utilisation d'une telle fonction doit obligatoirement être accompagnée de la documentation utile, sans que puisse être attendue une quelconque maîtrise par les étudiants de ces éléments. »

13.1 Le langage Python

ImportantLes briques exigibles, et elles seules

écriture	rôle
`nom = expression`	affectation
`#`	commentaire
`+ - * / **`	opérations arithmétiques
`== > < >= <= !=`	comparaisons, tests
`True False and or not`	logique
`if` / `elif` / `else`	instruction conditionnelle
`for` / `while`	boucles
`def f(p1, ..., pn)` et `return`	définition d'une fonction
`import ... as`, `from ... import *`	importation

Le programme insiste : « La maîtrise des structures de programmation de base (if, while, for) constitue l'un des objectifs majeurs de l'informatique en première année. »

Python : Quatre types, et les tests


n = 12                 # entier
prix = 19.9            # flottant
nom = "Dupont"         # chaine de caracteres
solde = True           # booleen

print(n + 3, n*2, n/5, n**2)
# 15 24 2.4 144
print(n >= 10, n != 12, n >= 10 and n != 12)
# True False False

Deux pièges d'écriture, et ce sont les plus fréquents de l'année : = affecte une valeur, == teste une égalité ; et n/5 rend un flottant ( $2, 4$ ) même quand les deux nombres sont entiers.

Python : Une fonction, et les trois branches


def remise(montant):
    if montant >= 500:
        return 0.10
    elif montant >= 200:
        return 0.05
    else:
        return 0.0

for m in [150, 300, 800]:
    print(m, remise(m), m*(1 - remise(m)))
# 150 0.0 150.0
# 300 0.05 285.0
# 800 0.1 720.0

L'ordre des tests compte : si l'on écrivait >= 200 en premier, un montant de $800$ tomberait dans cette branche et n'obtiendrait que $5 %$ . Un elif ne se lit que si tous les tests précédents ont échoué.

ImportantLes cinq savoir-faire exigibles en première année

C1 : manipuler les structures algorithmiques de base (if, for, while), connaître la syntaxe d'une fonction simple et savoir l'utiliser.
C2 : produire des graphiques et indicateurs afin d'interpréter des données statistiques.
C3 : étudier des suites numériques, calculer des valeurs, tracer des graphiques et conjecturer des résultats.
C4 : stocker, organiser et extraire des données structurées volumineuses.
C5 : modéliser des phénomènes aléatoires et effectuer des simulations de variables aléatoires.

13.2 Les bibliothèques

ImportantLa liste exigible, bibliothèque par bibliothèque

bibliothèque	fonctions exigibles
`import numpy as np`	`np.e`, `np.pi`
	`np.exp`, `np.log`, `np.sqrt`
	`np.abs`, `np.floor`
	`np.array`, `np.zeros`, `np.ones`
	`np.eye`, `np.arange`, `np.linspace`
	`np.reshape`, `np.dot`
	`np.sum`, `np.min`, `np.max`
	`np.mean`, `np.cumsum`, `np.median`
	`np.var`, `np.std`
`import numpy.random as rd`	`rd.random`
`import pandas as pd`	`pd.mean`, `pd.std`
`import matplotlib.pyplot as plt`	`plt.plot`, `plt.show`
	`plt.hist`, `plt.bar`, `plt.boxplot`

Les opérations + - * / s'appliquent aux tableaux coefficient par coefficient** ; np.dot est le seul produit matriciel. On obtient la taille d'un tableau par a, b = np.shape(M).

Python : Construire et interroger un tableau


import numpy as np

M = np.array([[12, 7, 5], [3, 9, 14]])
print(np.shape(M))        # (2, 3)
print(M[0, 2], M[1, 1])   # 5 9
print(np.sum(M), np.mean(M))
# 50 8.333333333333334
print(np.arange(0, 7, 2)) # [0 2 4 6]
print(np.linspace(0, 1, 5))
# [0.   0.25 0.5  0.75 1.  ]

np.arange avance d'un pas donné et s'arrête avant la borne ; np.linspace découpe un segment en un nombre de points donné, bornes comprises. Les confondre est la source d'erreur numéro un.

13.3 Thème 1 : études de suites

Le premier thème (compétences C1 et C3) demande de calculer les termes d'une suite, d'en exploiter graphiquement les résultats et de déterminer un rang d'arrêt, sur les exemples que le programme cite : « taux d'intérêt, emprunt ».

Python : Un emprunt, mois par mois


def capital(C0, taux, mensualite, n):
    C = C0
    for k in range(n):
        C = C*(1 + taux) - mensualite
    return C

print(capital(10000, 0.004, 300, 12))
# 6810.436510237627

On emprunte $10000$ euros à $0, 4 %$ par mois et l'on rembourse $300$ euros chaque mois. Après un an, il reste $6810, 44$ euros à devoir : on a versé $3600$ euros, mais la dette n'a baissé que de $3189, 56$ — la différence est l'intérêt.

Python : Un rang d'arrêt : quand la dette est-elle éteinte ?


C = 10000
n = 0
while C > 0:
    C = C*1.004 - 300
    n = n + 1
print(n, C)
# 36 -45.90819938813499

La boucle s'arrête au $3 6^{e}$ mois, avec un solde négatif : la dernière mensualité est en réalité plus petite. Après $35$ versements il reste $253, 08$ euros, qui produisent $254, 09$ euros à payer le mois suivant. Au total $10754, 09$ euros versés pour $10000$ empruntés, soit $754, 09$ euros d'intérêts.

AttentionChoisir entre for et while

On emploie for quand le nombre de tours est connu d'avance (« les douze premiers mois »), et while quand il dépend d'une condition (« tant que la dette est positive »).

Une boucle while dont la condition ne peut jamais devenir fausse ne s'arrête pas. Avant de lancer, on se demande toujours : qu'est-ce qui, dans le corps de la boucle, fait progresser vers l'arrêt ?

Python : Valeur approchée d'une limite


u = 1
n = 0
while abs(u - 2) > 1e-6:
    u = 1 + u/2
    n = n + 1
print(n, u)
# 20 1.9999990463256836

La suite $u_{n + 1} = 1 + \frac{u _{n}}{2}$ converge vers $2$ . Vingt tours suffisent pour être à moins de $1 0^{- 6}$ : l'écart à la limite est divisé par $2$ à chaque étape, et $2^{- 20}$ vaut environ $1 0^{- 6}$ .

13.4 Thème 2 : statistiques descriptives univariées

Définition 13.1Série statistique, effectifs, fréquences

Une série statistique est la liste des valeurs $x_{1}, \dots, x_{n}$ d'un caractère quantitatif relevées sur un échantillon de taille $n$ .

L'effectif d'une valeur est le nombre de fois où elle apparaît, sa fréquence est cet effectif divisé par $n$ .

ImportantPosition et dispersion

Position : la moyenne $x = \frac{1}{n} \sum x_{i}$ , la médiane (valeur qui partage la série triée en deux moitiés), le mode (valeur la plus fréquente), les quartiles $Q_{1}$ et $Q_{3}$ .

Dispersion : l'étendue $max - min$ , la variance empirique $\frac{1}{n} \sum (x_{i} - x)^{2}$ , l'écart type sa racine carrée, et l'écart interquartile $Q_{3} - Q_{1}$ .

Le programme demande de savoir comparer ces deux familles : moyenne et écart type se calculent, mais un seul point extrême les déplace ; médiane et quartiles ne bougent pas pour autant.

Python : Les indicateurs avec numpy


import numpy as np

ventes = np.array([12, 15, 9, 22, 15, 18, 15, 31, 11, 15])
print(np.mean(ventes), np.median(ventes))
# 16.3 15.0
print(np.var(ventes), np.std(ventes))
# 35.81 5.984145720150872
print(np.min(ventes), np.max(ventes))
# 9 31
print(np.cumsum(ventes))
# [ 12  27  36  58  73  91 106 137 148 163]

La moyenne $16, 3$ dépasse la médiane $15$ : c'est la signature d'une série tirée vers le haut par une valeur isolée, ici le $31$ . np.cumsum donne les totaux successifs — utile pour un chiffre d'affaires cumulé.

Python : Les mêmes indicateurs avec pandas


import pandas as pd

serie = pd.Series([12, 15, 9, 22, 15, 18, 15, 31, 11, 15])
print(serie.mean(), serie.std())
# 16.3 6.307843442008441
print(serie.median(), serie.count())
# 15.0 10

Attention, et c'est un piège classique : np.std divise par $n$ , tandis que l'écart type de pandas divise par $n - 1$ . On lit donc $5, 98$ d'un côté et $6, 31$ de l'autre sur la même série. Le programme définit les paramètres empiriques avec $n$ : c'est la valeur de numpy.

Python : Les trois représentations exigibles


import matplotlib.pyplot as plt

plt.bar([9, 11, 12, 15, 18, 22, 31], [1, 1, 1, 4, 1, 1, 1])
plt.show()

plt.hist(ventes, bins=[5, 10, 15, 20, 25, 30, 35])
plt.show()

plt.boxplot(ventes)
plt.show()

plt.bar dessine un diagramme en bâtons, plt.hist un histogramme par classes, plt.boxplot une boîte à moustaches. Chaque tracé se termine par plt.show(), sans quoi rien ne s'affiche.

13.5 Thème 3 : bases de données

Définition 13.2Le vocabulaire du modèle relationnel

Une base de données relationnelle est un ensemble de tables. Chaque table porte des colonnes (ou champs, ou attributs), chacune d'un type donné, et des lignes (ou enregistrements).

La clé primaire (PRIMARY KEY) est la colonne qui identifie une ligne sans ambiguïté. Une clé étrangère (FOREIGN KEY) est une colonne qui renvoie à la clé primaire d'une autre table. Les types se limitent ici à l'entier INTEGER et à la chaîne TEXT.

Exemple 13.3Interroger : SELECT, FROM, WHERE


SELECT nom, ville FROM clients;

SELECT nom FROM clients
WHERE ville = 'Nantes';

SELECT produit, montant FROM commandes
WHERE montant >= 500 AND id_client = 3;

SELECT nom FROM clients
WHERE ville <> 'Nantes' OR remise > 5;

SELECT choisit les colonnes, FROM la table, WHERE filtre les lignes. Les comparaisons disponibles sont =, <>, <, <=, >, >=, et l'on combine les conditions par AND, OR, NOT. Le point-virgule termine chaque requête.

Exemple 13.4Modifier : INSERT, UPDATE, DELETE


INSERT INTO clients
VALUES (7, 'Moreau', 'Rennes', 5);

UPDATE clients
SET remise = 10
WHERE ville = 'Nantes';

DELETE FROM commandes
WHERE montant < 20;

Ces trois commandes modifient la base, contrairement à SELECT qui se contente de lire. La plus dangereuse est DELETE : oublier la clause WHERE efface toutes les lignes de la table, sans avertissement et sans retour en arrière.

AttentionCe qui est exigible en SQL, et ce qui ne l'est pas

Les cinq commandes exigibles sont exactement : SELECT ... FROM ..., WHERE, INSERT INTO ..., DELETE FROM ... et UPDATE ....

Le programme énumère ensuite ce qui ne l'est pas — UNION, INTERSECTION, EXCEPT, MIN, MAX, SUM, AVG, COUNT, DISTINCT, ORDER BY — et conclut : « Ce ne sont pas des attendus du programme et ils sont non exigibles. » On peut donc les rencontrer dans un sujet, mais leur syntaxe y sera rappelée.

13.6 Thème 4 : probabilités

Le dernier thème (compétences C1, C2 et C5) demande de simuler des expériences aléatoires conduisant à une loi usuelle. Une seule fonction est exigible : rd.random, qui rend un nombre au hasard entre $0$ et $1$ .

Python : Simuler une épreuve de Bernoulli


import numpy.random as rd

def lancer(p):
    if rd.random() < p:
        return 1
    return 0

# rd.seed fixe le generateur : memes tirages a chaque
# execution (fonction non exigible, documentee ici)
rd.seed(3)
n = 10000
s = 0
for i in range(n):
    s = s + lancer(0.35)
print(s/n)
# 0.3596

rd.random() tombe dans $[0, p [$ avec probabilité exactement $p$ : le test rd.random() < p est une épreuve de Bernoulli. La fréquence observée, $0, 3596$ , approche $p = 0, 35$ .

Python : Simuler une loi binomiale, et la comparer


def binomiale(n, p):
    s = 0
    for i in range(n):
        s = s + lancer(p)
    return s

rd.seed(5)
essais = [binomiale(10, 0.35) for i in range(10000)]
print(essais.count(3)/10000)   # 0.253
print(sum(essais)/10000)       # 3.4713

La fréquence de la valeur $3$ vaut $0, 253$ , contre $(3 10) 0, 3 5^{3} 0, 6 5^{7} \approx 0, 252$ pour la loi exacte ; et la moyenne des essais vaut $3, 4713$ , contre $E (X) = n p = 3, 5$ .

Continuer sur Adloun : animation, QCM, fiches, exercices