NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 23/11/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique           Brèves de Maths    

            

LOGIQUE

 

Débutants

Logique

Intelligence artificielle

 

Glossaire

Algorithme

 

 

INDEX

 

 

Logique

Introduction

Algorithme débutant

Algorithmes

Programmation

Collège

Algorithmes TOP 15

Robots

Sommaire de cette page

>>> Approche

>>> Algorithme d'entraînement

>>> Répétition

>>> Pour simplifier

>>> Bilan

>>> S'exercer avec Scratch

 

 

 

 

 

ALGORITHMES

Totalement débutant

 

Explications et exemples pour bien comprendre cette notion.

 

 

 

APPROCHE

 

 

*    Vous allez vous laver les mains! Vous pratiquer un algorithme sans savoir que cela s'appelle comme cela.

 

*    Imaginez que vous rencontrez quelqu'un à qui vous devez tout expliquer, pas à pas, alors vous décrivez l'algorithme de lavage de mains.


*    Le lavage de mains est décrit en indiquant sept opérations simples. On utilise le mot "instructions". Un algorithme est une suite d'instructions. C'est une recette, une manière de faire, décrite pas à pas.

 

*    L'avantage est que n'importe qui peut se servir de cette description. Elle est valable pour moi, ma sœur, mon copain, mon correspondant au Canada …

 

*    Attention: l'important et ne pas oublier une instruction dans la description.

 

 

Note: dans le cadre des économies d'eau, il est conseillé de fermer le robinet avant de s'essuyer... me dit très justement Valery d'A.

 

 

 

Exemple avec l'indication d'un itinéraire

 

*    Pour allez de ma maison à mon bureau:

*         Monter dans la voiture;

*         Démarrer et avancer;

*         Tourner à la première à droite;

*         S'arrêter au feu et attendre le vert;

*         Avancer jusqu'au 3e carrefour;

*         Prendre la 2e à droite;

*         Etc.

 

 

*    La liste des instructions pour aller d'un point à un autre est une sorte d'algorithme. Ci-contre un exemple avec Google-Map.

 

 

 

Récréation

Choisir un chiffre C de 1 à 9, le multiplier par 37, ajouter ce nombre à lui-même, encore une fois. Surprenant non?

Exemple: je choisis 7. Alors, 7 x 37 = 259; 259 + 259 = 518; 518 + 259 = 777

Lorsque je choisis un chiffre C, je donne une valeur à C, j'affecte un chiffre à C.

 

 

Algorithme d'entraînement

*      On donne ce programme de calcul.

 

*      Faire un tableau montrant le résultat pour le nombre choisi au départ: 10, 8, 6, 4, 2, 0, 1/2

 

*    En injectant 10, le résultat est 32.

*    En injectant 6 ou 2, le résultat est nul.

*    Il existe une plage entre 2 et 6 pour laquelle le résultat est négatif.

 

 

*    Traitement algébrique

 

L'opération exécutée par cet algorithme peut être mise en équation avec x comme variable d'entrée et y le résultat.

 

y = (x – 6) (x – 2)

 

Nous vérifions que la fonction s'annule bien pour x = 6 et x = 2.

 

En développant: y = x² – 2x – 6x + 12 = x² – 8x + 12

Nous obtenons une fonction non-linéaire; Elle est du deuxième degré.

 

Cette question comptait pour 5 points sur 40 au Brevet de 2014

 

Exemple d'un algorithme simple

Étapes de construction d'une figure

Combien d'étapes pour que la figure comporte 439 carrés.

 

Principe du comptage

Pour passer d'une figure à la suivante on ajoute un élément à chacune des trois extrémités, soit  + 3 à chaque itération:

S(n + 1) = S(n) + 3 avec S(1) = 1

On compte:

Itération

1

2

3

4

5

6

n

n + 1

Quantité

1

4

7

10

13

16

(S(n)

S(n) + 3

Formulation

La quantité croit en fois 3 en partant de quelque chose: S = 3n + k;

En prenant une valeur quelconque comme:

n = 4 et S = 10 => 10 = 3 x 4 + k => k = –2  et  S = 3n – 2

 

Pour atteindre 439, quelle est la valeur de n?

439 = 3n – 2 => 3n = 441  =>  n = 147

 

 

Répétition

 

*    Quel est l'intérêt d'un l'algorithme? C'est de pouvoir le porter (l'implanter) dans un ordinateur ou une calculette pour faire des travaux:

*         fastidieux

*         répétitifs,

*         compliqués

 

*    Voyons cela pas à pas sur un exemple de calcul de carrés.

 

 

Calcul des dix premiers carrés C = n²

*      J'indique combien de carrés je désire dans une mémoire que j'appelle "Max". Si j'en veux 100, il me suffit de mettre 100 à la place de 10 comme ici.

1)      Mettre 10 dans la variable Max;

*      Le nombre à mettre au carré s'appelle n. Je mets 1 dans la mémoire n, pour commencer.

2)      Mettre 1 dans la variable n;

*      J'appelle n deux fois et je multiplie ces valeurs; cela fait bien le carré de n.

3)      Calculer n x n;

*      Le résultat est placé dans une nouvelle mémoire que je baptise C. Les baptêmes sont de ma responsabilité; je peux mettre ce que je veux.

4)      Mettre cette valeur dans C;

*      J'imprime plusieurs choses à la file indienne. D'abord la valeur qui est dans n, puis une suite de caractères à imprimer tels quels, et enfin la valeur du carré qui est C.
Ce qui donnera ici, par exemple: 1² = 1.

