Chapitre 1 · Logique booléenne et mathématique

Une proposition est un énoncé qui vaut vrai (1) ou faux (0), jamais les deux. Les connecteurs se définissent uniquement par leur table de vérité : c'est elle, et non l'intuition du français, qui dit ce qu'une expression vaut.

$p$	$q$	$p \land q$	$p \lor q$	$p \Rightarrow q$
1	1	1	1	1
1	0	0	1	0
0	1	0	1	1
0	0	0	0	1

b) Sur quelle ligne, et sur elle seule, l'implication $p \Rightarrow q$ est-elle fausse ? Traduisez cette ligne en français avec l'exemple : « si le fichier existe, alors la lecture réussit ».

Voir la correction

Réponse

b) La ligne $p=1$ , $q=0$ : la promesse n'est trahie que si le fichier existe et que la lecture échoue

b) Une seule ligne : $p=1$ et $q=0$ . Une implication n'est fausse que lorsque la prémisse est vraie et la conclusion fausse. Sur l'exemple : la promesse « si le fichier existe, alors la lecture réussit » n'est trahie que dans le cas où le fichier existe bel et bien et où la lecture échoue quand même. Si le fichier n'existe pas, la promesse n'est pas testée, et on la déclare tenue : les deux dernières lignes valent 1. C'est le point que les étudiants refusent le plus longtemps, parce que le « si » du français porte une idée de cause que le $\Rightarrow$ de la logique n'a pas.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 2 · Techniques de démonstration

La contraposée n'est pas une variante de style : c'est le choix qu'on fait quand l'hypothèse $P$ est PAUVRE, c'est-à-dire impossible à traduire en une écriture utile, alors que la négation de la conclusion, elle, se manipule sans effort. Le geste est toujours le même : on écrit $\lnot Q$ , on regarde si elle est riche, et si oui on démontre $\lnot Q \Rightarrow \lnot P$ , qui a exactement la même valeur de vérité d'après l'exercice 2.

Une règle de négation revient dans chaque question : la négation de « $A$ ou $B$ » est « $\lnot A$ et $\lnot B$ », et celle de « $A$ et $B$ » est « $\lnot A$ ou $\lnot B$ ».

b) Soient $x$ et $y$ deux entiers strictement positifs. Démontrez : si $xy>1\,000$ , alors $x>31$ ou $y>31$ .

Voir la correction

Réponse

b) Négation de la conclusion : $x \leq 31$ et $y \leq 31$ , donc $xy \leq 961 \leq 1\,000$ . L'énoncé est vrai

b) La conclusion est un OU, et la négation d'un OU est un ET : « $x \leq 31$ ET $y \leq 31$ ». C'est là que tout se joue, car cette négation est riche, elle donne deux majorations utilisables, alors que la conclusion d'origine, un OU, ne se manipule pas. Contraposée à démontrer : si $x \leq 31$ et $y \leq 31$ , alors $xy \leq 1\,000$ . Preuve : $x$ et $y$ étant strictement positifs, $xy \leq 31 \times 31 = 961 \leq 1\,000$ . Donc l'énoncé est vrai. La borne est fine : $31^{2}=961$ passe, et $32^{2}=1\,024$ dépasse bien 1 000, ce qui montre que le seuil 31 n'est pas choisi au hasard. Le piège, sanctionné à chaque examen : écrire la négation « $x \leq 31$ ou $y \leq 31$ ». Avec ce ou, le couple $(10\,;200)$ vérifie l'hypothèse et donne $xy=2\,000$ , la preuve s'effondre et l'étudiant conclut à tort que l'énoncé est faux.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 3 · Systèmes de numération informatique

Pour convertir un entier décimal vers la base $b$ , on divise à répétition par $b$ et on lit les restes DE BAS EN HAUT. Pour une partie fractionnaire, on multiplie à répétition par $b$ et on lit les parties entières DE HAUT EN BAS. Les deux algorithmes se ressemblent, mais le sens de lecture est inversé : c'est là que se perdent la moitié des points.

a) Convertissez 156 en binaire par divisions successives et vérifiez par les poids.

