ENSPY

 Humanités numériques (ING & SI) Niveau 1

 Art numériques (ING & SI) Niveau 1

Algorithmique

Enseignante : Mme NINKO Lidwine

Objectif du cours :

 Notions de base en algorithmique

 Types de données
 Notion de sous-programmes
 Nommage des variables, assertions, documentation …
 Structures algorithmiques fondamentales
 Algorithmes fondamentaux de recherche d’un élément, parcours, tri, …

Plan du cours

Chapitre 1 Notions et démarche algorithmique

Chapitre 2 Les structures algorithmiques

Chapitre 3 Les sous-programmes

Chapitre 4 Structure de données : les Tableaux

Chapitre 5 Structure de données : Les Enregistrements

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Chapitre 1 Notion et démarche algorithmique

1.1.Définitions
Un algorithme est la composition d'un ensemble fini d'étapes, chaque étape étant formée d'un
nombre fini d'opérations dont chacune est :
 Définie de façon rigoureuse et non ambiguë ;
 Effective (signifie pouvant être réalisée en un temps fini).
Un algorithme prend des données en entrée, exprime un traitement particulier et fournit des
données en sortie. Il est écrit dans un langage compréhensible par l’être humain. Le domaine
qui étudie les algorithmes est appelé algorithmique.

Un bon algorithme doit être :

 Correct : signifie pour chaque instance du problème, il se termine en produisant la
bonne sortie, c’est-à-dire il résout le problème posé.
 Efficace : mesure de la durée que met un algorithme pour produire un résultat.
Une instruction est une action élémentaire commandant à la machine un calcul ou une
communication avec un de ses périphériques (entrant ou sortant).
Une instruction de base peut être une affectation, une opération, un affichage à l’écran ou une
lecture à partir du clavier ou d’un fichier.

[Link] un cours d’algorithmique ?

Réponse : pour obtenir de la « machine » qu’elle effectue un travail à notre place

Problème : expliquer à la « machine » comment elle doit s'y prendre

Besoins :
o Savoir expliciter son raisonnement
o Savoir formaliser son raisonnement
o Concevoir (et écrire) des algorithmes : Séquence d’instructions qui décrit comment
résoudre un problème particulier

[Link]ésentation d’un algorithme

Un algorithme est généralement exprimé dans un langage informel, ou incomplètement
formalisé : texte libre (signifie description des différentes étapes en français), organigramme
(diagramme représentant les étapes), pseudo-code (version simplifiée d’un langage
informatique) ou autres. Par opposition, une démonstration mathématique ou un programme
informatique est exprimé en utilisant des langages formels. Cela signifie donc que l’écriture
d’un algorithme est souple, elle vise à exprimer une méthode de résolution de façon
compréhensible à un être humain. Mais pour la même raison, un algorithme ne peut pas être
traité directement par un ordinateur : il doit être formalisé, signifie transformé en un
programme.

On peut considérer un programme comme la traduction d’un algorithme dans un langage de

programmation, signifie un langage formel compréhensible par un ordinateur. On dit alors que
ce programme est l’implémentation de cet algorithme.

Dans ce cours, nous allons écrire des pseudo-codes.

2

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
[Link] problèmes fondamentaux de l’algorithmique
Complexité
 En combien de temps un algorithme va -t-il atteindre le résultat escompté ?
 De quel espace a-t-il besoin ?

Calculabilité :
 Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?
 Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?

Correction
 Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ?

[Link] bases du langage algorithmique

1.5.1. Les identificateurs

Un identificateur est une suite de lettres et chiffres contigus, dont le premier commence
nécessairement par une lettre. Le caractère _ (appelé « blanc souligné ») est considéré comme
une lettre ; il peut donc figurer à n'importe quelle place dans un identificateur.
1.5.2. Les commentaires
Afin de permettre une plus grande visibilité dans l’algorithme, il faudrait utiliser des
commentaires délimités par les sigles /*commentaires*/ si le commentaire s’étend sur plusieurs
lignes. Un commentaire sur une seule ligne est précédé de //

