<commit_before>LANGUAGE:   fr
TITLE:   Les traitements et les applications
MENUTITLE: Les traitements
AUTHOR:     Culture numérique
CSS: http://culturenumerique.univ-lille3.fr/css/base.css

# Comprendre les traitements

Pour être un utilisateur averti et un acteur dans notre monde numérique, il est utile de comprendre pourquoi les ordinateurs peuvent nous paraître parfois plus précis, rapide ou efficaces que nous, voire même intelligents. Nous savons tous qu'ils peuvent calculer très vite, et donc traiter rapidement de grandes quantités de données. C'est un premier élément de compréhension, mais qui ne suffit pas. Nous allons détailler ici une explication complémentaire qui est leur capacité à réaliser des traitements complexes  en combinant des traitements de base très simples. À force de combinaisons, de combinaisons de combinaisons, etc, on arrive à définir des tâches vraiment impressionnantes. Mais ces combinaisons, c'est nous qui les commandons et les décidons à travers des algorithmes, puis des programmes. Si bien qu'on retrouve dans cette "intelligence informatique" des ordinateurs toute l'ingéniosité des femmes et des hommes qui les ont programmés. 

Dans cet objectif, nous allons étudier comment les applications fonctionnent, comment elles sont construites, comment elles se coordonnent et comment elles manipulent des données complexes.

Pour introduire ce cours, considérons l'exemple de calcul d'itinéraire par un logiciel sur un site Web, une application mobile ou encore un petit ordinateur spécifique qu'on appelle abusivement GPS (le GPS est juste le système de qui permet de déterminer sa position sur terre.). Tout d'abord, réfléchissons aux informations que doit posséder ce programme. Pour cela, il suffit de réfléchir à quoi nous aurions besoin nous-même, si nous devions réaliser cette tâche sans machine. Tout d'abord, il faut connaître le point de départ. Le programme peut parfois obtenir par des dispositifs techniques (une puce GPS, la connexion réseau) ou il peut vous le demander explicitement. Il faut  connaître le point d'arrivée et le moyen de transport. Supposons, pour simplifier la présentation, que le logiciel dispose d'une ville de départ, d'une ville destination et que le moyen de transport choisi est la voiture.  Qu'est-ce qu'un itinéraire ? C'est une suite de routes à emprunter pour rejoindre sa destination mais nous pouvons aussi représenter un itinéraire par une suite de villes voisines,  toujours par souci de simplification. Le nombre de ces villes étapes peut être variable et parfois grand. Le programme comme vous peut-il disposer de la liste de tous les itinéraires possibles entre ces deux villes quelconques ? La réponse est non car cela nécessiterait bien trop de ressources de stockage. Il dispose uniquement des connexions directes entre villes voisines (la liste des routes en fait), ce qui représente déjà un grand volume mais qui peut être stocké dans un petit équipement comme un smartphone. Il doit calculer les itinéraires possibles à partir de ces données. Mais un programme ne peut pas non plus calculer tous les itinéraires possibles entre les deux villes que vous avez choisies car le temps de calcul serait trop long et vous n'allez pas de Lille à Paris en passant par Marseille ! Donc ce programme se doit d'être plus "intelligent" et calculer vite ne suffit pas.

C'est un programme qui va calculer les itinéraires, mais uniquement les plus courts ou les plus rapides à partir de cette connaissance des distances directes (sans ville étape) entre deux villes. Ce programme va utiliser un algorithme dit de recherche de plus court chemin, issu des travaux de recherche de mathématiciens et informaticiens ayant étudié ce problème. Un algorithme ? Quésaco ? Retenez simplement ici qu'un algorithme est une explication très précise de *comment* résoudre un problème. On pourrait ici comparer tous les chemins de longueur 3 (les triplets de villes), puis 4 (les quadruplets de villes), puis 5, ...  mais le temps d'exécution serait horriblement long et inadmissible.  Cet algorithme de plus court chemin inventé dans les années 50 est ingénieux. Nous n'allons pas détailler dans cette introduction, mais il permet de trouver une solution en un temps dont l'ordre de grandeur est du nombre de couples de villes et peut donc donner des réponses très rapidement.  Comme tous les algorithmes, il consiste à enchaîner et répéter des opérations très simples comme comparer des valeurs numériques, les ajouter, les mémoriser, ces valeurs représentant des villes ou des distances. Mais le génie n'est pas dans l'algorithme mais bien dans ceux qui l'ont conçu, qui ont trouvé cette représentation des villes et des distances et qui l'ont exprimé à l'aide de  cette combinaison d'opérations simples. 

Notre étonnement à propos des programmes et des ordinateurs va grandissant quand on combine des calculs comme celui d'un itinéraire avec d'autres calculs pour la reconnaissance vocale, la géolocalisation etc. L'ensemble combiné va former des solutions complètes qui analysent le son de votre voix, le transforment en mots et phrases, y retrouvent suffisamment de sens pour identifier des villes et des rues, des adresses de départ ou de destination, et vous indiquent le chemin le plus rapide en fonction du trafic. À ce stade, le programme est devenu un logiciel, un assistant qui peut dépasser les capacités de votre passager uniquement accompagné de ses connaissances et sa carte routière. 

