Initiation Algorithmique et programmation Page 1 / 32 I ...ecogest-nancy-metz.org/publications/1155.pdf · I Philippe Lacurie Séance du 8 octobre 2009 Initiation Algorithmique et

I

Philippe Lacurie Séance du 8 octobre 2009

Initiation Algorithmique et programmation pour la classe de seconde

Page 1 / 32

Sommaire 1 Introduction .......................................................................................................................... 2

1.1 Présentation .................................................................................................................. 2 1.2 Un exemple .................................................................................................................. 2 1.3 Définition ..................................................................................................................... 3 1.4 La représentation d'un algorithme ................................................................................ 4

2 Comment concevoir un algorithme ...................................................................................... 6 2.1 La méthode descendante .............................................................................................. 6 2.2 Un exemple .................................................................................................................. 6 2.3 Comment procéder ....................................................................................................... 7

3 Le langage algorithmique ..................................................................................................... 8 3.1 Les données .................................................................................................................. 8 3.2 L'organisation d'un algorithme ..................................................................................... 9 3.3 Les instructions d'entrées/sorties ................................................................................ 10 3.4 L'affectation ................................................................................................................ 11 3.5 Les structures conditionnelles .................................................................................... 11

3.5.1 La structure conditionnelle simple .................................................................... 11 3.5.2 La structure conditionnelle imbriquée ................................................................ 12

3.6 Les structures itératives .............................................................................................. 13 3.6.1 La structure itérative POUR ............................................................................... 13 3.6.2 La structure itérative REPETER ........................................................................ 14 3.6.3 La structure itérative TANT QUE ...................................................................... 15

3.7 La notion de fonction ................................................................................................. 15 3.8 Les procédures ............................................................................................................ 17 3.9 L'écriture d'un algorithme........................................................................................... 17

4 La programmation .............................................................................................................. 18 4.1 Introduction ................................................................................................................ 18 4.2 Quel langage ............................................................................................................... 18 4.3 Les langages abordés dans les manuels ou les documents officiels ........................... 19 4.4 Scratch ........................................................................................................................ 20

4.4.1 Présentation ........................................................................................................ 20 4.4.2 Les sites de référence ......................................................................................... 20 4.4.3 Installation .......................................................................................................... 20 4.4.4 L'environnement ................................................................................................. 21 4.4.5 L'écriture d'un programme ................................................................................. 22 4.4.6 Un peu de graphisme .......................................................................................... 25

4.5 Xcas ............................................................................................................................ 27 4.5.1 Présentation ........................................................................................................ 27 4.5.2 Les sites de référence ......................................................................................... 27 4.5.3 L'installation ....................................................................................................... 27 4.5.4 L'environnement ................................................................................................. 28 4.5.5 Utilisation de Xcas en programmation ............................................................... 29 4.5.6 Un exemple de programmes .............................................................................. 30

5 L'algorithmique et le programme de seconde .................................................................... 31 5.1 Les documents de référence ....................................................................................... 31

I



Page 2 / 32

1 Introduction

1.1 Présentation Ce document n'a pas pour but de faire du lecteur un spécialiste en algorithmique et programmation mais a la seule ambition d'initier à l'algorithmique à travers des exemples simples, puis d'aborder les premiers concepts de la programmation, celle-ci étant là uniquement pour montrer la mise en œuvre concrète d'un algorithme. L'algorithme est la phase initiale (mais importante) à toute programmation, que le programme soit écrit en langage évolué (Visual basic, C++, Delphi…) ou à l'aide de conditions sous Excel (ou autre). C'est en fait la phase de réflexion qui permet de solutionner un problème. L'apprentissage de l'algorithmique est un élément important qui par ailleurs permet de mieux comprendre le fonctionnement des ordinateurs, puisque ce fonctionnement est basé sur des programmes écrits à partir d'algorithmes.

1.2 Un exemple Tout comme M. Jourdain, vous pratiquez (de façon plus ou moins consciente) l'algorithmique tous les jours. Un exemple, le matin au réveil :

• Votre réveil sonne. • Vous avez différentes alternatives :

o Vous l'éteignez définitivement et vous levez (option 1) o Vous l'éteignez définitivement et vous rendormez (option 2) o Vous appuyez sur une touche pour qu'il résonne dans 5mn (option 3) o Vous le lancez de manière agressive à l'autre bout de la chambre (à priori idem

option 2)

Option 1 : Vous vous êtes levé, le traitement "réveil" est terminé Option 2 : Vous avez choisi l'option extinction définitive ou casse du réveil, le

traitement est terminé, mais vous serez en retard… Option 3 : Vous avez choisi l'option rappel dans 5 mn. A la prochaine sonnerie, vous

refaites tout le traitement "réveil" ci-dessus. A travers cet exemple simple, il est possible d'appréhender la notion d'algorithme. Tous les cas ne sont naturellement pas pris en compte, vous pourriez vous lever avant la sonnerie, ne pas avoir réglé la sonnerie… Mais ceci est une autre affaire qui ne prend pas en compte les mêmes paramètres de départ.

I



Page 3 / 32

1.3 Définition Logiciel ou programme : Un programme est une suite d'opérations écrites dans le langage de l'ordinateur et prévue pour effectuer une tache définie. Les phases d'écriture d'un programme sont :

• L'analyse du problème • L'écriture de l'algorithme ou des algorithmes correspondants • L'adaptation de l'algorithme à la machine, c'est à dire la codification dans le langage de

la machine. Ces phases peuvent se résumer au schéma suivant :

Algorithme Programmation RésultatsEnoncé duprobléme

Analyse Codification Execution

.

