Fiche formules + règles

Graphes, matrices, numérisation et algorithmique — révision rapide pour partiel BTS SIO.

Version HTML mobile : police uniforme, formules lisibles, tableaux défilables horizontalement si nécessaire. Sources : 9 photos de cours, fichier _Math.md, PDF Ellipses pour arithmétique, matrices et graphes. Le PDF ne couvre pas l’algorithmique appliquée ; la partie algorithmique est donc développée à partir des photos et du programme visé.

formulesrèglesméthodesexemplesmobile-first

0. Carte mentale du partiel

Bloc	Ce qu’il faut savoir faire
Algorithmique	Écrire et lire un pseudo-code ; suivre les variables ; utiliser `Pour` et `Tant que` ; comprendre Fibonacci.
Graphes	Lire un graphe orienté ; reconnaître arcs, chemins, boucles, circuits ; vérifier l’accessibilité.
Matrices de graphes	Construire une matrice d’adjacence ; interpréter $M^2$, $M^3$, $M^4$ ; utiliser $M+M^2+M^3+M^4$.
Matrices générales	Calculer un produit ligne-colonne ; utiliser l’identité $I$ ; exploiter une inverse dans $AX=Y$.
Numérisation	Convertir entre bases $2$, $10$, $16$ ; additionner en binaire.

Règle de travail rapide : pour chaque question, écrire d’abord la méthode, puis faire le calcul. Une procédure correcte rapporte souvent des points même si le calcul final contient une petite erreur.

1. Algorithmique — comprendre, lire, écrire

Cette partie comble le manque du PDF : l’algorithmique appliquée n’y est pas traitée. Elle est donc détaillée à partir des photos de cours et du périmètre du partiel.

1.1 Vocabulaire de base

Terme	Règle	Exemple
Variable	Zone mémoire nommée qui contient une valeur pouvant changer.	$a$, $b$, $c$, $i$
Déclaration	On annonce les variables et leur type.	`i, a, b, c : Entier`
Affectation	On met une valeur dans une variable. Ce n’est pas une équation.	$a \leftarrow 1$
Calcul	On calcule l’expression de droite, puis on stocke le résultat à gauche.	$c \leftarrow a+b$
Affichage	On écrit la valeur actuelle.	`Afficher(c)`
Compteur	Variable qui compte les tours de boucle.	$i$
Trace	Tableau des valeurs successives des variables.	colonnes $i,a,b,c$

Différence essentielle : $a=1$ est une égalité mathématique ; $a\leftarrow 1$ est une instruction qui modifie le contenu de $a$.

1.2 Lire un algorithme : méthode en 5 étapes

Repérer les variables déclarées et leur type.
Repérer les valeurs initiales : $a\leftarrow 1$, $b\leftarrow 1$, $i\leftarrow 1$.
Identifier le type de boucle : Pour ou Tant que.
Faire un tableau de trace : une ligne par tour.
Noter les valeurs affichées exactement au moment de l’instruction Afficher.

1.3 Boucle `Pour`

Règle : utiliser Pour quand le nombre de répétitions est connu avant de commencer.

Pour i allant de 1 à 8 faire
    instructions
FinPour

Cela signifie que les instructions sont exécutées pour :

$$i=1,2,3,4,5,6,7,8.$$

Il y a donc $8$ tours.

Déclencheur examen : « compléter le tableau d’exécution » ou « que va afficher l’algorithme ? »
Méthode : écrire les colonnes $i$, $a$, $b$, $c$, puis remplir ligne par ligne.

1.4 Boucle `Tant que`

Règle : utiliser Tant que quand la répétition dépend d’une condition.

i ← 1
Tant que i ≤ 8 faire
    instructions
    i ← i + 1
FinTantQue

Erreur classique : oublier $i\leftarrow i+1$. Si $i$ ne change pas, la condition peut rester vraie et la boucle peut ne jamais s’arrêter.

1.5 Fibonacci : idée mathématique

