TP Python – Ensembles en Python

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

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 – Quantificateurs sur une liste

Écris pour_tout(pred, liste) et il_existe(pred, liste) qui renvoient True ou False selon que le prédicat pred (une fonction) est vrai pour tous les éléments, ou pour au moins un. Sans utiliser all ni any. Que renvoie pour_tout(pred, []) ? Et il_existe(pred, []) ?

J'anticipe. Pour la liste [3, 5, 7, 9] et le prédicat « est impair » : quelle est la valeur de chacune des deux fonctions ? Même question avec « est premier ».

###

assert pourpy-undtout(lambda x: x % 2 == 1, [3, 5, 7, 9]) is Truebksl-nlassert pourpy-undtout(lambda x: x > 4, [3, 5, 7]) is Falsebksl-nlassert pourpy-undtout(lambda x: x > 4, []) is Truebksl-nlassert pourpy-undtout(lambda x: x == 3, [3, 3, 3]) is Truebksl-nlbksl-nl ∞/∞

def pourpy-undtout(pred, liste):bksl-nl """Vrai si pred(x) est vrai pour tous les éléments (vrai pour une liste vide)."""bksl-nl for x in liste:bksl-nl # À compléter : s'arrêter dès qu'un contre-exemple est trouvébksl-nl passbksl-nl return Falsebksl-nlbksl-nl

###

assert ilpy-undexiste(lambda x: x % 2 == 0, [3, 5, 8]) is Truebksl-nlassert ilpy-undexiste(lambda x: x % 2 == 0, [3, 5, 7]) is Falsebksl-nlassert ilpy-undexiste(lambda x: x > 0, []) is Falsebksl-nlassert ilpy-undexiste(lambda x: x == 9, [3, 5, 7, 9]) is Truebksl-nlbksl-nl ∞/∞

def ilpy-undexiste(pred, liste):bksl-nl """Vrai si pred(x) est vrai pour au moins un élément (faux pour une liste vide)."""bksl-nl for x in liste:bksl-nl # À compléter : s'arrêter dès qu'un exemple est trouvébksl-nl passbksl-nl return Truebksl-nlbksl-nl

Exercice B – L'ordre des quantificateurs

La relation d'accès est un ensemble de couples (utilisateur, serveur). Écris chacun_a_un_serveur(acces, utilisateurs, serveurs) (\(\forall u\, \exists s\)) et un_serveur_pour_tous(acces, utilisateurs, serveurs) (\(\exists s\, \forall u\)).

Je comprends. Construis une relation où la première est vraie et la seconde fausse. Peut-on en construire une où c'est l'inverse ?

###

U = ["u1", "u2"]bksl-nlS = ["s1", "s2"]bksl-nldiag = {("u1", "s1"), ("u2", "s2")}bksl-nlassert chacunpy-undapy-undunpy-undserveur(diag, U, S) is Truebksl-nlassert unpy-undserveurpy-undpourpy-undtous(diag, U, S) is Falsebksl-nlcommun = {("u1", "s1"), ("u2", "s1")}bksl-nlassert chacunpy-undapy-undunpy-undserveur(commun, U, S) is Truebksl-nlassert unpy-undserveurpy-undpourpy-undtous(commun, U, S) is Truebksl-nlassert chacunpy-undapy-undunpy-undserveur({("u1", "s1")}, U, S) is Falsebksl-nlassert unpy-undserveurpy-undpourpy-undtous(set(), U, S) is Falsebksl-nlassert chacunpy-undapy-undunpy-undserveur(set(), [], S) is Truebksl-nlbksl-nl ∞/∞

def chacunpy-undapy-undunpy-undserveur(acces, utilisateurs, serveurs):bksl-nl """Pour tout utilisateur u, il existe un serveur s tel que (u, s) est dans acces."""bksl-nl for u in utilisateurs:bksl-nl trouve = Falsebksl-nl for s in serveurs:bksl-nl # À compléter : mémoriser qu'un serveur a été trouvé pour ubksl-nl passbksl-nl if not trouve:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nldef unpy-undserveurpy-undpourpy-undtous(acces, utilisateurs, serveurs):bksl-nl """Il existe un serveur s tel que, pour tout utilisateur u, (u, s) est dans acces."""bksl-nl for s in serveurs:bksl-nl tous = Truebksl-nl for u in utilisateurs:bksl-nl # À compléter : si u n'a pas accès à s, alors s ne convient pasbksl-nl passbksl-nl if tous:bksl-nl return Truebksl-nl return Falsebksl-nlbksl-nl