Algorithme D'après le schéma ci-dessus, l'algorithme est un élément primordial. C'est lui qui transcrit le problème de façon claire. C'est la phase qui précède la programmation, et donc qui se trouve à la base de tous les traitements qui vont être ensuite effectués par le programme. En entreprise, les différentes fonctions, à savoir l'analyse, la codification et les tests sont souvent réalisés par des personnes différentes. La phase analyse est souvent confiée à un chef de projet qui réalise l'interface vis à vis du client. C'est lui qui est chargé de rédiger le cahier des charges, à savoir énoncer de façon claire la demande du client, puis c'est lui qui sur la base de ce cahier des charges valide les algorithmes. C'est la phase la plus importante, et même diront certains la plus noble. En fait, un algorithme traduit en une suite d'instructions ordonnées un ensemble d'opérations à réaliser en vue de l'obtention d'un résultat. Un algorithme est indépendant de la machine sur laquelle sera réalisé le programme, et est dans une certaine mesure indépendant des langages. Un algorithme ou un programme se schématise de la façon suivante :

TraitementDonnées en

sortieDonnées en

entrées .

I



Page 4 / 32

1.4 La représentation d'un algorithme Il existe différentes façons de représenter un algorithme. Les deux représentations majeures sont la représentation graphique et la représentation textuelle. La représentation graphique est beaucoup utilisée en automatisme, et est normalisée (le GRAFCET) pour représenter des séquences d'opérations pour un automate programmable (outil utilisé en automatisme). Elle est régulièrement utilisé en informatique industrielle. Exemple d'un algorithme graphique de gestion de pesage:

Premiere pesée

Acquisition poids et noDSD

Benne existante

Stockage pesée dans labase

Fin du cycle

Oui

Oui

Choix Langue

Saisie No Camion

No camion inexistant

Saisie PTRA

Stockage dans labase REI2001

Saisie No Benneou 0 si pas de benne

Erreur appelleropérateur

Non

Table PTRA

I



Page 5 / 32

Cette représentation est néanmoins assez peu utilisée, car elle est longue à mettre en œuvre (dessins), et volumineuse dés que les traitements sont importants. C'est la raison pour laquelle on lui préfère la représentation textuelle qui a le mérite d'être assez proche à la fois de nos façons d'écrire, de penser et de la programmation qui s’en suit. Les langages de programmation sont très proches de ces structures. Exemple de représentation textuelle :

VAR A : entier % variable saisie et à tester DEBUT LIRE ( 'entrez un nombre', A) SI A >=0 ALORS ECRIRE ('le nombre saisi est >=0') SINON ECRIRE ('le nombre saisi est <0') FINSI FIN

I



Page 6 / 32

2 Comment concevoir un algorithme

2.1 La méthode descendante Une méthode couramment utilisée est la méthode descendante. Cette méthode consiste à découper un problème donné en plusieurs petits problèmes, chacun d'entre eux étant alors plus facile à résoudre. Chaque problème élémentaire identifié fait partie d'un traitement donné, ce traitement étant parfaitement identifié.

2.2 Un exemple Pour illustrer cette méthode, je vais repartir d'un exemple d'un de mes professeurs de l'IUFM: Comment construire un bonhomme de neige ? Tout un chacun a dans sa vie réalisé un bonhomme de neige, mais là également, tout le monde n'a pas la même démarche. Une démarche peut être :

1) Faire le corps 2) Faire la tête 3) Poser la tête sur le corps 4) Trouver les accessoires (chapeau, écharpe, 2 cailloux (pour les yeux), carotte, pipe, balai) 5) Placer les accessoires

• Les points 3 et 4 sont des actions élémentaires qui à priori ne sont plus décomposables. • Les points 1 et 2 sont décomposables, et ont des similitudes puisque dans les 2 cas, il

s'agit de faire une boule mais de taille différente. • Pour faire une boule, la décomposition pourrait être :

o prendre de la neige dans ses mains o La serrer entre ses 2 mains afin d'en faire une boule compacte o La rouler dans la neige jusqu'à avoir la taille désirée (la taille est ici un élément

important) • De même pour placer les accessoires, tous les accessoires ne se placent pas de la même

façon. Il paraît donc important de décomposer cette action en plusieurs : o Enrouler l'écharpe entre le corps et la tête o Planter les cailloux au bon emplacement o Planter la carotte pour le nez o Planter le balai o Planter la pipe o Mettre le chapeau sur la tête

• Et pour poursuivre cette décomposition, si les opérations planter et mettre peuvent

sembler des opérations simples (action et lieu), enrouler peut être décomposée en plusieurs actions élémentaires.

Cet exemple emprunté à la vie courante montre une démarche de décomposition, laquelle peut être discutable puisque tout le monde ne procède pas de la même façon. Le bonhomme de

I



Page 7 / 32

neige pourrait par exemple être sculpté dans de la neige. Néanmoins, les objets manipulés à quelques exceptions prés restent les mêmes… Il n'y a donc pas qu'un algorithme possible pour arriver à la solution finale, et la décomposition d'un problème peut prendre des formes diverses en fonction du concepteur.

2.3 Comment procéder A la vue de ce qui précède, il semble important d'identifier 2 grands éléments qui sont :

• Les données manipulées • Les traitements à effectuer

Chaque traitement devra autant que faire se peut être découpé en action élémentaire. Dans la suite de ce document, nous verrons d'une part les données, et d'autre part la majorité des structures algorithmique, ce qui apportera un éclairage nouveau à la conception d'un algorithme.

I



Page 8 / 32