La suite de Fibonacci commence par deux valeurs initiales, puis chaque nouveau terme est la somme des deux précédents :

$$F_1=1,\qquad F_2=1,\qquad F_{n+2}=F_{n+1}+F_n.$$

Donc :

$$1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\dots$$

1.6 Fibonacci : pseudo-code avec boucle `Pour`

Algorithme Fibonacci
Déclaration
    i, a, b, c : Entier
Début
    a ← 1
    b ← 1
    Afficher(a)
    Afficher(b)
    Pour i allant de 1 à 8 faire
        c ← a + b
        Afficher(c)
        b ← a
        a ← c
    FinPour
Fin

Pourquoi l’ordre est important : on calcule d’abord $c\leftarrow a+b$. Ensuite seulement, on décale les anciennes valeurs : $b\leftarrow a$, puis $a\leftarrow c$.

1.7 Trace Fibonacci

Si au début $a=1$ et $b=1$ :

Tour	$a$ avant	$b$ avant	$c=a+b$	Valeur affichée
1	1	1	2	2
2	2	1	3	3
3	3	2	5	5
4	5	3	8	8
5	8	5	13	13

1.8 Guide pour écrire un algorithme propre

Donner un nom : Algorithme Nom.
Déclarer toutes les variables : i, a, b, c : Entier.
Initialiser les variables avant la boucle.
Choisir la bonne boucle : Pour si le nombre de tours est connu ; Tant que si on teste une condition.
Dans une boucle Tant que, modifier la variable de condition.
Afficher uniquement ce qui est demandé.
Vérifier avec une petite trace de 2 ou 3 tours.

2. Graphes orientés

2.1 Vocabulaire

Terme	Définition
Sommet	Point du graphe : $A$, $B$, $C$, $D$.
Arc	Flèche orientée : $A\to B$.
Chemin	Suite de sommets reliés par des arcs dans le bon sens.
Boucle	Arc qui part d’un sommet et revient au même sommet. Longueur $1$.
Circuit	Chemin fermé : sommet de départ = sommet d’arrivée.
Longueur	Nombre d’arcs utilisés dans le chemin.

Règle : dans un graphe orienté, $A\to B$ ne signifie pas automatiquement $B\to A$. Il faut vérifier le sens de chaque flèche.

2.2 Vérifier un chemin

Un chemin $(S_0,S_1,S_2,\dots,S_n)$ existe si tous les arcs suivants existent :

$$S_0\to S_1,\quad S_1\to S_2,\quad \dots,\quad S_{n-1}\to S_n.$$

$(A,B,A)$ existe si $A\to B$ et $B\to A$ existent.
$(A,C,D)$ existe si $A\to C$ et $C\to D$ existent.
$(B,A,B)$ est un circuit de longueur $2$ si $B\to A$ et $A\to B$ existent.

3. Matrice d’adjacence

3.1 Définition

Pour un graphe orienté de sommets $S_1,S_2,\dots,S_n$, la matrice d’adjacence est :

$$M=(m_{ij})_{1\leq i,j\leq n}$$

avec :

$$m_{ij}=\begin{cases}1 & \text{s’il existe un arc } S_i\to S_j,\\0 & \text{sinon.}\end{cases}$$

Règle à apprendre : ligne = sommet de départ ; colonne = sommet d’arrivée.

3.2 Exemple type

Avec l’ordre des sommets $A,B,C,D$ :

$$M=\begin{pmatrix}0&1&1&0\\1&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix}.$$

Version lisible même sans rendu LaTeX :

0110101000011000

$m_{AB}=1$ : il existe l’arc $A\to B$.
$m_{AC}=1$ : il existe l’arc $A\to C$.
$m_{AD}=0$ : il n’existe pas d’arc $A\to D$.
$m_{DA}=1$ : il existe l’arc $D\to A$.

3.3 Méthode de construction

