Stephane Dartois

On présente ici des éléments de corrections du premier TD Machine accompagné d’illustrations du déroulement des fonctions codées.

Pour la première question on a vu comment construire une fonction python prenant un entier positif en entrée, et retournant sa représentation binaire sous la forme d’un tuple de 0 et 1. On retrouve ici une version animée de cette fonction.

On utilise comme base de raisonnement la traduction d’un nombre de sa représentation binaire à sa représentation usuelle. C’est à dire que l’entier n plus petit que 2^k-1, représenté comme nombre binaire par le tuple (a_k-1, a_k-2,…,a₀) est $n= \sum_{m=0}^{k-1} a_m\times 2^{m}$. Ainsi la reste de la division Euclidienne par deux détermine si a₀ est 0 ou 1. Et la division Euclidienne n//2 résulte en $n//2= \sum_{m=1}^{k-1}a_m\times 2^{\color{red} m-1}$. Déterminer a₁ se fait alors maintenant exactement de la même manière, en étudiant le reste de la division Euclidienne par 2 de n//2. Prolongeant ce raisonnement via une boucle nous donne la fonction.

La question deux nous demande de construire la fonction inverse. Partant d’une représentation binaire on veut reconstruire l’entier. Pour ce faire, nous reconstruisons itérativement la somme $n= \sum_{m=0}^{k-1} a_m\times 2^{m}$.

Considérons par exemple le cas d’un tuple $(a_2,a_1,a_0).$ Posons $n=0.$ En implémentant la boucle, à la lecture du premier bit $a_2$, nous mettons à jour $n=2\times 0+a_2=a_2.$ Nous passons au bit suivant et mettons à jour $n=2\times a_2+a_1.$ Puis enfin, passant au dernier bit n est mis à jour de nouveau par $n=2\times(2\times a_2+a_1)+a_0=4\times a_2+ 2\times a_1+a_0$. Nous retrouvons, pour $k=3,$ la formule précédente.

La question 4 demande de générer toutes les suites binaires de longueur $k$. Nous pouvons le faire en appelant la fonction générant les toutes les représentations binaires des entiers strictement inférieur à $2^k.$

La question 5 nous demande quelle est la longueur de la plus longue sous-suite de 1 dans une chaine binaire. Pour se faire nous lisons les bits de la chaine binaire dans le sens qui nous convient (le résultat n’en dépend pas), et mettons à jour petit à petit la longueur de la plus longue sous-suite de 1 vu jusqu’à maintenant.