1.5.3. Les types de données

On distingue en général les données dites scalaires (constituées d’un seul élément) des données
structurées (vecteurs, tableaux...).

Les données scalaires

On parle aussi de données élémentaires. Elles sont constituées d’un unique élément. On
distingue cinq types :
 Le type entier
 Le type réel
 Le type caractère : lettres, chiffres, ponctuation…
 Le type chaine de caractères. Une chaîne de caractères est notée entre double cotes
(exemple "ceci est une chaîne de caractères").
 Le type booléen. Un booléen permet de symboliser les valeurs logiques VRAI et
FAUX.
Opérateurs de calcul disponibles pour les types de base :
 Entier : + ; – ; * ; div ; mod
 Réel : + ; – ; * ; /
 Booléen : et ; ou ; non

Opérateurs de comparaison (le résultat est un booléen) :

3

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
  Entier, réel, caractère, chaine de caractères : == ; <= ; < ; >= ; > ; !=
 Booléen : == ; !=

Exemples :
 x == y // x est égal à y
 x != y // x est différent de y
 x > y // x est plus grand que y
 x < y // x est plus petit que y
 x >= y // x est plus grand que, ou égal à y
 x <= y // x est plus petit que, ou égal à y

Les données dimensionnées

On parle aussi de données structurées.

 Type énuméré

Un type énuméré est un type permettant de représenter des objets pouvant prendre leur valeur
dans une liste finie et ordonnée de noms.

Exemple
Type jours_semaine = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) ;
Type maladies_infantiles= (varicelle, rougeole, tuberculose, poliomyelite, tetanos, diphterie) ;

 Type intervalle

Un type intervalle est un type dont les objets prennent leur valeur dans une portion de
l’intervalle des valeurs d’un autre type (entier, énuméré ou caractère).

Exemple
Type nombre = 0..99 ;
Type maladies = varicelle..diphterie;

 Type tableau
Un tableau est un ensemble d’éléments scalaires de même type, organisés suivant des colonnes
et des lignes.

 Type enregistrement
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é.

 Type pointeur
Un pointeur est un objet qui contient l’adresse mémoire d’une donnée ou d’une fonction.

 Type fichier
Un fichier est une collection homogène de données, ordonnée et de taille dynamique.

1.5.4. La déclaration
4

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
En informatique, la déclaration indique la partie de l’algorithme où on annonce que l’on va
utiliser un identificateur de variable.
1.5.5. Les instructions de base
a) L’affectation
Cette instruction permet d’attribuer une valeur à une variable.
La syntaxe est la suivante :
Identificateur de la variable  valeur à affecter ;

Exemple :
c256 ; //se lit c reçoit 256
s  s1+s2 ; //se lit s reçoit la valeur de la somme s1+s2

b) L’affichage ou écriture des données

Cette instruction permet d’afficher un résultat à l’écran. Elle permet de visualiser des données
placées en mémoire.
La syntaxe est la suivante :
Ecrire (‘‘message à afficher à l’écran’’) ; ou Afficher (‘‘message à afficher à l’écran’’) ;
Ecrire (identificateur de la variable) ; ou Afficher (identificateur de la variable) ;

Exemple :
Ecrire (‘‘Entrer le premier élément : ’’) ;
Ecrire (‘‘la surface du rectangle est :’’) ;
Ecrire (surface) ;
Ecrire (‘‘la surface du rectangle est : ’’, surface) ;

c) La lecture ou la saisie au clavier

Elle permet de placer en mémoire les informations fournies par l'utilisateur.
La syntaxe est la suivante :
Lire (identificateur de la variable) ;
Exemple : Lire(nom) ; Lire(prenom) ; Lire (a) ; Lire (a,b,c) ; Lire (cote) ; Lire (longueur) ; Lire
(largueur) ; Lire(quantite) ;

