Informatique MPSI / MP : L’essentiel
Louis Alvin
2 juin 2021
1 Représentation des nombres
Entiers (N) sur n bits : 2n valeurs : de 0 à 2n − 1.
Pour convertir un nombre en binaire : méthode des divisions euclidiennes successives par 2.
Entiers relatifs (Z) Méthode du complément à 2.
Si x > 0, on le représente sur n − 1 bits. Si x < 0 :
1) décomposition en binaire de 2n − x
2) écriture binaire de −x → inverser les bits → ajouter 1.
En complément à 2, on peut représenter J−2n−1 ; 2n−1 − 1K
Réels (R) : y = (1, b1 b2 ... bk ) ; norme IEEE-754 sur 64 bits.
— 1 bit de signe s
— exposant p sur 11 bits, représenté par p + 1023
— mantisse m sur 52 bits
2 Bases de données relationnelles – SQL
2.1 Opérateurs de base
: SELECT [DISTINCT] client FROM achats
Q
Projection c1 ,...,cp (t)
Sélection σc (t) : SELECT * FROM achats WHERE prix > 40
Conditions Opérateurs de comparaisons : =, !=, >, >=, ..., IS [NOT] NULL.
Opérateurs booléens : AND, OR, NOT.
Trier SELECT ... FROM ... ORDER BY ... ASC/DESC
Renommage ρa→b (t) :
SELECT client,prix-prix*remise/100 AS prix_reduit
FROM achats WHERE prix_reduit < 55
Opérateurs ensemblistes UNION, INTERSECT (sauf pour MySQL) ; EXCEPT (pour SQLite, MINUS sur MySQL).
2.2 Opérateurs plus complexes
Fonctions d’agrégation SELECT MAX(prix) FROM achats
Fonctions disponibles : MAX, MIN, SUM, AVG, COUNT
(COUNT(c) → nb colonnes non NULL ; COUNT(*) → nb total de colonnes)
Requêtes agrégatives GROUP BY et HAVING
N.B. : WHERE → avant les groupes ; HAVING → après les groupes
Produit cartésien ; Jointures Dans l’algèbre relationnelle, la jointure symétrique de deux tables t et t0 selon les
attributs a et a0 , est notée : t[a = a0 ]t0 ou t ./ 0 t0 et est définie par : t ./ 0 t0 = σa=a0 (t × t0 ).
a=a a=a
En SQL : SELECT * FROM batiments JOIN chambres
ON batiments.nom = chambres.batiment
1
LIMIT et OFFSET (tout à la fin d’une requête, généralement après ORDER BY)
LIMIT → renvoyer un nombre de lignes limité
OFFSET → effectue un décalage : nombre de lignes à passer avant de renvoyer le résultat
3 Algorithmes numériques
3.1 Recherche dichotomique dans une liste triée
def recherche_dicho(x,L):
i = 0
j = len(L)-1
while i <= j:
p = (i+j)//2
if L[p] == x:
return True
elif L[p] > x:
j = p - 1
else:
i = p + 1
return False
3.2 Calcul d’intégrale (méthode des rectangles)
On utilise la méthode des rectangles (gauches), dont la formule est :
n−1
R b−a X
Ia,b (f ) = × f (xi )
n i=0
def rectangles(f,a,b,n):
integrale = 0
h = (b-a)/n
x = a
for i in range(n):
integrale += f(x)
x = x+h
return h * integrale
Rb n−1
f (xi )+f (xi+1 )
Remarque : méthode des trapèzes : on approxime f (x)dx par .
P
a
h× 2
i=0
3.3 Résolution d’équation par recherche dichotomique
La fonction suivante renvoie une valeur approchée d’un zéro de f sur [a, b] avec une précision epsilon.
f (a) et f (b) de signes opposés, a < b, ε > 0.
def dichotomie(f, a, b, epsilon):
u,v = a,b
while v-u >= epsilon:
milieu = (u+v)/2
if f(u) * f(milieu) < 0:
v = milieu
else:
u = milieu
return u
3.4 Résolution d’équation par la méthode de Newton
Conditions : f doit être de classe C 1 sur [a, b] et f (a) et f (b) doivent être de signe opposé.
La méthode de Newton consiste à itérer la suite xn définie par :
(
x0 ∈ [a, b]
∀n ∈ N, xn+1 = xn − ff0(x n)
(xn )
2
def newton_residu(f, fprime, x0, epsilon):
x = x0
while (abs(f(x)) > epsilon):
x = x - f(x)/fprime(x)
return x
def newton_increment(f, fprime, x0, epsilon):
x, y = x0, x0 - f(x0)/fprime(x0)
while (abs(y - x) > epsilon):
x, y = y, y - f(y)/fprime(y)
return x
3.5 Résolution d’équation différentielle par la méthode d’Euler
y 0 = f (t, y)
Ordre 1 On considère une équation différentielle de la forme sur l’intervalle [a, b]
y(t0 ) = y0 (condition initiale)
(en général t0 = a).
On souhaite approximer la fonction y en un certain nombre d’instants répartis sur [a, b].
On note yi l’approximation de la fonction y à l’instant ti . On détermine les yi de proche en proche :
y(ti+1 ) = y(ti + h) = y(ti ) + h y 0 (ti ) + o(h) = yi + h f (ti , y(ti )) + o(h) ≈ yi + h f (ti , yi )
(D.L.) (y sol.)
yi+1 = yi + h × f (ti , yi ) y0 ∈ R
Au final, on a donc : avec
ti+1 = ti + h t0 = a
def euler(f, a, b, y0, n):
h = (b-a)/n
t, y = a, y0
T, Y = [a], [y0]
for i in range(n):
y = y + h * f(t,y)
Y.append(y)
t = t + h
T.append(t)
return T, Y
Ordre 2 Pour résoudre numériquement un système différentiel contenant n équations, on le voit comme une seule
ED de la forme Y 0 (t) = F (t, Y (t)) où t → Y (t) ∈ Rn est une fonction vectorielle.
Conséquence : dans la méthode d’Euler, la relation de récurrence vérifiée par les (yi ) est la même.
Euler ordre 1 yi+1 = yi + h × f (ti , yi ) ∈ R
Euler systèmes diff. Yi+1 = Yi + h × F (ti , Yi ) ∈ Rn
Implémentation Python y = y + h * f(t,y)
Attention : pour l’implémentation, on n’utilise pas des listes mais des tableaux Numpy. Par exemple :
def F(t,Y):
u,v = Y # ou encore : u,v = Y[0],Y[1]
x = 3*u + 4*v + t
y = 4 * np.cos(u) - 3*t
return np.array([x,y])
On peut alors utiliser la fonction euler telle quelle : LT,LY = euler(F,a,b,Y0,n).
y(t)
Ordre supérieur On considère le vecteur Y (t) = .
y 0 (t)
0
y 0 (t)
y (t)
Alors Y 0 (t) = 00 = 0 = F (t, Y (t)) ne dépend que de t, y(t) et y 0 (t).
y (t) 2y (t) + sin(y(t)) + t2
En Python :
def F(t,Y):
# Y = (y,y')
return np.array([Y[1], 2*Y[1] + np.sin(Y[0]) + t**2])
Cette méthode se généralise aux ED d’ordre p ≥ 3 et aux systèmes différentiels d’ordre p ≥ 2.
3
3.6 Résolution de système linéaire
On considère un système linéaire qu’on peut écrire matriciellement sous la forme :
a0,0 ... a0,n−1 x0 b0
.. .. .. ..
A ∈ Mn (R), X ∈ Rn (inconnue), B ∈ Rn .
. . . = . ⇐⇒ AX = B,
an−1,0 . . . an−1,n−1 xn−1 bn−1
On suppose que A ∈ GLn (R). Donc ∃! X ∈ Rn , AX = B.
Les matrices sont représentées par des tableaux Numpy à deux dimensions. On veillera à distinguer les opérations qui
copient un tableau de celles qui le
modifient directement → voir cours : Slices and views– Coupes
et vues.
1 4 −3 −3
Exemples : si A = , b = A[1] contient (−4 0 2) ; c = A[:,2] contient .
−4 0 2 2
Une instruction telle que A[1,2] = 7 modifie aussi b (qui vaut alors (−4 0 7)) et c : ce sont des vues.
On utilise cela lors de l’échange de deux lignes, pour éviter de copier le tableau entier.
Principe général Étape 1 : descente : on met le système sous forme triangulaire supérieure.
Étape 2 : remontée : on résout le système triangulaire.
Pour la formalisation, voir cours (Chap 15).
def echange(A,i,j):
tampon = A[i].copy()
A[i] = A[j]
A[j] = tampon
def recherche_pivot(A,j): # naïf
i = j
while A[i,j] == 0:
i = i + 1
return i
def elimination(A,b,j):
i = recherche_pivot(A,j)
echange(A,i,j)
echange(b,i,j)
for k in range(j+1, A.shape[0]):
b[k] = b[k] - (A[k,j]/A[j,j]) * b[j]
A[k] = A[k] - (A[k,j]/A[j,j]) * A[j]
def descente(A,b):
for j in range(A.shape[1]-1):
elimination(A,b,j)
def remonte(A,b):
n = A.shape[0]
X = np.zeros(n)
for k in range(n-1, -1, -1):
somme = 0
for l in range(k+1, n):
somme = somme + A[k,l]*X[1]
X[k] = (b[k]-somme) / A[k,k]
return X
def resolution(A,b):
A_copie = A.copy()
b_copie = b.copy()
descente(A_copie, b_copie)
return remonte(A_copie, b_copie)
4
4 Algorithmes de tri
4.1 Tri insertion
On insère L[i] à la bonne place dans la portion L[:i] déjà triée, pour i ∈ J1; len(L) − 1K.
Deux méthodes : soit on effectue des échanges à gauche tant que l’élément à insérer est inférieur à son voisin de
gauche, soit on décale les éléments à déplacer avant d’insérer le nouvel élément.
def tri_insertion(L):
for i in range(1,len(L)):
x = L[i]
j = i - 1 # indice de l'élément à comparer avec x
while j >= 0 and x < L[j]:
L[j+1] = L[j] # recopie à droite
j = j - 1
L[j+1] = x # insertion de x à la bonne place
Pas de return L : la liste est triée en place.
Complexité Dans le meilleur cas, si la liste est déjà triée, la complexité de ce tri est en O(n).
Dans le pire cas, L est triée dans l’ordre décroissant. On a alors une complexité en O(n2 ).
Complexité moyenne en O(n2 ) également.
4.2 Tri fusion
On coupe la liste en deux portions de taille presque égales qu’on trie récursivement, puis on fusionne en plaçant à
chaque étape le plus petit des éléments en tête de liste à fusionner à la suite des éléments déjà extraits.
[2, 7, 1, 4] [1, 2, 4, 7]
Exemple : [2, 7, 1, 4, 3, 6, 5, 8] −→ −→ −→ [1, 2, 3, 4, 5, 6, 7, 8]
[3, 6, 5, 8] tri récursif [3, 5, 6, 8] fusion
def fusion(L1,L2):
L = []
while L1 != [] and L2 != []:
if L1[0] > L2[0]:
L.append(L2.pop(0))
else:
L.append(L1.pop(0))
return L + L1 + L2
def tri_fusion(L):
if len(L) <= 1:
return L
L1 = tri_fusion(L[:len(L)//2]) # // et pas /
L2 = tri_fusion(L[len(L)//2:])
return fusion(L1,L2)
Fusion : On peut se passer des pop() en gardant en mémoire deux indices correspondant aux éléments de L1 et L2
à comparer. À la sortie du while, une seule des deux listes L1 et L2 est vide et l’autre contient des éléments supérieurs
à ceux de L.
Remarque : Ce n’est pas un tri en place (à cause des slicings).
Complexité T (n) = O(n log n) dans tous les cas (meilleur, pire, moyen).
4.3 Tri rapide
Aussi appelé Tri partition, ou Quicksort en anglais.
Principe On choisit un pivot p ∈ L.
La partition consiste à mettre la liste sous la forme : ≤ p p > p . Puis on trie récursivement les deux parties ≤ p
et > p.
deb i j fin
Comment partitionner ? Schéma de Lomuto : à chaque étape, L est de la forme : ↓ ↓ ↓ ↓
|p| ≤p | >p | ??? |
Initialement, ≤ p et > p sont vides, donc i = j = deb + 1.
Au tour de boucle j, si L[j] > p, il est à la bonne place et on ne fait rien ; si L[j] ≤ p, on échange L[j] et L[i].
5
def partition(L,deb,fin):
i = deb + 1
p = L[deb]
for j in range(deb+1, fin+1):
if L[j] <= p:
L[i],L[j] = L[j],L[i]
i = i + 1
L[deb],L[i-1] = L[i-1],L[deb]
return i - 1 # /!\
def tri_partition(L,deb,fin):
if deb < fin:
k = partition(L,deb,fin)
tri_partition(L,deb,k-1)
tri_partition(L,k+1,fin)
C’est un tri en place. Pour trier une liste en entier, on exécute tri_partition(L, 0, len(L)-1).
Complexité O(n2 ) dans le pire cas. O(n log n) dans le meilleur.
