Feuille d’entraînement ultra-rapide

Objectif : refaire les gestes attendus au partiel en 30 minutes, dans le même ordre que la Fiche HTML. Chaque bloc contient une question type, un indice, la méthode attendue et une correction modèle.

Utilisation : essaie d’abord mentalement ou sur brouillon. Ouvre l’indice si bloqué. Ouvre la correction uniquement après avoir formulé ta réponse.

ordre Fiche HTMLquestions type partielmobile lisibleLaTeX / matrices

Chrono conseillé : Algorithmique 7 min · Graphes/adjacence 7 min · Matrices 8 min · Bases/addition 6 min · Memory dump 2 min. 30:00

0. Carte mentale du partiel — échauffement 2 min

Question 0 — Classer les chapitres

En 30 secondes, écris les 5 zones à réviser et une compétence par zone.

Indice

Reprends les titres de la Fiche HTML : Algorithmique, Graphes, Matrices de graphes, Matrices générales, Numérisation.

Correction modèle

Algorithmique : lire/écrire un pseudo-code, tracer les variables.
Graphes : lire arcs, chemins, boucles, circuits.
Matrices de graphes : construire $M$, interpréter $M^2,M^3,M^4$.
Matrices générales : produit ligne-colonne, identité, inverse, résoudre $AX=Y$.
Numérisation : bases $2,10,16$, conversions, addition binaire.

1. Algorithmique — comprendre, lire, écrire

Question 1 — Lire les affectations

On donne :

a ← 1
b ← 1
c ← a + b
Afficher(c)

Que vaut $c$ et qu’affiche l’algorithme ?

Indice

Une affectation se lit de droite à gauche : on calcule d’abord le membre de droite, puis on stocke dans la variable de gauche.

Correction détaillée

$a=1$ et $b=1$, donc :

$$c\leftarrow a+b=1+1=2.$$

L’instruction Afficher(c) affiche donc 2.

Formulation BTS : « L’algorithme affecte 1 à $a$ et $b$, calcule $c=a+b$, donc $c=2$, puis affiche $2$. »

Question 2 — Boucle Pour : compléter une trace

a ← 1
b ← 1
Pour i allant de 1 à 4 faire
  c ← a + b
  Afficher(c)
  b ← a
  a ← c
FinPour

Compléter les valeurs affichées.

Indice

Fais un tableau avec les colonnes : tour, $a$ avant, $b$ avant, $c=a+b$, affichage, puis nouvelles valeurs de $a,b$.

Correction détaillée

Tour	$a$ avant	$b$ avant	$c=a+b$	Affiché	Après : $b\leftarrow a$, $a\leftarrow c$
1	1	1	2	2	$b=1$, $a=2$
2	2	1	3	3	$b=2$, $a=3$
3	3	2	5	5	$b=3$, $a=5$
4	5	3	8	8	$b=5$, $a=8$

Valeurs affichées : $2,3,5,8$.

Question 3 — Boucle Tant que : repérer l’erreur

i ← 1
Tant que i ≤ 8 faire
  c ← a + b
  Afficher(c)
  b ← a
  a ← c
FinTantQue

Pourquoi cet algorithme risque-t-il de ne jamais s’arrêter ?

Indice

Regarde la variable utilisée dans la condition : $i\le 8$.

Correction détaillée

La variable $i$ est testée dans la condition, mais elle n’est jamais modifiée dans la boucle.

Il faut ajouter :

i ← i + 1

Réponse attendue : « La boucle peut être infinie car $i$ reste égal à 1. Il faut incrémenter $i$ à chaque tour. »

Question 4 — Écrire un algorithme Fibonacci propre

Écris un pseudo-code qui affiche les 10 premiers termes de Fibonacci en partant de $1,1$.

Indice

Déclare $i,a,b,c$ en entiers ; initialise $a$ et $b$ ; affiche les deux premiers termes ; boucle pour calculer les suivants.

Correction modèle

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 8 tours ? Les deux premiers termes sont déjà affichés. Pour obtenir 10 termes au total, il reste $10-2=8$ termes à calculer.

2. Graphes orientés

Question 5 — Lire des chemins

On suppose que les arcs suivants existent : $$A\to B,\quad B\to A,\quad A\to C,\quad C\to D.$$ Dire si les chemins $(A,B,A)$, $(B,A,C,D)$ et $(A,D)$ existent.

Indice

Un chemin existe si chaque transition consécutive existe dans le bon sens.

Correction détaillée

$(A,B,A)$ existe car $A\to B$ et $B\to A$.
$(B,A,C,D)$ existe car $B\to A$, $A\to C$ et $C\to D$.
$(A,D)$ n’existe pas directement car l’arc $A\to D$ n’est pas donné.

Question 6 — Boucle ou circuit ?

Expliquer la différence entre une boucle et un circuit, puis donner un exemple avec $A$ et $B$.

Indice

Une boucle a longueur 1. Un circuit revient au départ après plusieurs arcs possibles.

Correction modèle

Une boucle est un arc du type $A\to A$.

Un circuit est un chemin fermé : il part d’un sommet et revient au même sommet. Exemple : $(A,B,A)$ si $A\to B$ et $B\to A$ existent.

3. Matrice d’adjacence

Question 7 — Construire $M$ à partir d’arcs

Ordre des sommets : $A,B,C,D$. Arcs : $$A\to B,\, A\to C,\, B\to A,\, B\to C,\, C\to D,\, D\to A.$$ Construire la matrice d’adjacence.

Indice

Ligne = départ. Colonne = arrivée. Remplis une ligne à la fois.

Correction détaillée

Avec l’ordre $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}.$$

Ligne $A$ : $A\to B$ et $A\to C$, donc $(0,1,1,0)$.

