Table de Karnaugh

Exercice type BTS pour maîtriser la simplification des fonctions booliennes via la table de Karnaugh.

Exercice 1.
Partie A.
On considère le graphe orienté G comportant 3 sommets notés A, B et C dont la matrice d’adjacence est P, où
\[
P = \begin{pmatrix}
1 & 0 & 0 \\
1 & 0 & 0 \\
1 & 0 & 0
\end{pmatrix}.
\]

$\bullet$ Dessiner une représentation du graphe G.
$\bullet$
$\circ$ Calculer la matrice $P^2$.
$\circ$ Combien de chemins de longueur 2 ont pour origine B ?
$\bullet$ Déterminer la matrice d’adjacence $P$ et le graphe de la fermeture transitive de G.

Partie B.
Dans un graphe orienté, on définit :
$\circ$ le degré entrant d’un sommet comme étant le nombre d’arcs menant à ce sommet.
$\circ$ le degré sortant d’un sommet comme étant le nombre d’arcs issus de ce sommet.

$\bullet$
$\circ$ Calculer le degré entrant du sommet C du graphe G défini dans la partie A.
$\circ$ Calculer le degré sortant du sommet C du graphe G défini dans la partie A.
$\bullet$ On étudie dans cette question les graphes orientés à trois sommets numérotés de 1 à 3.\\
On considère l’algorithme ci-dessous écrit en langage naturel où \texttt{Degré\_sortant} désigne une fonction de paramètres $M$ et $s$, $M$ étant une matrice à 3 lignes et 3 colonnes et $s$ un entier compris entre 1 et 3. Le coefficient de la matrice $M$ situé ligne $i$ colonne $j$ est noté $m_{ij}$.

Fonction Degré_sortant (M,s)
deg $\leftarrow$ 0
Pour j allant de 1 à 3 Faire
Si ...... Faire
......
Fin de Si
Fin de Pour
Retourner deg

Compléter cet algorithme pour que la fonction renvoie le degré sortant du sommet numéroté $s$ dans un graphe dont la matrice d’adjacence est $M$.

Exercice 2.

Une entreprise décide de mettre en place une authentification à plusieurs étapes permettant à ses employés d’accéder aux services en ligne qu’elle propose.

Partie A.
La première authentification consiste à utiliser un mot de passe.
À la première connexion, l’utilisateur doit créer un mot de passe de 8 à 16 caractères. Ces caractères peuvent être des lettres majuscules de l’alphabet ou des chiffres ou des caractères spéciaux (?, $\&$, etc.).
Pour être valide, un mot de passe doit remplir au moins l’une des trois conditions suivantes :
$\circ$ il contient au moins trois chiffres et au moins deux caractères spéciaux ;
$\circ$ il contient au moins dix lettres et au moins deux caractères spéciaux ;
$\circ$ il contient au moins dix lettres et au moins trois chiffres.

$\bullet$ Les mots de passe suivants sont-ils valides ? Justifier.
$\circ$ ABCDABCD ?\#
$\circ$ STU27ABCABCDE\&
$\bullet$ On définit les variables booléennes $a$, $b$ et $c$ de la manière suivante :
$\circ$ $a$ lorsque le mot de passe contient au moins trois chiffres, $\overline{a}$ sinon ;
$\circ$ $b$ lorsque le mot de passe contient au moins deux caractères spéciaux, $\overline{b}$ sinon ;
$\circ$ $c$ lorsque le mot de passe contient au moins dix lettres, $\overline{c}$ sinon.

$\circ$ On appelle $E$ l’expression booléenne qui traduit la validité d’un mot de passe. Traduire chacune des conditions de validité d’un mot de passe à l’aide des variables $a$, $b$ et $c$, puis en déduire une expression de $E$.
$\circ$ Représenter $E$ dans un tableau de Karnaugh, puis en déduire une expression simplifiée de $E$ sous la forme d’une somme de deux termes.
$\circ$ Traduire par une phrase l’expression simplifiée de $E$.
$\circ$ Déterminer l’expression booléenne $\overline{E}$ négation de $E$.