Fixer l’ordre des sommets : $A,B,C,D$.
Faire une ligne par sommet de départ.
Pour chaque ligne, demander : « depuis ce sommet, vers quels sommets partent les flèches ? »
Mettre $1$ si la flèche existe, $0$ sinon.

4. Puissances de matrices et chemins

Règle fondamentale : dans une matrice d’adjacence $M$, le coefficient $(i,j)$ de $M^k$ donne le nombre de chemins de longueur exactement $k$ allant de $S_i$ vers $S_j$.

$$(M^k)_{ij}=\text{nombre de chemins de longueur }k\text{ de }S_i\text{ vers }S_j.$$

Matrice	Interprétation
$M$	Chemins de longueur $1$ : arcs directs.
$M^2$	Chemins de longueur $2$.
$M^3$	Chemins de longueur $3$.
$M^4$	Chemins de longueur $4$.

4.1 Accessibilité

Pour savoir si un sommet peut atteindre un autre en plusieurs étapes, on peut regarder :

$$M+M^2+M^3+M^4.$$

Si le coefficient $(i,j)$ de cette somme est non nul, alors $S_j$ est accessible depuis $S_i$ avec une longueur comprise entre $1$ et $4$.

4.2 Fermeture transitive

La fermeture transitive indique simplement si un sommet peut en atteindre un autre, sans forcément compter le nombre de chemins.

$$\text{non nul}\Rightarrow 1,\qquad 0\Rightarrow 0.$$

5. Matrices générales

5.1 Formats

Une matrice de taille $m\times n$ a $m$ lignes et $n$ colonnes.

$$A=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&\ddots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}\end{pmatrix}.$$

5.2 Addition

L’addition est possible seulement si les matrices ont le même format :

$$A+B=(a_{ij}+b_{ij}).$$

5.3 Multiplication par une constante

$$\lambda A=(\lambda a_{ij}).$$

Chaque coefficient est multiplié par $\lambda$.

5.4 Multiplication de matrices

Le produit $A_{m\times n}\times B_{n\times p}$ est possible si le nombre de colonnes de $A$ est égal au nombre de lignes de $B$. Le résultat est de taille :

$$AB\in M_{m\times p}.$$

Formule :

$$(AB)_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}.$$

Règle pratique : coefficient $(i,j)$ du produit = ligne $i$ de la première matrice × colonne $j$ de la deuxième matrice.

$$\begin{pmatrix}a&b&c\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix}=ax+by+cz.$$

5.5 Exemple numérique

$$A=\begin{pmatrix}1&2\\0&1\end{pmatrix},\qquad B=\begin{pmatrix}3&4\\5&6\end{pmatrix}.$$

$$AB=\begin{pmatrix}1\cdot3+2\cdot5&1\cdot4+2\cdot6\\0\cdot3+1\cdot5&0\cdot4+1\cdot6\end{pmatrix}=\begin{pmatrix}13&16\\5&6\end{pmatrix}.$$

Erreur fréquente : en général $AB\neq BA$. La multiplication de matrices n’est pas commutative.

6. Matrice identité et inverse

6.1 Matrice identité

$$I_n=\begin{pmatrix}1&0&\cdots&0\\0&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\end{pmatrix}.$$

Exemple :

$$I_3=\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}.$$

Propriété :

$$AI=IA=A.$$

6.2 Matrice inverse

Une matrice $C$ est l’inverse de $A$ si :

$$CA=AC=I.$$

Dans les exercices de BTS, on demande souvent de vérifier qu’une matrice est inverse d’une autre en calculant un produit et en obtenant $I$.

6.3 Résolution type $AX=Y$

Si :

$$AX=Y$$

et si :

$$CA=I,$$

alors on multiplie à gauche par $C$ :

$$CAX=CY.$$

Comme $CA=I$ :

$$IX=CY.$$

Donc :

$$X=CY.$$

Raccourci examen : si $AX=Y$ et $CA=I$, alors $X=CY$. Attention : on multiplie à gauche, pas à droite.