5)      Imprimer "la valeur de n" suivi de " ²  ="  puis la "valeur de C";

*      C'est fini pour n = 1; je vais m'attaquer à n = 2 en ajoutant 1 dans la mémoire n (on dit aussi: j'incrémente n).

6)      Ajouter 1 à n;

*      Je vérifie que la nouvelle valeur de n n'est pas égale au maximum que je me suis donné: ici, n = 2, et non pas 10.

*      Alors, je recommence à partir de l'étape 3), car en 3)  je calcule le carré de 2. C'est ce que je cherche à faire. Inutile de le récrire.

7)      Si n = Max alors Arrêt,
sinon recommencer à partir de 3;

*      En retrouvant l'instruction 6), j'ajoute 1 à n qui devient 3, nombre qui ne vaut pas 10; alors je vais à nouveau me retrouver en 3) qui donnera n = 4.
Ainsi de suite.

*      Lorsque n = 10, valeur de Max, le déroulement de l'algorithme est terminé.

 

 

Pour simplifier …

 

*    Pour simplifier et avoir une meilleure vision globale, on réalise une sorte de figure, un graphe, un organigramme. Voici l'algorithme de calcul des carrés sous la forme d'un organigramme.

 

*    La partie initialisation permet de modifier les paramètres fixant le déroulement de l'algorithme.

*     Max donne la quantité de carrés désirés, et

*     n indique à partir de quelle valeur.

 

Chaque rectangle est une instruction élémentaire.

Ici, pour dire mettre 10 dans la mémoire nommée Max, on utilise le symbole ":=". On lit: M prend la valeur 10. C'est une affectation.

 

*    La boucle est la partie répétitive de l'algorithme. Elle comporte toujours une condition d'arrêt, de fin.

 

Un hexagone aplati indique un test dont le résultat est oui ou non (vrai ou faux). On indique clairement ce que l'on fait dans chacun des cas.

 


 

 

Imaginez une machine qui sait exécuter ces instructions, elle pourra le faire des milliers de fois sans se fatiguer et avec des valeurs aussi grandes que vous voulez.

Voir Exemple de recherche des nombres premiers (diaporama junior)

 

 

Affectation

L'affectation consiste à préciser la valeur d'une variable dans l'algorithme.

Si je veux affecter la valeur 10 à la variable baptisée Max, je note:

*    A := 10  (notation dans les programmes d'ordinateurs)

*    10  Max (notation sur les calculettes)

 

Bilan

 

Un algorithme est un mot savant pour dire "recette de calcul pour ordinateur". 

*    l'algorithme est universel: il fonctionne quelle que soit la machine utilisée. Cependant une transcription dans le langage propre de la machine utilisée sera indispensable.

*    il est paramétrable: il est possible de choisir des valeurs avant de lancer l'exécution de l'algorithme.

*    il est exigeant: toutes les choses à faire doivent être dites précisément et sans en oublier.

 

Un algorithme comporte trois types d'instructions, plus un:

*    ordre d'exécution (ajouter, multiplier, affecter …);

*    test conditionnel (si ceci alors … sinon …);

*    définition de boucle (faire 10 fois, tant que n <10 faire …); plus

*    les instructions pilotant les entrées et les sorties de données.

 

Tous les programmes du monde ont été et seront élaborés en utilisant des algorithmes. Cependant les informaticiens ont cherché à y échapper en inventant d'autres modes de traitement. Par exemple, en imitant le fonctionnement des neurones de l'homme ou même le comportement des animaux-sociaux.

 

 

S'exercer avec Scratch

Scratch: un jeu éducatif (gratuit sur Internet) qui permet la mise en place d'algorithmes et leur programmation sans que vous vous rendiez compte que vous programmez. Réalisation de scénettes. Plaisir immédiat.  Usage en ligne ou téléchargement. Dès l'âge de 8 ans. Utilisé dans les écoles. Il n'existe pas plus simple !

 

Calcul des carrés

 

Commentaire

On construit le programme en fouillant dans les boites à outils. On sélectionne les instructions (les barres horizontales) pour les amener dans la zone de travail et les assembler comme indiqué sur la copie ci-contre.

 

Le drapeau vert sert à démarrer le programme lorsqu'on clique dessus.

On a créé les variables Max, n et carré avec les outils Données.

La boucle répéter a été sélectionnée dans les outils Contrôle.

L'égalité n = Max comme la multiplication n x n sont extraites des outils Opérateurs.

On ajoute 1 à n avant au début de la boucle.

On attend une seconde avant le nouveau passage dans la boucle, ceci  pour laisser le temps de constater l'affichage de n et de son carré sur l'écran.

 

En bas, l'affichage tel qu'il apparait en fin de programme: le carré de 8 est 64.

 

 

 

 

Suite

*   AlgorithmesIntroduction

*    Affichage de l'heureExemple

*    AlgorithmeGlossaire

*    Mes premiers pas en programmation (en codage)

*    ProgrammationIndex

Voir

*    Automate

*    Dualité

*    Énigmes et paradoxes

*    Grands Hommes

*    Histoire de l'informatique

*    Histoire des ordinateurs

*    Intelligence

*    Intelligence des animaux

*    LogiqueIndex

*   Machine de Turing

*    Multimédia et informatiqueIndex

*    Outils de la logique

*    Puissance de calcul

*    Puzzles et énigmesIndex

*    Raisonnement

*    Réseaux neuronaux

*    Systèmes experts

*    Turing et le Bureau 47

Site

*    Algorithme pour l'apprenti programmeur

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/IAalgorD.htm