Cours dInformatique

1re anne SMP/SMC

2007/2008, Semestre 2
Mouad BEN MAMOUN
Moulay Driss RAHMANI
Dpartement de Mathmatiques et dInformatique,
Universit Mohammed V
ben_mamoun@[Link]
mrahmani@[Link]
2007/2008

Module I2, 1re anne S

Objectif et plan du cours

Objectif:

Apprendre les concepts de base de l'algorithmique et de la

programmation

Etre capable de mettre en oeuvre ces concepts pour analyser des

problmes simples et crire les programmes correspondants

Plan:

Gnralits (matriel dun ordinateur, systmes dexploitation, langages de

Algorithmique (affectation, instructions conditionnelles, instructions itratives,

MAPLE (un outil de programmation)

2007/2008

programmation, )

fonctions, procdures, )

Module I2, 1re anne S

Informatique?

Techniques du traitement automatique de linformation au

moyen des ordinateurs

Elments dun systme informatique

Applications
.(Word, Excel, Jeux, Maple, etc)
Langages
.(Java,C/C++, Fortran,etc)
Systme dexploitation
.(DOS,Windows, Unix, etc )
Matriel
.(PC, Macintosh, station SUN, etc)

2007/2008

Module I2, 1re anne S

Matriel: Principaux lments dun PC

Unit centrale (le botier)

Processeur ou CPU (Central Processing Unit)

Mmoire centrale
Disque dur, lecteur disquettes, lecteur CD-ROM
Cartes spcialises (cartes vido, rseau, ...)
Interfaces d'entre-sortie (Ports srie/parallle, )

Priphriques

2007/2008

