Premier jour de panne — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Premier jour de panne

Recherche séquentielle, dichotomique, arrière · niveau 2

Énoncé

Une fonction boolean ok(int jour) indique si un logiciel fonctionnait à une date donnée. On sait que ok(0) est vrai, que ok(N) est faux, et qu'une fois la panne apparue elle persiste. Écrire une fonction qui retourne le premier jour de panne en appelant ok au plus $⌈ lo g_{2} N ⌉$ fois. Quel est l'invariant ? Combien d'appels pour $N = 1000$ ?

Corrigé

C'est une dichotomie sur les jours, avec l'invariant

$I (g, d) : ok (g) est vrai et ok (d) est faux .$

Il est vrai pour $g = 0$ , $d = N$ . Si $d - g > 1$ , on interroge le jour $m$ du milieu ( $g < m < d$ ) : si ok(m) est vrai, $I (m, d)$ est vrai, sinon $I (g, m)$ l'est. À l'arrêt $d = g + 1$ : le jour $g$ fonctionnait, le jour suivant non. Le premier jour de panne est $d$ .


static int premierJourPanne(int N) {
    int g = 0, d = N;
    // I(g,d) : ok(g) est vrai et ok(d) est faux
    while (d - g > 1) {
        int m = g + (d - g) / 2;      // g < m < d
        if (ok(m)) g = m; else d = m;
    }
    return d;                         // ok(d-1) vrai, ok(d) faux
}

L'écart $d - g$ passe de $N$ à au plus $⌈(d - g) /2 ⌉$ à chaque appel : il faut au plus $⌈ lo g_{2} N ⌉$ appels, soit $10$ pour $N = 1000$ .


panne au jour 1 : trouve 1 en 9 appels (N=1000)
panne au jour 37 : trouve 37 en 10 appels (N=1000)
panne au jour 999 : trouve 999 en 10 appels (N=1000)
panne au jour 1000 : trouve 1000 en 10 appels (N=1000)

Cette méthode est celle de la commande git bisect, qui retrouve la version d'un logiciel qui a introduit une erreur.