Computation avec JavaScript

Cet article est en construction: un auteur est en train de le modifier.

En principe, le ou les auteurs en question devraient bientôt présenter une meilleure version.

---

Introduction

Cette page complémente le Tutoriel JavaScript de base avec l'analyse d'exemples d'algorithmes en JavaScript. Les exemples sont censés montrer des petites applications ou des simples jeux, mais sans l'interface utilisateur qui est traitée plutôt dans le Tutoriel JavaScript côté client et, surtout, dans la page Interactivité avec JavaScript qui utilise une approche avec des exemples expliqués de manière détaillée.

L'objectif de cet article est de montrer, avec des exemples pratiques, comment on peut combiner les éléments fondamentaux de la programmation pour construire une solution automatisée qui permet d'atteindre un objectif déterminé, que se soit un petit jeux ou du traitement de l'information.

Avant de voir les exemples, nous allons définir très superficiellement le concept de computation et le mettre en relation avec la programmation. Ensuite, nous verrons de manière technique comment se passe la computation/évaluation du code en JavaScript.

Prérequis

Pour lire cet article, des notions sur les éléments fondamentaux de la programmation, illustrés dans l'introduction à la programmation peuvent faciliter la compréhension à la fois des termes techniques et des concepts auxquels ils se réfèrent. Une exposition au moins à la syntaxe de JavaScript, disponible dans la deuxième section du Tutoriel JavaScript de base, est également conseillée, même si des références croisées à cette page sont disponibles surtout dans les premiers exemples.

Exemples traités dans l'article

Occasionnellement, nous allons utiliser un prompt() pour simuler des inputs différents, même si cet élément est disponible exclusivement dans le navigateur.

Les exemples sont censés fonctionnent dans tous les environnements où JavaScript peut être exécuté et par conséquent ils peuvent être testé directement dans la console du navigateur comme il a été suggéré dans le Tutoriel JavaScript de base. La seule exception concerne l'utilisation dans certains exemples de l'élément prompt() qui appartient à l'environnement JavaScript côté client, mais qui nous servira pour simuler facilement des inputs différents que vous aurez à fournir à travers la fenêtre.

Tous les exemples illustrés dans cette page sont disponibles dans un repository de GitHub. Ils suivent une numérotation qui sera utilisée pour les référencer également dans le texte, par exemple: 00-01.

• Repository MALTT-STIC/stic-1-computation-with-javascript
  pour télécharger les fichiers ou voir le code source complet

Lorsque le code des exemples est expliqué dans l'article, pour des raisons d'espace, souvent seulement les parties indispensables à la compérhension du concept expliqué seront affichés. En général, les numéros des lignes intéressées sera fourni pour pouvoir repérer le code dans les fichiers, par exemple 00-01 Lignes 10-20.

Définition de computation

Schéma de la Théorie de la computation, inspiré par Sipser (2012)

Pour définir la computation, nous allons introduire brièvement et de manière très superficielle la théorie de la computation (Sipser, 2012). Cette théorie s'intéresse à la question fondamentale de savoir quels sont les possibilités et, par conséquent, les limites (ou non possibilités) des calculateurs (Sipser, 2012). Par calculateurs il faut entendre tout système, physique ou théorique, qui permet de faire des calcules. En effet, cette théorie peut être vue sur un continuum entre deux pôles :

• le pôle théorique qui est plus étroitement lié à la logique et aux mathématiques ;
• le pôle appliqué qui est plus proche des objectifs de cette page et s'occupe d'implémenter physiquement les aspects théoriques dans des machines ou dans des programmes.

La théorie de la computation émerge de l'interaction de trois sous-théories (Sipser, 2012) :

1. La théorie de la complexité

   Cette branche analyse les raisons pour lesquelles certains problèmes sont faciles à résoudre et d'autres sont plus complexes.

2. La théorie de la computation

   Cette branche s'intéresse aux problèmes de manière dichotomique, en essayant de déterminer quels problèmes ont une solution possible et ceux qui, au contraire, ne peuvent pas être résolus.

3. La théorie des automates

   Cette branche concerne tous les éléments qui peuvent faire eux-mêmes ou contribuer à exécuter des calculs. Dans le cadre de nos objectifs pour cet article, on retrouve dans cette branche les ordinateurs ou dispositifs numériques en général, les compilateurs/interprètes, ainsi que les langages de programmation.

Nous introduisons ces concepts très abstraits pour illustrer que les dispositifs numériques qu'on utilise aujourd'hui sont directement lié à cette théorie, car on fait remonter typiquement la naissance de l'informatique (ou Computer Science) aux travaux de Alonzo Church et Alan Turing à propos du problème de la décision. En essayant de simplifier au maximum ces concepts, il s'agit de la possibilité de créer un système mécanique qui soit capable de déterminer si la solution trouvé à un problème à travers des algorithmes est correcte. La machine de Turing, un modèle théorique de calculateur, est le résultat de cette tentative et elle est à la base des dispositifs numériques qu'on utilise aujourd'hui. La plupart de ces dispositifs, en effet, est basé sur ce qu'on appelle l'architecture de Von Neumann, d'après le mathématicien John von Neumann, qui s'est inspiré aux travaux de Turing.

Définition informelle pour les objectifs de cet article

La théorie de la computation dépasse largement les objectifs de cet article, mais on peut néanmoins s'en servir pour formuler une définition informelle de la computation plus adaptée au contexte de cet article. On peut considérer le développement comme un processus qui consiste à :

Réduire la complexité d'un problème ou d'un besoin, par exemple une application interactive qui favorise l'apprentissage d'une langue étrangère, à un format assez simple pour qu'on puisse construire un algorithme à implémenter dans un dispositif avec un interprète JavaScript.

Réduire la complexité se réfère à la possibilité de décomposer toutes les fonctionnalités nécessaires à notre application pour qu'on puisse les traduire en code JavaScript. C'est à ce stade qu'il faut déployer les principes de la pensée computationnelle : décomposition, reconnaissance de pattern, abstraction et construction d'algorithmes. Il faut bien noter que ces capacités sont nécessaires pour pouvoir instruire la machine. S'il y avait une fonction JavaScript déjà disponible, du type Learn('Italiano') = Io parlo perfettamente l'italiano, on l'utiliserait ! Mais cela n'existe pas, et donc il faut utiliser les blocs constitutifs de la programmation (variables, boucles, structure de contrôle, ...) pour la construire.

Bibliographie

• Sipser, M. (2012). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. (Oeuvre très spécifique)