Moniteur (l'cran), clavier, souris

Modem, imprimante, scanner,
Module I2, 1re anne S

Quest ce quun systme dexploitation?

Ensemble de programmes qui grent le matriel et

contrlent les applications

Gestion des priphriques (affichage l'cran, lecture du clavier,

Gestion des utilisateurs et de leurs donnes (comptes,

Interface avec lutilisateur (textuelle ou graphique):

Contrle des programmes (dcoupage en taches, partage du

2007/2008

pilotage dune imprimante, )

partage des ressources, gestion des fichiers et rpertoires, )

Interprtation des commandes

temps processeur, )

Module I2, 1re anne S

Langages informatiques

Un langage informatique est un outil permettant de

donner des ordres (instructions) la machine

Intrt : crire des programmes (suite conscutive

dinstructions) dstins effectuer une tache donne

A chaque instruction correspond une action du processeur

Exemple: un programme de gestion de comptes bancaires

Contrainte: tre comprhensible par la machine

2007/2008

Module I2, 1re anne S

Langage machine

Langage binaire: linformation est exprime et manipule sous

forme dune suite de bits

Un bit (binary digit) = 0 ou 1 (2 tats lectriques)

8
Une combinaison de 8 bits= 1 Octet 2 256 possibilits qui permettent

de coder tous les caractres alphabtiques, numriques, et symboles tels que ?,*,&,

Le code ASCII (American Standard Code for Information Interchange) donne les

correspondances entre les caractres alphanumriques et leurs

reprsentation binaire, Ex. A= 01000001, ?=00111111

Les oprations logiques et arithmtiques de base (addition,

multiplication, ) sont effectues en binaire

2007/2008

Module I2, 1re anne S

L'assembleur

Problme: le langage machine est difficile comprendre par l'humain

Ide: trouver un langage comprhensible par l'homme qui sera

ensuite
converti en langage machine
Assembleur (1er langage): exprimer les instructions lmentaires de faon
symbolique
ADD A, 4

traducteur

LOAD B

langage machine

MOV A, OUT

+: dj plus accessible que le langage machine

-: dpend du type de la machine (nest pas portable)
portable
-: pas assez efficace pour dvelopper des applications complexes

Apparition des langages volus

2007/2008

Module I2, 1re anne S

Langages haut niveau

Intrts multiples pour le haut niveau:

proche du langage humain anglais (comprhensible)

permet une plus grande portabilit (indpendant du matriel)
Manipulation de donnes et dexpressions complexes (rels,
objets, a*b/c, )

Ncessit dun traducteur (compilateur/interprteur),

excution plus ou moins lente selon le traducteur
Code source

Compilateur ou

en langage volu

interprteur

2007/2008

Module I2, 1re anne S

Langage machine

Compilateur/interprteur

Compilateur: traduire le programme entier une fois pour toutes

exemple.c

Compilateur

fichier source

exemple

excution

fichier excutable

+ plus rapide lexcution

+ scurit du code source
- il faut recompiler chaque modification

Interprteur: traduire au fur et mesure les instructions du

programme chaque excution

[Link]
fichier source

2007/2008

Interprtation+excution

+ excution instantane apprciable pour les dbutants

- excution lente par rapport la compilation

Module I2, 1re anne S

10

Langages de programmation:

Deux types de langages:

Exemples de langages:

2007/2008

Langages procduraux
Langages orients objets

Fortran, Cobol, Pascal, C,

C++, Java,

Choix dun langage?

Module I2, 1re anne S

11

Etapes de ralisation dun programme

Enonc du problme
Spcification
Cahier des charges
Analyse
Algorithme
Traduction en langage
Programme source
Compilation
Programme excutable
Tests et modifications
Version finale et rsultats

La ralisation de programmes passe par lcriture dalgorithmes

Do lintrt de lAlgorithmique
2007/2008

Module I2, 1re anne S

12

Algorithmique

Le terme algorithme vient du nom du mathmaticien arabe

Khawarizmi (820 aprs J.C.)

Un algorithme est une description complte et dtaille des actions

effectuer et de leur squencement pour arriver un rsultat donn

Al-

Intrt: sparation analyse/codage (pas de proccupation de syntaxe)

Qualits: exact (fournit le rsultat souhait), efficace (temps dexcution, mmoire
occupe), clair (comprhensible), gnral (traite le plus grand nombre de cas
possibles),

Lalgorithmique dsigne aussi la discipline qui tudie les algorithmes et

leurs applications en Informatique

Une bonne connaissance de lalgorithmique permet dcrire des

algorithmes exacts et efficaces

2007/2008

Module I2, 1re anne S

13

Reprsentation dun algorithme

Historiquement, deux faons pour reprsenter un algorithme:

LOrganigramme: reprsentation graphique avec des symboles

(carrs, losanges, etc.)

offre une vue densemble de lalgorithme

reprsentation quasiment abandonne aujourdhui

Le pseudo-code: reprsentation textuelle avec une srie de

conventions ressemblant un langage de programmation (sans les
problmes de syntaxe)

2007/2008

plus pratique pour crire un algorithme

reprsentation largement utilise

Module I2, 1re anne S

14

Algorithmique

Notions et instructions de base

2007/2008

Module I2, 1re anne SMP/SMC

15

Notion de variable

Dans les langages de programmation une variable sert stocker

la valeur dune donne

Une variable dsigne en fait un emplacement mmoire dont

le contenu peut changer au cours dun programme (do le nom
variable)

Rgle : Les variables doivent tre dclares avant dtre

utilises, elle doivent tre caractrises par :

2007/2008

un nom (Identificateur)
Identificateur
un type (entier, rel, caractre, chane de caractres, )
Module I2, 1re anne S

16

Choix des identificateurs (1)

Le choix des noms de variables est soumis quelques rgles qui
varient selon le langage, mais en gnral:

Un nom doit commencer par une lettre alphabtique

exemple valide: A1

exemple invalide: 1A

doit tre constitu uniquement de lettres, de chiffres et du

soulignement _ (Eviter les caractres de ponctuation et les espaces)

valides: SMIP2007, SMP_2007 invalides: SMP 2005,SMI-2007,SMP;2007

doit tre diffrent des mots rservs du langage (par exemple en

Java:
Java int, float, else, switch, case, default, for, main, return , )

La longueur du nom doit tre infrieure la taille maximale spcifie

par le langage utilis

2007/2008

Module I2, 1re anne S

17

Choix des identificateurs (2)

Conseil: pour la lisibilit du code choisir des noms significatifs
qui dcrivent les donnes manipules
exemples: TotalVentes2004, Prix_TTC, Prix_HT

Remarque: en pseudo-code algorithmique, on va respecter

les rgles cites, mme si on est libre dans la
syntaxe

2007/2008

Module I2, 1re anne S

18

Types des variables

Le type dune variable dtermine lensemble des valeurs quelle peut
prendre, les types offerts par la plus part des langages sont:
Type numrique (entier ou rel)

Byte (cod sur 1octet): de 0 255

Entier court (cod sur 2 octets) : -32 768 32 767
Entier long (cod sur 4 ou 8 octets)
Rel simple prcision (cod sur 4 octets)
Rel double prcision (cod sur 8 octets)

Type logique ou boolen: deux valeurs VRAI ou FAUX

Type caractre: lettres majuscules, minuscules, chiffres, symboles,

exemples: A, a, 1, ?,

Type chane de caractre: toute suite de caractres,

exemples: " Nom, Prnom", "code postale: 1000",

2007/2008

Module I2, 1re anne S

19

Dclaration des variables

Rappel: toute variable utilise dans un programme doit avoir fait

lobjet dune dclaration pralable
En pseudo-code, on va adopter la forme suivante pour la
dclaration de variables

Variables

liste d'identificateurs : type

Exemple:
Variables

i, j,k : entier

x, y : rel
OK: boolen
ch1, ch2 : chane de caractres

Remarque: pour le type numrique on va se limiter aux entiers et

rels sans considrer les sous types

2007/2008

Module I2, 1re anne S

20

Linstruction daffectation

laffectation consiste attribuer une valeur une variable

(a

consiste en fait remplir o modifier le contenu d'une zone mmoire)

En pseudo-code, l'affectation se note avec le signe

Var e: attribue la valeur de e la variable Var

e peut tre une valeur, une autre variable ou une expression

Var et e doivent tre de mme type ou de types compatibles
laffectation ne modifie que ce qui est gauche de la flche

Ex valides: i 1
j i
x 10.3
OK FAUX
ch2 ch1 x 4
x j

k i+j
ch1 "SMI"

(voir la dclaration des variables dans le transparent prcdent)

non valides: i 10.3

2007/2008

OK "SMI"

Module I2, 1re anne S

j x
21

Quelques remarques

Beaucoup de langages de programmation (C/C++, Java, ) utilisent

le signe gal = pour laffectation . Attention aux confusions:

l'affectation n'est pas commutative : A=B est diffrente de B=A

l'affectation est diffrente d'une quation mathmatique :

A=A+1 a un sens en langages de programmation

A+1=2 n'est pas possible en langages de programmation et n'est pas
quivalente A=1

Certains langages donnent des valeurs par dfaut aux variables

dclares. Pour viter tout problme il est prfrable d'initialiser les
variables dclares

2007/2008

Module I2, 1re anne S

22

Exercices simples sur l'affectation (1)

Donnez les valeurs des variables A, B et C aprs excution
des instructions suivantes ?
Variables A, B, C: Entier
Dbut
A 3
B7
A B
B A+5
C A+ B
CBA
Fin
2007/2008

Module I2, 1re anne S

23

Exercices simples sur l'affectation (2)

Donnez les valeurs des variables A et B aprs excution des
instructions suivantes ?
Variables A, B : Entier
Dbut
A 1
B2
A B
BA
Fin
Les deux dernires instructions permettent-elles dchanger les
valeurs de A et B ?
2007/2008

Module I2, 1re anne S

24

Exercices simples sur l'affectation (3)

Ecrire un algorithme permettant dchanger les
valeurs de deux variables A et B

2007/2008

Module I2, 1re anne S

25

Expressions et oprateurs

Une expression peut tre une valeur, une variable ou une opration constitue
de variables relies par des oprateurs
exemples: 1, b, a*2, a+ 3*b-c,

L'valuation de l'expression fournit une valeur unique qui est le rsultat de

l'opration

Les oprateurs dpendent du type de l'opration, ils peuvent tre :

des oprateurs arithmtiques: +, -, *, /, % (modulo), ^ (puissance)

des oprateurs logiques: NON, OU, ET
des oprateurs relationnels: =, , <, >, <=, >=
des oprateurs sur les chanes: & (concatnation)

Une expression est value de gauche

droite mais en tenant compte de
priorits

2007/2008

Module I2, 1re anne S

26

Priorit des oprateurs

Pour les oprateurs arithmtiques donns ci-dessus, l'ordre de

priorit est le suivant (du plus prioritaire au moins prioritaire) :

^ : (lvation la puissance)
* , / (multiplication, division)
% (modulo)
+ , - (addition, soustraction)

exemple:

2+3*7

vaut 23

En cas de besoin (ou de doute), on utilise les parenthses pour

indiquer les oprations effectuer en priorit
exemple:

2007/2008

(2 + 3) * 7 vaut 35
3

Module I2, 1re anne S

27

Les instructions d'entres-sorties:

lecture et criture (1)

Les instructions de lecture et d'criture permettent la machine de

communiquer avec l'utilisateur

La lecture permet d'entrer des donns partir du clavier

En pseudo-code, on note: lire (var)

la machine met la valeur entre au clavier
dans la zone mmoire nomme var

Remarque: Le programme s'arrte lorsqu'il rencontre une

instruction Lire et ne se poursuit qu'aprs la frappe dune valeur
au clavier et de la touche Entre

2007/2008

Module I2, 1re anne S

28

Les instructions d'entres-sorties:

lecture et criture (2)

L'criture permet d'afficher des rsultats l'cran (ou de les crire

dans un fichier)

En pseudo-code, on note: crire (var)

la machine affiche le contenu de la
zone mmoire var

Conseil: Avant de lire une variable, il est fortement conseill

dcrire des messages lcran, afin de prvenir lutilisateur de
ce quil doit frapper

2007/2008

Module I2, 1re anne S

29

Exemple (lecture et criture)

Ecrire un algorithme qui demande un nombre entier l'utilisateur, puis
qui calcule et affiche le double de ce nombre

Algorithme Calcul_double
variables A, B : entier
Dbut
crire("entrer le nombre ")
lire(A)
B 2*A
crire("le double de ", A, "est :", B)
Fin
2007/2008

Module I2, 1re anne S

30

Exercice (lecture et criture)

Ecrire un algorithme qui vous demande de saisir votre nom puis
votre prnom et qui affiche ensuite votre nom complet
Algorithme AffichageNomComplet
variables Nom, Prenom, Nom_Complet : chane de caractres
Dbut
crire("entrez votre nom")
lire(Nom)
crire("entrez votre prnom")
lire(Prenom)
Nom_Complet Nom & Prenom
crire("Votre nom complet est : ", Nom_Complet)
Fin

2007/2008

Module I2, 1re anne S

31

Tests: instructions conditionnelles (1)

Les instructions conditionnelles servent n'excuter une instruction

ou une squence d'instructions que si une condition est vrifie

On utilisera la forme suivante: Si condition alors

instruction ou suite d'instructions1

Sinon
instruction ou suite d'instructions2
Finsi

2007/2008

la condition ne peut tre que vraie ou fausse

si la condition est vraie, se sont les instructions1 qui seront excutes
si la condition est fausse, se sont les instructions2 qui seront excutes
la condition peut tre une condition simple ou une condition compose de
plusieurs conditions

Module I2, 1re anne S

32

Tests: instructions conditionnelles (2)

La partie Sinon n'est pas obligatoire, quand elle n'existe pas et que
la condition est fausse, aucun traitement n'est ralis

On utilisera dans ce cas la forme simplifie suivante:

Si condition alors
instruction ou suite d'instructions1
Finsi

2007/2008

Module I2, 1re anne S

33

Exemple (SiAlorsSinon)
Algorithme AffichageValeurAbsolue (version1)
Variable x : rel
Dbut
Ecrire (" Entrez un rel : )
Lire (x)
Si (x < 0) alors
Ecrire ("la valeur absolue de ", x, "est:",-x)
Sinon
Ecrire ("la valeur absolue de ", x, "est:",x)
Finsi
Fin

2007/2008

Module I2, 1re anne S

34

Exemple (SiAlors)
Algorithme AffichageValeurAbsolue (version2)
Variable x,y : rel
Dbut
Ecrire (" Entrez un rel : )
Lire (x)
y x
Si (x < 0) alors
y -x
Finsi
Ecrire ("la valeur absolue de ", x, "est:",y)
Fin
2007/2008

Module I2, 1re anne S

35

Exercice (tests)
Ecrire un algorithme qui demande un nombre entier l'utilisateur,
puis qui teste et affiche s'il est divisible par 3
Algorithme Divsible_par3
Variable n : entier
Dbut
Ecrire " Entrez un entier : "
Lire (n)
Si (n%3=0) alors
Ecrire (n," est divisible par 3")
Sinon
Ecrire (n," n'est pas divisible par 3")
Finsi
Fin
2007/2008

Module I2, 1re anne S

36

Conditions composes

Une condition compose est une condition forme de plusieurs

conditions simples relies par des oprateurs logiques:
ET, OU, OU exclusif (XOR) et NON

Exemples :
x compris entre 2 et 6 : (x > 2) ET (x < 6)

n divisible par 3 ou par 2 : (n%3=0) OU (n%2=0)

deux valeurs et deux seulement sont identiques parmi a, b et c :
(a=b) XOR (a=c) XOR (b=c)

L'valuation d'une condition compose se fait selon des rgles

prsentes gnralement dans ce qu'on appelle tables de vrit

2007/2008

Module I2, 1re anne S

37

Tables de vrit
C1

C2

C1 ET C2

C1

C2

C1 OU C2

VRAI

VRAI

VRAI

VRAI

VRAI

VRAI

VRAI

FAUX

FAUX

VRAI

FAUX

VRAI

FAUX

VRAI

FAUX

FAUX

VRAI

VRAI

FAUX

FAUX

FAUX

FAUX

FAUX

FAUX

C1

C2

C1 XOR C2

C1

NON C1

VRAI

VRAI

FAUX

VRAI

FAUX

VRAI

FAUX

VRAI

FAUX

VRAI

FAUX

VRAI

VRAI

FAUX

FAUX

FAUX

2007/2008

Module I2, 1re anne S

38

Tests imbriqus

Les tests peuvent avoir un degr quelconque d'imbrications

Si condition1 alors
Si condition2 alors
instructionsA
Sinon
instructionsB
Finsi
Sinon
Si condition3 alors
instructionsC
Finsi
Finsi

2007/2008

Module I2, 1re anne S

39

Tests imbriqus: exemple (version 1)

Variable n : entier
Dbut
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors
Ecrire ("Ce nombre est ngatif")
Sinon
Si (n = 0) alors
Ecrire ("Ce nombre est nul")
Sinon
Ecrire ("Ce nombre est positif")
Finsi
Finsi
Fin
2007/2008

Module I2, 1re anne S

40

Tests imbriqus: exemple (version 2)

Variable n : entier
Dbut
Ecrire ("entrez un nombre : ")
Lire (n)
Si (n < 0) alors
Ecrire ("Ce nombre est ngatif")
Finsi
Si (n = 0) alors
Ecrire ("Ce nombre est nul")
Finsi
Si (n > 0) alors Ecrire ("Ce nombre est positif")
Finsi
Fin
Remarque : dans la version 2 on fait trois tests systmatiquement alors que dans
la version 1, si le nombre est ngatif on ne fait qu'un seul test
Conseil : utiliser les tests imbriqus pour limiter le nombre de tests et placer
d'abord les conditions les plus probables

2007/2008

Module I2, 1re anne S

41

Tests imbriqus: exercice

Le prix de photocopies dans une reprographie varie selon le
nombre demand: 0,5 DH la copie pour un nombre de copies
infrieur 10, 0,4DH pour un nombre compris entre 10 et 20 et
0,3DH au-del.
Ecrivez un algorithme qui demande lutilisateur le nombre de
photocopies effectues, qui calcule et affiche le prix payer

2007/2008

Module I2, 1re anne S

42

Tests imbriqus: corrig de l'exercice

Variables copies : entier
prix : rel
Dbut
Ecrire ("Nombre de photocopies : ")
Lire (copies)
Si (copies < 10) Alors
prix copies*0.5
Sinon Si (copies) < 20
prix copies*0.4
Sinon
prix copies*0.3
Finsi
Finsi
Ecrire (Le prix payer est : , prix)
Fin

2007/2008

Module I2, 1re anne S

43

Instructions itratives: les boucles

Les boucles servent rpter l'excution d'un groupe d'instructions un

certain nombre de fois

On distingue trois sortes de boucles en langages de programmation :

Les boucles tant que : on y rpte des instructions tant qu'une certaine
condition est ralise

Les boucles jusqu' : on y rpte des instructions jusqu' ce qu'une certaine

condition soit ralise

Les boucles pour ou avec compteur : on y rpte des instructions en faisant

voluer un compteur (variable particulire) entre une valeur initiale et une
valeur finale

(Dans ce cours, on va s'intresser essentiellement aux boucles Tant que et boucles

Pour qui sont plus utilises et qui sont dfinies en Maple)

2007/2008

Module I2, 1re anne S

44

Les boucles Tant que

TantQue

(condition)

instructions
FinTantQue

condition Vrai instructions

Faux

la condition (dite condition de contrle de la boucle) est value avant chaque

itration

si la condition est vraie, on excute instructions (corps de la boucle), puis, on

retourne tester la condition. Si elle est encore vraie, on rpte l'excution,

si la condition est fausse, on sort de la boucle et on excute l'instruction qui

est aprs FinTantQue

2007/2008

Module I2, 1re anne S

45

Les boucles Tant que : remarques

Le nombre d'itrations dans une boucle TantQue n'est pas connu

au moment d'entre dans la boucle. Il dpend de l'volution de la
valeur de condition

Une des instructions du corps de la boucle doit absolument

changer la valeur de condition de vrai faux (aprs un certain
nombre d'itrations), sinon le programme tourne indfiniment

Attention aux boucles infinies

Exemple de boucle infinie :

i2
TantQue (i > 0)
i i+1
(attention aux erreurs de frappe : + au lieu de -)
FinTantQue

2007/2008

Module I2, 1re anne S

46

Boucle Tant que : exemple1

Contrle de saisie d'une lettre majuscule jusqu ce que le caractre
entr soit valable
Variable C : caractre
Debut
Ecrire (" Entrez une lettre majuscule ")
Lire (C)
TantQue (C < 'A' ou C > 'Z')
Ecrire ("Saisie errone. Recommencez")
Lire (C)
FinTantQue
Ecrire ("Saisie valable")
Fin
2007/2008

Module I2, 1re anne S

47

Boucle Tant que : exemple2

Un algorithme qui dtermine le premier nombre entier N tel que la
somme de 1 N dpasse strictement 100
version 1
Variables som, i : entier
Debut
i0
som 0
TantQue (som <=100)
i i+1
som som+i
FinTantQue
Ecrire (" La valeur cherche est N= ", i)
Fin
2007/2008

Module I2, 1re anne S

48

Boucle Tant que : exemple2 (version2)

Un algorithme qui dtermine le premier nombre entier N tel que la somme
de 1 N dpasse strictement 100
version 2: attention l'ordre des instructions et aux valeurs initiales
Variables som, i : entier
Debut
som 0
i1
TantQue (som <=100)
som som + i
i i+1
FinTantQue
Ecrire (" La valeur cherche est N= ", i-1)
Fin
2007/2008

Module I2, 1re anne S

49

Les boucles Pour

Pour compteur allant de initiale finale par pas valeur du pas
instructions
FinPour
i initiale

i n'a pas atteint finale

Vrai

instructions

i i + pas

Faux
2007/2008

Module I2, 1re anne S

50

Les boucles Pour

Remarque : le nombre d'itrations dans une boucle Pour est connu

avant le dbut de la boucle

Compteur est une variable de type entier (ou caractre). Elle doit tre
dclare

Pas est un entier qui peut tre positif ou ngatif. Pas peut ne pas tre
mentionn, car par dfaut sa valeur est gal 1. Dans ce cas, le
nombre d'itrations est gal finale - initiale+ 1

Initiale et finale peuvent tre des valeurs, des variables dfinies

avant le dbut de la boucle ou des expressions de mme type que
compteur

2007/2008

Module I2, 1re anne S

51

Droulement des boucles Pour

1)

La valeur initiale est affecte la variable compteur

2)

On compare la valeur du compteur et la valeur de finale :

a)

Si la valeur du compteur est > la valeur finale dans le cas d'un pas
positif (ou si compteur est < finale pour un pas ngatif), on sort de la
boucle et on continue avec l'instruction qui suit FinPour

b)