En premier lieu, cet exemple montre qu'exécuter une application implique l'exécution de nombreux programmes en interaction avec l'environnement (utilisateur, périphériques, réseau). Il montre également qu'une application est construite en composant d'autres applications : récupérer les données saisies, extraire le nom de la ville, calculer un itinéraire, ... C'est ce principe de composition qui permet de passer d'une machine "bête" manipulant des 0 et des 1 à une machine "intelligente" réalisant des applications complexes. C'est également ce principe de composition qui permet de définir des algorithmes pour résoudre des problèmes. L'exemple a également permis de montrer que malgré les capacités sans cesse croissantes des machines, il faut être attentif à la taille des données mémorisées et au temps de calcul des programmes. Enfin, on peut noter que l'intelligence supposée de la machine est due à l'intelligence des hommes et femmes ayant conçu les applications.

Dans la suite du cours, nous présentons comment composer des opérations pour définir de nouvelles opérations et discutons des algorithmes, nous présentons les langages de programmation et la traduction des algorithmes en programmes. Nous terminons par l'étude de quelques exemples : comment un correcteur orthographique peut-il corriger vos fautes,  et comment une machine peut-elle jouer aux échecs ou au go.

```Activité
Programmes, logiciels {}
```


# Les algorithmes 

## Les algorithmes, les langages et la machine

Le mot algorithme a fait irruption dans les médias après que des avancées notables ont été réalisées dans le domaine de l'informatique et ont affecté la société. C'est par exemple la naissance de l'internet et ensuite des moteurs de recherche qui ont posé la question de société de l'accès à la connaissance et des monopoles économiques dans ce domaine:  "Quel algorithme est donc responsable du choix de l'ordre dans lequel les résultats apparaissent".  Mais comprendre ce qui se cache derrière ce mot algorithme ne peut être compris sans comprendre comment l'ordinateur fonctionne en tant que machine et comment on interagit avec lui par le langage. 

Le langage doit permettre de représenter des données, mais également des traitements. Nous l'avons abordé dans le module précédent à travers la question de la numérisation des données. Le langage, c'est pluriel et artificiel : il existe de nombreux langages informatiques, inventés par l'homme, et faisant souvent l'objet de normes ou de standards,  parfois de brevets ou parfois laissés libres d'accès et d'évolution à la communauté. Ce qui les distingue des langages (ou langues) naturels (naturelles), c'est qu'ils ont été conçus pour qu'une machine les interprète et non un être humain. Ils doivent donc être précis, formels, plus encore même que la notation musicale qu'on a toujours la possibilité d'interpréter librement. 

```activité
le rôle des linguistes : qui a inventé le mot ordinateur, qui est larry wall, noam chomsky...{}
```

La machine c'est l'ordinateur. Le mot inventé par un linguiste dans les années 50, fait référence à l'exécution d'ordres, d'instructions. En anglais le mot computer fait plutôt référence au calcul et les deux notions se retrouvent dans cette machine. Essentiellement la machine repose sur une *unité de calcul* qui fonctionne avec des valeurs représentées par des 0 et des 1. Elle utilise des *mémoires* pour retrouver ou ranger ces valeurs à des emplacements précisé par des numéros : les adresses. Enfin une *unité de contrôle* donne les ordres à l'unité de calcul et aux mémoires. Ce modèle abstrait de machine n'a pas bougé depuis les années 40. Il n'est peut être pas si simple de comprendre comment le réaliser physiquement mais plusieurs l'ont fait depuis le premier dans les années 40, parfois par défi, avec des objets mécaniques du quotidien. L'électricité,  puis l'électronique et  la miniaturisation ont considérablement réduit la taille et augmenté la rapidité de la mémoire,  de l'unité de calcul et l'unité de contrôle. Ces progrès l'ont aussi rendu plus économe et plus résistant. 

```activité
Trouver le schéma de l'architecture von neumann. {}
```
## L'illustration par le symbole

Rappelez-vous les conventions de langage dont nous avons parlé au module précédent, introduites pour représenter les caractères. Le caractère A majuscule a
pour nom "Latin Capital Letter A" et pour numéro 65.  Croyez-nous, en binaire ce 65 s'écrit 01000001.  Le caractère a minuscule a pour numéro 97. En binaire cela s'écrit 01100001. C'est remarquable car c'est juste le 6eme chiffre partant de la droite, un 0,  qui est transformé en 1 pour passer de l'un à l'autre. Et cela est vrai pour toutes les lettres de notre alphabet latin. D'un point de vue arithmétique, l'interprétation du changement de ce 6ème chiffre est simplement d'ajouter ou retirer 32 au numéro. 65 +32 fait bien 97. 

Ce choix de représentation, donc de langage pour représenter les symboles est donc très lié au fonctionnement binaire de la machine et à ses capacités de calcul arithmétique. C'est là l'ingéniosité des personnes qui ont conçu ce langage de représentation des symboles. À partir de cela, on peut facilement imaginer le traitement que doit réaliser la machine pour transformer un symbole stocké dans sa mémoire de majuscule en minuscule. Il suffit d'indiquer l'adresse où ce symbole est stocké. Imaginons que ce soit l'adresse 413. 

    Accéder à la mémoire à l'adresse 413 (retrouver la valeur binaire 
	                                      correspondant au code 
										  d'un symbole)
	Ajouter 32                           (c'est-à-dire, dans l'unité 
	                                      de calcul,  changer le 6ème 
										  chiffre de 0 en 1.)
	Ranger le résultat dans la mémoire 413 