Voir la correction

Réponse

a) $156 = 10011100_2$

a) $156 = 2(78) + 0$ ; $78 = 2(39)+0$ ; $39 = 2(19)+1$ ; $19 = 2(9)+1$ ; $9 = 2(4)+1$ ; $4 = 2(2)+0$ ; $2 = 2(1)+0$ ; $1 = 2(0)+1$ . Les restes lus de bas en haut donnent $10011100_2$ . Vérification par les poids : $128 + 16 + 8 + 4 = 156$ . Le contrôle par les poids est obligatoire, parce qu'il attrape l'erreur de sens de lecture, qui donnerait $00111001$ .

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 4 · L'arithmétique modulaire

Toute l'arithmétique modulaire tient dans une opération que l'on croit connaître depuis l'école primaire. Le fil de la série : on ne s'intéresse plus au QUOTIENT mais au RESTE, et un reste est toujours positif, même quand le dividende ne l'est pas.

c) Calculez $-17 \bmod 5$ et $-1 \bmod 12$ . Attention au signe du reste.

Voir la correction

Réponse

c) $-17 \bmod 5 = 3$ et $-1 \bmod 12 = 11$

c) Pour $-17$ par 5 : le quotient doit être choisi de sorte que le reste tombe dans $[0;5[$ . Avec $q=-4$ : $-17=5\times(-4)+3$ , donc $r=3$ . Le réflexe $-17=5\times(-3)-2$ donnerait $r=-2$ , qui n'est pas un reste valide. Pour $-1$ par 12 : $-1=12\times(-1)+11$ , donc $r=11$ : c'est le dernier cran de l'horloge avant de repasser par zéro, ce qui est exactement l'image à retenir.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 5 · Théorie des ensembles et relations

Soit $E = \{1,2,\dots,10\}$ l'ensemble de référence, $A = \{1,2,3,4,5,6\}$ et $B = \{4,5,6,7,8\}$ . On note $\overline{A}$ le complémentaire de $A$ dans $E$ .

a) Donnez $A \cup B$ , $A \cap B$ , $A \setminus B$ et $B \setminus A$ en extension.

Voir la correction

Réponse

a) $A \cup B = \{1,\dots,8\}$ , $A \cap B = \{4,5,6\}$ , $A \setminus B = \{1,2,3\}$ , $B \setminus A = \{7,8\}$

a) $A \cup B = \{1,2,3,4,5,6,7,8\}$ : tous les éléments qui sont dans l'un OU dans l'autre, comptés une seule fois. $A \cap B = \{4,5,6\}$ : ceux qui sont dans les deux. $A \setminus B = \{1,2,3\}$ : dans $A$ mais pas dans $B$ . $B \setminus A = \{7,8\}$ . Notez que $A \setminus B$ et $B \setminus A$ n'ont rien à voir : la différence n'est pas symétrique.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 6 · Fonctions injectives, surjectives, bijectives

Une relation de $A$ vers $B$ est n'importe quelle partie de $A \times B$ . Une FONCTION $f : A \to B$ est une relation qui remplit deux conditions, et deux seulement : chaque élément de $A$ a une image (EXISTENCE), et il n'en a qu'une (UNICITÉ). Tout le chapitre repose sur ce départ, parce qu'une relation qui échoue sur l'une des deux conditions ne mérite même pas qu'on demande si elle est injective.

La figure donne quatre relations de $A = \{1,2,3\}$ vers $B = \{a,b,c\}$ , dessinées en diagramme sagittal : une flèche du départ vers l'arrivée pour chaque couple de la relation.

a) Parmi les quatre relations de la figure, lesquelles sont des fonctions de $A$ vers $B$ ? Pour chaque relation rejetée, nommez la condition qui manque.

Voir la correction

Réponse

a) Les fonctions sont (1) et (4) ; (2) rate l'existence, (3) rate l'unicité