Exercice C – Opérations sur les ensembles

Écris operations(a, b) qui renvoie le tuple (intersection, réunion, différence a \ b, différence symétrique) sous forme d'ensembles Python, sans utiliser les opérateurs &, |, -, ^ (utilise des boucles et le test in).

###

A = {1, 2, 3, 4, 5, 6}bksl-nlB = {2, 4, 6, 8}bksl-nlassert operations(A, B) == ({2, 4, 6}, {1, 2, 3, 4, 5, 6, 8}, {1, 3, 5}, {1, 3, 5, 8})bksl-nlassert operations(set(), {1}) == (set(), {1}, set(), {1})bksl-nlassert operations({1, 2}, {1, 2}) == ({1, 2}, {1, 2}, set(), set())bksl-nlassert operations({1}, {2}) == (set(), {1, 2}, {1}, {1, 2})bksl-nlbksl-nl ∞/∞

def operations(a, b):bksl-nl """Renvoie (a ∩ b, a ∪ b, a \ b, a Δ b) sans les opérateurs d'ensembles."""bksl-nl inter = set()bksl-nl reunion = set()bksl-nl diff = set()bksl-nl sym = set()bksl-nl for x in a:bksl-nl # À compléter : x est dans la réunion ; dans l'intersection ou la différence ?bksl-nl passbksl-nl for x in b:bksl-nl # À compléter : x est dans la réunion ; dans la différence symétrique s'il n'est pas dans abksl-nl passbksl-nl # À compléter : la différence symétrique contient aussi a bbksl-nl return (inter, reunion, diff, sym)bksl-nlbksl-nl

Exercice D – Les parties d'un ensemble

Écris parties(elements) qui renvoie la liste des parties de la liste elements (chaque partie est un ensemble). Utilise les nombres de 0 à \(2^n - 1\) : le bit de rang i de k dit si elements[i] est dans la partie numéro k.

###

assert parties([]) == [set()]bksl-nlassert parties(["a"]) == [set(), {"a"}]bksl-nlp = parties(["a", "b", "c"])bksl-nlassert len(p) == 8bksl-nlassert p[0] == set() and p[7] == {"a", "b", "c"}bksl-nlassert p[5] == {"a", "c"}bksl-nlassert len(parties([1, 2, 3, 4, 5])) == 32bksl-nlassert all(x in p for x in [{"a"}, {"b"}, {"c"}, {"a", "b"}, {"b", "c"}])bksl-nlbksl-nl ∞/∞

def parties(elements):bksl-nl """Liste des 2py-strpy-strn parties de la liste elements, chacune sous forme d'ensemble."""bksl-nl n = len(elements)bksl-nl resultat = []bksl-nl for k in range(2 py-strpy-str n):bksl-nl partie = set()bksl-nl for i in range(n):bksl-nl # À compléter : si le bit de rang i de k vaut 1, ajouter elements[i]bksl-nl passbksl-nl resultat.append(partie)bksl-nl return resultatbksl-nlbksl-nl

Exercice E – Groupes communs

Écris groupes_communs(groupes, u, v) qui renvoie l'ensemble des noms de groupes auxquels appartiennent à la fois les utilisateurs u et v. groupes est un dictionnaire nom → ensemble de membres.

###

G = {"Compta": {"ana", "ben", "chloé"}, "RH": {"chloé", "dan"}, "Direction": {"ben", "eli"}}bksl-nlassert groupespy-undcommuns(G, "ana", "ben") == {"Compta"}bksl-nlassert groupespy-undcommuns(G, "chloé", "dan") == {"RH"}bksl-nlassert groupespy-undcommuns(G, "ana", "dan") == set()bksl-nlassert groupespy-undcommuns(G, "ben", "ben") == {"Compta", "Direction"}bksl-nlbksl-nl ∞/∞

def groupespy-undcommuns(groupes, u, v):bksl-nl """Ensemble des noms de groupes contenant à la fois u et v."""bksl-nl communs = set()bksl-nl for nom in groupes:bksl-nl # À compléter : ajouter nom si u ET v sont membres du groupebksl-nl passbksl-nl return communsbksl-nlbksl-nl