Algorithmique
et JavaScript

Introduction

Algorithme

Ensemble de règles opératoires dont l'application permet de résoudre un problème énoncé au moyen d'un nombre fini d'opérations.

Un algorithme peut être traduit, grâce à un langage de programmation, en un programme exécutable par un ordinateur.

Larousse

Un algorithme, très simplement, c’est une méthode.

Une façon systématique de procéder pour faire quelque chose : trier des objets, situer des villes sur une carte, multiplier deux nombres, extraire une racine carrée, chercher un mot dans le dictionnaire…

Ph. Flajolet & É. Parizot, Qu'est-ce qu'un algorithme ?

Algorithmique

Étude de la résolution de problèmes par la mise en œuvre de suites d'opérations élémentaires selon un processus défini aboutissant à une solution.

Arrêté du 27 juin 1989 relatif à
l'enrichissement du vocabulaire de l'informatique

Programme

1. Description de la suite, souvent cyclique, d'opérations que doit effectuer une machine quelconque (machine à laver, machine-outil, réacteur chimique à charges discrètes, ordinateur, etc.).
2. Ensemble d'instructions et de données représentant un algorithme et susceptible d'être exécuté par un ordinateur.

Larousse

Langage informatique

Tandis que le langage naturel permet de communiquer avec d'autres humains,
le langage informatique permet de s'adresser à des ordinateurs.

Le langage informatique permet de formuler des algorithmes.

À l'instar du langage naturel, le langage informatique est défini par une grammaire
que tout programmeur doit respecter pour se faire comprendre par la machine.

Cette grammaire définit les mots acceptés par le langage
et les différentes façons de les assembler pour construire des phrases.

Une phrase adressée à un ordinateur est appelée instruction.

JavaScript

• Créé en 1995 par Brendan Eich
• Mocha, puis LiveScript, puis JavaScript
• Développé pour Netscape Communicator
• Standardisé en 1997 sous le nom d'ECMAScript

Généalogie

Node.js1/3

• Créé en 2009 par Ryan Dahl
• Environnement d'exécution JavaScript
• Développement JS côté serveur
• Basé sur le moteur JS de Chrome : V8
• Mode interactif (REPL) ou mode fichier

Node.js2/3

aassif@localhost # nodejs
Welcome to Node.js v16.17.1.
Type ".help" for more information.
> 'Hello, World!'
'Hello, World!'
> Math.PI
3.141592653589793
> null

> undefined

> .exit
aassif@localhost # 

Node.js3/3

// Affiche "Hello, World!"
console.log ('Hello, World!');

aassif@localhost # nodejs hello-world.js
Hello, World!
aassif@localhost # 

Variables

Architecture de von Neumann

https://fr.wikipedia.org/wiki/Architecture_de_von_Neumann

Variable ?

Conteneur pour une valeur susceptible d'être manipulée ou modifiée.

• Nom ou identifiant
• Type de donnée
• Portée

Identifiant

Règles de nommage

Un identifiant doit respecter des règles établies par le langage.

En JavaScript, le premier caractère doit être une lettre, $ ou _ ;
les chiffres sont également acceptés à partir du deuxième caractère.

Mots réservés

Certains noms sont interdits car ils ont un rôle dans le langage.

break / case / catch / class / const / continue / debugger / default / delete / do / else / export / extends / finally / for / function / if / import / in / instanceof / new / return / super / switch / this / throw / try / typeof / var / void / while / with / yield ECMAScript 2015

Déclaration

• Pour manipuler une variable, il faut avoir déclaré son existence
• Cette étape indispensable est nommée déclaration
• En JavaScript : mot-clé let suivi de l'identifiant choisi

// Déclaration unique.
let variable;
// Déclarations multiples.
let var1, var2, var3;

Affectation

Attribution d'une valeur à une variable.

variable = valeur

La valeur affectée peut être une donnée ou une autre variable.

// Déclaration de "var1".
let var1;
// Affectation de la donnée 0.
var1 = 0;
// Déclaration avec initialisation.
let var2 = var1;

Constantes

Variable à affectation unique !

const constante = valeur;

> const zero;
const zero;
      ^^^^