Si compteur est <= finale dans le cas d'un pas positif (ou si compteur
est >= finale pour un pas ngatif), instructions seront excutes

2007/2008

i.

Ensuite, la valeur de compteur est incrmente de la valeur du pas

si pas est positif (ou dcrment si pas est ngatif)

ii.

On recommence l'tape 2 : La comparaison entre compteur et

finale est de nouveau effectue, et ainsi de suite

Module I2, 1re anne S

52

Boucle Pour : exemple1

Calcul de x la puissance n o x est un rel non nul et n un
entier positif ou nul
Variables x, puiss : rel
n, i : entier
Debut
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss 1
Pour i allant de 1 n
puiss puiss*x
FinPour
Ecrire (x, " la puissance ", n, " est gal ", puiss)
Fin

2007/2008

Module I2, 1re anne S

53

Boucle Pour : exemple1 (version 2)

Calcul de x la puissance n o x est un rel non nul et n un entier
positif ou nul (version 2 avec un pas ngatif)
ngatif
Variables x, puiss : rel
n, i : entier
Debut
Ecrire (" Entrez respectivement les valeurs de x et n ")
Lire (x, n)
puiss 1
Pour i allant de n 1 par pas -1
puiss puiss*x
FinPour
Ecrire (x, " la puissance ", n, " est gal ", puiss)
Fin
2007/2008

