Computation avec JavaScript

Mattia A. Fritz
TECFA, Université de Genève

Théorie de la computation

• Théorie de la complexité
  Pourquoi des problèmes sont plus simples à résoudre et d'autres plus difficiles ?
• Théorie de la computation
  Pourquoi des problèmes ont une solution algorithmique et d'autres pas?
• Théorie des automates
  Comment faire ainsi que des agents contribuent à l'exécution d'algorithmes ?

Langage de programmation

Utiliser une notation conventionnelle destinée à formuler des algorithmes et produire des programmes informatiques qui les appliquent.

• Éléments littéraux
  L'élément représente soi-même, par exemple un chiffre, le nom d'une personne, etc.
• Éléments symboliques
  L'élément représente quelque chose d'autre, qu'on peut par exemple manier ou transformer

let name = "My name is Bond, James Bond"

Éléments littéraux

Les éléments littéraux peuvent être de différents types. On peut connaître le type à travers la commande typeof dans la console F12. Parmi les plus utilisés figurent :

          // Éléments numériques
          typeof 100
          typeof 3.14
          // Éléments textuels/suites de caractères
          typeof "Hello"
          typeof 'Ajourd\'hui j\'apprends JavaScript'
          typeof "1234567890"
          // Éléments logiques
          typeof true
          typeof false
          // Éléments spéciaux
          typeof undefined
          typeof null  
          

Éléments symboliques

Les éléments symboliques d'un bout de code informatique se divisent en deux types :

• Éléments symboliques conventionnels
  Ce sont des mots clés réservés par le langage qui sont déjà associés à un rôle ou une fonction spécifique. Par exemple:
  

  let, if, function, while, do, typeof, Math.PI, Math.random(), ...

• Éléments symboliques arbitraires/personnalisés
  Ce sont des créations ad hoc pour accomplir les intentions du développeur qui peut définir ses propres éléments (e.g. variables et fonctions). Par exemple :
  

  giveStudentFeedback(), shuffleMemoryCards(), checkAnswer(), ...

Facteurs principaux

En combinant éléments littéraux et symboliques, la computation s'appuie principalement sur trois processus :

• Identifier et stocker les données
  Surtout lorsque la computation se fait progressivement et/ou sur beaucoup de données, il est nécessaire de pouvoir faire référence aux données de manière unique et précise.
• Exploiter ou créer des procédures pour traiter les données
  Les données sont censées évoluer dans la logique de la computation vers des états plus intéressants/utiles (e.g. le score à un quiz, une photo améliorée, ...)
• Insérer des méta-éléments pour diriger la computation
  La computation doit souvent s'adapter à des conditions qui déterminent si, quand et quel code exécuter (e.g. selon le résultat d'autres computations précédentes).

Identification et stockage

• Affecter une valeur à une variable
  

  
            var score_actuelle = 156;
            

• Affecter une liste à une variable et identifier un élément
  

  
            var countries = ["France", "Italy", "Switzerland", "Canada"];
            countries[2];
            

• Affecter un objet à une variable et identifier une propriété
  

  
            var cours = {
              name: "Introduction to psychology",
              professor: "M. Dupont",
              students: ["John", "Jane", "Jack", "Jill"]
            };
            cours.professor;
            

Procédure de traitement

• Exemple générique pour déclarer une fonction
  

  
                function myProcedure(input) {
                  //Do something
                  var output = input + " transformation";
                  return output;
                }
                

• Inverser l'ordre des lettres dans une suite de caractères
  

  
                function reverseWord(word) {
                  return word.split('').reverse().join('');
                }
  
                reverseWord("Hello"); //Donne "olleH"
                

Diriger la computation

• Exemple d'une structure simple
  

  
                if (score > 4) {
                  congratulateStudent(score);
                }
                

• Exemple d'une structure de contrôle composite
  

  
                if (testStatus == "complete" && score < 4) {
                  randomComfortingMessage();
                  takeTestAgain("easy");
                } else if (testStatus == "complete" && score >= 4) {
                  congratulateStudent(score);
                  takeTestAgain("hard");
                } else {
                  nextQuestion();
                }
                