3 Le langage algorithmique Attention, il n'y a pas de norme pour représenter un algorithme, mais plutôt des habitudes qui sont globalement reconnues par beaucoup de professionnels et d'enseignants. L'important dans un algorithme, c'est essentiellement la précision du traitement, et la gestion des informations en entrée et en sortie. J'insiste sur le fait qu'un algorithme n'est pas un programme. Nous étudierons ci-après uniquement l'algorithme textuel. Afin de mettre en œuvre une pratique simple, nous utiliserons une démarche descendante, c'est à dire qui part des données pour arriver au résultat. La démarche s'appuiera donc sur :

• La détermination des données utiles pour résoudre le problème • Le détail de chaque étape permettant d'arriver au résultat.

Attention, dans ce qui suit les éléments écrits entre crochets sont facultatifs

3.1 Les données Les données comprennent l'ensemble des informations qui vont être manipulées :

o Celles fournies en entrée o Celles nécessaires au fonctionnement de l'algorithme o Celles fournies en sortie (le ou les résultat(s))

Les données sont de deux types, à savoir des variables ou des constantes.

o Les constantes font références à une valeur fixe qui sera la même pendant tout le traitement. Une constante ne peut être modifiée par le programme

o Les variables représentent des données dont la valeur change au cours du traitement.

La déclaration de ces données La syntaxe utilisée est :

nom : type [= valeur] % commentaire

Il est également possible de déclarer des valeurs du même type sur une même ligne Exemples :

Tva : reel = 19.6 % taux de tva Qte : entier % quantité saisie Prix : reel % prix HT saisi Res : réel % résultat A, B : reel % Variables de travail

De même afin que la déclaration des données soit plus claire, il est possible d'utiliser des mots clés :

CONST Tva : reel = 19.6 % taux de tva

I



Page 9 / 32

VAR

Qte : entier % quantité saisie Prix : decimal % prix HT saisi Res : réel % résultat A, B : reel % Variables de travail

Les commentaires sont, bien sur, facultatifs mais aident à comprendre le sens de chacune des données. Il est important qu' un algorithme soit lisible par tout le monde. Les données étant un élément essentiel, en préciser le sens apporte un éclairage supplémentaire. Les données peuvent être de types constantes (des valeurs qui ne changent pas dans le programme) ou variables (qui seront manipulées et modifiées par le programme) Le nommage de ces données Attention, il est important d'observer certaines règles dans le nom de ces données afin que l'algorithme soit facilement transposable en programme, à savoir :

o Le nom donné est explicite. Il faut éviter les variables de nom : toto, titi … o Le nom ne comporte ni espace, ni caractère spéciaux, ni accent o La premiére lettre est en majuscule, le reste en minuscule

Tous ces éléments ne sont que des conventions. Les types de données

Type Exemple Numérique Entier 125 200 0 -10

Réel 12.5 3.14159 -27.365 Caractère 'A' 'B' '0' Chaîne de caractère 'bonjour' 'il est 9 heures' Booléen vrai faux D'autres types existent, mais ne seront pas vu ici. Attention, un caractère ou une chaîne de caractère est encadrée de guillemets. Le séparateur décimal est le point.

3.2 L'organisation d'un algorithme Suite à la déclaration des données, va commencer le traitement proprement dit. Ce traitement est constitué d'une suite d'instructions s'exécutant de façon ordonnée. Ce traitement afin qu'il soit mis en valeur est encadré par les mots clés DEBUT et FIN. De même que pour la déclaration des données, il est possible d'insérer des commentaires afin de donner des précisions sur certains traitements. Ces commentaires sont précédés du signe %.

I



Page 10 / 32

Syntaxe : DEBUT

Instruction 1 Instruction 2 … Instruction n % Ceci est la dernière instruction

FIN Les instructions sont illustrés par les différents éléments que nous allons voir ci-après.

