Point fixe

Définition

Soit T un tableau contenant des entiers relatifs. On appellera point fixe du tableau un entier k tel que T[k] = k.

Exercice 1

Une liste L contient des entiers relatifs tous distincts et rangés en ordre croissant.
Soit k un indice tel que L[k] > k.
Expliquer pourquoi si la liste L présente un indice i tel que L[i] = i, alors on a nécessairement i < k.

Solution

On a L[k] > k, donc L[k] ≥ k+1 (puisque L ne contient que des entiers).
Comme les éléments de la liste sont distincts et rangés en ordre croissant, on a L[k+1] > L[k].
On a donc L[k+1] > L[k]≥ k+1, d'où L[k+1] > k+1.

On voit en réitérant l'argument utilisé que l'on aura L[j] > j pour tout indice j ≥ k.

Si L présente un point fixe, ce ne peut donc être qu'avant k.

Exercice 2

La fonction Python ci-dessous:

def point_fixe(tab):
    for i in range(len(tab)):
        if tab[i] == i:
            return i
    return None

prend en entrée une liste d'entiers relatifs (tous distincts et en ordre croissant), renvoie None si la liste ne présente pas de point fixe et renvoie un indice point fixe sinon.

Quel est le nombre de tests if tab[i] == i: effectués au pire des cas ?

Solution

Lorsque la liste ne présente pas de point fixe, il y aura une comparaison par indice, soit n = len(tab) comparaisons.

Exercice 3

Proposer une programmation de la fonction précédente améliorant le cas "au pire" détecté ci-dessus, en vous appuyant sur le principe de dichotomie.

Solution

Un code possible:

def pointfixe(tab):

    gauche, droite = 0, len(tab)-1
    if tab[gauche] > gauche: return None
    if tab[droite] < droite: return None

    while gauche <= droite:
        centre = (gauche + droite)//2
        if tab[centre] == centre: return centre
        if tab[centre] > centre:
            gauche, droite = gauche, centre-1
        else:
            gauche, droite = centre+1, droite

    return None

Remarque

Pour créer rapidement des listes de test pour la fonction précédente, on pourra utiliser:

n = 12
L = [randint(-n,n) for i in range(n)] 
L = set(L)
L = list(L)
L.sort()

Explication:

• [randint(-n,n) for i in range(n)] crée une liste de n entiers tirés au hasard entre -n et n.
• L = set(L) transforme cette liste en ensemble (set), ce qui a notamment pour effet de supprimer les doublons.
• L = list(L): on retransforme L en liste.
• L.sort(): on trie la liste en ordre croissant.

Exercice 4

On suppose maintenant que la liste L ne contient que des entiers naturels. Donner un algorithme en temps constant renvoyant un point fixe s'il y en a un, ou None s'il n'y en a pas.

Solution

Si les entiers contenus sont positifs ou nuls, dès qu'il y a au moins un point fixe alors 0 en est un.
En effet si L[0] > 0, il n' y a pas de point fixe (raisonnement fait plus haut).

D'où un programme à temps constant:

def pointfix(tab):
    if tab[0] == 0:
            return 0
    return None