Partie B.
Pour la seconde authentification, le serveur de l’entreprise envoie à l’utilisateur un mot de passe codé qu’il devra décoder.
Le serveur de l’entreprise code un mot de passe de la façon suivante :
$\circ$ à chaque lettre de l’alphabet, on associe son rang $x$ (de 0 à 25) ;
$\circ$ on fixe une clé $(a ; b)$, où $a$ et $b$ sont deux entiers naturels compris entre 0 et 25 ;
$\circ$ on calcule le reste $y$ de la division de $ax + b$ par 26 ; on détermine ainsi le plus petit entier naturel $y$ vérifiant $y \equiv ax + b \pmod{26}$ ;
$\circ$ on cherche ensuite la lettre de l’alphabet dont le rang est $y$ ;
$\circ$ cette lettre code la lettre donnée au départ.

$\bullet$ Le serveur de l’entreprise utilise la clé $(9; 15)$.
$\circ$ Montrer que la lettre C est codée par la lettre H.
$\circ$ Par quelle lettre est codée la lettre E ?
$\bullet$ L’utilisateur veut décoder la lettre V associée à l’entier $y = 21$. Pour cela il doit déterminer le plus petit entier naturel $x$ vérifiant $21 \equiv 9x + 15 \pmod{26}$.
$\circ$ Déterminer un entier $c$ vérifiant $9 \times c \equiv 1 \pmod{26}$.
$\circ$ Montrer que si $21 \equiv 9x + 15 \pmod{26}$ alors $x \equiv 18 \pmod{26}$.
$\circ$ Décoder la lettre V.

Exercice 3.

