Première NSI Algorithmes et programmation
french
Algorithmes et programmation
I. Introduction
1. Définitions
Définition :
Un algorithme est un ensemble ordonné d’instructions élémentaires dont l’application permet de résoudre un pro-
blème.
Un algorithme
— permet de résoudre un problème défini sur un ensemble fini de données.
— est constitué d’opérations élémentaires : arithmétiques, logiques, transfert de données, comparaisons . . .
— est organisé selon des règles précises
— retourne une réponse après un nombre fini d’étapes.
Les algorithmes sont déterministes : même résultat sur les mêmes données.
2. Un exemple d’algorithme
Cet algorithme possède bien un nombre fini d’étapes. De plus, l’ordre des étapes est important : on ne peut pas monter
les blancs en neige avant de séparer les blancs des jaunes. À la fin de l’exécution de cet algorithme, le problème initial
Loread Page 1/7
Première NSI Algorithmes et programmation
a été résolu : préparer un tiramisu. Cependant, pour un même problème, il peut exister plusieurs algorithmes différents.
Par exemple, on peut changer le nombre d’étapes ou bien l’ordre et quand même arriver à résoudre le même problème.
3. De l’algorithme au programme
Un programme est la traduction d’un algorithme dans un langage de programmation « compréhensible » par une machine,
un ordinateur. Il existe plusieurs langages de programmation : Pyhton, Scilab, C++, etc.
Les étapes de mise en œuvre d’un programme sont :
1. Comprendre le problème
2. Concevoir l’algorithme
3. Coder l’algorithme (traduire l’algorithme en langage de programmation)
4. Éditer le programme (Saisir le programme sur ordinateur)
5. Compiler le programme
6. Exécuter le programme
7. Vérifier et valider le programme avec un jeu de tests.
II. Les composantes d’un algorithme
Un exemple :
1. Les données
1.1. Données en mémoire
Une donnée est un morceau de programme qui contient de l’information, qui peut être un entier, un flottant, une expression
. . . etc. Elle est située à un certain emplacement en mémoire, ayant une adresse : une référence.
La mémoire : c’est l’espace où les données sont stockées pour l’utilisation par l’algorithme. La mémoire est comme un
ensemble de boites, chaque boite contient une donnée et dispose d’un numéro.
Loread Page 2/7
Première NSI Algorithmes et programmation
Pour accéder à une donnée, on indique la boite où se trouve la donnée.
Pour stocker une donnée, on indique la boite où mettre la valeur à stocker.
1.2. Données : variables et constantes
Afin de faciliter l’accès aux données en mémoire, on utilise des symboles qui identifient de façon abstraite et unique un
emplacement précis. Ces symboles sont appelés variables en langage algorithmique.
Lorsque le contenu d’une variable (c-à-d un emplacement) ne doit pas être modifié par l’algorithme, on dit que cette
variable est une constante. Une variable possède :
• Un nom : on parle de l’identifiant.
• Un type qui caractérise l’ensemble des valeurs que peut prendre la variable.
• Une valeur
On déclare une variable en lui donnant un nom et un type. Le nom est composé de lettres et de chiffres, il doit commencer
par une lettre et ne contient pas de signe de ponctuation ni d’espace.
1.3. Notion de type
La forme du contenu d’une variable est définie par le type. A toute variable est associé obligatoirement un type.
Un type permet de définir :
• l’ensemble des valeurs possibles de la variable
• l’ensemble des opérations possibles applicables à la variable
• la forme de codage de la donnée dans la machine.
Exemples de type : booléen (V ou F), entier, réel, caractère, chaine, etc.
Lorsqu’un type de données est associé à une variable, celle-ci ne peut plus en changer et son contenu doit obligatoirement
être du même type.
2. Les instructions
Les instructions d’un algorithme sont exécutées dans l’ordre une à la suite de l’autre, en séquence. On ne peut pas
arbitrairement changer cette séquence.
Exemple :
Mettre les chaussettes puis les chaussures
N’EST PAS ÉQUIVALENT À
Mettre les chaussures puis les chaussettes.
2.1. Affectation d’une variable
L’affectation c’est l’opération qui permet d’associer une valeur à une variable. La valeur peut être une constante, une
valeur d’une autre variable, ou un résultat calculé.
Syntaxe : nom_var ←− valeur (le membre de gauche reçoit le membre de droite).
Exemple 1 :
Déclaration Note1, Note2 : réel
Moyenne : réel
Affectation Note1 ←− 12
Note2 ←− 14
Moyenne ←− (Note1 + Note2)/2
En Python l’opérateur d’affectation d’une valeur à une variable est le signe égal : « = ».
x = 2 se lit : 2 est affecté à x. On dit que x référence l’objet 2.
Cette instruction produit les effets suivants :
— le nom de variable x est créé et stocké dans l’espace mémoire nom, elle est déclarée ;
— la valeur 2, un entier en l’occurrence, est créée et stockée dans une autre zone de la mémoire ;
— un type a été attribué à x. En Python c’est le type int (integer) car la valeur est un entier ;
Loread Page 3/7
Première NSI Algorithmes et programmation
— un lien est créé, faisant pointer x vers 2.
Une affectation n’est pas définitive, la dernière effectuée rompt le lien de l’ancienne et en établit un nouveau. Dit rapide-
ment, la nouvelle écrase l’ancienne, comme cela est le cas pour a dans l’exemple ci-dessous :
Exemple (en Python)
>>> a = 5 # a pointe vers la valeur 5
>>> b = a # b pointe aussi vers 5
>>> a = 4 # a pointe vers une nouvelle valeur : 4
>>> b
5 # b reste pointé sur 5
Examinons les lignes 1 et 2 de l’exemple.
Leur effet est illustré par la figure ci-contre :
a pointe vers 5 et b pointe aussi vers 5, et non vers a.
À présent réaffectons a grâce à la ligne 3. L’ancien objet vers
lequel pointait a, en l’occurrence 5, ne peut pas être modifié
puisqu’il est immuable. Donc cette nouvelle affectation rompt
l’ancien lien et en établit un autre vers l’objet 4 nouvellement
créé. La ligne 4 le confirme : b a conservé sa première valeur
bien que a ait changé d’assignation.
2.2. Entrées et sorties d’un algorithme
Échange d’informations entre l’algorithme et l’utilisateur, via les périphériques externes (clavier, écran, souris, disque, . . .)
Notations :
Entrée : lire(x) # lecture de la variable x au clavier
Sortie : écrire(x) ou afficher(x) # écriture de la valeur de la variable x vers l’écran par exemple.
En Python :
Entrée Sortie
>>> x = 10
>>> x = input ( " Saisir la valeur de x : " )
>>> print ( x ) # on affiche la valeur de x
Saisir la valeur de x : # Python est en attente
10
3. Structure globale d’un algorithme
La structure globale d’un algorithme est :
• Déclaration des variables et des constantes
• Lecture des données
• Écriture des instructions
• Affichage des résultats
Algorithme Nom_algorithme Entête Exemple : Calcul de la moyenne de deux notes
Algorithme Calcul_moyenne
Déclarations des Var note1, note2, moyenne : réel
Const : [Constantes]
constantes et des Début
Var : [Variables ] Écrire("Donner la première note : ")
variables Lire note1
Début Écrire("Donner la deuxième note : ")
Lire note2
[Instructions] Traitements
moyenne ←− (note1+note2)/2
Fin Ecrire("La moyenne est : ",moyenne)
Fin
Loread Page 4/7
Première NSI Algorithmes et programmation
III. Structures fondamentales
1. Les instructions conditionnelles
Elles permettent d’exécuter des instructions uniquement si certaines conditions sont réalisées. Ce sont des aiguillages qui
commandent l’exécution ou la non-exécution de séquences d’instructions, des embranchements.
Syntaxe :
Forme simple Exemple En Python
if X > 0 :
print (X , " est positif " )
Début Début
Si condition alors Si (X>0) alors
bloc d’instructions écrire (X, "est positif") Les blocs sont indentés et précédés de
Fin Si Fin Si « : » et la fin de l’indentation marque
Fin Fin la fin de la structure
Remarque : La condition est une expression de type booléen construite en général avec les comparateurs <, =, >, . . . et
les opérateurs logiques ET, OU, NON.
Forme complète Exemple En Python
Début Début
Si condition alors Si (X<Y) alors
bloc 1 d’instructions Min ←− X
if X < Y :
Sinon Sinon Min = X
bloc 2 d’instructions Min ←− Y else :
Fin Si Fin Si Min = Y
Fin Fin
2. Les instructions itératives
2.1. La boucle bornée ou la boucle Pour
Les boucles Pour sont des blocs d’instructions qui sont répétées un nombre de fois déterminé.
Syntaxe :
Début
Pour indice allant de n1 à n2 faire
bloc d’instructions
Fin Pour
Fin
Exemple : Calcul de la somme des 10 premiers entiers naturels.
En pseudo-code En Python
resultat = 0
Algorithme Somme_10 for i in range (1 , 11 ) :
Var i, resultat : entiers resultat = resultat + i
print ( " La somme de 1 à 10 est : " , resultat )
Début
resultat ←− 0
Pour i allant de 1 à 10 faire L’instruction for i in range(1,11) fait parcourir à la variable
i tous les entiers de 1 à 10.
resultat ←− resultat+i
Les deux points « : » marquent le début du bloc d’instruc-
Fin Pour tions de la boucle for. Il n’y a pas d’instruction de fin de
écrire ("La somme de 1 à 10 est : ",resultat) boucle for, c’est l’indentation qui indique les instructions
Fin faisant partie de la boucle.
Quelques règles d’usage :
— Les bornes ne doivent pas être modifiées au cours de l’évaluation de la boucle.
— Le compteur ne doit pas changer dans le corps de la boucle.
— On utilise la boucle Pour lorsqu’on connait exactement le nombre d’itérations.
Loread Page 5/7
Première NSI Algorithmes et programmation
Remarque : boucles « POUR » imbriquées : on parle de boucles imbriquées dès qu’une boucle est incluse dans le corps
d’une autre.
2.2. La boucle non bornée ou la boucle Tant que
Les boucles Tant que sont des blocs d’instructions dont les itérations se poursuivent tant qu’une certaine condition est
réalisée. Ce sont des boucles conditionnelles. Le nombre d’itérations peut être indéterminé.
Syntaxe :
Début
Tant que condition faire
bloc d’instructions
Fin Tant que
Fin
Exemple : Calcul de 7! = 1 × 2 × 3 × 4 × 5 × 6 × 7 (lire factorielle 7).
En pseudo-code En Python
Algorithme Fact_7 i = 1
Var i, resultat : entiers resultat = 1
Début while i < = 7 :
i ←− 1 resultat = resultat * i
i=i+1
resultat ←− 1 print ( " Le résultat est : " , resultat )
Tant que i 6 7 faire
resultat ←− resultat ×i
i ←− i + 1 Les deux points « : » marquent le début du bloc d’instruc-
Fin Tant que tions de la boucle while. Il n’y a pas d’instruction de fin de
écrire ("Le résultat est : ",resultat) boucle while, c’est l’indentation qui indique les instructions
Fin faisant partie de la boucle.
Remarque 1 : La condition est une expression de type booléen. Tant que condition est vraie, la boucle est répétée et si
elle n’est pas vérifiée, les instructions à l’intérieur de la boucle ne sont pas effectuées.
Remarque 2 : Du point de vue de la sémantique, la boucle for est un cas particulier de boucle while. On peut toujours
transformer une boucle for en boucle while mais la réciproque est fausse.
3. Les fonctions
Définition :
Une fonction est une suite d’instructions qui définissent un sous-programme et qui renvoient un résultat pouvant
être utilisé autant de fois que nécessaire dans un programme plus général.
L’un des principaux intérêts d’une fonction est d’éviter d’écrire toujours la même séquence d’instructions lorsque l’on
sait que cette séquence va servir plusieurs fois. Les fonctions permettent de gagner du temps et surtout de rendre un
programme plus lisible.
Syntaxe : on déclare une fonction de la façon suivante :
Fonction nom_de_la_fonction (paramètre(s) de la fonction) : type de la valeur retournée
Var : variable_local1 : type ; ...
Début
Instructions de la fonction
Fin
Remarques :
— On utilise une fonction en précisant son nom suivi des paramètres entre parenthèses.
— Les parenthèses sont toujours présentes même lorsqu’il n’y a pas de paramètres.
Exemple : Fonction qui renvoie le minimum entre deux valeurs
Loread Page 6/7
Première NSI Algorithmes et programmation
En pseudo-code En Python
Fonction minimum(a,b : entier ) : entier def minimum (a , b ) :
Début if a < = b :
return a
Si a 6 b alors else :
Retourner a return b
Sinon Min = minimum (4 , 15 )
Retourner b print ( " Le min entre 4 et 15 est : " , Min )
Fin
Les deux points « : » marquent le début du bloc d’instruc-
Algorithme calcul_minimum tions de la fonction. L’indentation qui indique les instruc-
Début tions faisant partie de la fonction.
Min ←− minimum(4,15)
écrire ("Le minimum entre 4 et 15 est : ",Min)
Fin
Loread Page 7/7