Formulaire de maths du BTS SIO

Ce formulaire rassemble sur une page les formules, les tables et les méthodes de l'E3 « Mathématiques pour l'informatique » : numération, arithmétique modulaire, logique et algèbre de Boole, ensembles, matrices, graphes, ordonnancement MPM et pseudo-code. Il n'existe pas de formulaire officiel à l'épreuve : seules quelques formules de base peuvent être rappelées en tête du sujet. Tout ce qui suit est donc à savoir, et chaque partie renvoie au cours qui l'explique.

Numération

Puissances de 2.

Chiffres hexadécimaux.

Méthodes.

• Base b vers base 10 : on additionne chaque chiffre multiplié par la puissance de b de son rang. (2F4A)₁₆ = 2 × 16³ + 15 × 16² + 4 × 16 + 10 = 12 106.
• Base 10 vers base b, partie entière : divisions successives par b ; les restes, lus du dernier au premier, donnent les chiffres.
• Base 10 vers base 2, partie fractionnaire : multiplications successives par 2 ; les parties entières, lues du premier au dernier, donnent les chiffres après la virgule.
• Base 2 ↔ base 16 : groupes de 4 bits à partir de la virgule.
• Sur n bits, on code 2ⁿ entiers naturels, de 0 à 2ⁿ − 1 (de 0 à 255 sur un octet).
• En base 2, multiplier par 2ᵏ décale les chiffres de k rangs vers la gauche ; diviser par 2ᵏ, de k rangs vers la droite.
• Un nombre négatif s'écrit avec le signe moins, quelle que soit la base.

Cours : bases de numération, conversions, nombres à virgule.

Arithmétique modulaire

• Division euclidienne de a par b (b ≠ 0) : a = b × q + r, avec 0 ≤ r < b.
• Congruence : a ≡ b [n] si et seulement si n divise a − b, c'est-à-dire si a et b ont le même reste dans la division par n.
• Compatibilité : si a ≡ b [n] et c ≡ d [n], alors a + c ≡ b + d [n], a × c ≡ b × d [n] et aᵏ ≡ bᵏ [n].
• Nombre premier : entier p ≥ 2 dont les seuls diviseurs sont 1 et p. Pour tester n, il suffit d'essayer les diviseurs premiers jusqu'à √n.
• Algorithme d'Euclide : PGCD(a ; b) = PGCD(b ; r), où r est le reste de a par b ; le PGCD est le dernier reste non nul.
• a et b sont premiers entre eux si PGCD(a ; b) = 1.
• Multiples modulo n : modulo n, les multiples de a sont les multiples de d = PGCD(a ; n) ; il y en a n ÷ d. Le parcours d'une liste circulaire de n éléments par sauts de a passe par tous les éléments si et seulement si PGCD(a ; n) = 1.
• Inverse modulo n : a' tel que a × a' ≡ 1 [n] ; il existe si et seulement si PGCD(a ; n) = 1.

Inverses modulo 26 (les 12 valeurs de a premières avec 26) :

Chiffrement affine (A = 0, B = 1, …, Z = 25) : y ≡ a × x + b [26], avec PGCD(a ; 26) = 1 ; déchiffrement : x ≡ a' × (y − b) [26]. Il y a 12 × 26 = 312 clés (a ; b) valides.

Cours : division euclidienne, PGCD, congruences, inverse modulaire, chiffrement affine.

Logique et algèbre de Boole

Connecteurs (1 = vrai, 0 = faux) :

• a ⇒ b a la même valeur que ā + b. Sa contraposée b̄ ⇒ ā lui est équivalente ; sa réciproque b ⇒ a ne l'est pas.
• Lois de De Morgan : le complément de a + b est ā b̄ ; le complément de ab est ā + b̄.
• Quantificateurs : la négation de « ∀x, P(x) » est « ∃x, non P(x) » ; la négation de « ∃x, P(x) » est « ∀x, non P(x) ». L'ordre de deux quantificateurs différents compte.

Règles du calcul booléen.

Tableau de Karnaugh (3 variables) : colonnes dans l'ordre 00, 01, 11, 10 (deux voisines ne diffèrent que d'une variable, y compris par le bord). On entoure des rectangles de 1, 2, 4 ou 8 cases de 1, les plus grands possible ; chaque regroupement donne le produit des variables qui y restent constantes. On regroupe les 0 de la même façon pour obtenir le complément.

