TP Python – Circuits, tableaux de Karnaugh et masques
BTS SIO SISR 1re année – Mathématiques pour l'informatique – S10
Note
Comment ce TP fonctionne. Chaque exercice a un éditeur Python intégré à la page (il s'exécute dans ton navigateur, rien à installer). Avant de lancer, écris sur ta feuille ce que tu anticipes (« J'anticipe »). Puis lance et compare. Le bouton Valider exécute des tests : un test réussi ne dispense pas de comprendre pourquoi.
Exercice A – Les mintermes d'une fonction
Écris mintermes(f, n) qui renvoie la liste des numéros de lignes (de 0 à \(2^n - 1\), l'ordre de la table de vérité) pour lesquelles la fonction f de n arguments vaut 1. Le numéro de ligne k donne les valeurs des variables par son écriture binaire sur n bits (le bit de poids fort est la première variable).
J'anticipe. Pour f = lambda a, b, c: (a and c) or not b, quelles lignes attends-tu ? Compare à l'exercice 3 des exercices.
def mintermes(f, n):bksl-nl """Numéros des lignes (0 à 2py-strpy-strn - 1) pour lesquelles f vaut 1."""bksl-nl resultat = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl valeurs = []bksl-nl for i in range(n):bksl-nl # À compléter : le bit de rang (n - 1 - i) de kbksl-nl valeurs.append(0)bksl-nl if f(py-strvaleurs):bksl-nl resultat.append(k)bksl-nl return resultatbksl-nlbksl-nl
Exercice B – Vérifier une simplification
Écris meme_fonction(f, g, n) qui renvoie True si f et g donnent le même résultat sur les \(2^n\) combinaisons. Utilise-la pour contrôler tes simplifications de la feuille d'exercices.
Je comprends. Pourquoi suffit-il de tester les \(2^n\) combinaisons pour être sûr de l'égalité de deux expressions ? Pourquoi ne peut-on pas faire de même avec des nombres entiers ?
def memepy-undfonction(f, g, n):bksl-nl """Vrai si f et g donnent le même résultat sur les 2py-strpy-strn combinaisons."""bksl-nl for k in range(2 py-strpy-str n):bksl-nl valeurs = []bksl-nl for i in range(n):bksl-nl valeurs.append((k >> (n - 1 - i)) & 1)bksl-nl # À compléter : renvoyer False si f et g diffèrent sur cette combinaisonbksl-nl return Truebksl-nlbksl-nl
Exercice C – Tout avec des NAND
Écris non_nand, et_nand, ou_nand et xor_nand en n'utilisant que la fonction nand fournie.
def nand(a, b):bksl-nl return 1 - (a & b)bksl-nlbksl-nldef nonpy-undnand(a):bksl-nl # À compléter : uniquement avec nandbksl-nl return 0bksl-nlbksl-nldef etpy-undnand(a, b):bksl-nl # À compléter : uniquement avec nandbksl-nl return 0bksl-nlbksl-nldef oupy-undnand(a, b):bksl-nl # À compléter : uniquement avec nandbksl-nl return 0bksl-nlbksl-nldef xorpy-undnand(a, b):bksl-nl # À compléter : quatre portes nandbksl-nl return 0bksl-nlbksl-nl
Exercice D – Additionneur
Écris additionneur_complet(a, b, c) qui renvoie (somme, retenue) pour trois bits (0 ou 1), à l'aide de ^, & et |. Puis écris additionne(x, y) qui additionne deux chaînes de bits de même longueur et renvoie la somme sur une position de plus. Exemple : additionne("0110", "0111") donne "01101" (6 + 7 = 13).
def additionneurpy-undcomplet(a, b, c):bksl-nl """Renvoie (somme, retenue) pour trois bits."""bksl-nl somme = 0 # À compléter : a ^ b ^ cbksl-nl retenue = 0 # À compléter : (a & b) | (c & (a ^ b))bksl-nl return (somme, retenue)bksl-nlbksl-nldef additionne(x, y):bksl-nl """Additionne deux chaînes de bits de même longueur ; résultat sur une position de plus."""bksl-nl n = len(x)bksl-nl resultat = ""bksl-nl retenue = 0bksl-nl for i in range(n - 1, -1, -1):bksl-nl # À compléter : additionner les bits de rang i et la retenue,bksl-nl # ajouter la somme au début du résultat, mémoriser la nouvelle retenuebksl-nl passbksl-nl return str(retenue) + resultatbksl-nlbksl-nl
Exercice E – Masques et adresses
Écris les fonctions de masques.py : prefixe_vers_masque(n) (par exemple 26 donne "255.255.255.192"), adresse_reseau(ip, masque) (ET bit à bit octet par octet), diffusion(ip, masque) (les bits de machine mis à 1) et nb_machines(n) (adresses utilisables pour le préfixe n).
Je comprends. Pourquoi retire-t-on 2 au nombre d'adresses du réseau ?
def prefixepy-undverspy-undmasque(n):bksl-nl """Masque décimal pointé d'un préfixe n (0 à 32)."""bksl-nl octets = []bksl-nl for i in range(4):bksl-nl bits = min(8, max(0, n - 8 py-str i)) # nombre de bits à 1 dans cet octetbksl-nl # À compléter : valeur de l'octet = 256 - 2 py-strpy-str (8 - bits)bksl-nl octets.append("0")bksl-nl return ".".join(octets)bksl-nlbksl-nldef adressepy-undreseau(ip, masque):bksl-nl """ET bit à bit, octet par octet."""bksl-nl a = ip.split(".")bksl-nl m = masque.split(".")bksl-nl octets = []bksl-nl for i in range(4):bksl-nl # À compléter : int(a[i]) & int(m[i])bksl-nl octets.append("0")bksl-nl return ".".join(octets)bksl-nlbksl-nldef diffusion(ip, masque):bksl-nl """Adresse réseau dont tous les bits de machine sont à 1."""bksl-nl a = ip.split(".")bksl-nl m = masque.split(".")bksl-nl octets = []bksl-nl for i in range(4):bksl-nl # À compléter : (int(a[i]) & int(m[i])) | (255 - int(m[i]))bksl-nl octets.append("0")bksl-nl return ".".join(octets)bksl-nlbksl-nldef nbpy-undmachines(n):bksl-nl """Nombre d'adresses utilisables pour le préfixe n."""bksl-nl return 0 # À compléterbksl-nlbksl-nl