d) L’incrémentation / la décrémentation
L’incrémentation consiste à augmenter la valeur d’une variable tandis que la décrémentation
consiste à diminuer la valeur d’une variable.
La syntaxe de l’incrémentation est la suivante :
identificateur de la variable  identificateur de la variable + valeur à ajouter ;

La syntaxe de la décrémentation est la suivante :

identificateur de la variable  identificateur de la variable - valeur à réduire ;

NB : il faut noter que la décrémentation et l’incrémentation modifient la valeur de la variable

initiale.

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Exemple : compteur  compteur +1 ; (incrémentation)
Pas  Pas – 2 ; (décrémentation)

[Link] étapes de résolution d’un problème

Face à un problème quelconque, nous devons nous poser au préalable un certain nombre de
questions. La réponse à ces questions facilitera la résolution du problème c'est-à-dire aboutir à
un résultat. Les étapes de résolution d’un problème sont les suivantes :
 Comprendre l’énoncé du problème
 Décomposer le problème en sous-problèmes plus simples à résoudre
 Associer à chaque sous problème, une spécification :
o Les données nécessaires
o Les données résultantes
o La démarche à suivre pour arriver au résultat en partant d’un ensemble de données.
 Elaboration d'un algorithme.

1.7. Le formalisme général d’un algorithme

Un algorithme est écrit en utilisant un Langage de Description d’Algorithme (LDA).

L’algorithme ne doit pas être confondu avec le langage proprement dit. Il comprend les parties
suivantes :
 En-tête : nom de l’algorithme
 Déclarations des constantes, des types et des variables.
 Déclarations des fonctions, procédures
 Corps de l’algorithme : il est constitué des actions du traitement. Il est délimité par les
termes Début et Fin.

1.7.1. L’entête

Il permet tout simplement d’identifier l’algorithme. La syntaxe est la suivante :

Algorithme <nom de l’algorithme> ;
Exemple d’entête : Algorithme calcul_surface;
Autres exemples Algorithme Calcul_notes_etudiant ; Algorithme somme_reel ;

1.7.2. Déclaration des constantes, types, variables

La déclaration : c’est une liste exhaustive des objets, grandeurs utilisés et manipulés dans le
corps de l’algorithme. Cette liste est placée en début d’algorithme.

a) Déclaration des constantes

Les constantes représentent des objets (nombre, caractères, …) dont la valeur ne peut pas être
modifiée pendant l’exécution de l’algorithme.

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Le mot clé est const ou constante.
La syntaxe est la suivante : const <Nom de la constante> = Valeur ;

Exemple : const PI = 3.14 ;

const MAX = 1000 ;
const TVA = 0.1925 ;

b) Déclaration des types

C’est dans cette section qu’on fait la déclaration des types structurés ou dimensionnés. Exemple
de types structurés : les tableaux, les enregistrements.
Pour créer des enregistrements, il faut déclarer un nouveau type, basé sur d'autres types
existants, qu'on appelle type structuré. Après avoir défini un type structuré, on peut l'utiliser
comme un type normal en déclarant une ou plusieurs variables de ce type.

c) Déclaration des variables

Elles représentent les objets (des nombres, des caractères, des chaînes de caractères, des
booléennes ; …) dont la valeur peut être modifiée au cours de l’exécution de l’algorithme. Cette
instruction permettant de réserver de l’espace mémoire pour stocker des données. Elle dépend
du type des données : entier, réel, caractère, chaine de caractères, tableau, etc.

Le mot clé permettant d’effectuer la déclaration d’une variable est Var ou Variable. La syntaxe
est la suivante :
Var <Nom de la variable> : Type de la variable ;

Exemples : Var s : réel ;

Var j : entier ;
Var c : caractère ;
Var trouve : booléen ;
Var longueur : réel ;
Var largeur : réel ;
Var nom, prenom : chaine de caractères ;