Uncaught SyntaxError: Missing initializer in const declaration
> const zero = 0;

> zero;
0
> zero = 1;
Uncaught TypeError: Assignment to constant variable.
> 

Portée d'une variable1/2

• Domaine d'existence d'une variable
• Une variable existe dans le bloc où elle a été déclarée
• Un bloc est un ensemble d'instructions délimité par des accolades
• Un bloc peut contenir d'autres blocs, appelés sous-blocs
• Une variable est héritée par les sous-blocs

Portée d'une variable2/2

// "un" n'existe pas encore.
let un = 1;
// "un" existe.
{
  // "un" existe.
  // "deux" n'existe pas encore.
  let deux = 2;
  // "un" et "deux" existent :)
}
// "un" existe toujours.
// "deux" n'a jamais existé ici.

Type de donnée

Définit la nature des valeurs que peut prendre une donnée
et les opérateurs qui peuvent lui être appliqués.

• Booléens (vrai ou faux)
• Nombres (0, -0.5, 10¹⁰⁰, etc.)
• Chaînes de caractères (« bonjour »)
• Objets (données structurées)
• Fonctions (séquences d'instructions)
• undefined

Booléens1/2

• Type boolean (d'après George Boole)
• Deux éléments, appelés valeurs de vérité :

  true	vrai
  false	faux

Booléens2/2

> true
true
> false
false
> let vrai = true;

> vrai;
true
> typeof vrai;
'boolean'
> 

Opérateur de négation1/2

!operande

• Opérateur préfixe unaire
• Permet de construire une expression en le combinant avec un opérande
• Cet opérande peut être une donnée, une variable ou une autre expression
• Une expression construite à partir d'un opérateur de négation et d'un opérande vaut la négation de l'opérande, c'est à dire son contraire : faux pour vrai et vrai pour faux

Opérateur de négation2/2

> !true
false
> !false
true
> !!true
true
> !!false
false
> 

Opérateurs de comparaison1/3

• Opérateurs infixes binaires
• Deux opérandes de type identique
• Comparent les valeurs des deux opérandes
• Expressions booléennes : vrai ou faux

Opérateurs de comparaison2/3

Opérateurs de comparaison3/3

> true === true
true
> true === false
false
> false === true
false
> false === false
true
> 

> true !== true
false
> true !== false
true
> false !== true
true
> false !== false
false
> 

 (expr1 === expr2)  ===  (expr2 === expr1) 
 (expr1 !== expr2)  ===  (expr2 !== expr1) 
 (expr1 !== expr2)  === !(expr1 === expr2) 
!(expr1 !== expr2)  ===  (expr1 === expr2) 

Opérateurs logiques1/3

• Opérateurs infixes binaires
• Deux opérandes de type booléen
• Combinent les deux opérandes
• Expressions de type booléen

Opérateurs logiques2/3

Opérateurs logiques3/3

> true || true
true
> true || false
true
> false || true
true
> false || false
false
> 

> true && true
true
> true && false
false
> false && true
false
> false && false
false
> 

 !(expr1 && expr2) === (!expr1 || !expr2)
 !(expr1 || expr2) === (!expr1 && !expr2)

Nombres

• Type number
• Nombres entiers et nombres flottants
• +Infinity, -Infinity, NaN

Opérateurs arithmétiques1/2

+ - * / %

• Opérateurs infixes binaires
• Deux opérandes de type numérique
• Expressions de type numérique

Opérateurs arithmétiques2/2

> 1 + 2
3
> 5 / 2
2.5
> 5 % 2
1
> 0.1 + 0.2
0.30000000000000004
> typeof NaN
'number'
> 

Opérateurs d'affectation

Il est possible de combiner une opération et une affectation

Incrémentation

• Opérateurs unaires préfixe et postfixe
• Opérande de type numérique
• Expressions de type numérique

Les deux formes ont pour effet d'additionner 1 à la valeur d'une variable ;
la première de façon immédiate, l'autre de façon différée.

y = ++x; équivaut à x += 1; y = x;

y = x++; équivaut à y = x; x += 1;

Décrémentation

• Opérateurs unaires préfixe et postfixe
• Opérande de type numérique
• Expressions de type numérique

Les deux formes ont pour effet de soustraire 1 à la valeur d'une variable ;
la première de façon immédiate, l'autre de façon différée.

y = --x; équivaut à x -= 1; y = x;

y = x--; équivaut à y = x; x -= 1;

Opérateurs de comparaison

=== !==

< <= > >=

• Opérateurs infixes binaires
• Deux opérandes de type numérique
• Expressions de type booléen

Priorité

Arbre syntaxique

a /= (b + 5) * c++;

Chaînes de caractères1/2

• Type string
• Contenu textuel
• Délimitées par des quotes '' ou des guillemets ""
• Opérateurs de concaténation + et +=

Chaînes de caractères2/2

// Déclaration d'une chaîne de caractères
let bonjour = "Bonjour !";

// Longueur d'une chaîne de caractères
let n = bonjour.length;           // 9

// Accès à un caractère par son index
let c = bonjour [0];              // 'B'

// Accès à une portion de chaîne
let s = bonjour.substring (3, 7); // 'jour'

Objets1/2

Objets structurés avec propriétés nommées

• Type object
• Délimités par des accolades { }
• Paires 'clé' : valeur
• Paires séparées par des virgules

Objets2/2

let algo =
{
  code : 'AlgoJS',
  intitule : "Algorithmique et JavaScript",
  enseignant : {prenom: 'Aassif', nom: 'Benassarou'},
  'volume-horaire' : 47
};

console.log (algo.code);              // AlgoJS
console.log (algo.enseignant.nom);    // Benassarou
console.log (algo['volume-horaire']); // 47

JSON

• JavaScript Object Notation
• Format d'échange de données
• Syntaxe très compacte
• Limité aux types natifs

Conversion explicite

• Boolean(expression)
• Number(expression)
• String(expression)

Conversion en booléen

> Boolean(0)
false
> Boolean(1)
true
> Boolean("")
false
> Boolean("false")
true
> Boolean(null)
false
> Boolean(undefined)
false
> 

Conversion en nombre

> Number(true)
1
> Number(false)
0
> Number("1.23e2")
123
> Number("0x7b")
123
> Number(null)
0
> Number(undefined)
NaN
> 

Conversion en chaîne

> String(true)
'true'
> String(false)
'false'
> String(1.23e2)
'123'
> String(0x7b)
'123'
> String(null)
'null'
> String(undefined)
'undefined'
> 

Comparaison faible

== et !=

Comparaison avec conversion.

Usage déconseillé en algorithmique !

> 1 == '1'
true
> null == undefined
true
> 

Attention !

Contrairement à d'autres langages, comme le C, le C++ ou le Java,
JavaScript est un langage interprété, faiblement typé.

main(k){float i,j,r,x,y=-16;while(puts(""),y++<15)for(x
=0;x++<84;putchar(" .:-;!/>)|&IH%*#"[k&15]))for(i=k=r=0;
j=r*r-i*i-2+x/25,i=2*r*i+y/10,j*j+i*i<11&&k++<111;r=j);}

gcc mandelbrot.c -o mandelbrot

Travaux pratiques

• TP nº 1 : variables
• TP nº 2 : expressions

Structures
de contrôle

Structure de contrôle ?

Les structures de contrôle font partie intégrante des langages informatiques.

Généralement, elles sont mises en places à l'aide de mots-clés et de blocs.

Elles proposent un cheminement non linéaire au sein d'un programme ;
certaines conditionnent l'éxécution d'instructions,
d'autres permettent de les répéter.

Condition1/2

Exécution conditionnée d'un bloc d'instructions

if (condition)
{
  // Instructions exécutées
  // si condition vaut "true".
  instructions;
}

Condition2/2

Alternative1/2

if (condition)
{
  // Instructions exécutées
  // si condition vaut "true".
  instructions1;
}
else
{
  // Instructions exécutées
  // si condition vaut "false".
  instructions2;
}

Alternative2/2

Exercice1/2

Exercice2/2

// Tirage aléatoire.
let x = Math.random ();
//console.log ('x', x);

// Booléen.
let b = (x >= 0.5);
//console.log ('b', b);

// Alternative
if (b)
  console.log ('vrai');
else
  console.log ('faux');

Opérateur conditionnel1/2

condition ? valeur1 : valeur2

• Opérateur ternaire
• 1^er opérande de type booléen
• 2^e et 3^e opérandes de type identique
• valeur1 si condition ; valeur2 sinon

Opérateur conditionnel2/2

Cet opérateur permet de créer des expressions conditionnelles.

let x = Math.random ();

if (x >= 0.5)
  console.log ('vrai');
else
  console.log ('faux');

let x = Math.random ();
console.log (x >= 0.5 ? 'vrai' : 'faux');

Conditions imbriquées1/2

if (condition1)
{
  instructions1;
  if (condition2) {instructions2;}
  else            {instructions3;}
  instructions4;
}
else
{
  instructions5;
  if (condition3) {instructions6;}
  else            {instructions7;}
  instructions8;
}

Conditions imbriquées2/2

Conditions en cascade 1/2

if (condition1) {
  instructions1;
}
else
  if (condition2) {
    instructions2;
  }
  else
    if (condition3) {
      instructions3;
    }
    else {
      instructions4;
    }

Conditions en cascade 2/2

Cas multiples1/2

if (expression === valeur1)
{
  instructions1;
}
else if (expression === valeur2)
{
  instructions2;
}
// …
else
{
  instructions;
}

Cas multiples2/2

switch (expression)
{
  case valeur1 :
    instructions1; break;

  case valeur2 :
    instructions2; break;

  // …
  default :
    instructions;
}

Travaux pratiques

Boucle ?

• Répétition d'un bloc d'instructions
• Jusqu'à ce qu'une condition soit remplie
• Attention aux boucles infinies !

Boucle à pré-condition1/2

while (condition) {instructions;}

• Mot-clé while
• Condition de répétition booleénne
• Bloc d'instructions également appelé corps

Boucle à pré-condition2/2

Exercice1/2

Exercice2/2

// Tirage aléatoire.
let x = Math.random ();
// Nombre d'essais.
let n = 1;

// Tant que "x" < 0.5…
while (x < 0.5)
{
  // Nouveau tirage.
  x = Math.random ();
  // Incrémentation du compteur.
  ++n; // n = n + 1;
}

console.log (n);

Boucle à post-condition1/3

do {instructions;} while (condition);

• Mots-clés do et while
• Condition évaluée après une première itération
• Corps de la boucle exécuté au moins une fois

Boucle à post-condition2/3

Boucle à post-condition3/3

let x = 0, n = 0;

do
{
  x = Math.random ();
  ++n;
}
while (x < 0.5);

console.log (n);

Boucle à compteur1/4

for (initialisation; condition; mise_à_jour) {instructions;}

Boucle à compteur2/4

Boucle à compteur3/4

// Répéter 10 fois :
for (let i = 0; i < 10; ++i)
{
  // Afficher "bonjour !"
  console.log ('bonjour !');
}

// Répéter 10 fois :
for (let i = 0; i < 10; ++i)
{
  // Afficher le compteur.
  console.log (i);
}

Boucle à compteur4/4

// Ouverture d'un bloc
// pour limiter la portée
// de la variable
{
  // Déclaration du compteur
  let i = 0;
  // Test de la condition
  while (i < 10)
  {
    // Corps de la boucle
    console.log (i);
    // Incrémentation
    ++i;
  }
}

Itération d'un objet1/2

Accès tour à tour aux propriétés d'un objet

for (let variable in objet) {instructions;}

• La variable variable est un itérateur de l'objet objet
• Cet itérateur parcourt les propriétés de l'objet au fil d'une boucle
• Il vaut d'abord le nom de la 1^re propriété, puis celui de la seconde, etc.
• La boucle s'arrête dès que toutes les propriétés ont été parcourues

Itération d'un objet2/2

let algo =
{
  code : 'AlgoJS',
  intitule : "Algorithmique et JavaScript",
  enseignant : {prenom: 'Aassif', nom: 'Benassarou'},
  'volume-horaire' : 47
};

for (let k in algo) console.log (k, algo[k]);

code AlgoJS
intitule Algorithmique et JavaScript
enseignant { prenom: 'Aassif', nom: 'Benassarou' }
volume-horaire 47

Travaux pratiques

Fonctions

Fonction ?

Ré-utilisation du code

• Éviter la duplication du code
• Moins de code = moins de bugs
• Meilleure lisibilité

Syntaxe

function f (param1, param2, …, param)
{
  instructions;
}

• Mot-clé function suivi du nom de la fonction
• param1, param2, …, param sont les paramètres de la fonction
• Leur nombre et leurs types dépendent du seul développeur
• L'ensemble des instructions constitue le corps de la fonction

Paramètres

Un paramètre est une variable locale à la fonction.

Son nom permet de l'identifier dans le corps de la fonction.

function f (a, b)
{
  console.log ('a', a);
  console.log ('b', b);
}

Résultat

Une fonction peut retourner un résultat avec le mot-clé return.

function f (param1, param2, …, param)
{
  instructions;
  return expression;
}

Une fonction sans résultat a pour type de retour undefined.

Appel de fonction1/3

f (expr1, expr2, …, expr)

Pour invoquer une fonction, il faut lui fournir des arguments.

Cette action se nomme appel de fonction.

Les types des expressions doivent correspondre aux types attendus.

Les arguments sont alors substitués aux paramètres,
le corps de la fonction est évalué et la fonction renvoie un résultat.

Un appel de fonction est une expression
dont la valeur est égale à celle du resultat retourné.

Appel de fonction2/3

// Carré.
function f (x)
{
  return x * x;
}

f (3);     // 9
f (f (3)); // 81

Appel de fonction2/3

// Somme.
function g (x, y)
{
  return x + y;
}

g (1, 2);    // 3
g (1, '2');  // '12'
g (1, 2, 3); // 3
g (1);       // NaN

Arguments par défaut

En JavaScript, le nombre d'arguments et le nombre de paramètres peuvent différer.

Tout argument absent lors de l'appel vaut undefined.

Il est possible de spécifier une valeur par défaut pour chaque argument.

function f (param1 = v1, param2 = v2, …, param = valeur)
{
  instructions;
}

Récursivité1/2

Fonction dont le calcul nécessite d'invoquer la fonction elle-même.

// Suite de Fibonacci : 0, 1, 1, 2, 3, 5, 8, …
function f (n)
{
  return (n < 2 ? n : f (n-2) + f (n-1));
}

Récursivité2/2

function f (n)
{
  let u = 0;
  let v = 1;
  for (let i = 2; i <= n; ++i) {
    let t = u + v;
    u = v;
    v = t;
  }
  return v;
}

Modules

// Déclaration de la fonction.
function f () {console.log ("f");}
// Exportation de la fonction.
export {f};

// Importation de la fonction.
import {f} from "./fonction.mjs";
// Utilisation de la fonction.
f ();

Travaux pratiques

Tableaux

Tableau ?

Un tableau est une liste ordonnée de \(n\) valeurs.

Les valeurs contenues dans un tableau sont appelées éléments.

Généralement, ces valeurs sont toutes du même type.

Chaque élément est identifié par son indice (de \(0\) à \(n-1\)).

\[ \underbrace{ \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 0&1&2&3&4&5&6&7&8&9\\ \hline \end{array} }_{10} \]

Syntaxe1/2

En JavaScript, un tableau est un objet de classe Array

Sa taille est accessible via une propriété nommée length

Ses éléments le sont via l'opérateur []

Son initialisation s'effectue également avec des crochets
entre lesquels sont énumérés tous ses éléments.

Syntaxe2/2

> let tableau = [4, 8, 15, 16, 23, 42];

> tableau;
[ 4, 8, 15, 16, 23, 42 ]
> typeof tableau;
'object'
> tableau.length;
6
> tableau [5];
42
> typeof tableau [5];
'number'
> 

Itération d'un tableau1/2

for (let i = 0; i < tableau.length; ++i)
  console.log (i, tableau [i]);

0 4
1 8
2 15
3 16
4 23
5 42

Itération d'un tableau2/2

Accès tour à tour aux éléments d'un tableau

for (let variable in tableau) {instructions;}
for (let variable of tableau) {instructions;}

• La variable variable est un itérateur du tableau tableau
• Cet itérateur parcourt les éléments du tableau au fil d'une boucle
• Il prend d'abord pour valeur le 1^er élément, puis le second, etc.
• La boucle s'arrête dès que tous les éléments ont été parcourus

Décomposition

// Accès au premier élément.
let locke = tableau [0];
// Accès au deuxième élément.
let reyes = tableau [1];
// Accès eu troisème élément.
let ford  = tableau [2];

// Accès simultané aux trois éléments.
let [locke, reyes, ford] = tableau;

Reste1/2

> let tableau = [4, 8, 15, 16, 23, 42];

> let [locke, reyes, ...etc] = tableau;

> etc.length;
4
> etc;
[ 15, 16, 23, 42 ]
> 

Reste2/2

// Paramètres du reste.
function f (a, b, ...params)
{
  // Utilisation de "a" et "b".
  console.log (a, b);

  // Utilisation de "params".
  for (let p of params)
    console.log (p);
}

Insertion, etc.

tableau.push (expr1, expr2, …, expr);

let resultat = t1.concat (t2, t3, …, t);

Travaux pratiques

Programmation
fonctionnelle

Fonction fléchée ?

(param1, param2, …, param) => {instructions;}

• Syntaxe compacte
• Anonyme la plupart du temps
• Variable this indemne

Array.forEach1/3

Exécution d'une tâche élément par élément

tableau.forEach (variable => {instructions;});

• La méthode Array.forEach est invoquée à partir d'un objet de type Array
• Sous sa forme la plus courante, elle n'accepte qu'un seul paramètre appelé callback
• Ce callback est une fonction qui sera appelée pour chaque élément du tableau
• La signature d'un callback est imposée par la méthode qui l'accepte

Array.forEach2/3

tableau.forEach ((v, i, t) => {instructions;});

Le callback attendu doit accepter trois arguments :

Array.forEach3/3

> let tableau = [4, 8, 15, 16, 23, 42];

> let somme = 0;

> tableau.forEach (x => {somme += x;});

> somme;
108
> 

Array.map1/3

Création d'un nouveau tableau par transformations élémentaires

let destination = source.map (variable => expression);

• Le tableau destination contient autant d'éléments que le tableau source
• Les éléments de destination sont construits à partir des éléments de source
• Le callback passé en argument formalise la transformation appliquée à chaque élément

Array.map2/3

let destination = source.map ((v, i, t) => expression);

Le callback attendu doit accepter trois arguments :

Array.map3/3

> let tableau = [4, 8, 15, 16, 23, 42];

> tableau.map (x => Math.sqrt (x));
[ 2,
  2.8284271247461903,
  3.872983346207417,
  4,
  4.795831523312719,
  6.48074069840786 ]
> 

Array.filter1/3

Sous-ensemble du tableau d'origine

let destination = source.filter (predicat);

• Les éléments de source sont conservés s'ils remplissent une condition donnée
• Le prédicat passé en argument formalise la condition appliquée à chaque élément
• C'est une fonction qui retourne true pour chaque élément devant être conservé

Array.filter2/3

let destination = source.map ((v, i, t) => expression);

Le callback attendu doit accepter trois arguments :

Array.filter3/3

> let tableau = [4, 8, 15, 16, 23, 42];

> tableau.filter (x => x % 2);
[ 15, 23 ]
> 

Array.reduce1/3

Calcul d'un résultat unique construit par récurrence

let resultat = tableau.reduce (callback, accumulateur);

• Le paramètre accumulateur représente une valeur initiale
• La fonction callback sera invoquée pour chaque élément
• Ce callback retournera un nouvel accumulateur,
  calculé à partir de l'élément courant et de l'accumulateur courant
• Ce nouvel accumulateur sera utilisé, à son tour, au prochain élément

Array.reduce2/3

let resultat = tableau.reduce ((a, v, i, t) => expression, a0);

Array.reduce3/3

> let tableau = [4, 8, 15, 16, 23, 42];

> tableau.reduce ((somme, x) => somme + x, 0);
108
> 

Travaux pratiques