Un tutoriel sur la conversion analogique-numérique.

Objectif.

Le but de ce tutoriel est de comprendre comment deviner une valeur analogique à partir de comparaisons et de découvrir la recherche dichotomique.

Introduction.

  1. L'ordinateur peut grâce à un convertisseur numérique analogique générer une tension en volt, grâce à la fonction output(tension); qui varie en 0 et 1.023 volts et est donnée en milli-volts. Il peut aussi comparer cette tension à la tension inconnue avec la fonction compare(); qui renvoie -1 si la tension inconnue est plus petite et 1 si elle plus grande ou égale.
  2. Le schéma est illustré ici :
    Bien entendu, ici, nous simulons ce mécanisme par une petite proglet.
  3. Comment deviner la tension inconnue qui varie entre 0 est 1023 millivolts ?

Travail proposé.

  1. Tester toutes les valeurs.

    Essayer le programme suivant :
    int v = 1023;
    while(v >= 0) {
        output(v);
        if (compare() == 1) {
            echo("valeur = "+v);
        }
        v = v - 1;
    }
    • Que se passe t'il ? Que manque t'il pour qu'il fonctionne comme nous l'espérions ?
    • Ajoutons alors l'instruction break; (que nous découvrons ici) et qui permet de sortir de la boucle while : si le programme rencontre break;, il sort de la boucle. A quel endroit l'insérer pour que cela marche ?
    Noter que cet algorithme est bien long car il faut essayer toutes les valeurs.
  2. Couper le problème en deux.

    Voici une idée : On va couper l'espace de recherche en deux, puis en deux, puis en deux, etc. Dans le programme suivant on a déjà divisé l'espace de recherche en 2 !

    // La valeur est donc comprise entre 0 et 1023

    output(512); if (compare() == 1) {

    // Si le test est vrai, nous savons que la valeur est plus petite que 512

        echo("La valeur est comprise entre 0 et 511");

    // A vous de compléter en comparant à 256

    } else {

    // Si le test est faux, nous savons que la valeur est plus grande ou égale à 512

    echo("La valeur est comprise entre 512 et 1023");

    // A vous de compléter en comparant à 768

    }
    • Compléter ce code en comparant à 256 et 768, puis utilisant le tableau ci dessous à 128, etc. Et essayer le résultat ...
      On remarque qu'en 3 étapes nous avons déjà une idée de la valeur à 12.5% près, mais c'est bien long à écrire !
    • Notez que les intervalles sont de :
      512 milli-volts à la 1ère étape
      256 milli-volts à la 2ème étape
      128 milli-volts à la 3ème étape
      et si nous avions continué les intervalles suivantes auraient quelles valeurs ? Continuer jusqu'à trouver une intervalle plus petite que 1.
      Ce calcul se fait en combien d'étapes finalement ? Et ceci au lieu de ... tester les 1024 valeurs !
  3. L'algorithme dichotomique.

    Essayons maintenant avec une boucle :

    //  ? à vous de commenter les lignes qui suivent

    int min = 0, max = 1024;
    while(max - min > 1) {
        echo("La valeur est comprise entre " + (min) + " et " + (max - 1));

    //  ? à vous de COMPLETER et commenter les lignes qui suivent

        int milieu = (min + max) / 2;
        output(milieu); if (compare() == 1) {
            ??? = ???;
        } else {
            ??? = ???;
        }
    }
    • Compléter ce programme et ajouter au texte de programme des commentaires à chaque ligne pour expliquer comment il fonctionne.
    • Essayez-le et concluez sur l'intérêt d'utiliser une telle méthode qui divise l'espace de recherche par 2 puis 2 etc.
    • A l'aide de wikipedia expliquer en deux lignes pourquoi cette méthode s'appelle dichotomique.
  4. Aller plus loin.

    Supposez que nous regardions l'annuaire téléphonique des 1048576 habitants des Alpes-Maritimes, triés par ordre alphabétique :
    • Expliquez en 2/3 lignes comment utiliser une méthode dichotomique pour chercher une personne parmi plus d'un million de personnes !
    • A l'aide de la suite des chiffres suivants, devinez en combien d'étapes la recherche dichotomique permet de trouver une personne parmi ce gros million :
      0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576
      Note : cette liste de chiffres sont les puissances de 2: 2^0, 2^1, 2^2, etc...
    • A partir de la ligne de code1 :
      n = n + 1; u = u * 2; echo("2^" + n + "=" + u);
      écrire une boucle qui calcule les puissances de 2 de 0 à 20.

Remarques.

  1. La fonction void echo(String string) affiche une chaîne de caractères sur la console.