L'unité de contrôle doit juste assurer que ces 3 instructions soient réalisées successivement dans cet ordre, *en séquence*. Nous n'irons pas dans les détails du langage numérique inventé pour représenter ces 3 instructions, ce n'est pas très important ici. Par contre, les  notions importantes à retenir sont les suivantes. Premièrement nous sommes parvenus à créer un traitement qui porte un sens pour nous, à partir de la représentation numérique d'une information et grâce à une combinaison d'instructions. Deuxièmement, l'ordonnancement en séquence des instructions constitue le premier outil de combinaison. Nous venons de décrire un algorithme simple ! 


## Et si ce n'était pas une lettre majuscule ?

L'ordinateur est d'abord une machine très obéissante et exécute scrupuleusement les ordres qu'on lui donne. Le traitement précédent ajoutera 32 au numéro même si celui-ci n'est pas le numéro d'une lettre majuscule. Par exemple le numéro 64 représente l'arobase @  et si on lui ajoutait 32 cela donnerait une apostrophe inversée (`).  Pour contrôler cela, il faut introduire une vérification que nous pouvons décrire comme :

    Accéder à la mémoire à l'adresse 413 
	Si la valeur est comprise entre 65 et 90 Alors 
       Ajouter 32 
	   Ranger le résultat dans la mémoire 413 

Parmi les instructions de base que l'unité de calcul sait faire, outre les opérations arithmétiques, nous disposons aussi des comparaisons. 
Le *si* que nous venons d'utiliser très naturellement est la deuxième façon de combiner des instructions. Remarquez que l'algorithme utilise à la fois des *séquences* et un *si*. C'est une combinaison qui permet de considérer différentes  *alternatives* dans le déroulement de l'algorithme, sous certaines conditions. 

## Et pour un texte complet ?

Supposons maintenant que ce soit un texte complet que nous voulons mettre en majuscules... Là encore c'est une articulation entre langage de représentation, machines et algorithmes que nous allons illustrer. Dans un premier temps, il faut choisir une représentation du texte. Ce sera une suite de symboles stockés dans la mémoire les uns à la suite des autres et terminés par un symbole spécial représenté en binaire par 0000000. Ce choix de représentation n'est pas normalisé mais est souvent utilisé. De plus, du point de vue de la machine,  l'unité de calcul permet de faire des opérations sur les valeurs aussi bien que sur des adresses (qui sont aussi des valeurs). L'algorithme lui s'écrira :

    L'adresse courante est 413
    Accéder à la mémoire à l'adresse courante
	Répéter tant que la valeur n'est pas 0000000
  	   Si la valeur est comprise entre 65 et 90 Alors 
          Ajouter 32 
	      Ranger le résultat dans la mémoire à l'adresse courante
       Ajouter 1 à l'adresse courante 
       Accéder à la mémoire à l'adresse courante 

Voilà la troisième manière de combiner des instructions : la répétition. Les informaticiens l'appellent *la boucle*, ou *l'itération*. 



## Les trois combinaisons

Rappelons un petit point d'étape. Machines,  langages (incluant la représentation numérique de l'information et des traitements), et algorithmes sont intimement liés, dépendants.  Autrement dit,  comprendre l'une de ces notions demande d'avoir aussi quelques notions à propos des autres. Les ordinateurs depuis leur création dans les années 40 suivent tous une même organisation qui comprend une unité de calcul de la mémoire et une unité de contrôle. C'est l'architecture de von Neumann. Nous avons illustré ce fonctionnement sur une tâche simple de passage d'un texte en majuscule et mis en évidence 3 structures de combinaison d'instructions qui peuvent être traduites dans l'unité de contrôle: la séquence qui fait passer à l'instruction suivante, l'alternative qui permet de choisir la prochaine instruction selon la valeur d'un test et la répétition d'instructions tant qu'un test est satisfait. 

Une grande force de ces combinaisons est qu'elles s'appliquent sur des instructions de base de la machine comme consulter la mémoire ou réaliser une opération arithmétique, mais aussi sur d'autre combinaisons. L'exemple précédent l'illustre bien. Nous avons une séquence de mémorisation, suivie d'un accès à la mémoire et suivi ensuite par une répétition. La répétition comprend elle-même une alternative suivie en séquence par une opération arithmétique et un accès à la mémoire. 

C'est un vrai jeu de construction! À la manière des Legos où partant de briques de bases, par assemblage on construit des maisons et des villes, on est devant un univers infini de possibilités, pourvu que vous ayez autant de  briques que voulu, où toute votre créativité peut s'exprimer. 

Dans le monde informatique, au fur et à mesure de ces combinaisons, les traitements deviennent de plus en plus impressionnants et puissants. Mais les principes de base restent identiques. Par exemple dans le cas de notre application d'assistance routière, nous retrouvons la composition en séquence de la reconnaissance vocale des directions, le calcul d'itinéraire et son affichage. L'alternative permet, si le lieu d'arrivée n'est pas connu, d'afficher un message plutôt que l'itinéraire. L'itération est la combinaison qui permet la répétition des annonces vocales tant que vous n'êtes pas arrivé... 

## Calculer et calculable 

À partir des instructions de base de la machine, on construit donc des traitements par un algorithme en utilisant les trois modes de composition que sont la séquence, l'alternative et l'itérative. Est-ce suffisant ? Oui car il existe un **théorème** qui affirme que tout ce qui est calculable avec une machine peut être défini par quelques opérations élémentaires et les opérations de composition que sont la suite (ou la séquence), l'alternative et l'itérative. Ce théorème a été démontré au milieu du vingtième siècle par des mathématiciens et des logiciens. Ceci soulève immédiatement la question : une machine peut-elle tout calculer ? La réponse, démontrée à la même époque, est négative : il existe des problèmes que ne peut pas résoudre une machine. Par exemple, il est montré qu'il n'existe pas d'algorithme qui prend en entrée une suite d'instructions contenant des alternatives et des itératives et qui répond en sortie cette suite d'instructions va s'arrêter en un temps fini lorsqu'on l'exécutera. Ces sujets soulèvent des problèmes importants qui ont été et sont encore étudiés par les mathématiciens, les informaticiens, les logiciens et les philosophes. Notons enfin, que savoir qu'un problème est calculable ne suffit pas à savoir le traiter car le temps de calcul peut être prohibitif.

## Les algorithmes

Nous utilisons tous, plus ou moins consciemment, des algorithmes plus
ou moins précis dans notre quotidien : pour réaliser des calculs, pour
organiser un déplacement, pour organiser notre journée de travail,
pour réaliser une tâche complexe. Par exemple, pour aller à pied de
mon domicile à un restaurant dont je connais l'adresse, je vais suivre
des rues, tourner à certaines intersections et parcourir la rue du
restaurant jusqu'à arriver devant sa porte selon un algorithme que je
me suis fixé, quitte à l'adapter si je me trompe en chemin. Nous
pouvons noter que nous n'utilisons pas tous le même algorithme et même
que je peux choisir un algorithme différent selon la météo, ma
connaissance de la destination, mon humeur ... Quant aux machines, les
algorithmes devront être définis de façon très précise en prévoyant à
l'avance toutes les situations possibles. Il existe également
plusieurs algorithmes possibles pour résoudre un même problème. Le
choix sera effectué en fonction des compétences du concepteur et de
contraintes comme l'efficacité de l'algorithme mesurée par le temps de
calcul.


```activité
::Modèle de machine::
[markdown]
**Modèle de machine**
Proposer une ressource simple et poser des questions sur modèle de Von Neuman
```

```activité
::Les minuscules en majuscules::
[markdown]
**Les minuscules en majuscules**
On souhaite apprendre à la machine à faire la transformation inverse, à savoir transformer les minuscules en majuscules. 
- Pour transformer un caractère minuscule en majuscule, quelle instruction faut-il changer dans `Maj2MinCara` ?
- Pensez-vous qu'on puisse apprendre à une machine à faire cette nouvelle instruction ?
- Expliquez ce qu'il faut changer dans `Maj2MinChaine` pour obtenir un programme `Min2MajChaine` qui prend en entrée une séquence de caractères et qui transforme les minuscules en majuscules et laisse tous les autres caractères inchangés.
{#### retirer 32 au code au
lieu d'ajouter 32 ; oui, on doit pouvoir apprendre à notre machine à
faire une soustraction de deux entiers même si cela semble un petit
peu plus compliqué que l'addition ; tester si le code du caractère est entre 97 et 123 et appeler le programme qui transforme minuscule en majuscule.}
```

```activité
::Robot::
[markdown]
**Programmer un robot simpliste**
Activité sur le robot ?
```

```activité
::Plusieurs algorithmes pour un même problème::
[markdown]
**Plusieurs algorithmes pour un même problème**<commit_msg>intro algo<commit_after>LANGUAGE:   fr
TITLE:   Les traitements et les applications
MENUTITLE: Les traitements
AUTHOR:     Culture numérique
CSS: http://culturenumerique.univ-lille3.fr/css/base.css

# Comprendre les traitements

Pour être un utilisateur averti et un acteur dans notre monde numérique, il est utile de comprendre pourquoi les ordinateurs peuvent nous paraître parfois plus précis, rapide ou efficaces que nous, voire même intelligents. Nous savons tous qu'ils peuvent calculer très vite, et donc traiter rapidement de grandes quantités de données. C'est un premier élément de compréhension, mais qui ne suffit pas. Nous allons détailler ici une explication complémentaire qui est leur capacité à réaliser des traitements complexes  en combinant des traitements de base très simples. À force de combinaisons, de combinaisons de combinaisons, etc, on arrive à définir des tâches vraiment impressionnantes. Mais ces combinaisons, c'est nous qui les commandons et les décidons à travers des algorithmes, puis des programmes. Si bien qu'on retrouve dans cette "intelligence informatique" des ordinateurs toute l'ingéniosité des femmes et des hommes qui les ont programmés. 

Dans cet objectif, nous allons étudier comment les applications fonctionnent, comment elles sont construites, comment elles se coordonnent et comment elles manipulent des données complexes.

Pour introduire ce cours, considérons l'exemple de calcul d'itinéraire par un logiciel sur un site Web, une application mobile ou encore un petit ordinateur spécifique qu'on appelle abusivement GPS (le GPS est juste le système de qui permet de déterminer sa position sur terre.). Tout d'abord, réfléchissons aux informations que doit posséder ce programme. Pour cela, il suffit de réfléchir à quoi nous aurions besoin nous-même, si nous devions réaliser cette tâche sans machine. Tout d'abord, il faut connaître le point de départ. Le programme peut parfois obtenir par des dispositifs techniques (une puce GPS, la connexion réseau) ou il peut vous le demander explicitement. Il faut  connaître le point d'arrivée et le moyen de transport. Supposons, pour simplifier la présentation, que le logiciel dispose d'une ville de départ, d'une ville destination et que le moyen de transport choisi est la voiture.  Qu'est-ce qu'un itinéraire ? C'est une suite de routes à emprunter pour rejoindre sa destination mais nous pouvons aussi représenter un itinéraire par une suite de villes voisines,  toujours par souci de simplification. Le nombre de ces villes étapes peut être variable et parfois grand. Le programme comme vous peut-il disposer de la liste de tous les itinéraires possibles entre ces deux villes quelconques ? La réponse est non car cela nécessiterait bien trop de ressources de stockage. Il dispose uniquement des connexions directes entre villes voisines (la liste des routes en fait), ce qui représente déjà un grand volume mais qui peut être stocké dans un petit équipement comme un smartphone. Il doit calculer les itinéraires possibles à partir de ces données. Mais un programme ne peut pas non plus calculer tous les itinéraires possibles entre les deux villes que vous avez choisies car le temps de calcul serait trop long et vous n'allez pas de Lille à Paris en passant par Marseille ! Donc ce programme se doit d'être plus "intelligent" et calculer vite ne suffit pas.

C'est un programme qui va calculer les itinéraires, mais uniquement les plus courts ou les plus rapides à partir de cette connaissance des distances directes (sans ville étape) entre deux villes. Ce programme va utiliser un algorithme dit de recherche de plus court chemin, issu des travaux de recherche de mathématiciens et informaticiens ayant étudié ce problème. Un algorithme ? Quésaco ? Retenez simplement ici qu'un algorithme est une explication très précise de *comment* résoudre un problème. On pourrait ici comparer tous les chemins de longueur 3 (les triplets de villes), puis 4 (les quadruplets de villes), puis 5, ...  mais le temps d'exécution serait horriblement long et inadmissible.  Cet algorithme de plus court chemin inventé dans les années 50 est ingénieux. Nous n'allons pas détailler dans cette introduction, mais il permet de trouver une solution en un temps dont l'ordre de grandeur est du nombre de couples de villes et peut donc donner des réponses très rapidement.  Comme tous les algorithmes, il consiste à enchaîner et répéter des opérations très simples comme comparer des valeurs numériques, les ajouter, les mémoriser, ces valeurs représentant des villes ou des distances. Mais le génie n'est pas dans l'algorithme mais bien dans ceux qui l'ont conçu, qui ont trouvé cette représentation des villes et des distances et qui l'ont exprimé à l'aide de  cette combinaison d'opérations simples. 

Notre étonnement à propos des programmes et des ordinateurs va grandissant quand on combine des calculs comme celui d'un itinéraire avec d'autres calculs pour la reconnaissance vocale, la géolocalisation etc. L'ensemble combiné va former des solutions complètes qui analysent le son de votre voix, le transforment en mots et phrases, y retrouvent suffisamment de sens pour identifier des villes et des rues, des adresses de départ ou de destination, et vous indiquent le chemin le plus rapide en fonction du trafic. À ce stade, le programme est devenu un logiciel, un assistant qui peut dépasser les capacités de votre passager uniquement accompagné de ses connaissances et sa carte routière. 

En premier lieu, cet exemple montre qu'exécuter une application implique l'exécution de nombreux programmes en interaction avec l'environnement (utilisateur, périphériques, réseau). Il montre également qu'une application est construite en composant d'autres applications : récupérer les données saisies, extraire le nom de la ville, calculer un itinéraire, ... C'est ce principe de composition qui permet de passer d'une machine "bête" manipulant des 0 et des 1 à une machine "intelligente" réalisant des applications complexes. C'est également ce principe de composition qui permet de définir des algorithmes pour résoudre des problèmes. L'exemple a également permis de montrer que malgré les capacités sans cesse croissantes des machines, il faut être attentif à la taille des données mémorisées et au temps de calcul des programmes. Enfin, on peut noter que l'intelligence supposée de la machine est due à l'intelligence des hommes et femmes ayant conçu les applications.

Dans la suite du cours, nous présentons comment composer des opérations pour définir de nouvelles opérations et discutons des algorithmes, nous présentons les langages de programmation et la traduction des algorithmes en programmes. Nous terminons par l'étude de quelques exemples : comment un correcteur orthographique peut-il corriger vos fautes,  et comment une machine peut-elle jouer aux échecs ou au go.

```Activité
Programmes, logiciels {}
```


# Les algorithmes 

## Expliquer clairement et précisément 

Le mot algorithme a fait irruption dans les médias après que des avancées notables ont été réalisées dans le domaine de l'informatique et ont affecté la société. C'est par exemple la naissance de l'internet et ensuite des moteurs de recherche qui ont posé la question de société de l'accès à la connaissance et des monopoles économiques dans ce domaine:  "Quel algorithme est donc responsable du choix de l'ordre dans lequel les résultats apparaissent". 

La tentative d'une définition scientifique du mot algorithme pourrait effaroucher plus d'un lecteur. Mais pour une introduction à une culture informatique, on peut plus certainement extraire les idées principales derrière ce mot algorithme. L'algorithme c'est d'abord *une explication de comment on résout un problème*. C'est donc pour nous, humains, cette explication, et pas pour les machines. Un célèbre livre d'introduction à l'algorithmique commence par "Before there were computers, there were algorithms.". Car nous passons nos journées à résoudre des petits problèmes du quotidien : pour faire son café le matin, pour organiser un déplacement ou notre journée de travail, ... Et nous sommes capables de les expliquer. "Je prépare mon café en prenant un filtre dans sa boite, le place dans la cafetière, j'y mets autant de cuillers de café que je veux de tasses,  je verse de l'eau dans la réserve tant que le niveau ne correspond pas au nombre de tasses choisi,  j'appuie sur le bouton de marche arrêt. Mais si je veux expliquer ma façon de procéder il faut que je sois clair. Être clair c'est au moins deux choses : il faut que les instructions que je donne soient bien claires et qu'on sache les réaliser. La clarté c'est éviter les ambiguïtés par exemple dans l'ordre dans lequel on doit faire les choses ou dans le sens des mots qu'on utilise. Par exemple "j'y mets" signifie je mets dans le filtre et pas dans un autre compartiment de la cafetière. Qu'on sache réaliser les instruction c'est faire une hypothèse sur ce que peut faire la personne à qui on s'adresse. Par exemple, si vous vous adressez à un invité chez vous, il ne sait peut être pas où vous rangez votre café et pourra pas résoudre son problème de petit déjeuner. 


On retrouve ces exigences quand on parle d'algorithme en informatique. Mais tout est exacerbé. Le texte de vos explications  doit être très précis et ne contenir aucune ambiguïté. N'importe qui doit pouvoir réaliser ce que vous décrivez, de façon automatique, sans penser, juger ou réfléchir. *Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique* dit <NAME>. Enlever la pensée, c'est devenir très bête. Imaginez avoir affaire à un imbécile et que le réservoir de votre cafetière était déjà plein. Si vous avez indiqué "je verse de l'eau dans la réserve tant que le niveau ne correspond pas au nombre de tasses choisi" et bien c'est l'inondation assurée si l'imbécile en question ne prépare qu'une tasse. Être clair est précis n'est pas suffisant... Il faut aussi que les explications soient justes dans toutes circonstances, sinon c'est le bug!

Comprendre ce qui se cache derrière ce mot algorithme ne peut être compris sans comprendre comment l'ordinateur fonctionne en tant que machine numérique et comment on interagit avec lui par le langage.


## Les algorithmes, les langages et la machine


La machine c'est l'ordinateur. Le mot inventé par un linguiste dans les années 50, fait référence à l'exécution d'ordres, d'instructions. En anglais le mot computer fait plutôt référence au calcul et les deux notions se retrouvent dans cette machine. Essentiellement la machine repose sur une *unité de calcul* qui fonctionne avec des valeurs représentées par des 0 et des 1. L'unité de calcul sait changer des 0 en 1, faire des calculs simples comme des additions, comparer des nombres. Elle utilise des *mémoires* pour retrouver ou ranger ces valeurs à des emplacements précisés par des numéros : les adresses. Enfin une *unité de contrôle* donne les ordres à l'unité de calcul et aux mémoires. Ce modèle de machine n'a pas bougé depuis les années 40. Il n'est peut être pas si simple de comprendre comment le réaliser physiquement et cela dépasse le cadre ce cours mais plusieurs l'ont fait depuis le premier dans les années 40 ! L'électricité,  puis l'électronique et  la miniaturisation ont considérablement réduit la taille et augmenté la rapidité de la mémoire,  de l'unité de calcul et l'unité de contrôle. Ces progrès ont aussi rendu l'ordinateur plus économe et plus résistant si bien qu'on le retrouve désormais dans tous les milieux et toutes les situations. 

```activité
Trouver le schéma de l'architecture von neumann. {}
```

Le langage informatique c'est ce qui permet d'interagir avec la machine. Le langage doit permettre de représenter des données, mais également des traitements. Nous l'avons abordé dans le module précédent à travers la question de la numérisation des données. Le langage, dans l'univers du numérique, c'est pluriel et artificiel : il existe de nombreux langages informatiques, inventés par l'homme, et faisant souvent l'objet de normes ou de standards,  parfois de brevets ou parfois laissés libres d'accès et d'évolution à la communauté. Ce qui les distingue des langages (ou langues) naturels (naturelles), c'est qu'ils ont été conçus pour qu'une machine les interprète et non un être humain. Ils doivent donc être précis, formels, plus encore même que la notation musicale qu'on a toujours la possibilité d'interpréter librement. 

```activité
le rôle des linguistes : qui a inventé le mot ordinateur, qui est larry wall, noam chomsky...{}

Que pensez vous de la phrase de <NAME> dans Structure and Interpretation of Computer Programs : 
Programs must be written for people to read, and only incidentally for machines to execute. {}
```



## L'illustration par le symbole

Rappelez-vous les conventions de langage dont nous avons parlé au module précédent, introduites pour représenter les caractères. Le caractère A majuscule a pour nom "Latin Capital Letter A" et pour numéro 65.  Croyez-nous, en binaire ce 65 s'écrit 01000001.  Le caractère a minuscule a pour numéro 97. En binaire cela s'écrit 01100001. C'est remarquable car c'est juste le 6eme chiffre partant de la droite, un 0,  qui est transformé en 1 pour passer de l'un à l'autre. Et cela est vrai pour toutes les lettres de notre alphabet latin. Le passage de majuscule à minuscule consiste juste à changer un 0 par un 1 à la sixième position. D'un point de vue arithmétique, l'interprétation du changement de ce 6ème chiffre est simplement d'ajouter ou retirer 32 au numéro. 65 +32 fait bien 97. 

Ce choix de représentation, donc de langage pour représenter les symboles est donc très lié au fonctionnement binaire de la machine et à ses capacités de calcul arithmétique. C'est là l'ingéniosité des personnes qui ont conçu ce langage de représentation des symboles. À partir de cela, on peut facilement imaginer le traitement que doit réaliser la machine pour transformer un symbole stocké dans sa mémoire de majuscule en minuscule. Il est nécessaire de connaître l'adresse où ce symbole est stocké. Imaginons que ce soit l'adresse 413. 

    Accéder à la mémoire à l'adresse 413 (retrouver la valeur binaire 
	                                      correspondant au code 
										  d'un symbole)
	Ajouter 32                           (c'est-à-dire, dans l'unité 
	                                      de calcul,  changer le 6ème 
										  chiffre de 0 en 1.)
	Ranger le résultat dans la mémoire 413 

Nous retrouvons dans cet exemple l'organisation de la machine avec ses adresses, sa mémoire, son unité de calcul et son unité de contrôle. L'unité de contrôle doit juste assurer que ces 3 instructions soient réalisées successivement dans cet ordre, *en séquence*. Nous n'irons pas dans les détails du langage numérique inventé pour représenter ces 3 instructions, ce n'est pas très important ici. Par contre, les  notions importantes à retenir sont les suivantes. Premièrement nous sommes parvenus à créer un traitement qui porte un sens pour nous, à partir de la représentation numérique d'une information et grâce à une combinaison d'instructions. Deuxièmement, l'ordonnancement en séquence des instructions constitue le premier outil de combinaison. Nous venons de décrire un algorithme simple ! 


## Et si ce n'était pas une lettre majuscule ?

L'ordinateur est d'abord une machine très obéissante et exécute scrupuleusement les ordres qu'on lui donne. Le traitement précédent ajoutera 32 au numéro même si celui-ci n'est pas le numéro d'une lettre majuscule. Par exemple le numéro 64 représente l'arobase @  et si on lui ajoutait 32 cela donnerait une apostrophe inversée (`). Cela consisterait en une erreur, un bug, car ce n'est pas ce qui est attendu ! On devrait ne permettre le passage en majuscules ou minuscules qu'aux symboles alphabétiques. Pour contrôler cela, il faut introduire une vérification que nous pouvons décrire comme :

    Accéder à la mémoire à l'adresse 413 
	Si la valeur est comprise entre 65 et 90 Alors 
       Ajouter 32 
	   Ranger le résultat dans la mémoire 413 
    Fin du Si
	
	
Parmi les instructions de base que l'unité de calcul sait faire, outre les opérations arithmétiques, nous disposons aussi des comparaisons. 
Le *si* que nous venons d'utiliser très naturellement est la deuxième façon de combiner des instructions. Remarquez que l'algorithme utilise à la fois des *séquences* et un *si*. C'est une combinaison qui permet de considérer différentes *alternatives* dans le déroulement de l'algorithme, sous certaines conditions. 

## Et pour un texte complet ?

Supposons maintenant que ce soit un texte complet que nous voulons mettre en majuscules... Là encore c'est une articulation entre langage de représentation, machines et algorithmes que nous allons illustrer. Dans un premier temps, il faut choisir une représentation du texte. Ce sera une suite de symboles stockés dans la mémoire les uns à la suite des autres et terminés par un symbole spécial représenté en binaire par 0000000. Ce choix de représentation est très souvent utilisé. De plus, du point de vue de la machine, l'unité de calcul permet de faire des opérations sur les valeurs aussi bien que sur des adresses (qui sont aussi des valeurs). L'algorithme lui s'écrira :

    L'adresse courante est 413
    Accéder à la mémoire à l'adresse courante
	Répéter tant que la valeur n'est pas 0000000
  	   Si la valeur est comprise entre 65 et 90 Alors 
          Ajouter 32 
	      Ranger le résultat dans la mémoire à l'adresse courante
	   Fin du Si
       Ajouter 1 à l'adresse courante 
       Accéder à la mémoire à l'adresse courante 
    Fin de la répétition 
	
Voilà la troisième manière de combiner des instructions : la répétition. Les informaticiens l'appellent *la boucle*, ou *l'itération*. Le sens de cette répétition peut être précisé. Lorsque l'unité de contrôle demande à exécuter la répétition, l'unité de calcul vérifie que la valeur n'est pas 00000000. Si tel est le cas tout ce qui se trouve entre la répétition et la fin de répétition sera exécuté, puis on reviendra au point où il faut vérifier la valeur n'est pas 00000000, et ainsi de suite. La répétition s'arrêtera lorsque la valeur sera 00000000. 

## Les trois combinaisons

Rappelons un petit point d'étape. Machines,  langages (incluant la représentation numérique de l'information et des traitements), et algorithmes sont intimement liés, dépendants.  Autrement dit,  comprendre l'une de ces notions demande d'avoir aussi quelques notions à propos des autres. Les ordinateurs depuis leur création dans les années 40 suivent tous une même organisation qui comprend une unité de calcul de la mémoire et une unité de contrôle. C'est l'architecture de von Neumann. Nous avons illustré ce fonctionnement sur une tâche simple de passage d'un texte en majuscule et mis en évidence 3 structures de combinaison d'instructions qui peuvent être traduites dans l'unité de contrôle: la séquence qui fait passer à l'instruction suivante, l'alternative qui permet de choisir la prochaine instruction selon la valeur d'un test et la répétition d'instructions tant qu'un test est satisfait. 

Une grande force de ces combinaisons est qu'elles s'appliquent sur des instructions de base de la machine comme consulter la mémoire ou réaliser une opération arithmétique, mais aussi sur d'autre combinaisons. L'exemple précédent l'illustre bien. Nous avons une séquence de mémorisation, suivie d'un accès à la mémoire et suivi ensuite par une répétition. La répétition comprend elle-même une alternative suivie en séquence par une opération arithmétique et un accès à la mémoire. 

C'est un vrai jeu de construction! À la manière des Legos où partant de briques de bases, par assemblage on construit des maisons et des villes, on est devant un univers infini de possibilités, pourvu que vous ayez autant de  briques que voulu, où toute votre créativité peut s'exprimer. 

Dans le monde informatique, au fur et à mesure de ces combinaisons, les traitements deviennent de plus en plus impressionnants et puissants. Mais les principes de base restent identiques. Par exemple dans le cas de notre application d'assistance routière, nous retrouvons la composition en séquence de la reconnaissance vocale des directions, le calcul d'itinéraire et son affichage. L'alternative permet, si le lieu d'arrivée n'est pas connu, d'afficher un message plutôt que l'itinéraire. L'itération est la combinaison qui permet la répétition des annonces vocales tant que vous n'êtes pas arrivé... 

## Calculer et calculable 

À partir des instructions de base de la machine, on construit donc des traitements par un algorithme en utilisant les trois modes de composition que sont la séquence, l'alternative et l'itérative. Est-ce suffisant ? Oui car il existe un **théorème** qui affirme que tout ce qui est calculable avec une machine peut être défini par quelques opérations élémentaires et les opérations de composition que sont la suite (ou la séquence), l'alternative et l'itérative. Ce théorème a été démontré au milieu du vingtième siècle par des mathématiciens et des logiciens. Ceci soulève immédiatement la question : une machine peut-elle tout calculer ? La réponse, démontrée à la même époque, est négative : il existe des problèmes que ne peut pas résoudre une machine. Par exemple, il est montré qu'il n'existe pas d'algorithme qui prend en entrée une suite d'instructions contenant des alternatives et des itératives et qui répond en sortie cette suite d'instructions va s'arrêter en un temps fini lorsqu'on l'exécutera. Ces sujets soulèvent des problèmes importants qui ont été et sont encore étudiés par les mathématiciens, les informaticiens, les logiciens et les philosophes. Notons enfin, que savoir qu'un problème est calculable ne suffit pas à savoir le traiter car le temps de calcul peut être prohibitif.




```activité
Qu'est-ce qu'un algorithme en 1 minute : https://www.youtube.com/watch?v=u9XEsJypSdc {}

::Modèle de machine::
[markdown]
**Modèle de machine**
Proposer une ressource simple et poser des questions sur modèle de Von Neuman
```

```activité
::Les minuscules en majuscules::
[markdown]
**Les minuscules en majuscules**
On souhaite apprendre à la machine à faire la transformation inverse, à savoir transformer les minuscules en majuscules. 
- Pour transformer un caractère minuscule en majuscule, quelle instruction faut-il changer dans `Maj2MinCara` ?
- Pensez-vous qu'on puisse apprendre à une machine à faire cette nouvelle instruction ?
- Expliquez ce qu'il faut changer dans `Maj2MinChaine` pour obtenir un programme `Min2MajChaine` qui prend en entrée une séquence de caractères et qui transforme les minuscules en majuscules et laisse tous les autres caractères inchangés.
{#### retirer 32 au code au
lieu d'ajouter 32 ; oui, on doit pouvoir apprendre à notre machine à
faire une soustraction de deux entiers même si cela semble un petit
peu plus compliqué que l'addition ; tester si le code du caractère est entre 97 et 123 et appeler le programme qui transforme minuscule en majuscule.}
```

```activité
::Robot::
[markdown]
**Programmer un robot simpliste**
Activité sur le robot ?
```

```activité
::Plusieurs algorithmes pour un même problème::
[markdown]
**Plusieurs algorithmes pour un même problème**
{'fraction_non_alphanumeric': 0.03501624937062297, 'fraction_numerical': 0.006316656749210418, 'mean_word_length': 4.638792102206736, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 7, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2175058', 'n_tokens_mistral': 13052, 'n_tokens_neox': 12604, 'n_words': 6620}