Module I2, 1re anne S

54

Boucle Pour : remarque

Il faut viter de modifier la valeur du compteur (et de finale)

l'intrieur de la boucle. En effet, une telle action :

perturbe le nombre d'itrations prvu par la boucle Pour

rend difficile la lecture de l'algorithme
prsente le risque d'aboutir une boucle infinie
Exemple : Pour i allant de 1 5
i i -1
crire(" i = ", i)
Finpour

2007/2008

Module I2, 1re anne S

55

Lien entre Pour et TantQue

La boucle Pour est un cas particulier de Tant Que (cas o le nombre d'itrations
est connu et fix) . Tout ce qu'on peut crire avec Pour peut tre remplac
avec TantQue (la rciproque est fausse)

Pour compteur allant de initiale finale par pas valeur du pas

instructions
FinPour
peut tre remplac par :
(cas d'un pas positif)

2007/2008

compteur initiale
TantQue compteur <= finale
instructions
compteur compteur+pas
FinTantQue

Module I2, 1re anne S

56

Lien entre Pour et TantQue: exemple

Calcul de x la puissance n o x est un rel non nul et n un entier positif ou
nul (version avec TantQue)
TantQue
Variables x, puiss : rel
n, i : entier
Debut
Ecrire (" Entrez la valeur de x ")
Lire (x)
Ecrire (" Entrez la valeur de n ")
Lire (n)
puiss 1
i1
TantQue (i<=n)
puiss puiss*x
i i+1
FinTantQue
Ecrire (x, " la puissance ", n, " est gal ", puiss)
Fin

2007/2008

Module I2, 1re anne S

57

Boucles imbriques

Les instructions d'une boucle peuvent tre des instructions

itratives. Dans ce cas, on aboutit des boucles imbriques

Exemple:
Pour i allant de 1 5
Pour j allant de 1 i
crire("O")
FinPour
crire("X")
FinPour

2007/2008

Excution
OX
OOX
OOOX
OOOOX
OOOOOX

Module I2, 1re anne S

58

Les boucles Rpter jusqu

Rpter
instructions
Jusqu'

instructions

condition
condition

Faux

Vrai

Condition est value aprs chaque itration

les instructions entre Rpter et jusqu sont excutes au moins une fois et
leur excution est rpte jusqu ce que condition soit vrai (tant qu'elle est
fausse)

2007/2008

Module I2, 1re anne S

59

Boucle Rpter jusqu : exemple

Un algorithme qui dtermine le premier nombre entier N tel que la somme de 1
N dpasse strictement 100 (version avec rpter jusqu')

Variables som, i : entier

Debut
som 0
i0
Rpter
i i+1
som som+i
Jusqu' ( som > 100)
Ecrire (" La valeur cherche est N= ", i)
Fin
2007/2008

Module I2, 1re anne S

60

Choix d'un type de boucle

Si on peut dterminer le nombre d'itrations avant l'excution de la

boucle, il est plus naturel d'utiliser la boucle Pour

S'il n'est pas possible de connatre le nombre d'itrations avant

l'excution de la boucle, on fera appel l'une des boucles TantQue
ou rpter jusqu'

Pour le choix entre TantQue et jusqu' :

2007/2008

Si on doit tester la condition de contrle avant de commencer les

instructions de la boucle, on utilisera TantQue

Si la valeur de la condition de contrle dpend d'une premire

excution des instructions de la boucle, on utilisera rpter jusqu'
Module I2, 1re anne S

61

MAPLE

Prsentation gnrale et
syntaxe des instructions de
base

2007/2008

Module I2, 1re anne SMP/SMC

62

Maple

Maple est un logiciel de calcul formel et numrique

Calcul formel : calcul sur des expressions littrales sans valuation

numrique (Maple peut calculer des drives, des intgrales, des
dveloppements limits, )

> int(1-x+x^3,x);
> taylor(sin(x),x=0,6);

x2 x4
x
2
4
x3 x5
x
O(x 6 )
6 120

Calcul numrique : calcul sur des valeurs (avec une grande prcision)

> 30!;

265252859812191058636308480000000

> evalf(sqrt(2),50);
1.414213562373095048801688
7242096980785696718753769
2007/2008

Module I2, 1re anne S

63

Maple : les packages

Maple dispose d'un certain nombre de packages (librairies). Chacun

de ces packages est spcialis dans un traitement particulier. Comme
exemples de ces packages, on a :

linalg : pour l'algbre linaire

plots : pour le trac des courbes
geometry : pour la gomtrie
student : ce package est conu pour assister l'enseignement des
mathmatiques de base (intressant pour les tudiants)

Pour utiliser certaines commandes et fonctions de Maple, il faut

d'abord charger le package qui les contient avec la commande with :

2007/2008

with (NomLibrairie) : charge le package NomLibrairie

with (NomLib, NomCmd) : charge la commande NomCmd du package
NomLib

Module I2, 1re anne S

64

Maple : Gnralits

Chaque instruction Maple doit se terminer par ; ou :

Si l'instruction se termine par ; Maple l'excute et affiche le rsultat
Si l'instruction se termine par : Maple l'excute sans afficher le rsultat

Pour introduire un texte en tant que commentaire,

commentaire il suffit de prcder la
ligne par # ( le texte est alors ignor par Maple)

Il est aussi possible d'crire des commentaires en cliquant sur l'icne T

de la barre d'outils et sur l'icne [> pour revenir en mode normal

Maple fait la distinction entre les lettres majuscules et minuscules (SMI,

Smi, smI et smi sont diffrents pour Maple)

2007/2008

Module I2, 1re anne S

65

Maple : nom et type des variables

Le nom d'une variable peut tre une combinaison de lettres et de

chiffres, mais qui commence par une lettre, qui ne contient pas
d'espaces et qui est diffrente des mots rservs (commandes Maple)

Le type d'une variable est attribu automatiquement par Maple selon

le contexte (exemple : si A prend la valeur 2, A sera de type integer,
integer si
A prend la valeur , A2 sera de type float)
float

Les principaux types dfinis en Maple sont : integer (entier), float

(rel), fraction (rationnel), complex (complexe), string (chane de
caractres), boolean (boolen), array (tableau), matrix (matrice)

Maple offre quelques commandes relatifs aux types :

ex : whattype(var)
donne le type de la variable var
whattype

2007/2008

Module I2, 1re anne S

66

Maple : l'affectation

Le symbole d'affectation se note en Maple avec :=

exemple :
i:= 1; j:= i+1;

Attention : en Maple a=b n'est pas une instruction d'affectation,

mais une expression de type logique (boolean)
boolean qui est vrai si les
deux valeurs a et b sont gales et fausse sinon

Maple n'value l'expression logique a=b que si on le demande

explicitement. Pour cela, on utilisera la commande evalb
exemple :
a:= 1; b:= 2;
> a=b;
1=2
> evalb (a=b);
false

2007/2008

Module I2, 1re anne S

67

Maple : instructions d'entres-sorties

print(var
print( ) permet d'afficher la valeur de la variable var (c'est l'quivalent de
crire en pseudo code). Si var n'a pas de valeur, Maple affiche le nom de la
variable

print(`chaine
`) permet d'afficher la chane de caractres qui est entre ` `
print(`

> a:=1: b:=2: print(`a vaut`,a, `et b vaut`,b);

a vaut ,1 et b vaut, 2

readstat permet de saisir des donnes partir du clavier (c'est l'quivalent

de lire en pseudo code)

Syntaxe: var:=readstat(`texte`)
Maple affiche le texte entre ` ` et
readstat
attend qu'on entre une valeur au clavier qui doit tre suivie de ; ou :

> n:=readstat(`entrez la valeur de n : `);

Remarque : il existe d'autres commandes pour les entres-sorties en Maple

2007/2008

Module I2, 1re anne S

68

Maple : syntaxe des tests

criture en pseudo code

Traduction en Maple

Si

if

condition
instructions

alors

Finsi

Si

condition
instructions 1
Sinon
instructions2
Finsi
2007/2008

condition
instructions

then

fi;

alors

if

condition
instructions1
else
instructions2
fi;

Module I2, 1re anne S

then

69

Maple : syntaxe des boucles

criture en pseudo code

Traduction en Maple

TantQue condition
instructions

while
condition
instructions

FinTantQue

od;
od

Pour i allant de v1 v2 par pas p

instructions
FinPour

for i from v1 to v2 by p do
instructions
od;

2007/2008

Module I2, 1re anne S

do

70

ALGORITHMIQUE

Fonctions et procdures

2007/2008

Module I2, 1re anne SMP/SMC

71

Fonctions et procdures

Certains problmes conduisent des programmes longs, difficiles

crire et comprendre. On les dcoupe en des parties appeles
sous-programmes ou modules

Les fonctions et les procdures sont des modules (groupe d'instructions)

indpendants dsigns par un nom. Elles ont plusieurs intrts :

permettent de "factoriser" les programmes,

programmes cd de mettre en commun
les parties qui se rptent

permettent une structuration et une meilleure lisibilit des programmes

2007/2008

facilitent la maintenance du code (il suffit de modifier une seule fois)

ces procdures et fonctions peuvent ventuellement tre rutilises dans
d'autres programmes
Module I2, 1re anne S

72

Fonctions

Le rle d'une fonction en programmation est similaire celui d'une

fonction en mathmatique : elle retourne un rsultat partir des
valeurs des paramtres

Une fonction s'crit en dehors du programme principal sous la forme :

Fonction nom_fonction (paramtres et leurs types) : type_fonction

Instructions constituant le corps de la fonction
retourne
FinFonction

Pour le choix d'un nom de fonction il faut respecter les mmes rgles que celles
pour les noms de variables
type_fonction est le type du rsultat retourn
L'instruction retourne sert retourner la valeur du rsultat

2007/2008

Module I2, 1re anne S

73

Fonctions : exemples

La fonction SommeCarre suivante calcule la somme des carres de

deux rels x et y :
Fonction SommeCarre (x : rel, y: rel ) : rel
variable z : rel
z x^2+y^2
retourne (z)
FinFonction

La fonction Pair suivante dtermine si un nombre est pair :

Fonction Pair (n : entier ) : boolen
retourne (n%2=0)
FinFonction

2007/2008

Module I2, 1re anne S

74

Utilisation des fonctions

L'utilisation d'une fonction se fera par simple criture de son nom

dans le programme principale. Le rsultat tant une valeur, devra
tre affect ou tre utilis dans une expression, une criture, ...

Exepmle :

Lors de l'appel Pair(3) le paramtre formel n est remplac par le

paramtre effectif 3

2007/2008

Algorithme exepmleAppelFonction
variables z : rel, b : boolen
Dbut
b Pair(3)
z 5*SommeCarre(7,2)+1
crire("SommeCarre(3,5)= ", SommeCarre(3,5))
Fin

Module I2, 1re anne S

75

Procdures

Dans certains cas, on peut avoir besoin de rpter une tache dans plusieurs
endroits du programme, mais que dans cette tache on ne calcule pas de
rsultats ou qu'on calcule plusieurs rsultats la fois

Dans ces cas on ne peut pas utiliser une fonction, on utilise une procdure

Une procdure est un sous-programme semblable une fonction mais qui

ne retourne rien

Une procdure s'crit en dehors du programme principal sous la forme :

Procdure nom_procdure (paramtres et leurs types)

Instructions constituant le corps de la procdure
FinProcdure

Remarque : une procdure peut ne pas avoir de paramtres

2007/2008

Module I2, 1re anne S

76

Appel d'une procdure

L'appel d'une procdure, se fait dans le programme principale ou dans une

autre procdure par une instruction indiquant le nom de la procdure :
Procdure exemple_proc ()

FinProcdure
Algorithme exepmleAppelProcdure
Dbut
exemple_proc ()

Fin

Remarque : contrairement l'appel d'une fonction, on ne peut pas affecter la

procdure appele ou l'utiliser dans une expression. L'appel d'une
procdure est une instruction autonome

2007/2008

Module I2, 1re anne S

77

Paramtres d'une procdure

Les paramtres servent changer des donnes entre le programme

principale (ou la procdure appelante) et la procdure appele

Les paramtres placs dans la dclaration d'une procdure sont appels

paramtres formels.
formels Ces paramtres peuvent prendre toutes les valeurs
possibles mais ils sont abstraits (n'existent pas rellement)

Les paramtres placs dans l'appel d'une procdure sont appels

paramtres effectifs.
effectifs ils contiennent les valeurs pour effectuer le
traitement

Le nombre de paramtres effectifs doit tre gal au nombre de paramtres

formels. L'ordre et le type des paramtres doivent correspondre

2007/2008

Module I2, 1re anne S

78

Transmission des paramtres

Il existe deux modes de transmission de paramtres dans les langages de
programmation :

La transmission par valeur : les valeurs des paramtres effectifs sont

affectes aux paramtres formels correspondants au moment de l'appel de la
procdure. Dans ce mode le paramtre effectif ne subit aucune modification

La transmission par adresse (ou par rfrence) : les adresses des

paramtres effectifs sont transmises la procdure appelante. Dans ce mode,
le paramtre effectif subit les mmes modifications que le paramtre formel lors
de l'excution de la procdure

Remarque : le paramtre effectif doit tre une variable (et non une valeur)
lorsqu'il s'agit d'une transmission par adresse

En pseudo-code, on va prciser explicitement le mode de transmission dans la

dclaration de la procdure

2007/2008

Module I2, 1re anne S

79

Transmission des paramtres : exemples

Procdure incrementer1 (x : entier par valeur, y : entier par adresse)
adresse
x x+1
y y+1
FinProcdure
Algorithme Test_incrementer1
Test_incrementer
variables n, m : entier
Dbut
n3
m3
incrementer1(n, m)
rsultat :
crire (" n= ", n, " et m= ", m)
n=3 et m=4
Fin
Remarque : l'instruction x x+1 n'a pas de sens avec un passage par valeur

2007/2008

Module I2, 1re anne S

80

Transmission par valeur, par adresse : exemples

Procdure qui calcule la somme et le produit de deux entiers :
Procdure SommeProduit (x,y: entier par valeur, som, prod : entier par adresse)
adresse
som x+y
prod x*y
FinProcdure

Procdure qui change le contenu de deux variabales :

Procdure Echange (x : rel par adresse, y : rel par adresse)
adresse
variables z : rel
zx
xy
yz
FinProcdure

2007/2008

Module I2, 1re anne S

81

Variables locales et globales (1)

On peut manipuler 2 types de variables dans un module (procdure ou

fonction) : des variables locales et des variables globales.
globales Elles se
distinguent par ce qu'on appelle leur porte (leur "champ de dfinition", leur
"dure de vie")

Une variable locale n'est connue qu' l'intrieur du module ou elle a t

dfinie. Elle est cre l'appel du module et dtruite la fin de son excution

Une variable globale est connue par l'ensemble des modules et le

programme principale. Elle est dfinie durant toute lapplication et peut tre
utilise et modifie par les diffrents modules du programme

2007/2008

Module I2, 1re anne S

82

Variables locales et globales (2)

La manire de distinguer la dclaration des variables locales et globales

diffre selon le langage

En gnral, les variables dclares l'intrieur d'une fonction ou

procdure sont considres comme variables locales

En pseudo-code, on va adopter cette rgle pour les variables locales et on

dclarera les variables globales dans le programme principale

Conseil : Il faut utiliser autant que possible des variables locales plutt que
des variables globales. Ceci permet d'conomiser la mmoire et d'assurer
l'indpendance de la procdure ou de la fonction

2007/2008

Module I2, 1re anne S

83

Fonctions et procdures en Maple (1)

En Maple, il n'y a pas de distinction entre les notions de fonction et

procdure. Les deux se dclarent de la mme faon comme suit :
identificateur:= proc (paramtres)
l1 , ..., l n
local
;
g 1 , ..., g k
global
;
instructions
rsultat
end;

Identificateur est le nom de la fonction ou de la procdure

En Maple, on prcise explicitement si les variables sont locales ou

globales par les mots cls local et global

2007/2008

Module I2, 1re anne S

84

Fonctions et procdures en Maple (2)

Une variable globale est connue en dehors de la procdure o elle a t

dfinie dans l'ensemble de la session de calcul

Les paramtres, les variables locales et globales sont facultatifs, ils peuvent
ne pas figurer dans la dclaration

Une procdure Maple peut rendre un seul rsultat (comme une fonction),
plusieurs rsultats ou aucun rsultat

Pour rendre plusieurs rsultats, on peut utiliser une liste, un ensemble, un

tableau (on verra ces structures la sance prochaine)

Le rsultat de la procdure est donn soit implicitement par la dernire

instruction, soit par la commande RETURN

RETURN ( v1 , ... , v n ) arrte le droulement de la procdure et renvoie les

valeurs de v1 , ... , v n sous forme d'une squence

2007/2008

Module I2, 1re anne S

85

Procdures Maple : remarques

Maple interdit la modification de la valeur d'un paramtre

l'intrieur d'une procdure (pas de transmission par adresse)

Aprs end; Maple affiche le texte de la procdure. Dans le cas o

end est suivi de : rien n'est affich
> carre:=proc(x,y)
> x^2+y^2;
> end;
carre:=proc (x, y) x^2+y^2 end proc

En Maple, une procdure peut tre appele sans tre affecte. Elle
peut aussi tre affecte une variable
> carre(1,2);
> a:=carre(3,3);

2007/2008

5
a := 18
Module I2, 1re anne S

86

Procdures Maple : exemples (1)

> exemple:=proc(a,b)
> local c,d,e;
> c:=a+b; d:=a-b; e:=a*b;
> RETURN(c,d,e);
> d:=c+e;
> end:
> exemple(4,7);

11, -3, 28

Remarque : l'excution s'arrte aprs RETURN. L'instruction d:=c+e n'est

pas excute, le rsultat est donn sous forme d'une squence

2007/2008

Module I2, 1re anne S

87

Procdures Maple : exemples (2)

Exemple : procdure qui calcule la somme des n premiers entiers
> somme:=proc()
> local n,i,som;
> som:=0;
> n:=readstat(`entrez la valeur de n : `);
> for i from 1 to n do
> som:=som+i;
> od;
> print(`somme=`,som);
> end;
> somme();

2007/2008

sur l'cran apparat le message :

entrez la valeur de n :
si on entre 3, on obtient somme=,6
Module I2, 1re anne S

88

Rcursivit

Un module (fonction ou procdure) peut s'appeler lui-mme: on dit

que c'est un module rcursif

Tout module rcursif doit possder un cas limite (cas trivial) qui
arrte la rcursivit

Exemple : Calcul du factorielle

Fonction fact (n : entier ) : entier
Si (n=0) alors
retourne (1)
Sinon
retourne (n*fact(n-1))
n*fact(n-1)
Finsi
FinFonction

2007/2008

Module I2, 1re anne S

89

Fonctions rcursives : exercice

Ecrivez une fonction rcursive (puis itrative) qui calcule le terme n

de la suite de Fibonacci dfinie par :
U(0)=U(1)=1
U(n)=U(n-1)+U(n-2)
Fonction Fib (n : entier ) : entier
Variable res : entier
Si (n=1 OU n=0) alors
res 1
Sinon
res Fib(n-1)+Fib(n-2)
Finsi
retourne (res)
FinFonction

2007/2008

Module I2, 1re anne S

90

Fonctions rcursives : exercice (suite)

Une fonction itrative pour le calcul de la suite de Fibonacci :

Fonction Fib (n : entier ) : entier
Variables i, AvantDernier, Dernier, Nouveau : entier
Si (n=1 OU n=0) alors
retourne (1)
Finsi
AvantDernier 1, Dernier 1
Pour i allant de 2 n
Nouveau Dernier+ AvantDernier
AvantDernier Dernier
Dernier Nouveau
FinPour
retourne (Nouveau)
FinFonction

Remarque: la solution rcursive est plus facile crire

2007/2008

Module I2, 1re anne S

91

Procdures rcursives : exemple

Une procdure rcursive qui permet d'afficher la valeur binaire d'un entier n

Procdure binaire (n : entier )

Si (n<>0) alors
binaire (n/2)
crire (n mod 2)
Finsi
FinProcdure

2007/2008

Module I2, 1re anne S

92

ALGORITHMIQUE

Les tableaux

2007/2008

Module I2, 1re anne SMP/SMC

93

Exemple introductif

Supposons qu'on veut conserver les notes d'une classe de 30 tudiants pour
extraire quelques informations. Par exemple : calcul du nombre d'tudiants
ayant une note suprieure 10

Le seul moyen dont nous disposons actuellement consiste dclarer 30

variables, par exemple N1, , N30.
N30 Aprs 30 instructions lire, on doit crire
30 instructions Si pour faire le calcul

nbre 0
Si (N1 >10) alors nbre nbre+1 FinSi
.
Si (N30>10) alors nbre nbre+1 FinSi
c'est lourd crire
Heureusement, les langages de programmation offrent la possibilit de
rassembler toutes ces variables dans une seule structure de donne
appele tableau

2007/2008

Module I2, 1re anne S

94

Tableaux

Un tableau est un ensemble d'lments de mme type dsigns par

un identificateur unique

Une variable entire nomme indice permet d'indiquer la position

d'un lment donn au sein du tableau et de dterminer sa valeur

La dclaration d'un tableau s'effectue en prcisant le type de ses

lments et sa dimension (le nombre de ses lments)

En pseudo code :

variable tableau identificateur[dimension] : type

Exemple :

variable tableau notes[30] : rel

On peut dfinir des tableaux de tous types : tableaux d'entiers, de

rels, de caractres, de boolens, de chanes de caractres,

2007/2008

Module I2, 1re anne S

95

Tableaux : remarques

L'accs un lment du tableau se fait au moyen de l'indice. Par exemple,

notes[i] donne la valeur de l'lment i du tableau notes

Selon les langages, le premier indice du tableau est soit 0, soit 1. Le plus
souvent c'est 0 (c'est ce qu'on va adopter en pseudo-code). Dans ce cas,
notes[i] dsigne l'lment i+1 du tableau notes

Il est possible de dclarer un tableau sans prciser au dpart sa dimension.

Cette prcision est faite ultrieurement
.

Par exemple, quand on dclare un tableau comme paramtre d'une procdure, on

peut ne prciser sa dimension qu'au moment de l'appel

En tous cas, un tableau est inutilisable tant quon na pas prcis le nombre de ses
lments

Un grand avantage des tableaux est qu'on peut traiter les donnes qui y sont
stockes de faon simple en utilisant des boucles

2007/2008

Module I2, 1re anne S

96

Tableaux : exemples (1)

Pour le calcul du nombre d'tudiants ayant une note suprieure

10 avec les tableaux, on peut crire :
Variables

i ,nbre : entier
tableau notes[30] : rel

Dbut
nbre 0
Pour i allant de 0 29
Si (notes[i] >10) alors
nbre nbre+1
FinSi
FinPour
crire ("le nombre de notes suprieures 10 est : ", nbre)
Fin
2007/2008

Module I2, 1re anne S

97

Tableaux : saisie et affichage

Procdures qui permettent de saisir et d'afficher les lments d'un tableau :

Procdure SaisieTab(n : entier par valeur, tableau T : rel par rfrence )
variable i: entier
Pour i allant de 0 n-1
crire ("Saisie de l'lment ", i + 1)
lire (T[i] )
FinPour
Fin Procdure
Procdure AfficheTab(n : entier par valeur, tableau T : rel par valeur )
variable i: entier
Pour i allant de 0 n-1
crire ("T[",i, "] =", T[i])
FinPour
Fin Procdure

2007/2008

Module I2, 1re anne S

98

Tableaux : exemples d'appel

Algorithme principale o on fait l'appel des procdures SaisieTab et

AfficheTab :
Algorithme Tableaux
variable p : entier
tableau A[10] : rel
Dbut
p 10
SaisieTab(p, A)
AfficheTab(10,A)
Fin

2007/2008

Module I2, 1re anne S

99

Tableaux : fonction longueur

La plus part des langages offrent une fonction longueur qui donne la dimension
du tableau. Les procdures Saisie et Affiche peuvent tre rcrites comme suit :
Procdure SaisieTab( tableau T : rel par rfrence )
variable i: entier
Pour i allant de 0 longueur(T)-1
longueur(T)crire ("Saisie de l'lment ", i + 1)
lire (T[i] )
FinPour
Fin Procdure
Procdure AfficheTab(tableau T : rel par valeur )
variable i: entier
Pour i allant de 0 longueur(T)-1
longueur(T)
crire ("T[",i, "] =", T[i])
FinPour
Fin Procdure

2007/2008

Module I2, 1re anne S

100

Tableaux : syntaxe Maple

En Maple, un tableau se dfinit en utilisant le type array comme suit :

identificateur:= array (a..b)

Identificateur est le nom du tableau

a et b sont les bornes de l'indice du tableau

Il est possible d'entrer directement toutes les valeurs d'un tableau .

Exemple:

> A:=array(1..4,[5,8,1,7]);

Il est galement possible de les entrer un par un comme suit :

Exemple :
> T:=array(1..3);
> T[1]:=1: T[2]:=3: T[3]:=5:

Pour afficher tous les lments d'un tableau, il suffit d'utiliser la commande
print > print(T);
[1, 3, 5]

2007/2008

Module I2, 1re anne S

101

Tableaux en malpe : exemple

Une procdure qui calcule la moyenne des lments d'un tableau :

> moyenne:=proc(n,T)
> local i,s;
> s:=0;
> for i from 1 to n do
> s:=s+T[i];
> od;
> s/n;
> end;
> A:=array(1..4,[5,8,1,7]);
> moyenne(4,A);

2007/2008

rsultat : 21/4

Module I2, 1re anne S

102

Tableaux deux dimensions

Les langages de programmation permettent de dclarer des

tableaux dans lesquels les valeurs sont repres par deux indices.
indices
Ceci est utile par exemple pour reprsenter des matrices

En pseudo code, un tableau deux dimensions se dclare ainsi :

variable tableau identificateur[dimension1] [dimension2] : type

Exemple : une matrice A de 3 lignes et 4 colonnes dont les lments

sont rels

variable tableau A[3][4] : rel

A[i][j] permet d'accder llment de la matrice qui se trouve

lintersection de la ligne i et de la colonne j

2007/2008

Module I2, 1re anne S

103

Exemples : lecture d'une matrice

Procdure qui permet de saisir les lments d'une matrice :

Procdure SaisieMatrice(n : entier par valeur, m : entier par valeur ,
tableau A : rel par rfrence )
Dbut
variables i,j : entier
Pour i allant de 0 n-1
crire ("saisie de la ligne ", i + 1)
Pour j allant de 0 m-1
crire ("Entrez l'lment de la ligne ", i + 1, " et de la colonne ", j+1)
lire (A[i][j])
FinPour
FinPour
Fin Procdure

2007/2008

Module I2, 1re anne S

104

Exemples : affichage d'une matrice

Procdure qui permet d'afficher les lments d'une matrice :

Procdure AfficheMatrice(n : entier par valeur, m : entier par valeur
,tableau A : rel par
valeur )
Dbut
variables i,j : entier
Pour i allant de 0 n-1
Pour j allant de 0 m-1
crire ("A[",i, "] [",j,"]=", A[i][j])
FinPour
FinPour
Fin Procdure

2007/2008

Module I2, 1re anne S

105

Exemples : somme de deux matrices

Procdure qui calcule la somme de deux matrices :

Procdure SommeMatrices(n, m : entier par valeur,
tableau A, B : rel par valeur , tableau C : rel par rfrence )
Dbut
variables i,j : entier
Pour i allant de 0 n-1
Pour j allant de 0 m-1
C[i][j] A[i][j]+B[i][j]
FinPour
FinPour
Fin Procdure

2007/2008

Module I2, 1re anne S

106

Appel des procdures dfinies sur les matrices

Exemple d'algorithme principale o on fait l'appel des procdures dfinies
prcdemment pour la saisie, l'affichage et la somme des matrices :

Algorithme Matrices
variables tableau M1[3][4],M2 [3][4],M3 [3][4] : rel
Dbut
SaisieMatrice(3, 4, M1)
SaisieMatrice(3, 4, M2)
AfficheMatrice(3,4, M1)
AfficheMatrice(3,4, M2)
SommeMatrice(3, 4, M1,M2,M3)
AfficheMatrice(3,4, M3)
Fin
2007/2008

Module I2, 1re anne S

107

Matrices : syntaxe Maple

Pour dfinir une matrice en Maple, on peut utiliser le type array ou le type
matrix comme suit :

identificateur:= array (a1..b1, a2..b2)

identificateur:= matrix(n, m)

a1 et b1 sont les bornes du premier indice du tableau

a2 et b2 sont les bornes du deuxime indice du tableau
n est le nombre de lignes et m le nombre de colonnes

Il est possible d'entrer directement toutes les valeurs d'une matrice

Exemple:

> A:=matrix(2, 3, [ [7,0,1], [2,4,3]] );

Le type matrix est disponible dans le package linalg.

linalg Il faut donc charger ce
package avec la commande with(linalg) avant d'utiliser ce type

2007/2008

Module I2, 1re anne S

108

Tableaux : 2 problmes classiques

Recherche dun lment dans un tableau

Recherche squentielle
Recherche dichotomique

Tri d'un tableau

2007/2008

Tri par slection

Tri rapide

Module I2, 1re anne S

109

Recherche squentielle

Recherche de la valeur x dans un tableau T de N lments :

Variables i: entier, Trouv : boolen

i0 , Trouv Faux
TantQue (i < N) ET (Trouv=Faux)
Si (T[i]=x) alors
Trouv Vrai
Sinon
ii+1
FinSi
FinTantQue
Si Trouv alors
// c'est quivalent crire Si Trouv=Vrai alors
crire ("x appartient au tableau")
Sinon
crire ("x n'appartient pas au tableau")
FinSi

2007/2008

Module I2, 1re anne S

110

Recherche squentielle (version 2)

Une fonction Recherche qui retourne un boolen pour indiquer si une valeur
x appartient un tableau T de dimension N.
x , N et T sont des paramtres de la fonction

Fonction Recherche(x : rel, N: entier, tableau T : rel ) : boolen

Variable i: entier
Pour i allant de 0 N-1
Si (T[i]=x) alors
retourne (Vrai)
FinSi
FinPour
retourne (Faux)
FinFonction
2007/2008

Module I2, 1re anne S

111

Notion de complexit d'un algorithme

Pour valuer lefficacit d'un algorithme, on calcule sa complexit

Mesurer la complexit revient quantifier le temps d'excution et l'espace

mmoire ncessaire

Le temps d'excution est proportionnel au nombre des oprations

effectues. Pour mesurer la complexit en temps, on met en vidence
certaines oprations fondamentales, puis on les compte

Le nombre d'oprations dpend gnralement du nombre de donnes

traiter. Ainsi, la complexit est une fonction de la taille des donnes. On
s'intresse souvent son ordre de grandeur asymptotique

En gnral, on s'intresse la complexit dans le pire des cas et la

complexit moyenne

2007/2008

Module I2, 1re anne S

112

Recherche squentielle : complexit

Pour valuer lefficacit de l'algorithme de recherche squentielle, on va

calculer sa complexit dans le pire des cas. Pour cela on va compter le
nombre de tests effectus

Le pire des cas pour cet algorithme correspond au cas o x n'est pas dans
le tableau T

Si x nest pas dans le tableau, on effectue 3N tests : on rpte N fois les

tests (i < N), (Trouv=Faux) et (T[i]=x)

La complexit dans le pire des cas est d'ordre N,

N (on note O(N))
O(N)

Pour un ordinateur qui effectue 106 tests par seconde on a :

2007/2008

103

106

109

temps

1ms

1s

16mn40s

Module I2, 1re anne S

113

Recherche dichotomique

Dans le cas o le tableau est ordonn, on peut amliorer l'efficacit

de la recherche en utilisant la mthode de recherche dichotomique

Principe : diviser par 2 le nombre d'lments dans lesquels on

cherche la valeur x chaque tape de la recherche. Pour cela on
compare x avec T[milieu] :

2007/2008

Si x < T[milieu], il suffit de chercher x dans la 1re moiti du tableau

entre (T[0] et T[milieu-1])

Si x > T[milieu], il suffit de chercher x dans la 2me moiti du tableau

entre (T[milieu+1] et T[N-1])

Module I2, 1re anne S

114

Recherche dichotomique : algorithme

inf0 , supN-1, Trouv Faux
TantQue (inf <=sup) ET (Trouv=Faux)
milieu(inf+sup)div2
Si (x=T[milieu]) alors
Trouv Vrai
SinonSi (x>T[milieu]) alors
infmilieu+1
Sinon
supmilieu-1
FinSi
FinSi
FinTantQue
Si Trouv alors crire ("x appartient au tableau")
Sinon crire ("x n'appartient pas au tableau")
FinSi

2007/2008

Module I2, 1re anne S

115

Exemple d'excution

Considrons le tableau T :

Si la valeur cherch est 20 alors les indices inf, sup et milieu vont voluer
comme suit :

10 15 17 18 24 27 30

inf

sup

milieu

Si la valeur cherch est 10 alors les indices inf, sup et milieu vont voluer
comme suit :

2007/2008

inf

sup

milieu

Module I2, 1re anne S

116

Recherche dichotomique : complexit

La complexit dans le pire des cas est d'ordre log 2 N

L'cart de performances entre la recherche squentielle et la recherche

dichotomique est considrable pour les grandes valeurs de N

2007/2008

Exemple: au lieu de N=1milion 220 oprations effectuer avec une

recherche squentielle il suffit de 20 oprations avec une recherche
dichotomique

Module I2, 1re anne S

117

Tri d'un tableau

Le tri consiste ordonner les lments du tableau dans lordre

croissant ou dcroissant

Il existe plusieurs algorithmes connus pour trier les lments dun

tableau :

Le tri par slection

Le tri par insertion
Le tri rapide

Nous verrons dans la suite l'algorithme de tri par slection et

l'algorithme de tri rapide. Le tri sera effectu dans l'ordre croissant

2007/2008

Module I2, 1re anne S

118

Tri par slection

Principe : l'tape i, on slectionne le plus petit lment parmi les

(n - i +1) lments du tableau les plus droite. On l'change ensuite avec
l'lment i du tableau

9
4
1
7
3
Exemple :
tape 1: on cherche le plus petit parmi les 5 lments du tableau. On
lidentifie en troisime position, et on lchange alors avec llment 1 :
1

2007/2008

tape 2: on cherche le plus petit lment, mais cette fois partir du

deuxime lment. On le trouve en dernire position, on l'change avec
1
3
9
7
4
le deuxime:

tape 3:

Module I2, 1re anne S

9
119

Tri par slection : algorithme

Supposons que le tableau est not T et sa taille N

Pour i allant de 0 N-2

indice_ppe i
Pour j allant de i + 1 N-1
Si T[j] <T[indice_ppe] alors
indice_ppe j
Finsi
FinPour
temp T[indice_ppe]
T[indice_ppe] T[i]
T[i] temp
FinPour
2007/2008

Module I2, 1re anne S

120

Tri par slection : complexit

Quel que soit l'ordre du tableau initial, le nombre de tests et d'changes

reste le mme

On effectue N-1 tests pour trouver le premier lment du tableau tri, N-2
tests pour le deuxime, et ainsi de suite. Soit : (N-1)+(N-2)++1 = N(N-1)/2
On effectue en plus (N-1) changes.

La complexit du tri par slection est d'ordre N la fois dans le meilleur

des cas, en moyenne et dans le pire des cas

Pour un ordinateur qui effectue 106 tests par seconde on a :

2007/2008

103

106

109

temps

1s

11,5 jours

32000 ans

Module I2, 1re anne S

121

Tri rapide

Le tri rapide est un tri rcursif bas sur l'approche "diviser pour rgner"
(consiste dcomposer un problme d'une taille donne des sous problmes
similaires mais de taille infrieure faciles rsoudre)

Description du tri rapide :

2007/2008

1) on considre un lment du tableau qu'on appelle pivot

2) on partitionne le tableau en 2 sous tableaux : les lments infrieurs ou

gaux pivot et les lments suprieurs pivot. on peut placer ainsi la
valeur du pivot sa place dfinitive entre les deux sous tableaux

3) on rpte rcursivement ce partitionnement sur chacun des sous

tableaux cres jusqu' ce qu'ils soient rduits un un seul lment

Module I2, 1re anne S

122

Procdure Tri rapide

Procdure TriRapide(tableau T : rel par adresse, p,r:
p,r entier par valeur)
variable q: entier
Si p <r alors
Partition(T,p,r,q)
TriRapide(T,p,q-1)
TriRapide(T,q+1,r)
FinSi
Fin Procdure
A chaque tape de rcursivit on partitionne un tableau T[p..r] en deux sous
tableaux T[p..q-1] et T[q+1..r] tel que chaque lment de T[p..q-1] soit
infrieur ou gal chaque lment de A[q+1..r] . L'indice q est calcul
pendant la procdure de partitionnement
2007/2008

Module I2, 1re anne S

123

Procdure de partition
Procdure Partition(tableau T : rel par adresse, p,r:
p,r entier par valeur,
q: entier
par adresse )
Variables i, j: entier
pivot: rel
pivot T[p], ip+1, j r
TantQue (i<=j)
TantQue (i<=r et T[i] <=pivot) i i+1 FinTantQue
TantQue (j>=p et T[j] >pivot ) j j-1 FinTantQue
Si i <j alors
Echanger(T[i], T[j]), i i+1, j j-1
FinSi
FinTantQue
Echanger(T[j], T[p])
qj
Fin Procdure

2007/2008

Module I2, 1re anne S

124

Tri rapide : complexit et remarques

La complexit du tri rapide dans le pire des cas est en O(N)

La complexit du tri rapide en moyenne est en O(N log N)

Le choix du pivot influence largement les performances du tri rapide

Le pire des cas correspond au cas o le pivot est chaque choix le plus petit
lment du tableau (tableau dj tri)

diffrentes versions du tri rapide sont proposs dans la littrature pour rendre
le pire des cas le plus improbable possible, ce qui rend cette mthode la plus
rapide en moyenne parmi toutes celles utilises

2007/2008

Module I2, 1re anne S

125