7. Numérisation — bases 2, 10, 16

7.1 Décomposition dans une base

Un nombre en base $b$ s’écrit comme une somme de puissances de $b$ :

$$(a_na_{n-1}\dots a_1a_0)_b=\sum_{k=0}^{n}a_kb^k.$$

Base	Chiffres autorisés	Puissances
$2$	$0,1$	$1,2,4,8,16,32,64,128,\dots$
$10$	$0,1,\dots,9$	$1,10,100,1000,\dots$
$16$	$0,1,\dots,9,A,B,C,D,E,F$	$1,16,256,4096,\dots$

$$A=10,\quad B=11,\quad C=12,\quad D=13,\quad E=14,\quad F=15.$$

7.2 Binaire vers décimal

$$11011_2=1\cdot2^4+1\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0.$$

$$11011_2=16+8+0+2+1=27_{10}.$$

7.3 Décimal vers binaire

Méthode : divisions euclidiennes successives par $2$, puis lecture des restes de bas en haut.

Exemple utile :

$$185_{10}=10111001_2.$$

Vérification :

$$10111001_2=128+32+16+8+1=185.$$

7.4 Hexadécimal vers décimal

$$1CE_{16}=1\cdot16^2+C\cdot16^1+E\cdot16^0.$$

Comme $C=12$ et $E=14$ :

$$1CE_{16}=1\cdot256+12\cdot16+14=256+192+14=462_{10}.$$

7.5 Décimal vers hexadécimal

Méthode : divisions euclidiennes successives par $16$, puis lecture des restes de bas en haut. Si un reste est supérieur à $9$, le remplacer par la lettre correspondante.

$$11\mapsto B,\qquad 14\mapsto E.$$

7.6 Binaire vers hexadécimal

Méthode : regrouper les bits par paquets de $4$, en partant de la droite.

$$10111001_2=1011\ 1001_2=B9_{16}.$$

8. Addition binaire

8.1 Règles d’addition

$$0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=10_2.$$

Avec une retenue :

$$1+1+1=11_2.$$

8.2 Exemple du tableau

$$11011_2+00101_2.$$

En décimal :

$$11011_2=27_{10},\qquad 00101_2=5_{10}.$$

$$27+5=32.$$

Or :

$$32_{10}=100000_2.$$

Ainsi :

$$11011_2+101_2=100000_2.$$

9. Déclencheurs de questions

Formulation dans l’énoncé	Réflexe à appliquer
« Que signifie $m_{ij}=1$ ? »	Il existe un arc du sommet ligne $i$ vers le sommet colonne $j$.
« Construire la matrice d’adjacence »	Fixer l’ordre des sommets ; ligne = départ ; colonne = arrivée ; mettre $1$ ou $0$.
« Interpréter $M^3$ »	Les coefficients donnent le nombre de chemins de longueur exactement $3$.
« Sommet accessible ? »	Regarder $M+M^2+M^3+M^4$ ou la fermeture transitive.
« Calculer $AB$ »	Vérifier les formats ; faire ligne par colonne.
« $AX=Y$ et $CA=I$ »	Multiplier à gauche par $C$ ; conclure $X=CY$.
« Convertir en base 2 »	Divisions par $2$ ou décomposition en puissances de $2$.
« Convertir en base 16 »	Divisions par $16$ ou paquets de $4$ bits.
« Boucle Pour »	Nombre de tours connu ; tracer les variables à chaque tour.
« Boucle Tant que »	Condition ; vérifier que la variable de contrôle évolue.

10. Memory dump de début d’épreuve

Adjacence : ligne = départ, colonne = arrivée
(M^k)ij = nombre de chemins de longueur k de i vers j
A(m×n) B(n×p) ⇒ AB(m×p)
AX = Y, CA = I ⇒ X = CY
F(n+2) = F(n+1) + F(n)
1 + 1 = 10₂
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15