Page 63 - Activités algorithmiques avec Python en spécialité Mathématiques

Thème : combinatoire & probabilités
TI-83 Premium CE Edition Python
TI-82 Advanced Edition Python
Niveau : spécialité maths Terminale
La combinatoire des parties
L. DIDIER & R. CABANE
La combinatoire des parties
Présentation et objectifs
Dans le programme (spécialité Terminale)
Situation déclenchante
Lundi Mardi
Contenus
Nombre des parties d’un ensemble à n éléments. Lien avec les n -uplets de {0,1}, les mots de longueur n sur un alphabet à deux éléments, les chemins dans un arbre, les issues dans une succession de n épreuves de Bernoulli.
Combinaisons de k éléments d’un ensemble à n éléments : parties à k éléments de l’ensemble. Représentation en termes de mots ou de chemins. Exemple d’algorithme
Génération des parties à 2, 3 éléments d'un ensemble fini.
– (le chef de service) Alex, je voudrais former une équipe avec quelques membres du service qui s’entendent vraiment bien. Peux-tu me faire la liste de toutes les équipes possibles ? Peu importe le nombre d’équipiers.
– Votre liste va être longue, non ?
– Peu importe...
– Bien chef.
– Alex, tu avais raison, il y en a trop....
– Chef, on pourrait décider que l’équipe est
formée de quatre personnes
– Bonne idée, fais-moi ça au plus vite.
– Oui chef.
– Et fais-moi une proposition d’équipe à partir de
ta nouvelle liste, n’importe laquelle.
Il s‘agit donc ici de parties (ou sous-ensembles) d’un ensemble à n éléments, par exemple E={0,1,...,n−1}, non pour les dénombrer (voir la fiche sur le triangle de Pascal) mais pour les énumérer
c’est-à-dire en faire une liste soit complète soit limitée aux parties à k éléments (combinaisons).
▸ La représentation informatique d’un ensemble peut se faire de diverses manières, la plus simple étant fournie par les listes, en convenant de ne pas prêter attention à l’ordre des éléments. Pour plus de facilité dans la saisie comme l’affichage, les chaînes de caractères sont commodes d’autant
22
▸ Manipulations de listes : voir l’appendice 1 pour plus de détails sur les syntaxes appropriées.
qu’elles peuvent être parfois traitées avec la même syntaxe que les listes
.
▸ Les sous-ensembles seront donc pris comme des sous-listes ou des sous-chaînes (selon le contexte), et la collection des sous-ensembles sera formée comme une liste de listes ou une liste de chaînes. Par sous-liste d’une liste L on entend une liste formée de certains éléments distincts de L (dans le même ordre que dans L), et par sous-chaîne d’une chaîne de caractères s on entend une chaîne formée de certains caractères de s, dans le même ordre. Le respect de l’ordre nous évitera d’avoir des « doublons » comme "ab" vis-à-vis de "ba".
▸ Enfin, au lieu de produire une liste des parties, nous pouvons aussi chercher à en tirer une au hasard, en veillant à ce que ce tirage soit « équiprobable ».
22 Attention : au contraire des listes, les chaînes ne sont pas « mutables » en Python, au sens où on ne peut modifier leurs éléments.
Ce document est mis à disposition sous licence Creative Commons 61 © Texas Instruments 2021 / Photocopie autorisée