3.3 Les instructions d'entrées/sorties L'instruction d'entrée Un périphérique d'entrée est un dispositif permettant de faire "rentrer" des informations à l'intérieur d'un ordinateur. Les périphériques d'entrée sont le clavier, la souris, le disque dur, un CD (DVD) rom… Acquérir une information en entrée consiste à prendre l'information sur ce périphérique. Il est donc important de préciser ce périphérique quand cela est nécessaire. Par défaut, le clavier est utilisé, mais ce pourrait être un clic de souris, ou un fichier sur le disque dur. Syntaxe : LIRE ([nom du périphérique,] nom variable1 [, nom variable2, …] Ici, seules les données acquises au clavier seront traitées Exemples : LIRE (x) % la donnée saisie au clavier est stockée dans la variable x % Saisie au clavier de 2 données successives qui seront stockées dans les variables Qte et Prix LIRE (Qte, Prix) Le mot clé LIRE en fonction du besoin pourrait être remplacé par un autre mot plus significatif (ATTENDRE (souris, double-clic)), SAISIR_CLAVIER, ENTRER … Souvent, par simplification, un texte est associé pour poser une question avant la saisie LIRE ('entrez la quantité', Qte) L'instruction de sortie De même que précédemment, l'instruction de sortie est liée à un périphérique de sortie (écran, imprimante, disque dur …) Sortir une information consiste à l'envoyer sur le périphérique de sortie. Par défaut, l'écran est utilisé. C'est le seul périphérique de sortie qui sera utilisé ici. Syntaxe : ECRIRE ([nom du périphérique,] nom variable1 [, nom variable2, …]

I



Page 11 / 32

Exemples : ECRIRE (x) % le contenu de la variable x est ECRIRE ('bonjour') % Le mot bonjour est affiché % Le contenu de la variable x est visualisé suite au mot bonjour ECRIRE ('bonjour Monsieur' , x)

3.4 L'affectation Cette instruction représentée classiquement par une flèche (� ) consiste à affecter une valeur à une variable. Cette valeur peut être une valeur exacte, provenir d'une autre variable ou être le résultat d'une expression entre valeurs et/ou variables. Il est possible surtout en phase d’initiation d’utiliser des verbes, voire le signe = en lieu et place de la flèche Syntaxe : Nom variable � expression ou valeur Exemples :

Qte � 10 Nom� 'Dupont' PrixTTC � PrixHT * 1.196 TotalTTC � PrixTTC * Qte Ok � Vrai % la variable booléenne Ok reçoit la valeur vrai.

Une expression est un ensemble d'opérations effectuées sur des variables et/ou des valeurs. Les opérations possibles sont toutes celles de l’arithmétique (adition, multiplication, soustraction …), la priorité des opérations devant être prises en compte. En cas de doute, il est possible d'utiliser des parenthèses. Il est également possible d'utiliser des fonctions RACINE, trigonométriques, ENT (partie entiére) ou DEC (partie décimale)…. x � RACINE (y) % mets dans x la racine carrée de y.

3.5 Les structures conditionnelles

3.5.1 La structure conditionnelle simple Cette structure permet de réaliser un traitement soumis à l'évaluation d'un ou de plusieurs critères. Dans ce type de structure, toutes les instructions ne sont pas exécutées. Syntaxe :

SI condition ALORS Instructions alors [SINON Instructions sinon ] FINSI

• Les instructions alors ne s'exécutent que si la condition est remplie. • Les instructions sinon (facultatives) ne s'exécutent que si la condition n'est pas remplie

On peut également noter : Qte = 10 Ou Qte prend la valeur 10

I



Page 12 / 32

La condition est souvent de forme logique et compare le contenu d'une variable à une autre variable ou à une valeur. Les opérateurs pouvant être utilisés sont :

Signe Opération = comparaison > supérieur < inférieur >= supérieur ou égal <= inférieur ou égal <> ou != différent

Exemple :

Saisie d’un nombre. S'il est positif ou nul, on affiche >=0 S'il est négatif, on affiche <0

VAR A : entier % variable saisie et à tester DEBUT LIRE ( 'Entrez un nombre', A) SI A >=0 ALORS ECRIRE ('le nombre saisi est >=0') SINON ECRIRE ('le nombre saisi est <0') FINSI FIN

3.5.2 La structure conditionnelle imbriquée Il est possible également d'imbriquer des conditions afin de réaliser des tests en cascade. En reprenant l'exemple précédent, on rajoute le test si nul.

VAR A : entier % variable saisie et à tester DEBUT LIRE ( 'entrez un nombre', A) SI A >=0 ALORS SI A = 0 ALORS ECRIRE ('Le nombre saisi est nul') SINON ECRIRE ('le nombre saisi est >0') FINSI SINON ECRIRE ('le nombre saisi est <0') FINSI FIN

I



Page 13 / 32

Attention, les structures SI imbriquées doivent également se terminer par l'instruction FINSI. Afin que l'algorithme soit lisible, il est important d'utiliser une indentation du programme.

3.6 Les structures itératives Ces structures sont également appelées répétitives. Elles permettent d'effectuer plusieurs fois un traitement. La fin du traitement étant liée à une condition. Pour mettre en œuvre ce type de structure, il est nécessaire de se poser 3 questions :

o Quelles sont les initialisations nécessaires (quelles valeurs doivent avoir mes variables)

o Quelles instructions constituent le corps de l'itération o Quelle est la condition d'arrêt

Il existe en fait trois structures itératives.

o La structure POUR s'utilise lorsque le nombre d'itération est connu au départ o La structure REPETER lorsque le nombre d'itération n''est pas connu mais au

moins supérieur à 1 o La structure TANT QUE dans les autres cas

3.6.1 La structure itérative POUR Cette structure permet de répéter un ensemble d'opérations un nombre fini de fois. Ce nombre d'itération est connu à l'avance. Syntaxe :

POUR indice DE valeur_debut A valeur_fin [PAS p] FAIRE Instructions à exécuter

FIN POUR La variable indice permet de compter les itérations. A chaque itération, cet indice est augmenté de 1 ou de la valeur du pas p s'il est spécifié. Exemple :

Affichage de la table de multiplication d'un nombre saisi au clavier. ,

VAR X : entier % Nombre dont on calcule la table de multiplication Res : entier % variable de calcul i : entier % indice DEBUT LIRE ( 'Entrez un nombre', X) ECRIRE ('Table de multiplication du nombre ' , X) POUR i DE 1 A 10 FAIRE Res � X*i ECRIRE (Res) FIN POUR FIN

I



Page 14 / 32

3.6.2 La structure itérative REPETER Cette structure est utilisée pour répéter une suite d'instruction qui doit au moins être exécutée une fois. La condition de fin de boucle est testée à la fin de chaque itération. Syntaxe :

REPETER Instructions à exécuter

JUSQU'A condition_de_fin

A la fin de chaque itération la condition est testée. Si elle est fausse, la boucle se ré-exécute. Sinon, le traitement de la boucle est fini. Exemple : On effectue la saisie de nombres que l'on additionne. Si un 0 est saisi, le traitement est terminé et le résultat affiché.

VAR X : entier % Nombre en saisie Res : entier % Résultat du calcul DEBUT Res � 0 % initialisation de Res REPETER LIRE ( 'Entrez un nombre', X) Res � Res + X JUSQU'A X = 0 ECRIRE ('Le résultat est : ' , Res) FIN

I



Page 15 / 32

3.6.3 La structure itérative TANT QUE La condition est testée avant l'exécution des instructions. Tant que la condition est réalisée, le traitement à l'intérieur du bloc est réalisé. Syntaxe :

TANT QUE condition FAIRE Instructions à faire

FINTANTQUE Attention, il est important de remarquer que le test est fait avant l'exécution, contrairement à la structure précédente. Exemple : On reprend la table de multiplication, en saisissant 2 nombres à savoir le multiplicateur et une borne de fin.

VAR X : entier % Nombre dont on calcule la table de multiplication Y : entier % borne de fin I : entier indice de calcul Res : entier % résultat DEBUT LIRE (‘Entrez le multiplicateur', X) LIRE (‘Entrez la borne de fin', Y) ECRIRE ('Table de multiplication du nombre ' , X) I � 1 TANT QUE I <= Y FAIRE Res � X*I ECRIRE (Res) I � I+1 FINTANTQUE FIN

Il ne faut faire le traitement que si la valeur saisie pour Y est valide. D'où l'importance du test avant, et donc l'utilisation de la structure TANTQUE. Si la borne de fin est saisie à 0, aucun traitement dans la boucle ne sera fait.

3.7 La notion de fonction Dans un algorithme, on peut être amené à utiliser plusieurs fois un même traitement sur des données. Plutôt que de répéter n fois ce traitement, il est plus astucieux de le regrouper, de le nommer et de l'appeler en cas de besoin. Cette méthode s'appelle créer une fonction.

I



Page 16 / 32

Syntaxe : FONCTION nom_de _la_fonction (param1 : type, …paramn : type) :type VAR …. Res : type DEBUT Instructions RETOURNER (Res) FIN

• les paramètres passés entre parenthèses correspondent aux variables sur lesquelles la

fonction va travailler. • Le type en fin de déclaration de la fonction correspond au type de la valeur retournée,

ici Res • L'instruction RETOURNER est utilisée pour renvoyer la valeur finale. • Une fonction peut retourner plusieurs valeurs, mais ce n'est plus dans notre programme.

(Nous verrons néanmoins ensuite la notion de procédure) • Les variables déclarées dans la fonction sont locales à cette fonction et ne sont pas

connues de l'algorithme principal. Dans l'écriture d'un algorithme, les fonctions sont déclarées avant le corps principal de celui-ci. Exemple Ecrire la fonction qui élève à la puissance y un nombre x passé.

FONCTION Puissance (x:reel, y:entier ) : reel VAR i:entier % indice de boucle Res : reel % résultat du calcul DEBUT Res � 1 % init du résultat POUR i de 1 A y FAIRE Res � Res * x FIN POUR RETOURNER (Res) FIN

Appel de la fonction dans le corps principal de l'algorithme :

VAR Nb : reel % Nombre dont on calcule la puissance FPui : entier % facteur de puissance Val : reel % résultat DEBUT LIRE ( 'Entrez le Nombre ', Nb) LIRE ( 'Entrez le Facteur', Fpui) Val � PUISSANCE (Nb, Fpui) ECRIRE ('le résultat est : ',Val) FIN

I



Page 17 / 32

3.8 Les procédures Dans une premiére approche, il est possible d'assimiler les procédures à des fonctions. La différence majeure vue coté utilisateur est qu'une procédure ne renvoie pas de valeurs, ou tout au moins, si des informations sont retournées, elles le sont en mettant à jour les variables du programme appelant. Une procédure peut être assimilée à une partie de code séparée du programme principal, qui peut prendre des paramètres en entrée et réalise un traitement. L'utilisation d'une procédure permet d'isoler une partie du traitement du programme principal, et rend donc celui-ci plus lisible. C'est également ce que l'on appelle la modularité qui est importante en programmation. Cette partie sortant du cadre de ce cours, je ne développerai pas plus cette notion.

3.9 L'écriture d'un algorithme Il existe de nombreux logiciels permettant d'écrire, voire de mettre au point des algorithmes :

• Le logiciel ExecAlgo : http://www.maths.ac-aix-marseille.fr/spip/IMG/zip/Execalgo.exe.zip

• AlgoBox : http://www.xm1math.net/algobox/ Néanmoins je pense et ceci est un avis personnel, qu'il faut rester sur une écriture manuel sans outils annexes. Il ne faut pas confondre l'écriture d'un algorithme et l'écriture d'un programme. L'écriture d'un algorithme doit rester libre et même s'il faut garder une certaine rigueur il faut éviter de tomber dans une difficulté syntaxique proche de la programmation. Le but d'un algorithme reste la décomposition d'un problème afin, en final d'écrire un programme et non d'écrire deux fois un programme dans des langages différents. Si toutefois cela peut vous aider en temps qu'enseignant, n'hésitez pas, le logiciel execAlgo étant entre autre conseillé pour l'apprentissage de l'algorithmique en série L.

I



Page 18 / 32

4 La programmation

4.1 Introduction La programmation est la phase ultime qui permet de voir le résultat. Cette phase pour importante qu'elle soit n'est en fait que la traduction dans le langage de la machine et dans un langage particulier d'un algorithme. Le but ici n'est pas de vous former à la programmation, ni ce document, ni le temps imparti ne sont suffisant, mais de vous donner quelques éléments permettant de traduire ou de reproduire dans un langage, des algorithmes simples afin de "faire tourner" sur une machine le résultat de votre travail. Cette phase peut également dans certains cas vous permettre de vérifier si le raisonnement algorithmique est correct. Même s'il est possible de faire tourner un algorithme, c'est à dire prendre un cas concret, se mettre en lieu et place de la machine et d’observer les variations des données en fonction des traitements, le programme illustre mieux ces concepts.

4.2 Quel langage Il existe de multiples langages qui dépendent

o du système d'exploitation o du type d'application o du niveau d'abstraction o …

Pour n'en citer que quelques-uns :

o C, C++, C# o Delphi, Visual Basic,Wwindev , Power Builder o PHP, Pithon, Javascript, VB Script o Eiffel, Ada o …

Le document Algorithmique et projet de l'académie de Montpellier ou sur Eduscol fait le tour de certains de ces langages : http://webpeda.ac-montpellier.fr/mathematiques/IMG/pdf/Doc_ress_algo_v25.pdf Extrait : Supports de programmation Comme aucun logiciel ou langage n’est imposé par le programme, on montrera ci-après différents types d’environnements de programmation. Les calculatrices graphiques programmables peuvent être exploitées grâce à leur commodité d’usage en classe entière. Cependant, leurs limites dues à leur petite taille et leur capacité mémoire incitent à proposer aux élèves des activités s’appuyant sur des logiciels utilisables sur ordinateur. Une large part des exemples proposés ci-après est parfaitement traitable avec des calculatrices comme support. Une piste intéressante pourrait être d’organiser l’enseignement autour d’une progressivité dans les outils utilisés au cours de l’année (sans pour autant les multiplier) en traitant des exemples sur plusieurs environnements.

I



Page 19 / 32

Il peut être également intéressant de mettre en avant le fait que la complexification de l’algorithme détermine de manière plus ou moins ouverte le choix de l’instrument comme par exemple pour les problèmes liés :

• au temps de calcul ; • à la nature, la taille ou la précision des nombres utilisés ; • à la lisibilité de l’algorithme ; • à la nature de la sortie.

Nombreux sont les logiciels qui peuvent être utilisés2 : des logiciels dédiés (comme SCRATCH, EXECALGO ou LINOTTE...), aux logiciels de programmation (PYTHON...) ou liés au calcul scientifique (SCILAB...) en passant par les logiciels de calcul formel (XCAS, MAXIMA, WIRIS...) qui proposent un module de programmation. Ces derniers permettront de travailler sur des types de données plus spécifiques (très grands nombres, expressions algébriques...). On pourra à l’occasion utiliser le tableur qui, s’il traduit parfaitement les instructions conditionnelles, tend cependant à cacher les itérations sous les opérations de recopie de formules. Le document de référence présente quelques exemples dans différents langages

4.3 Les langages abordés dans les manuels ou les documents officiels

• Nathan Hyperbole 2009: o Calculatrices Texas et Casio o Scratch o Xcas

• Rien à ce jour chez les autres éditeurs (en date de fin aout 2009)

• Document Eduscol (ou Montpellier) sur l'algo (docRess_algo Version 2.5):

o Scratch o Xcas o Calculatrices Texas et Casio o Linotte, Python et Scilab dans une moindre mesure

• Document Irem - apmep (juin 2009)

o Xcas o Caml

Il existe une multitude de langage, néanmoins il reste important de choisir celui qui vous permettra de mutualiser des ressources au sein de l'établissement, voire au sein de votre académie. Les langages ressortant le plus souvent étant scratch et Xcas, ce sont ceux que j'ai choisi de vous présenter succinctement ci-après. Pourquoi différents logiciels ?

En fait, ils sont complémentaires. Scratch permet en assemblant des briques d'écrire de petits programmes rapidement. Xcas est un environnement de calcul formel qui dispose d'un mode de programmation et par ce coté se rapproche plus d'un langage de programmation.

I



Page 20 / 32

4.4 Scratch

4.4.1 Présentation1 SCRATCH est un langage de programmation qui permet de créer des animations, des jeux, de la musique … SCRATCH existe dans de nombreuses langues (on préfèrera la traduction « français-Canada » à la traduction française). SCRATCH est conçu pour aider les jeunes à créer et partager des projets grâce à la technologie Java. L’environnement SCRATCH se distingue de ceux qui suivent par sa capacité à gérer la programmation événementielle voire parallèle : un projet SCRATCH ne se réduit pas à un seul algorithme, il inclut généralement des éléments multimédias (sons, images animées) ainsi qu’une multiplicité d’algorithmes s’exécutant tour à tour.

4.4.2 Les sites de référence Site officiel (téléchargement, exemples …)

http://scratch.mit.edu/ Guides d'apprentissage :

http://guides.recitmst.qc.ca/scratch/

Tutoriels : http://squeaki.recitmst.qc.ca/wakka.php?wiki=ScratchInitiation/v

Dont la version complète en PDF : http://squeaki.recitmst.qc.ca/wakka.php?wiki=ScratchInitiation/download&file=livre_initiation_scratch.pdf

4.4.3 Installation Scratch est téléchargeable sur le site ci-dessus. Vous pouvez si vous n'êtes pas familiarisé choisir le français comme langue pour le site. Il n'est également pas obligatoire de s'enregistrer pour télécharger le logiciel. Le fichier a télécharger fait un peu plus de 30 Mo, l'installation étant des plus classique. Attention, Scratch est basé sur Java tout comme geogebra. Si Java n'est pas installé, vous pouvez le télécharger ici : http://www.java.com/fr/download/

1 Document Algo (Eduscol)

I



Page 21 / 32

4.4.4 L'environnement Une fois le logiciel lancé, ci-joint la fenêtre obtenue :

Cette fenêtre est votre environnement de développement, mise au point de programmes …. Ci-joint un descriptif des zones issu des tutoriaux cités précédemment2 :

2 http://squeaki.recitmst.qc.ca/wakka.php?wiki=PremiersPas

I



Page 22 / 32

4.4.5 L'écriture d'un programme Pour écrire un programme, vous devez assembler des briques prédéfinies. Dans la palette des briques, vous allez trouver les différentes catégories d'objet:

et en sélectionnant une catégorie, les possibilités de celle-ci : A droite, vous retrouverez toutes les structures de contrôle vues précédemment à savoir les conditionnelles et les itératives ainsi que d'autres contrôles liés à l'utilisation du logiciel. Les différents contrôles sont colorés, ce qui est une aide dans la conception des programmes Pour avoir de l'aide sur un contrôle, il suffit de cliquer du bouton droit sur celui-ci puis de sélectionner aide.

I



Page 23 / 32

Pour écrire un programme, vous sélectionnerez les différents éléments dont vous avez besoin puis les assemblerez comme des briques de lego. Vous voulez récupérer un projet ou partager le votre, il suffit de prendre le fichier portant l'extension sb, celui-ci contient votre programme. Petit exemple rapide de mise en œuvre, nous allons essayer de programmer l'algorithme du début :


1) Créer un nouveau projet que vous allez nommer Script 1 (Menu Fichier puis nouveau …) 2) Créez une variables A (Menu Variable puis nouvelles variables 3) Faire la saisie. Attention, vous êtes obligé de travailler avec le menu capteur et d'affecter ensuite la réponse à votre variable