Le tableau ci-dessous donne les différentes tâches à réaliser pour aménager une salle informatique dans un lycée, leurs durées et leurs conditions d’antériorité. (Le tableau n'est pas reproduit ici.)
Le but de cet exercice est d’ordonner la réalisation de ces tâches de façon à ce que la salle soit disponible le plus rapidement possible.
On considère le graphe orienté correspondant aux conditions d’antériorité données par le tableau précédent. Les sommets A, B, C, D, E, F, G et H représentent les repères des tâches à réaliser.
1. Déterminer le niveau de chacun des sommets du graphe.
2. Donner le tableau des successeurs de chacun des sommets du graphe.
Construire le graphe d’ordonnancement du projet (Méthode P.E.R.T. ou M.P.M.).
3. Déterminer, pour chaque tâche, les dates au plus tôt et au plus tard.
4. En déduire le chemin critique et la durée minimale de réalisation du projet.
5. La tâche E prend une semaine de retard. Quelle est l’incidence de ce retard sur la durée totale de ce projet ? Justifier.

Partie B.
Le gestionnaire du lycée considère que le projet est envisageable lorsqu’il satisfait à l’une au moins des conditions suivantes :
1. Le matériel vidéo est acheté dans un magasin local et est de fabrication française.
2. Le matériel vidéo n’est pas de fabrication française et il coûte moins de 500 euros.
3. Le matériel vidéo n’a pas été acheté dans un magasin local, est de fabrication française et a coûté moins de 500 euros.
On définit les variables $a$, $b$, $c$ de la façon suivante :
$a$ : le matériel vidéo coûte moins de 500 euros ; $\overline{a}$ : le matériel vidéo coûte 500 euros ou plus.
$b$ : le matériel vidéo est acheté dans un magasin local ; $\overline{b}$ : le matériel vidéo n’est pas acheté dans un magasin local.
$c$ : le matériel vidéo est de fabrication française ; $\overline{c}$ : le matériel vidéo n’est pas de fabrication française.
$\circ$ Écrire une expression booléenne $E$ traduisant que le projet est envisageable, à l’aide des variables booléennes $a$, $b$, $c$.
$\circ$
1. À l’aide d’un tableau de Karnaugh, déterminer une écriture simplifiée de $E$ à deux termes.
2. En déduire une interprétation simplifiée des conditions pour que le projet soit envisageable.
$\circ$ Dans le projet présenté, le matériel vidéo coûte plus de 500 euros, n’est pas de fabrication française mais sera acheté localement. Ce projet est-il envisageable ?

Exercice 4 : un problème de routage.

Les parties A et B sont indépendantes.

Partie A.
On considère un réseau de commutation de paquets constitué de 6 routeurs A, B, C, D, E et F. Chaque paquet reçu par l’un des routeurs doit être acheminé vers un autre routeur, jusqu’à atteindre sa destination finale. Dans le tableau ci-dessous, on a résumé les règles de routage d’un routeur à un autre routeur (tableau non reproduit).

On considère le graphe simple orienté $G$ constitué des sommets A, B, C, D, E et F. Les sommets représentent les routeurs. Si un sommet X peut transmettre un paquet vers un sommet Y alors on a l’arc X $\to$ Y.
$\circ$
1. Recopier et compléter le tableau des successeurs et des prédécesseurs du graphe $G$ (tableau non reproduit).
2. Déterminer la matrice d’adjacence $M$ du graphe $G$, les sommets étant rangés par ordre alphabétique.
$\circ$
1. Calculer $M^3$.
2. Combien existe-t-il de chemins de longueur 3 allant du sommet B au sommet D ?
$\circ$
1. Déterminer la matrice $M^*$ de la fermeture transitive du graphe $G$.
2. Que signifie le nombre 1 à l’intersection de la troisième ligne et la sixième colonne de $M^*$ ?
$\circ$ Existe-t-il un chemin hamiltonien dans ce graphe ? Si oui, en indiquer un.

Partie B.
Dans un parc informatique, chaque machine connectée à un réseau peut être identifiée à l’aide d’une adresse IPv4.
$\circ$
1. Dans la base 2, un octet est constitué de 8 chiffres. Déterminer le plus grand entier noté en base 10 qu’on peut écrire sous la forme d’un octet.
2. Une adresse IPv4 étant constituée de 4 octets notés en base 10 et séparés par un point, quel nombre maximal d’adresses IPv4 peuvent être attribuées ?
$\circ$ Le routeur C de la partie A gère les connexions réseaux d’un parc informatique de 8 machines étiquetées de 1 à 8. Le DHCP de ce routeur est paramétré de telle façon qu’il attribue une plage de 49 adresses IPv4 allant de 192.168.1.2 jusqu’à 192.168.1.50. Les 8 machines sont identifiées grâce aux adresses IPv4 suivantes (tableau non reproduit). Écrire le premier octet commun aux adresses de ces machines sous forme binaire puis sous forme hexadécimal.

Exercice 5.
Le spam, courriel indésirable ou pourriel, est une communication électronique non sollicitée, en premier lieu via le courrier électronique. Il s’agit en général d’envois en grande quantité effectués à des fins publicitaires. Un étudiant en BTS SIO a développé un logiciel anti spam. Le filtre mis en place par l’étudiant se base sur les trois variables booléennes suivantes :
$a$ : l’objet du message contient au moins un terme douteux (gratuit, offre, promotion, gagner...), $\overline{a}$ : l’objet du message ne contient aucun terme douteux ;
$b$ : le corps du message contient des images ou des hyperliens, $\overline{b}$ : le corps du message ne contient ni images, ni hyperliens ;
$c$ : les messages de l’expéditeur sont rarement lus, $\overline{c}$ : les messages de l’expéditeur sont lus fréquemment.
Avec ce logiciel, un courriel est considéré comme indésirable si :
1. l’objet du message contient au moins un terme douteux avec un corps du message contenant des images ou des hyperliens ;
2. l’objet du message ne contient aucun terme douteux mais le corps du message contient des images ou des hyperliens et les messages de l’expéditeur sont rarement lus ;
3. le corps du message ne contient ni images, ni hyperliens mais les messages de l’expéditeur sont rarement lus.

$\circ$ Traduire chaque condition par une expression booléenne en fonction des variables $a$, $b$ et $c$ puis déterminer l’expression booléenne $E$ traduisant les conditions pour qu’un courriel soit considéré comme indésirable. Pour la suite de l’exercice, on admet que $E = ab + \overline{c}\,\overline{a} + b\overline{c}$.
$\circ$
1. Présenter $E$ dans une table de Karnaugh.
2. Un courriel, ayant comme objet « promotion : une réduction de 50\% ... » et dont les messages de l’expéditeur sont lus fréquemment, peut-il être considéré comme indésirable ? Justifier.
3. En utilisant la table de Karnaugh, déduire l’expression simplifiée de $E$ sous la forme d’une somme de deux termes dont l’un est éventuellement un produit.
$\circ$ Traduire, en français, la règle pour considérer un courriel comme indésirable.
$\circ$ Donner une expression de $\overline{E}$.

---

Pour plus de détails, consulter le PDF ci-joint.

---