Les tableaux de Karnaugh permettent de représenter facilement des expressions Booléennes. Dans le cadre du programme, on se limitera à deux ou trois variables.

Graphes et Logique (Tableaux de Karnaugh) — Résumé

I. Tableaux de Karnaugh

Cas à 2 variables

Le tableau comprend $2^2 = 4$ cases, correspondant aux produits $ab$, $a\bar{b}$, $\bar{a}b$
et $\bar{a}\bar{b}$. La première ligne correspond à $a$, la seconde à $\bar{a}$; la première
colonne à $b$, la seconde à $\bar{b}$.

Pour simplifier, on colorie les cases correspondant à l'expression, puis on regroupe les cases
adjacentes/symétriques coloriées.

Exemple : $F = ab + a\bar{b} + \bar{a}b \Rightarrow F = a + b$

Cas à 3 variables

Le tableau comprend $2^3 = 8$ cases. Les colonnes suivent un code de Gray :
$ab$, $a\bar{b}$, $\bar{a}\bar{b}$, $\bar{a}b$ et les lignes $c$, $\bar{c}$.
Deux colonnes consécutives ne diffèrent que d'un bit.

$$\begin{array}{c|cccc}
& ab & a\bar{b} & \bar{a}\bar{b} & \bar{a}b \\\hline
c & & & & \\
\bar{c} & & & &
\end{array}$$

II. Graphes orientés — Rappels

La $\textit{matrice d'adjacence}$ $M$ d'un graphe à $n$ sommets est une matrice $n \times n$
où $m_{ij} = 1$ s'il existe un arc de $i$ vers $j$, $0$ sinon.

$M^k$ donne le nombre de chemins de longueur $k$ entre chaque paire de sommets.

La $\textit{fermeture transitive}$ $\hat{P} = M \oplus M^{[2]} \oplus \cdots \oplus M^{[n]}$
indique l'existence d'au moins un chemin entre chaque paire de sommets.

Le $\textit{degré entrant}$ d'un sommet = somme de sa colonne dans $M$.
Le $\textit{degré sortant}$ d'un sommet = somme de sa ligne dans $M$.

Algorithme du degré sortant :

Fonction Degré_sortant(M, s)
deg ← 0
Pour j allant de 1 à 3 Faire
Si m_sj > 0 Faire
deg ← deg + 1
Fin de Si
Fin de Pour
Retourner deg

III. Ordonnancement (PERT/MPM)

On construit le graphe par niveaux. Pour chaque tâche on calcule :

$\textit{Date au plus tôt}$ : longueur du plus long chemin depuis le début (traitement
par niveaux croissants).

$\textit{Date au plus tard}$ : en partant de la fin, on soustrait la durée de chaque tâche
à la date au plus tard de son successeur (on garde la plus petite s'il y a plusieurs
successeurs).

Le $\textit{chemin critique}$ passe par les sommets dont date au plus tôt $=$ date au plus
tard. Un retard sur une tâche hors chemin critique n'affecte pas la durée totale si le
retard est inférieur ou égal à la marge disponible.

IV. Applications booléennes — Exercices types

Exercice 2 — Validation de mot de passe

Variables : $a$ = au moins 3 chiffres ; $b$ = au moins 2 caractères spéciaux ;
$c$ = au moins 10 lettres.
$$E = ab + \bar{a}bc + \bar{b}c$$
Après simplification par Karnaugh :
$$\boxed{E = b \cdot a + c}$$
soit : le mot de passe est valide s'il contient au moins deux caractères spéciaux et
au moins trois chiffres, ou s'il contient au moins dix lettres.

Négation : $\bar{E} = \bar{b}\bar{c} + \bar{a}\bar{c}$

Exercice 3 PB — Projet envisageable

Variables : $a$ = coûte moins de 500 € ; $b$ = acheté localement ; $c$ = fabrication française.
$$E = bc + a\bar{c} + a\bar{b}c$$
Simplification par Karnaugh :
$$\boxed{E = a + bc}$$
soit : le projet est envisageable si le matériel coûte moins de 500 €, ou s'il est
acheté localement et de fabrication française.

Exercice 5 — Filtre anti-spam

Variables : $a$ = objet douteux ; $b$ = corps avec images/liens ; $c$ = expéditeur rarement lu.
$$E = ab + \bar{a}c + \bar{b}c$$
On admet $E = ab + \bar{b}c + \bar{a}c$. Simplification par Karnaugh :
$$\boxed{E = c + ab}$$
soit : un courriel est indésirable si les messages de l'expéditeur sont rarement lus,
ou si l'objet est douteux et le corps contient des images ou hyperliens.

Négation : $\bar{E} = \bar{c}(\bar{a} + \bar{b}) = \bar{a}\bar{c} + \bar{b}\bar{c}$

V. Codage affine (Exercice 2 PB)

On code la lettre de rang $x$ par la lettre de rang $y$ où :
$$y \equiv ax + b \pmod{26}$$
Pour décoder, on cherche $c$ tel que $a \cdot c \equiv 1 \pmod{26}$ (inverse de $a$ modulo 26),
puis $x \equiv c(y - b) \pmod{26}$.

Exemple avec clé $(9\,;\,15)$ : C (rang 2) $\to$ $9 \times 2 + 15 = 33 \equiv 7 \pmod{26}$
$\to$ H. Pour décoder V ($y=21$) : $9c \equiv 1 [26] \Rightarrow c=3$, puis
$x \equiv 3(21-15) = 18 [26] \Rightarrow$ S.

VI. Adressage IPv4

Un octet sur 8 bits représente au maximum $2^8 - 1 = 255$ en décimal. Une adresse IPv4
(4 octets) permet $256^4 = 4\,294\,967\,296$ adresses. Conversion :
$192 = (11000000)_2 = (\text{C0})_{16}$.

---

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

---