4) effectuer le test. Ici aussi vous êtes obligé d'adapter puisque le >= n'existe pas. et de plus il faut à la fois combiner un contrôle (si… ) et un opérateur ( >)

5) Afficher le résultat. Ici aussi, le résultat, à savoir l'affichage ne peut se faire que par l'intermédiaire d'un objet graphique. C'est votre objet à l'écran qui renvoie une information. Vous devez donc attacher systématiquement votre script à un objet afin d'avoir accés à la fonction dire du menu apparence. Une fois terminé, vous n'avez plus qu'à exécuter votre programme en cliquant sur le drapeau vert

I



Page 24 / 32

Votre script final et le résultat associé ressemblent alors à ceci :

Notez l'importance des couleurs afin de bien s'y retrouver dans les différentes fonctions du logiciel. Suite à ce petit exemple et avec un peu d'entrainement, vous devriez être capable de programmer des algorithmes simples. N'hésitez pas à reprendre les exemples du document de référence sur l'algorithmique déjà cité et à vous entrainer à les reproduire.

I



Page 25 / 32

4.4.6 Un peu de graphisme Un des atouts également de Scratch est la manipulation des objets graphiques. Grâce à cet outil vous pouvez être capable de tracer des courbes et autres éléments dont vous pouvez avoir besoin. Attention cependant le logiciel reste limité et vous aurez des difficultés pour tracer des repères complets à moins de passer beaucoup de temps. Ci-joint un exemple tiré du Nathan qui permet de montrer un petit tracé :

