Possible idea | energy efficient houses, energy efficient homes, home energy saving,

exercice | algorithme|Pourquoi nous avons tous besoin des algorithmes



Où deux vieux monsieurs partagent un langage universel


Gare de Lyon, Paris, minuit bien tassé. Il n'y a que lui et moi dans cette rue. Le vieux monsieur qui vient vers moi a deux choses dans la main : la carte d'un hôtel de la rue Jeanne d'Arc et ces quelques caractères « กรุณา » ? écrits sur un bout de papier dans une langue dont je ne reconnais même pas l'écriture. En revanche, ce dont il a besoin est facile à deviner.

Comment lui expliquer le chemin partant de la gare de Lyon vers cet hôtel près de l'hôpital de la Pitié ?
    En anglais ? À mon « Speaking English ? » il répond quelque chose comme «ไม่ เสียใจ  » !
        En faisant un plan ? Ni lui ni moi n'avons de crayon !
Nous voilà donc sans aucun langage commun ni aucun support commun. Et pourtant j'ai une information compliquée à lui passer.

Je lui montre alors le trajet sur mon smartphone, il semble comprendre de quoi il est question. Mais comment va-t-il le mémoriser et le traduire en geste de marche ? C'est lui qui va avoir la bonne idée : il m'invite par des gestes à lui miner le trajet. J'ai donc besoin de lui dire «tout droit pendant N pas» en mimant "→N" (c'est à dire un geste de la main pour mimer un pas, suivi du nombre de pas compté sur les doigts) ;  «quart de tour à gauche» en mimant "┐" (un geste de la main) et  «quart de tour à droite» disons  "┘". Je n'ai plus qu'à lui donner la suite des  →N , ┐ , ┘ qui décrivent le chemin, à partir de ce que me donne mon smartphone et hop le tour est joué.
Nous voilà donc à créer un langage minimal pour coder cette information dont nous comprenons lui et moi le sens.

Il comprend immédiatement ce mini-langage. La chance veut aussi qu'il puisse compter sur les doigts comme un français le fait. Comme c'est une séquence d'actions, son cerveau comme tous les cerveaux humains, peut l'apprendre facilement "comme une danse ou une chanson". Il répète donc le mime devant moi quelques instants. Et moi de lui montrer sur mon smartphone qu'on peut vérifier le trajet au fur et à mesure que son mime est joué.
Nous voilà donc avec le problème soldé.

Lui et moi avons bien rigolé ce soir là. Plus tard, la photographie de son petit bout de papier m'a permis d'aller sur le Web découvrir que l'écriture est du thaï.

Où la morale de l'anecdote a plus d'un millénaire.


Si je me permets de raconter cette histoire ici, c'est qu'il me semble que c'est une belle histoire de... science informatique.
Nous avons codé une information dont nous comprenions lui et moi le sens, même si, une fois codée, les mouvements de doigts et de mains avaient juste l'air de gestes bizarroïdes. À défaut de parler le même langage nous avons donc fabriqué un langage mécanique minimal qui nous a permis de communiquer le trajet à effectuer. Ce langage ne peut pas servir à grand chose d'autre, mais il permet d'exprimer tous les trajets piétons d'un point à un autre dans une ville pas trop compliquée. La séquence d'actions à effectuer que ce soit pour un robot, un vieux thaï ou une jeune gauloise, est formellement identique. Pour désigner une telle abstraction on parle d'algorithme. Cet algorithme nous l'avons implémenté sous forme d'une "comptine de geste" pour que son cerveau* le conserve sans soucis.
* En effet, notre cerveau n'est pas capable de mémoriser plus de 4 ou 5 items dans sa mémoire de travail, mais il peut apprendre des séquences beaucoup plus longues si elles sont tournée sous forme de séquences de gestes ou de signes.
 
Mais alors, dans quelle mesure cette façon de penser sous forme "algorithmique" peut-elle servir au delà de ce petit cas particulier ?
Pour répondre à cette question j'ai besoin d'inviter dans ce texte plusieurs grands collègues scientifiques. D'abord Gérard Berry qui nous explique très simplement :
"Un algorithme, c’est tout simplement une façon de décrire dans ses moindres détails comment procéder pour faire quelque chose. Il se trouve que beaucoup d’actions mécaniques, toutes probablement, se prêtent bien à une telle décortication. Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique (ordinateur, ..). On ne travaille donc qu'avec un reflet numérique du système réel avec qui l'algorithme interagit."
Les scientifiques savent que ces algorithmes sont devenus des outils structurants y compris en sciences de la vie, de la matière, de la terre, ou de l'humain. Mieux encore, trouver l'explication scientifique ultime d'un phénomène ne se réduit plus juste trouver "l'équation mathématique qui l'explique" mais plutôt "l'algorithme informatique qui le simule" comme l'explique Gilles Dowek. Ce n'est pas uniquement une "explication" mais un modèle qui pourra être simulé numériquement pour être confronté aux mesures effectuées.

Une culture des algorithmes