Cours : connecteurs, quantificateurs, simplification, Karnaugh.

Ensembles et applications

• card(A ∪ B) = card(A) + card(B) − card(A ∩ B).
• card(E × F) = card(E) × card(F) ; un ensemble à n éléments a 2ⁿ parties.
• Complémentaires : le complément de A ∪ B est Ā ∩ B̄ ; le complément de A ∩ B est Ā ∪ B̄.
• Relation d'équivalence : réflexive, symétrique, transitive ; ses classes forment une partition. Relation d'ordre : réflexive, antisymétrique, transitive.
• Application f de E dans F : chaque élément de E a une et une seule image. f(A) est l'ensemble des images des éléments de A ; f⁻¹(B) est l'ensemble des éléments de E dont l'image est dans B.
• Injective : deux éléments distincts ont des images distinctes. Surjective : tout élément de F a au moins un antécédent. Bijective : les deux. Pour des ensembles finis : injective ⇒ card(E) ≤ card(F) ; surjective ⇒ card(E) ≥ card(F).
• Composée : g∘f(x) = g(f(x)) ; on applique f d'abord. La composée de deux injections est une injection, de deux surjections une surjection, de deux bijections une bijection.

Cours : opérations sur les ensembles, relations, applications.

Matrices

• Une matrice de n lignes et p colonnes est de dimension n × p.
• Produit : A (n × p) × B (p × q) donne une matrice n × q ; le coefficient de la ligne i et de la colonne j est aᵢ₁b₁ⱼ + aᵢ₂b₂ⱼ + … + aᵢₚbₚⱼ (ligne i de A « fois » colonne j de B).
• Le produit est associatif mais pas commutatif : en général, A × B ≠ B × A.
• Notation en ligne : (1 0 ; 0 1) se lit ligne par ligne, « ; » sépare les lignes.
• Matrice identité I₂ = (1 0 ; 0 1) : A × I = I × A = A.
• Inverse : B est l'inverse de A si A × B = B × A = I ; on le note A⁻¹. Pour le montrer, on calcule le produit.
• Système : A × X = C donne X = A⁻¹ × C (on multiplie à gauche par A⁻¹).
• Puissance : Mᵏ = M × M × … × M (k facteurs), à la calculatrice à partir de l'ordre 3.

Cours : calcul matriciel.

Graphes

• Matrice d'adjacence M : le coefficient de la ligne i et de la colonne j vaut 1 s'il existe un arc du sommet i vers le sommet j, 0 sinon. Le nombre de 1 est le nombre d'arcs.
• Puissances : le coefficient (i ; j) de Mᵏ est le nombre de chemins de longueur k de i à j.
• Opérations booléennes : 1 ⊕ 1 = 1 (somme), 1 ⊗ 0 = 0 (produit). La puissance booléenne M⁽ᵏ⁾ dit s'il existe un chemin de longueur k.
• Fermeture transitive (n sommets) : M̂ = M ⊕ M⁽²⁾ ⊕ … ⊕ M⁽ⁿ⁾, ou algorithme de Roy-Warshall. Un 1 sur la diagonale de M̂ signale un circuit passant par ce sommet.
• Niveaux (graphe sans circuit) : niveau 0, les sommets sans prédécesseur ; on les retire, et les nouveaux sommets sans prédécesseur forment le niveau 1, et ainsi de suite. Si on bloque avant la fin, le graphe a un circuit.
• Chemin hamiltonien : chemin qui passe une et une seule fois par chaque sommet ; il a n − 1 arcs.

Cours : représentations, puissances, fermeture transitive, niveaux.

Ordonnancement (méthode MPM)

Notations : t date de début au plus tôt, T date de début au plus tard, d durée ; p parcourt les tâches antérieures, s les tâches suivantes.

Une tâche est critique si sa marge totale est nulle ; le chemin critique relie les tâches critiques du début à la fin, et sa durée est la durée minimale du projet. Pour toute tâche, 0 ≤ MC ≤ ML ≤ MT.

Cours : méthode MPM, marges.

Pseudo-code et Python

Les motifs à reconnaître : une somme s'initialise à 0, un produit à 1 ; un compteur part de 0 et augmente sous condition ; un maximum s'initialise avec le premier élément ; une recherche s'arrête dès que l'élément est trouvé et renvoie un résultat par défaut après la boucle.

Cours : pseudo-code et Python, boucles, algorithmes des maths.

Calculatrice

Le détail est au chapitre 4.