I



Page 26 / 32

Ci-joint de façon plus lisible le programme ci-dessus que vous pourrez améliorer :

Attention, lorsque vous travaillez avec les positions de x et de y, il faut savoir que l'origine se trouve au centre de l'écran et que l'écran à une dimension de 480 de large (côte en x) et 360 de haut (côte en y). Vous pouvez également jouer sur la couleur du stylo, son épaisseur … grâce au menu stylo (menu à droite). Avec certains petits défauts que vous pourrez corriger, ci-joint ci-dessous le résultat :

I



Page 27 / 32

4.5 Xcas

4.5.1 Présentation3 Xcas est un système de calcul formel pour Windows, Mac OSX et Linux/Unix. Il permet de faire du calcul formel, des représentations graphiques dans le plan ou l’espace, de la géométrie dynamique (dans le plan ou dans l’espace), du tableur, des statistiques et de la programmation. XCAS est aussi accessible en ligne. Dans cette partie, je n'aborderai pas les possibilités calculateur de Xcas (solveur, editeur d'équation …) mais seules les possibilités liées à l'algorithmique et à la programmation seront abordées. Les personnes étant familier de Mapple pourront y retrouver un outil similaire par certains points.

4.5.2 Les sites de référence Le site officiel (téléchargement, tutoriaux …)