Noms de variables
 Un nom de variable est une séquence de lettres (a → z, A → Z) et de chiffres (0 → 9),
qui doit toujours commencer par une lettre.
 Seules les lettres ordinaires sont autorisées. Les cédilles, les espaces, les caractères
spéciaux tels que $, #, @, etc. sont interdits, à l'exception du caractère _ (souligné).

1.7.3. Déclaration des fonctions, procédures

a) Déclaration de la fonction
Une fonction est un bloc d’instructions nommée et paramétrée, réalisant une certaine tâche. Elle
admet zéro, un ou plusieurs paramètres et renvoie toujours un résultat. La syntaxe de déclaration
d’une fonction est la suivante :
Fonction nom_fonction (parametre1 : type,…, parametren : type): type valeur ;

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Début
….
nom_fonction  …
Retourner (nom_fonction) ;
FinFonction ;

Exemple : Ecrire une fonction qui calcule la moyenne de trois notes.

Fonction moyenne (note1 : réel, note2 : réel, note3 : réel) : réel ;

Début
moyenne  (note1 + note2 + note3) / 3 ;
retourner (moyenne) ;
FinFonction ;

b) Déclaration de la procédure

Tout comme une fonction, une procédure est un ensemble d’ordre accomplissant une tâche
particulière. Elle peut être utilisée pour calculer zéro ou plusieurs résultats.
La syntaxe de déclaration d’une procédure est la suivante :
Procédure nom_procédure (parametre1 : type, …, parametren : type) ;
Début
…

FinProcédure ;
Exemple :

Procédure moyenne2 (note1 : entier, note2 : entier, note3 : entier, var moy : réel) ;
Début
moy  (note1 + note2 + note3) / 3 ;
FinProcédure

1.8. Langage algorithmique

Algorithme NomAlgorithme ;
/*Ceci est un commentaire*/
/*déclaration de constante*/
/*déclaration de types*/
/*déclaration de variables*/
/*déclaration de procédures, fonctions*/

Début
Instruction1 ;
.
.
Instructionn ;
Fin

 Il faut avoir une écriture rigoureuse

 Il faut avoir une écriture soignée
8

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
  Il est nécessaire de commenter les algorithmes
 Il existe plusieurs solutions algorithmiques à un problème posé : il faut rechercher
l’efficacité de ce que l’on écrit

NB : L’écriture algorithmique est un travail de programmation à visée universelle : un

algorithme ne dépend pas du langage dans lequel il est implémenté, ni de la machine qui
exécutera le programme correspondant.

1.9. Phase d’analyse

Elle consiste à extraire de l’énoncé du problème des éléments de modélisation.

Technique : Distinguer en soulignant de différentes couleurs :

 Quel est le but de l’algorithme (traitement à réaliser)
 Quelles sont les données en entrée du problème
 Où vont se situer les résultats en sortie

Exemple d’énoncé d’un problème

Soit la longueur et la largeur d’un rectangle. Ecrire un algorithme qui permet de calculer son
périmètre.

Analyse du problème

Soit la longueur et la largeur d’un rectangle. Ecrire un algorithme qui permet de calculer son
périmètre.

Analyse du problème

But de l’algorithme : calculer la surface d’un cercle connaissant son diamètre

Données en entrée : longueur, largeur

Données en sortie : périmètre

Pseudo code

Algorithme calcul_perimetre_rectangle ;
var perimetre, longueur, largeur : réel ;
Début
Ecrire(‘‘Entrer la longueur du rectangle’’) ;
Lire(longueur) ;
Ecrire(‘‘Entrer la largeur du rectangle’’) ;
Lire(largeur) ;
perimetre(longueur + largeur)*2 ;
Ecrire(‘‘Le périmètre du rectangle est :’’, perimetre) ;
Fin

Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine