TP Python – Relations et applications sur des ensembles finis

BTS SIO SISR 1re année – Mathématiques pour l'informatique – S11

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.

Dans ce TP, une relation est un ensemble de couples ({(1, 2), (2, 2)}) et une application est un dictionnaire ({1: "a", 2: "b"}) dont les clés forment l'ensemble de départ.

Exercice A – Produit cartésien

Écris produit(a, b) qui renvoie l'ensemble des couples (x, y) avec x dans a et y dans b.

J'anticipe. Combien de couples pour a de 3 éléments et b de 4 ? Que renvoie produit(a, set()) ?

###

assert produit({1, 2}, {"a"}) == {(1, "a"), (2, "a")}bksl-nlassert produit(set(), {1, 2}) == set()bksl-nlassert produit({1, 2, 3}, {4, 5}) == {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}bksl-nlassert len(produit(range(3), range(4))) == 12bksl-nlassert produit({1}, {2}) != produit({2}, {1})bksl-nlbksl-nl ∞/∞

def produit(a, b):bksl-nl """Ensemble des couples (x, y), x dans a, y dans b."""bksl-nl resultat = set()bksl-nl for x in a:bksl-nl # À compléter : une boucle sur b, qui ajoute le couple (x, y)bksl-nl passbksl-nl return resultatbksl-nlbksl-nl

Exercice B – Propriétés d'une relation

Écris est_reflexive(r, e), est_symetrique(r), est_antisymetrique(r) et est_transitive(r). r est un ensemble de couples, e l'ensemble sur lequel on travaille.

Je comprends. Pour la transitivité, pourquoi faut-il deux boucles imbriquées sur les couples ? Quelle propriété est vraie « à vide » pour la relation vide ?

###

E = {1, 2, 3, 4}bksl-nlleq = {(x, y) for x in E for y in E if x <= y}bksl-nlassert estpy-undreflexive(leq, E) and estpy-undantisymetrique(leq) and estpy-undtransitive(leq)bksl-nlassert not estpy-undsymetrique(leq)bksl-nldiv = {(x, y) for x in E for y in E if y % x == 0}bksl-nlassert estpy-undreflexive(div, E) and estpy-undantisymetrique(div) and estpy-undtransitive(div) and not estpy-undsymetrique(div)bksl-nldiff = {(x, y) for x in E for y in E if x != y}bksl-nlassert not estpy-undreflexive(diff, E) and estpy-undsymetrique(diff) and not estpy-undantisymetrique(diff) and not estpy-undtransitive(diff)bksl-nlr = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}bksl-nlassert estpy-undreflexive(r, {1, 2, 3}) and estpy-undsymetrique(r) and estpy-undtransitive(r) and not estpy-undantisymetrique(r)bksl-nlassert estpy-undsymetrique(set()) and estpy-undantisymetrique(set()) and estpy-undtransitive(set()) and not estpy-undreflexive(set(), {1})bksl-nlsomme7 = {(x, y) for x in range(1, 7) for y in range(1, 7) if x + y == 7}bksl-nlassert estpy-undsymetrique(somme7) and not estpy-undtransitive(somme7) and not estpy-undreflexive(somme7, range(1, 7))bksl-nlbksl-nl ∞/∞

def estpy-undreflexive(r, e):bksl-nl for x in e:bksl-nl # À compléter : renvoyer False si (x, x) n'est pas dans rbksl-nl passbksl-nl return Truebksl-nlbksl-nldef estpy-undsymetrique(r):bksl-nl for (x, y) in r:bksl-nl # À compléter : renvoyer False si (y, x) n'est pas dans rbksl-nl passbksl-nl return Truebksl-nlbksl-nldef estpy-undantisymetrique(r):bksl-nl for (x, y) in r:bksl-nl # À compléter : renvoyer False si (y, x) est dans r avec x != ybksl-nl passbksl-nl return Truebksl-nlbksl-nldef estpy-undtransitive(r):bksl-nl for (x, y) in r:bksl-nl for (z, t) in r:bksl-nl # À compléter : si y == z, le couple (x, t) doit être dans rbksl-nl passbksl-nl return Truebksl-nlbksl-nl

Exercice C – Classes d'équivalence

Écris classes(r, e) qui renvoie la liste des classes d'équivalence (des ensembles) d'une relation d'équivalence r sur e, rangées par plus petit élément croissant.

###

e = set(range(1, 11))bksl-nlr = {(x, y) for x in e for y in e if (x - y) % 3 == 0}bksl-nlassert classes(r, e) == [{1, 4, 7, 10}, {2, 5, 8}, {3, 6, 9}]bksl-nlpairs = {(x, y) for x in range(1, 7) for y in range(1, 7) if (x - y) % 2 == 0}bksl-nlassert classes(pairs, set(range(1, 7))) == [{1, 3, 5}, {2, 4, 6}]bksl-nlassert classes({(1, 1), (2, 2)}, {1, 2}) == [{1}, {2}]bksl-nlassert classes(set(), set()) == []bksl-nlbksl-nl ∞/∞

def classes(r, e):bksl-nl """Classes d'équivalence de r sur e, par plus petit élément croissant."""bksl-nl vus = set()bksl-nl resultat = []bksl-nl for x in sorted(e):bksl-nl if x in vus:bksl-nl continuebksl-nl classe = set()bksl-nl for y in e:bksl-nl # À compléter : ajouter y à la classe de x si (x, y) est dans rbksl-nl passbksl-nl resultat.append(classe)bksl-nl # À compléter : mémoriser les éléments de la classe comme déjà vusbksl-nl return resultatbksl-nlbksl-nl

Exercice D – Injective, surjective, bijective

Écris est_injective(f), est_surjective(f, b) et est_bijective(f, b) pour une application f (dictionnaire) d'ensemble d'arrivée b.

Je comprends. Pourquoi peut-on tester l'injectivité en comparant le nombre de valeurs distinctes au nombre de clés ?

###

f1 = {1: "a", 2: "b", 3: "a", 4: "c"}bksl-nlf2 = {1: "a", 2: "b", 3: "c", 4: "d"}bksl-nlf3 = {1: "a", 2: "b", 3: "c"}bksl-nlassert estpy-undinjective(f1) is False and estpy-undsurjective(f1, "abc") is True and estpy-undbijective(f1, "abc") is Falsebksl-nlassert estpy-undinjective(f2) is True and estpy-undsurjective(f2, "abcd") is True and estpy-undbijective(f2, "abcd") is Truebksl-nlassert estpy-undinjective(f3) is True and estpy-undsurjective(f3, "abcd") is False and estpy-undbijective(f3, "abcd") is Falsebksl-nlmod5 = {x: x % 5 for x in range(10)}bksl-nlassert estpy-undinjective(mod5) is False and estpy-undsurjective(mod5, range(5)) is Truebksl-nlassert estpy-undinjective({}) is Truebksl-nlbksl-nl ∞/∞

def estpy-undinjective(f):bksl-nl valeurs = set()bksl-nl for x in f:bksl-nl # À compléter : ajouter l'image de x aux valeursbksl-nl passbksl-nl return False # À compléter : comparer len(valeurs) et len(f)bksl-nlbksl-nldef estpy-undsurjective(f, b):bksl-nl valeurs = set()bksl-nl for x in f:bksl-nl # À compléter : ajouter l'image de x aux valeursbksl-nl passbksl-nl return False # À compléter : comparer valeurs et set(b)bksl-nlbksl-nldef estpy-undbijective(f, b):bksl-nl return False # À compléter : en utilisant les deux fonctions précédentesbksl-nlbksl-nl

Exercice E – Images, réciproque et composée

Écris image_directe(f, x), image_reciproque(f, y), composee(g, f) (le dictionnaire de \(g \circ f\)) et reciproque(f) (l'application réciproque d'une bijection, ou None si f n'est pas injective).

###

f = {x: x % 5 for x in range(10)}bksl-nlassert imagepy-unddirecte(f, {0, 1, 2, 3}) == {0, 1, 2, 3}bksl-nlassert imagepy-unddirecte(f, {2, 7, 9}) == {2, 4}bksl-nlassert imagepy-undreciproque(f, {0}) == {0, 5}bksl-nlassert imagepy-undreciproque(f, {1, 2}) == {1, 2, 6, 7}bksl-nlassert imagepy-undreciproque(f, {5}) == set()bksl-nlu = {1: 3, 2: 5}bksl-nlv = {3: "x", 5: "y"}bksl-nlassert composee(v, u) == {1: "x", 2: "y"}bksl-nlassert reciproque({1: "a", 2: "b", 3: "c"}) == {"a": 1, "b": 2, "c": 3}bksl-nlassert reciproque({1: "a", 2: "a"}) is Nonebksl-nlassert reciproque({}) == {}bksl-nlassert composee(reciproque(u), u) == {1: 1, 2: 2}bksl-nlbksl-nl ∞/∞

def imagepy-unddirecte(f, x):bksl-nl """Ensemble des images des éléments de x."""bksl-nl resultat = set()bksl-nl for a in x:bksl-nl # À compléter : ajouter l'image de abksl-nl passbksl-nl return resultatbksl-nlbksl-nldef imagepy-undreciproque(f, y):bksl-nl """Ensemble des éléments de départ dont l'image est dans y."""bksl-nl resultat = set()bksl-nl for a in f:bksl-nl # À compléter : ajouter a si f[a] est dans ybksl-nl passbksl-nl return resultatbksl-nlbksl-nldef composee(g, f):bksl-nl """Dictionnaire de g o f : x -> g(f(x))."""bksl-nl resultat = {}bksl-nl for x in f:bksl-nl # À compléter : resultat[x] = g(f(x))bksl-nl passbksl-nl return resultatbksl-nlbksl-nldef reciproque(f):bksl-nl """Application réciproque (b -> a), ou None si f n'est pas injective."""bksl-nl inverse = {}bksl-nl for a in f:bksl-nl # À compléter : si f[a] est déjà une clé de inverse, renvoyer None ;bksl-nl # sinon associer f[a] à abksl-nl passbksl-nl return inversebksl-nlbksl-nl