http://www-fourier.ujf-grenoble.fr/~parisse/ Site permettant une utilisation en ligne pour le calcul formel (sans installation) :

http://vds1100.sivit.org/giac/giac_online/demoGiacPhp.php Doc officielle de Xcas sur la programmation :

http://www-fourier.ujf-grenoble.fr/~parisse/giac/doc/fr/casrouge/casrouge.html

4.5.3 L'installation Téléchargez l'installation à cette adresse (fichier exe de 30 Mo) :

http://www-fourier.ujf-grenoble.fr/~parisse/giac/xcasinst.exe L'installation se déroule de manière classique.

3 Document Algo (Eduscol)

I



Page 28 / 32

4.5.4 L'environnement Une fois le logiciel lancé, ci-joint la fenêtre de l'environnement :

Au démarrage, Xcas se trouve en mode calcul formel. Il est alors possible de maniére interactive de faire appel à des résolutions d'équation, de traçage de courbes … Pour se faire, explorer par exemple le menu scolaire et testez resoudre ou graphe dans le sous-menu seconde. Ci-joint les explications sur cette fenêtre4 :

4 http://www-fourier.ujf-grenoble.fr/~parisse/giac/doc/fr/tutoriel/node2.html

I



Page 29 / 32

Pour effectuer une opération en calcul formel, il suffit de la saisir dans la lige de commande puis de l'exécuter. Le résultat apparaîtra en dessous. Ci-joint exemple de tracé d'un graphique:

4.5.5 Utilisation de Xcas en programmation Pour rentrer en mode programmation, il faut saisir Alt P Vous pouvez dés lors saisir un programme puis l'exécuter. à l'aide du bouton OK. N'oubliez pas également de sauvegarder votre programme à l'aide du bouton save. Le fichier sauvegardé porte alors l'extension cxx.