Ligne $B$ : $B\to A$ et $B\to C$, donc $(1,0,1,0)$.

Ligne $C$ : $C\to D$, donc $(0,0,0,1)$.

Ligne $D$ : $D\to A$, donc $(1,0,0,0)$.

Question 8 — Interpréter un coefficient

Dans la matrice précédente, que signifient $m_{AC}=1$ et $m_{AD}=0$ ?

Indice

$m_{ij}$ se lit « ligne $i$, colonne $j$ ».

Correction modèle

$m_{AC}=1$ signifie qu’il existe un arc direct $A\to C$.

$m_{AD}=0$ signifie qu’il n’existe pas d’arc direct $A\to D$.

4. Puissances de matrices et chemins

Question 9 — Interpréter $M^3$

On donne que le coefficient ligne $A$, colonne $D$ de $M^3$ vaut $2$. Interpréter cette information.

Indice

$M^k$ compte les chemins de longueur exactement $k$.

Correction modèle

Le coefficient $(A,D)$ de $M^3$ vaut $2$, donc il existe 2 chemins de longueur exactement 3 allant de $A$ vers $D$.

La phrase importante est : « longueur exactement 3 », pas « au plus 3 ».

Question 10 — Accessibilité

Si le coefficient $(B,D)$ de $M+M^2+M^3+M^4$ est non nul, que peut-on conclure ?

Indice

La somme regroupe les chemins de longueurs 1, 2, 3 et 4.

Correction modèle

On peut conclure que $D$ est accessible depuis $B$ par un chemin de longueur comprise entre $1$ et $4$.

On ne connaît pas forcément le nombre exact minimal d’arcs sans regarder les puissances séparément.

5. Matrices générales

Question 11 — Produit ligne-colonne

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

Indice

Chaque coefficient du résultat = une ligne de $A$ multipliée par une colonne de $B$.

Correction détaillée

$$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}.$$

Question 12 — Format du produit

Le produit $A_{3\times 2}B_{2\times 4}$ est-il possible ? Si oui, quelle est la taille du résultat ?

Indice

Colonnes de $A$ = lignes de $B$ ? Résultat = lignes de $A$ × colonnes de $B$.

Correction modèle

Oui, car $A$ a $2$ colonnes et $B$ a $2$ lignes.

Le résultat est de taille $3\times4$.

$$A_{3\times2}B_{2\times4}=AB_{3\times4}.$$

6. Matrice identité et inverse

Question 13 — Utiliser $CA=I$

On sait que $AX=Y$ et que $CA=I$. Exprimer $X$ en fonction de $C$ et $Y$.

Indice

Multiplie l’égalité $AX=Y$ à gauche par $C$.

Correction détaillée

$$AX=Y$$ $$CAX=CY$$ $$(CA)X=CY$$ $$IX=CY$$ $$X=CY.$$

Phrase attendue : comme $CA=I$, on obtient $X=CY$.

Question 14 — Reconnaître l’identité

Quelle est la matrice identité d’ordre $3$ ? Pourquoi est-elle importante ?

Indice

Des $1$ sur la diagonale principale, des $0$ ailleurs.

Correction modèle

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

Elle est importante car elle joue le rôle du nombre $1$ : $AI=IA=A$ quand les formats conviennent.

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

Question 15 — Binaire vers décimal

Convertir $11011_2$ en base 10.

Indice

Écris les puissances de 2 : $2^4,2^3,2^2,2^1,2^0$.

Correction détaillée

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

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

Question 16 — Décimal vers binaire

Convertir $185_{10}$ en base 2.

Indice

Décompose avec les puissances de 2 : $128,64,32,16,8,4,2,1$.

Correction détaillée

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

Donc les bits pour $128,64,32,16,8,4,2,1$ sont :

$$1\ 0\ 1\ 1\ 1\ 0\ 0\ 1.$$

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

Question 17 — Hexadécimal vers décimal

Convertir $1CE_{16}$ en base 10.

Indice

$C=12$, $E=14$.

Correction détaillée

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

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

8. Addition binaire

Question 18 — Addition du tableau

Calculer $11011_2+101_2$.

Indice

Aligne les nombres à droite : $11011_2+00101_2$.

Correction détaillée

  11011
+ 00101
=100000

Vérification décimale :

$$11011_2=27_{10},\qquad 101_2=5_{10},\qquad 27+5=32=100000_2.$$

Donc :

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

Question 19 — Règle de retenue

Que valent $1+1$ et $1+1+1$ en binaire ?

Correction

$$1+1=10_2,$$

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

Dans une addition posée, cela signifie qu’on écrit le bit de droite et qu’on transporte une retenue.

9. Déclencheurs de questions

Question 20 — Associer question et réflexe

Pour chaque formulation, écris le réflexe attendu.

Énoncé	Réflexe attendu
« Construire la matrice d’adjacence »
« Interpréter $M^3$ »
« $AX=Y$ et $CA=I$ »
« Convertir en base 16 »

Correction modèle

Matrice d’adjacence : ligne = départ, colonne = arrivée, $1$ si arc, $0$ sinon.
$M^3$ : nombre de chemins de longueur exactement $3$.
$AX=Y$ et $CA=I$ : multiplier à gauche par $C$, conclure $X=CY$.
Base 16 : divisions par 16 ou paquets de 4 bits depuis le binaire ; utiliser $A=10, B=11, C=12, D=13, E=14, F=15$.

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

Question 21 — À réciter sans regarder

Cache la correction et écris les 7 lignes à mettre sur brouillon au début de l’épreuve.

Correction à mémoriser

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

Version 30 minutes sans écrire : lis chaque question, réponds oralement, ouvre seulement les corrections. Version active : écris les calculs dans les zones de réponse puis compare.