Dans tous les secteurs socio-économiques, tous impactés par le numérique, on imagine aisément que ceux qui maîtriseront ces fondamentaux seront les créateurs du monde qui vient.
De même qu'avoir une culture médicale permet de rester maître des solutions proposées par le médecin qui nous soigne, avoir une culture informatique permet de choisir, paramétrer, adapter, changer, les logiciels et objets numériques que nous devons utiliser. Apprendre un peu de programmation permet de malaxer ce concept essentiel d'algorithme qui est le fondement des objets informatiques.
Pour découvrir cette notion, c'est sur )i(nterstices que Philippe Flajolet nous explique ce qu'est un algorithme.
" Penser est la noblesse de l’esprit, ce qui reste difficilement explicable. Calculer (y compris manipuler des signes) est bien plus simple et systématique, et pour tout dire mécanisable".
Ainsi, en comprenant ce que les algorithmes permettent de faire ou pas, les artistes peuvent ils créer des oeuvres d'art assisté par ordinateur où il ne s'agit pas d'utiliser des logiciels, mais de détourner des algorithmes pour "faire fonctionner" de nouvelles oeuvres d'arts. Il ne s'agit pas de remplacer l'artiste par un ordinateur... quel intérêt ? Mais de regarder tout ce qui peut être délégué à un mécanisme algorithmique pour, au delà, permettre et obliger l'esprit humain à se dépasser. Conduire son esprit à penser et créer au delà de ce qu'un ordinateur peut calculer, voilà le défi que l'artiste du numérique doit relever.

Définition d'algorithme


Le différence entre un algorithme et un programme est souvent une question de niveau de détail. Un algorithme est souvent exprimé avec une notation indépendante de tout langage de programmation alors qu'un programme est écrit dans un langage de programmation particulier.
Une autre différence entre algorithme et programme est que l'exécution d'un algorithme doit toujours se terminer avec un résultat, alors que celle d'un programme peut conduire à une boucle infinie (ne jamais s'arrêter).
Un algorithme est donc une méthode pour résoudre un problème particulier dont on est sûr qu'elle trouve toujours une réponse en un temps d'exécution fini.
Exemple : Pour déterminer si un entier $n$ est premier (à savoir qu'il ne contient pas de facteur autre que $1$ et $n$), l'algorithme suivant peut être utilisé :
Pour chaque entier $i$$2 \le i < n$, vérifier si $i$ est un facteur de $n$ (en divisant $n$ par $i$ puis en vérifiant si le résultat est entier). Si c'est le cas, arrêter avec la réponse ``non''. Si aucune valeur $i$ n'est facteur de $n$, alors arrêter avec la réponse ``oui''.
Il y a dans cette définition (informelle) d'algorithme un problème majeur. Prenons l'exemple des nombres premiers. Pourquoi peut-on supposer que l'on sait comment diviser $n$ par $i$ et vérifier que le résultat est un entier ? Ne faudrait-il pas avoir un algorithme pour ça aussi ? Et si jamais on trouve un algorithme pour cette division, ne faudrait-il pas trouver un algorithme pour chaque étape de celle-ci ? Et ainsi de suite. Ou, au contraire, pourquoi ne peut-on pas simplement supposer que ``vérifier si un entier est premier'' est une opération élémentaire ? Pourquoi est-il nécessaire de trouver un algorithme pour cette opération ?
En d'autres termes : comment savoir si une opération est élémentaire (et ne nécessite par conséquent aucun algorithme) ?
La réponse est qu'une opération est élémentaire lorsque un ordinateur peut l'exécuter très rapidement, en réalité en un nombre relativement faible de cycles d'horloge.
Le lecteur de ce livre ne sait pas forcément déterminer si une opération est élémentaire au sens du paragraphe précédent. Heureusement cela ne sera pas nécessaire. La notion de type abstraitexaminée dans la section suivante nous permettra de savoir si une opération est élémentaire dans le sens ci-dessus.

Les types structurés et les enregistrements

Les types structurés et les enregistrements

Introduction

Contrairement aux tableaux qui sont des structures de données dont tous les éléments sont de même type, les
enregistrements sont des structures de données dont les éléments peuvent être de type différent et qui se rapportent à
la même entité sémantique (analogie avec Merise).Les éléments qui composent un enregistrement sont appelés
champs.



Avant de déclarer une variable enregistrement, il faut avoir au préalable définit son type, c'est à dire le nom et le type
des champs qui le compose. Le type d'un enregistrement est appelé type structuré. (Les enregistrements sont parfois
appelé structures, en analogie avec le langage C)
Préalable: déclaration d'un type structuré
Jusqu'à présent, nous n'avons utilisé que des types primitifs (caractères, entiers, réels, chaînes) et des tableaux de types
primitifs. Mais il est possible de créer nos propres types puis de déclarer des variables ou des tableaux d'éléments de ce
type.
Pour ce faire, il faut déclarer un nouveau type, fondé sur d'autres types existants. Après l’avoir défini, on peut dès lors
utiliser ce type structuré tout autre type normal en déclarant une ou plusieurs variables de ce type. Les variables de type
structuré sont appelées enregistrements.
La déclaration des types structurés se fait dans une section spéciale des algorithmes appelée Type, qui précède la section
des variables (et succède à la section des constantes). Si l’algorithme comporte des sous-programmes, les types et les
constantes sont déclarées en dehors du programme.

Syntaxes :

Exemple:

I. Déclaration d'un enregistrement à partir d'un type structuré


Une fois qu'on a défini un type structuré, on peut déclarer des variables enregistrements exactement de la
même façon que l'on déclare des variables d'un type primitif.
Type
Structure nom_type
nom_champ1: type_champ1
nom_champN: type_champN
FinStruct
Type
Structure tpersonne
nom : chaîne
prénom : chaîne
âge : entier
FinStruct