a) Les fonctions sont (1) et (4). La relation (2) échoue sur l'EXISTENCE : l'élément 2 n'a aucune flèche qui en part, donc $f(2)$ ne désigne rien et l'écriture elle-même perd son sens. La relation (3) échoue sur l'UNICITÉ : deux flèches partent de 1, vers $a$ et vers $b$ , donc $f(1)$ désignerait deux objets à la fois. Le test se lit d'un coup d'oeil sur un diagramme sagittal : il faut EXACTEMENT UNE flèche au départ de CHAQUE élément de gauche. Ni zéro, ni deux. Rien n'est exigé à l'arrivée en revanche : un élément de $B$ peut recevoir zéro, une ou dix flèches sans qu'on quitte le cadre des fonctions. C'est précisément cette dissymétrie entre le départ et l'arrivée qui produira l'injectivité et la surjectivité dans les exercices suivants.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 7 · Récurrence et récursivité

La récurrence est le seul outil qui démontre une infinité d'énoncés en deux lignes. Le fil de la série : une démonstration par récurrence a DEUX étapes, et laisser tomber l'une ou l'autre ne produit pas une démonstration incomplète, elle produit une démonstration fausse.

d) Que se passe-t-il si l'on oublie l'HÉRÉDITÉ ? Illustrez avec « $n^{2}+n+41$ est premier ».

Voir la correction

Réponse

d) $n^{2}+n+41$ est premier de $n=0$ à $n=39$ , puis $40^{2}+40+41 = 1681 = 41^{2}$

d) Sans hérédité, vérifier des cas ne prouve rien non plus. La propriété « $n^{2}+n+41$ est premier » est vraie pour $n=0$ , où l'on obtient 41, pour $n=1$ , où l'on obtient 43, et en fait pour tous les entiers de 0 à 39. Elle est FAUSSE en $n=40$ , car $40^{2}+40+41=1681=41^{2}$ . Quarante vérifications successives ne valent pas une démonstration : l'hérédité est ce qui remplace une infinité de vérifications.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 8 · Introduction aux graphes et aux matrices

La matrice d'adjacence $M$ d'un graphe à $n$ sommets est la matrice $n \times n$ dont le coefficient $M_{ij}$ vaut 1 s'il existe un arc du sommet $i$ vers le sommet $j$ , et 0 sinon. Elle contient exactement la même information que le dessin, mais elle se calcule. Le graphe orienté ci-dessous a quatre sommets numérotés de 1 à 4.

b) Que représentent la somme des coefficients d'une ligne ? Et d'une colonne ?

Voir la correction

Réponse

b) Ligne : degré SORTANT. Colonne : degré ENTRANT

b) La somme de la ligne $i$ est le nombre d'arcs partant de $i$ , c'est-à-dire son degré SORTANT. La somme de la colonne $j$ est le nombre d'arcs arrivant en $j$ , son degré ENTRANT. Confondre les deux est l'erreur qui fausse toute la suite du chapitre, parce qu'elle revient à transposer le graphe.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Chapitre 9 · Dénombrement et probabilités

Le coefficient binomial compte les sous-ensembles, et sa relation de récurrence est la même que celle d'un algorithme récursif. C'est aussi l'occasion de retrouver la programmation dynamique du chapitre sur la récurrence et la récursivité.

a) Démontrez la relation de Pascal $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ par un argument de dénombrement, sans calcul.

Voir la correction

Réponse

a) Les parties se répartissent selon qu'elles contiennent $x$ ou non : $\binom{n-1}{k-1} + \binom{n-1}{k}$

a) On compte les parties à $k$ éléments d'un ensemble de $n$ éléments, en isolant un élément particulier $x$ . Ces parties se répartissent en deux catégories sans recouvrement. Celles qui CONTIENNENT $x$ : il reste à choisir $k-1$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k-1}$ . Celles qui ne le contiennent PAS : il faut choisir les $k$ éléments parmi les $n-1$ autres, soit $\binom{n-1}{k}$ . Toute partie relève d'exactement un des deux cas, d'où l'égalité. Aucun calcul, seulement un partage en deux.

L'exercice complet, avec toutes ses questions →

La série du chapitre · la fiche de révision

Faire le point : Mathématiques pour l'informatique (201-N11)

Ce que le cours suppose

Les chapitres du cours

Et maintenant ?