La syntaxe de Xcas est à la fois proche d'un Basic et d'un langage C. Il est également possible d'utiliser une grammaire française.

• Toutes les lignes doivent se terminer par un signe ; • Les commentaires dans un programme commencent par // • Une chaîne de caractère est encadrée par un " (guillemet double )

Ce menu vous permet d'insérer des structures de contrôle (If, For …)

Ce bouton permet d'exécuter le programme

I



Page 30 / 32

4.5.6 Un exemple de programmes Le but ici n'est pas de recopier le guide de programmation de Xcas déjà cité précédemment qui est très bien fait mais de vous montrer quelques exemples de programmes tirés des algorithmes précédents afin de vous familiariser avec les syntaxes. En reprenant un des algorithmes du début :


Par manque de temps (le mien également), nous n'irons pas plus loin aujourd'hui. Je pense que cela suffit déjà bien amplement et il faut en laisser pour plus tard…

I



Page 31 / 32

5 L'algorithmique et le programme de seconde

5.1 Les documents de référence Le référentiel de la classe de seconde : http://webpeda.ac-montpellier.fr/mathematiques/IMG/pdf/pgm2nde2009.pdf Extrait des pages 9 et 10 : Algorithmique (objectifs pour le lycée) La démarche algorithmique est, depuis les origines, une composante essentielle de l’activité mathématique. Au collège, les élèves ont rencontré des algorithmes (algorithmes opératoires, algorithme des différences, algorithme d’Euclide, algorithmes de construction en géométrie). Ce qui est proposé dans le programme est une formalisation en langage naturel propre à donner lieu à traduction sur une calculatrice ou à l’aide d’un logiciel. Il s’agit de familiariser les élèves avec les grands principes d’organisation d’un algorithme : gestion des entrées-sorties, affectation d’une valeur et mise en forme d’un calcul. Dans le cadre de cette activité algorithmique, les élèves sont entraînés :

• à décrire certains algorithmes en langage naturel ou dans un langage symbolique ; • à en réaliser quelques uns à l’aide d’un tableur ou d’un petit programme réalisé sur une

calculatrice ou avec un logiciel adapté ; • à interpréter des algorithmes plus complexes.

Aucun langage, aucun logiciel n’est imposé. L’algorithmique a une place naturelle dans tous les champs des mathématiques et les problèmes posés doivent être en relation avec les autres parties du programme (fonctions, géométrie, statistiques et probabilité, logique) mais aussi avec les autres disciplines ou la vie courante. À l’occasion de l’écriture d’algorithmes et de petits programmes, il convient de donner aux élèves de bonnes habitudes de rigueur et de les entraîner aux pratiques systématiques de vérification et de contrôle. Instructions élémentaires (affectation, calcul, entrée, sortie).

Les élèves, dans le cadre d’une résolution de problèmes, doivent être capables : • d’écrire une formule permettant un calcul ; • d’écrire un programme calculant et donnant la valeur d’une fonction ;

ainsi que les instructions d’entrées et sorties nécessaires au traitement. Boucle et itérateur, instruction conditionnelle

Les élèves, dans le cadre d’une résolution de problèmes, doivent être capables : • de programmer un calcul itératif, le nombre d’itérations étant donné ; • de programmer une instruction conditionnelle, un calcul itératif, avec une fin de

boucle conditionnelle.

I



Page 32 / 32

Un document ressource d'accompagnement sur le site de Montpellier : http://webpeda.ac-montpellier.fr/mathematiques/IMG/pdf/Doc_ress_algo_v25.pdf Quelques extraits : Le programme de seconde a été conçu pour être enseigné et mis en œuvre en s’appuyant assez largement sur les progrès de la science et de la technique informatiques, qu’il s’agisse de logiciels ou de la pensée algorithmique. Depuis une dizaine d’années le développement de l’usage de logiciels (calculatrice ou ordinateur) a permis de développer chez les élèves la capacité d’expérimenter, suscitant le sens de l’observation tout en faisant naitre de nouvelles questions relatives à la nature de la démonstration. C’est dans ce contexte que l’introduction d’une familiarisation avec l’algorithmique prend sa place dans une pratique des Mathématiques dont un axe principal est la formation des élèves à la démarche scientifique sous toutes ses formes. Algorithmes et démarche algorithmique La sensibilisation de l’élève à la question de la « démarche algorithmique » pourra se faire en évitant toute technicité ou exposé systématique… Les compétences suivantes pourront être identifiées et travaillées :

• comprendre et analyser un algorithme préexistant ; • modifier un algorithme pour obtenir un résultat particulier ; • analyser la situation : identifier les données d’entrée, de sortie, le traitement...; • mettre au point une solution algorithmique : comment écrire un algorithme en « langage

courant » en respectant un code, identifier les boucles, les tests, des opérations d’écriture, d’affichage... ;

• valider la solution algorithmique par des traces d’exécution et des jeux d’essais simples ;

• adapter l’algorithme aux contraintes du langage de programmation : identifier si nécessaire la nature des variables... ;

• valider un programme simple. Le spécimen Nathan en ligne (le premier livre avec le nouveau programme) :

http://www.nathan.fr/specimens/viewer.asp?ean=9782091724904&org=push Deux documents intéressants sur le site de l'IREM : http://download.tuxfamily.org/tehessinmath/les%20pdf/irem10juin09.pdf

http://download.tuxfamily.org/tehessinmath/les%20pdf/PafAlgo.pdf

Documents

Initiation Algorithmique et programmation Page 1 / 32 I ...ecogest-nancy-metz.org/publications/1155.pdf · I Philippe Lacurie Séance du 8 octobre 2009 Initiation Algorithmique et