Mélanger les trois...

La computation même de logiques simples nécessite plusieurs lignes de code. Ici l'exemple du jeu du morpion que vous pouvez tester en ouvrant la console JavaScript sur cette page avec la touche F12 et en tapant x(case) ou o(case) pour jouer. Par exemple x(1), o(5), x(3), ...

/**
 * We need some variable to stock information that will be used throughout the game
 */

var players = {
  x: {
    name: "Player 1",
    score: 0
  },
  o: {
    name: "Player 2",
    score: 0
  }
};

//It is up to x to make the first move
var whoseTurnIsIt = "x";

//The 9 cases are empty by defualt
var cases = [];

/**
 * Now the functions for the game
 */

//Reset the cases to have a new game
function newGame() {
  cases = [];
}

//This is the main function that add the mark to the case and makes the cheks
function addMark(who, where) {
  //check if it is the right turn
  if (whoseTurnIsIt != who) {
    console.log("ERROR, it is up to", players[whoseTurnIsIt].name, "to play!");
    return;
  }
  //check that the provided case is between 1 and 9 and it is an integer
  if (where < 1 || where > 9 || parseInt(where) !== where) {
    console.log("ERROR, please provide a case between 1 and 9");
    return;
  }
  //check if the case is free
  if (cases[where]) {
    console.log("ERROR, this case is already taken");
    return;
  }

  //add the mark to the specified position
  cases[where] = who;

  //printBoard
  printBoard();

  //checkIfPlayer wins
  isWinningMove(who);

  //Switch turn
  switchTurn();

  //Check if there are still cases empty or play a new game
  isGameFinished();
}

//Switch turn
function switchTurn() {
  if (whoseTurnIsIt == "x") {
    whoseTurnIsIt = "o";
  } else {
    whoseTurnIsIt = "x";
  }
}

//Check if player wins
function isWinningMove(who) {
  var won = false;
  var winningCombinations = [
    [1, 2, 3],
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9],
    [1, 5, 9],
    [3, 5, 7],
    [4, 5, 6],
    [7, 8, 9]
  ];

  //Iterate the combinations
  for (let i = 0; i < winningCombinations.length; i++) {
    //Retrieve the symbole inside the three winning cases
    let case1 = cases[winningCombinations[i][0]];
    let case2 = cases[winningCombinations[i][1]];
    let case3 = cases[winningCombinations[i][2]];

    //Check if all the cases have the same symbol and are not empty
    if (case1 && case1 === case2 && case2 === case3) {
      won = true;
    }
  }

  //If the player has won, show a message, increase the score, and start a new game
  if (won) {
    players[who].score++;
    console.log("Congratulations ", players[who].name, " You have won!");
    console.log("Player 1 has", players.x.score, "points");
    console.log("Player 2 has", players.o.score, "points");
    newGame();
  }
}

//Print the board
function printBoard() {
  var board = "-------------\n";
  board += "|";
  for (let i = 1; i <= 9; i++) {
    board += " " + (cases[i] || "-") + " |";
    if (i % 3 == 0) {
      board += "\n-------------\n";
      if (i != 9) {
        board += "|";
      }
    }
  }
  console.log(board);
}

//Check if there are some cases left to go on the game
function isGameFinished() {
  //If there is at least one case empty, get back to the game
  for (let i = 1; i <= 9; i++) {
    if (!cases[i]) {
      return;
    }
  }
  //Otherwise start a new game
  console.log(
    "It's a draw! Let's start a new one. It is up to",
    players[whoseTurnIsIt].name,
    "to play!"
  );
  newGame();
}

//shortCuts so that you must use commands such as x(1) or o(9)
function x(where) {
  addMark("x", where);
}
function o(where) {
  addMark("o", where);
}

          

Pour aller plus loin

Les concepts abordés dans cette présentation sont traités de manière plus exhaustive dans l'article Computation avec JavaScript sur EduTechWiki.

EduTechWiki est un wiki sur la technologie éducative hébergé est maintenu par TECFA, une unité de l'Université de Genève, depuis 2006.