Compteur binaire

Cours/Algorithmie/Algorithmes classiques/Compteur binaire

Un entier écrit sous forme binaire peut s'écrire comme un tableau $x$ composées de bits (entier valant 0 ou 1). Par exemple l'entier 19 s'écrira $[1, 0, 0, 1, 1]$

L'algorithme algorithme successeur(N: [bit]) → vide: suivant prend en paramètre un entier écrit sous sa forme binaire et qui le modifie pour que sa valeur soit l'entier suivant. L'algorithme n'augmente pas la taille en bits de l'entier passé et donc succ([1, 1, 1, 1]) change le tableau en entrée en [0, 0, 0, 0].

Cette fonction permet d'écrire le code suivant :

n ← [1, 0, 0, 1, 1]
successeur(n)
affiche n à l'écran

Qui affichera [1, 0, 1, 0, 0]

Les fonctions qui ne rendent rien modifient souvent leurs paramètres.

L'algorithme

algorithme successeur(N: [bit]) → vide:
    i ← n.longueur - 1

    tant que (i ≥ 0) et (N[i] == 1):
        N[i] ← 0
        i ← i - 1

    si i ≥ 0:
        N[i] ← 1

code python

def successeur(N):
    i = len(N) - 1

    while (i >= 0) and (N[i] == 1):
        N[i] = 0
        i -= 1

    if i >= 0:
        N[i] = 1

Démontrez que l'algorithme précédent répond aux spécifications.

Que valent ses complexités min et max ?

Complexité en moyenne

Analysez selon le nombre en entrée le nombre d'itérations dans la boucle tant que.

Montrez que que le nombre moyen d'itérations de la boucle tant que sous un modèle que vous expliciterez, vaut :

$$ W_\text{moy}(N) = \mathcal{O}(1) \cdot \sum_{i=0}^{N-1} i \cdot \frac{1}{2^{i+1}} $$

Conclure que la moyenne de l'algorithme vaut $\mathcal{O}(1)$

Vérification

Que le nombre moyen d'itération valent 1 est assez contre intuitif. Vérifiez expérimentalement qu'en moyenne, si l'on appelle successeur $2^N$ fois à partir de $[0] * N$ :

on a bien cyclé sur tous les éléments
en moyenne le nombre d'itération dans la boucle vaut bien 1.

Codez l'algorithme successeur en python puis :

modifiez le pour qu'il rende le nombre d'itération dans la boucle effectuée pour calculer le successeur.
parcourir tous les nombres possible (en partant de $[0] * N$ affichez itérativement les successeurs)
une fois tous les nombres vus, afficher le nombre moyens d'itération de la boucle while de l'algorithme successeur.

Récursif

fonction tous_rec(N: [bit], i: entier) → vide:

    si i == -1:
        affiche à l'écran N
    sinon:
        pour chaque x de [0, 1]:
        N[i] ← x
        tous_rec(N, i-1)

algorithme tous(n) → vide:
    N ← nouveau tableau de bit de taille n

    tous_rec(N, n-1)

code python

def tous_rec(N, i):
    if i == 0:
        print(n)
    else:
        for x in range(2):
            N[i] = x
            compteur(N, i -  1)

def tous(n):
    N = n * [0]
    tous_rec(N, n-1)

Montrez que l'algorithme ci-dessus est une façon récursive d'afficher tous les nombres binaires à $n$ bits.

Quelle est sa complexité en instruction et en mémoire de cet algorithme ?

Généralisation

Modifiez tous(n: [bit]) → vide pour afficher l'ensemble des jets de $n$ dés à 6 faces ?