Problème :

Jeux pédagogique (gestion des ressources)

Aider les deux nobles paysans Ahmed et Ali de partager leur huile d’olive en deux quantités égaux dans les conditions suivantes :

​

• Quantité : 8 litres;
• Resource : 1 bidon de 8L;

1 bidon de 5L;

1 bidon de 3L.

• situation : le bidon de 8L est complètement remplit et les autres sont vides;
• Question : Ecrire les étapes a suivre afin de partager l’huile.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

1

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

2

Résolution du jeux :

La situation actuel est : B8←8L, B5←0L, B3←0L.

​

La situation souhaite est : B8←4L, B5←4L, B3←0L.

• B8←8L, B5←0L, B3←0L;

​

• B8←3L, B5←5L, B3←0L;

​

• B8←3L, B5←2L, B3←3L;

​

• B8←6L, B5←2L, B3←0L;

​

• B8←6L, B5←0L, B3←2L;

​

• B8←1L, B5←5L, B3←2L;

​

• B8←1L, B5←4L, B3←3L;

​

• B8←4L, B5←4L, B3←0L.

Résolution du jeux :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

3

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

4

Enoncé du problème

Cahier des charges

Algorithme

Programmation

Résultats

Etapes de réalisation d’un programme

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

5

• Intérêt :

séparation analyse/codage (pas de préoccupation de syntaxe)

•  Qualités :
• Exact (fournit le résultat souhaité) ;
• Efficace (temps d’exécution, mémoire occupée) ;
• Clair (compréhensible) ;
• Général (traite le plus grand nombre de cas possibles) ;
• …

• Une bonne connaissance de l’algorithmique permet d’écrire des algorithmes exacts et efficaces

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

6

Notion d’algorithme

I) Définition de l’algorithme :

Un algorithme est une suite d’actions appliquées sur des données dans un ordre logique afin d’obtenir des résultats.

Exemple :

Réaliser une opération de calcule grâce à la calculatrice, tel que 2+7 :

Début

• Allumer la calculatrice
• Taper la touche ❷
• Taper la touche +
• Taper la touche ❼
• Taper la touche =
• Puis on obtient le résultat 9 à l’écran

Fin

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

7

Remarque :

La résolution d’un problème se fait par la méthode suivante(analyse) :

• Déterminer les données (entrés) ;
• Déterminer le résultat (sortie) ;
• Déterminer le processus de transformation des données en résultat (traitement).

Exercice d’application :

Calculer la somme de deux nombres réels.

• L’analyse :

• Les données fournies :

Deux nombre réel A et B

• Le résultat désiré :

La somme S de deux nombres

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

8

• Le processus de transformation des données en résultat :

Additionner les deux nombres A et B pour obtenir le résultat S

II) Notion de données  :

Une constante est une donnée fixe qui ne varie pas tout le long de l’algorithme.

Exemples :

Pi (π)=3,14 ; g=9,81 N/g ;R=8,31 SI ; Na=6,02 10²³  ; e=1,6 10^-19

1) Les constantes :

Une variable est le nom d’un espace mémoire (case mémoire) dont le contenu peut changer pendant l’exécution d’un algorithme.

2) Les variables :

Exemples :

Nom_eleve ; note_eleve ; Prix_unitaire ; x ; nom4

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

9

3) Les caractéristiques d’une donnée :

Pour définir une donnée il faut préciser les éléments suivants :

• Le nom de la donnée (identificateur)  ;
• Le type de donnée (caractère, chaîne de caractères, entier, réel, booléen, …) ;
• La nature de la donnée (constante, variable).

Règles :

• Les données (variables et constantes) doivent être déclarées avant d’être utilisées ;

• Le choix des noms de variables est soumis à quelques règles :

• Un nom doit commencer par une lettre alphabétique ;

• Doit être constitué uniquement de lettres, de chiffres et du soulignement _ (Eviter les caractères de ponctuation et les espaces) ;

• Doit être différent des mots réservés du langage ;

• La longueur du nom doit être inférieure à la taille maximale spécifiée par le langage utilisé ;

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

10

Conseil :

Pour la lisibilité du code choisir des noms significatifs qui décrivent les données manipulées.

Remarque :

En pseudo-code algorithmique, on va respecter les règles citées, même si on est libre dans la syntaxe.

Rappel :

• Toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable ;

• En pseudo-code, on va adopter la forme suivante pour la déclaration de variables :

Variables liste d'identificateurs : type

Exemples :

Variables i, j,k : entier

x, y : réel

OK : booléen

ch1, ch2 : chaîne de caractères

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

11

Remarques :

Deux valeurs VRAI ou FAUX, TRUE ou FALSE, 0 ou 1.

• Le type d’une variable détermine l’ensemble des valeurs qu’elle peut prendre, les types offerts par la plupart des langages sont:  

Type numérique (entier ou réel) :

Type logique ou booléen :

• Entier court (codé sur 2 octets) ;
• Entier long (codé sur 4 ou 8 octets) ;
• Réel simple précision (codé sur 4 octets) ;
• Réel double précision (codé sur 8 octets).

Lettres majuscules, minuscules, chiffres, symboles, ….

Type caractère :

Type chaîne de caractère :

Toute suite de caractères.

Exemples :

’A’, ’a’, ’1’, ’?’, …

Exemples :

"Nom, Prénom", "code postale:1000", "CPGE ", …

• Pour le type numérique on va se limiter aux entiers et réels sans considérer les sous types. 

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

12

1) Instruction de lecture :

III) Les instructions de base  :

Cette instruction permet de lire les données à travers le clavier, appelée également Instruction d’entrée.

L’instruction de lecture est notée :

Syntaxe :

Lire (Variable)

Exemples :

Lire (Note_eleve4) ; Lire (x) ; Lire (A8)

2) Instruction d’écriture :

Cette instruction permet d’afficher un message, le contenu d’une variable et/ou le résultat d’une opération de calcul, appelée aussi Instruction de sortie.

L’instruction d’écriture est représentée par :

Syntaxe :

Ecrire (Variable) ; Ecrire ("message") ; Ecrire (opération de calcul)

Exemples :

Ecrire (Note_eleve4) ; Ecrire ("Bonjour") ; Ecrire ((Note_eleve4+x)/3) ; Ecrire (x,A8,x+A8)

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

13

3) L’affectation (Assignation) :

Cette instruction permet d’attribuer une valeur à une variable, elle est représentée par une flèche dirigée vers la gauche "←".

Syntaxe :

Variable ← valeur, une autre variable ou bien une expression

Exemples :

X ← 12

X ← Y+4

Y ← X

12

X

Y+4

12

12

16

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

14

Exercice1 :

Donnez les valeurs des variables A, B et C après exécution des instructions suivantes ?

• Algorithme :

Algorithme Affectation1

Variables A, B, C : Entier

Debut

A←3

B←7

A←B

B←A+5

C←A+B

C←B-A

Ecrire (A,B,C)

Fin

• Version1 :

Algorithme Affectation2

Variables A, B : Entier

Debut

A←1

B←2

A←B

B←A

Ecrire (A,B)

Fin

• Version2 :

Les deux dernières instructions (Version2) permettent-elles d’échanger les valeurs de A et B ?

Exercice2 :

Ecrire un algorithme permettant d’échanger les valeurs de deux variables A et B

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

15

• La transformation des données en résultat :

Appliquer la relation qui donne la moyenne de deux nombres.

• Algorithme :

• Version1 :

Algorithme Moyenne1

Variables A, B, C : Réel

Debut

Lire (A)

Lire (B)

C ← (A+B)/2

Ecrire (C)

Fin

L’en-tête

Les déclarations

Le corps

Algorithme Moyenne1

Variables A, B, C : Réel

Debut

Lire (A,B)

C ← (A+B)/2

Ecrire (C)

Fin

Exercice d’application :

Ecrire un algorithme qui permet de lire deux nombres réels et d’afficher leur moyenne.

• L’analyse du problème :

• Les données fournies :

Deux nombres réels

• Le résultat désiré :

La moyenne des deux nombres réels

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

16

Algorithme Moyenne2

Variables A, B, C : Réel

Debut

Ecrire ("Donner la valeur de A")

Lire (A)

Ecrire ("Donner la valeur de B")

Lire (B)

C ← (A+B)/2

Ecrire ("La moyenne de A et B est :",C)

Fin

L’en-tête

Les déclarations

Le corps

• Version2 :

Algorithme Moyenne2

Variables A, B, C : Réel

Debut

Ecrire ("Donner la valeur de A et de B")

Lire (A,B)

C ← (A+B)/2

Ecrire ("La moyenne de A et B est :",C)

Fin

Ou bien :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

17

Remarques :

• Par convention, l’algorithme note certains des opérateurs différemment :

• Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est le suivant

(du plus prioritaire au moins prioritaire) :

• ^ (la puissance) ;
• * , / (multiplication, division) ;
• mod (modulo) ;
• + , - (addition, soustraction).

2 + 3 * 7 vaut 23

Exemples :

• En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer les opérations

à effectuer en priorité :

Exemples :

(2 + 3) * 7 vaut 35

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

18

Langages informatiques

I) Définition :

Un langage informatique est un outil permettant de donner des ordres (instructions) à la machine.

Définition :

II) Langage machine :

• Intérêt : écrire des programmes (suite consécutive d’instructions) destinés à effectuer une tâche donnée ;

• Contrainte : être compréhensible par la machine.

• Langage binaire : l’information est exprimée et manipulée sous forme d’une suite de bits ;

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

• Une combinaison de 8 bits= 1 Octet 🡺 2⁸=256 possibilités qui permettent de coder tous les caractères alphabétiques, numériques, et symboles tels que ?,*,&, … ;

• Les opérations logiques et arithmétiques de base (addition, multiplication, …) sont effectuées en binaire.

• Le code ASCII (American Standard Code for Information Interchange) donne les correspondances entre les caractères alphanumériques et leurs représentations binaires.

Exemple :

A= 01000001

?=00111100

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

19

II) Langage haut niveau :

• Intérêts multiples pour le langage haut niveau :

• Nécessite un traducteur (compilateur/interpréteur) ;

• Exécution plus ou moins lente selon le traducteur.

• Proche du langage humain «anglais» (compréhensible) ;

• Permet une plus grande portabilité (indépendant du matériel) ;

• Manipulation de données et d’expressions complexes (réels, objets, a*b/c, …).

• Compilateur : traduire le programme entier une fois pour toutes :

1) Compilateur/interpréteur :

• + plus rapide à l’exécution ;

• + sécurité du code source ;

• - il faut recompiler à chaque modification.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

20

• Interpréteur : traduire au fur et à mesure les instructions du programme à chaque exécution.

• + exécution instantanée appréciable pour les débutants ;

• - exécution lente par rapport à la compilation.

Un langage de programmation est un langage informatique composé d’un ensemble d’instructions pouvant être traduites et exécutées par un ordinateur.

Exemple :

Basic, Pascal, COBOL, Fortaran, C, C⁺⁺, LOGO, Python,…

A) Définition d’un langage de programmation :

1) Langages python (Code python) :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

21

B) Définition d’un programme :

Un programme est une suite ordonnée d’instructions, compréhensibles par l’ordinateur, appliqué à des données afin d’obtenir des résultats.

C) L’identificateur :

Un identificateur en langage python doit débuter par une lettre suivie par un nombre de lettres ou de chiffres.

x, max, val4

Exemple :

D) Les types de données :

• Le type entier :

Pas de valeur limite explicite, correspond au moins au long int du C (-2⁶³ à 2⁶³ ).

• Le type réel :

Correspond au double du C (-1.7 10³⁰⁸ à +1.7 10³⁰⁸) .

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

22

• Le type chaine de caractères :

Ce type sert à manipuler les caractères.

• Le type booléen :

Ce type prend la valeur False pour faux et la valeur True pour vrai.

C) Les instructions :

i) l’instruction d’entrée :

L’instruction de lecture est symbolisée par input, elle permet le transfert des données vers la mémoire centrale .

Syntaxe :

l’identificateur=input() 

ii) l’instruction de sortie  :

L’écriture se fait de façon semblable que la lecture à l’aide de l’instruction print.

Syntaxe :

print(l’identificateur)

Exemple :

x=input() 

Exemple :

print(x) 

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

23

iii) l’instruction d’affectation :

Cette instruction permet de mettre une valeur dans une variable. Le symbole de l’affectation est =

Syntaxe :

variable = valeur

Remarques :

• print permet d’afficher un texte.

• Les codes de format :

Exemple :

x=4 

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

24

Résultats

Enoncé du problème

Cahier des charges

Algorithme

Programme source

Interprétation et Exécution

Etapes de réalisation d’un programme

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

25

Structures de contrôle de base

I) Structure séquentielle :

La structure séquentielle est une suite d’instructions qui s’exécute l’une après l’autre dès le début jusqu'à la fin dans un algorithme.

Exemple :

Calcul de la moyenne des deux nombres réels A et B.

Définition :

(Algorithme et Programmation)

Langage python

​

# Programme Moyenne

A=input('Donner A:')

B=input('Donner B:')

A=float(A)

B=float (B)

Moyenne=(A+B)/2

print("La moyenne de",A,"et",B,"=",Moyenne)

Algorithme

​

Algorithme Moyenne

Variables A, B, Moyenne : Réel

Debut

Ecrire ("Donner la valeur de A")

Lire (A)

Ecrire ("Donner la valeur de B")

Lire (B)

Moyenne ← (A+B)/2

Ecrire ("La moyenne de A et B est :", Moyenne )

Fin

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

26

1) Définition :

II) Structure alternative :

La structure alternative permet d’exécuter un bloc d’instructions ou un autre en fonction de la réponse de la condition.

Langage python

​

if condition: ou if condition:

Instruction Instructions

Algorithme

​

Si condition alors

Instruction ou suite d'instructions

Finsi

2) Structure alternative simple :

Cette structure permet d’effectuer certaines opérations ou au contraire de ne rien faire.

Syntaxe :

Si la condition est vérifiée alors le bloc d’instructions serait exécuté, sinon il serait ignoré.

Cette instruction se lit :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

27

Langage python

​

if Moyenne= =10:

print("Juste la moyenne")

Algorithme

​

Si Moyenne=10 alors

Ecrire ("Juste la moyenne")

Finsi

Remarques :

Exemple :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

28

Cette structure permet d’exécuter un bloc d’instructions ou un autre en fonction d’une condition.

Si la condition est vérifiée alors le bloc d’instructionsA sera exécuté et le bloc, d’instructionsB sera ignoré. Sinon le bloc d’instructionsB sera exécuté et le bloc d’instructionsA sera ignoré.

3) Structure alternative complète :

Cette instruction se lit :

Syntaxe :

Code python

​

if condition: ou if condition:

InstructionA InstructionsA

else : else :

InstructionB InstructionsB

Algorithme

​

Si condition alors

InstructionsA

Sinon

InstructionsB

Finsi

Exemple :

Langage python

if Moyenne= =10:

print("Juste la moyenne")

else :

print("La moyenne est différente de 10")

Algorithme

Si Moyenne=10 alors

Ecrire ("Juste la moyenne")

Sinon

Ecrire ("La moyenne est différente de 10")

Finsi

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

29

4) Structure alternative imbriquée  :

Cette structure est utilisée quand on a plus de deux conditions.

Syntaxe :

Algorithme

​

Si (condition1) alors

InstructionsA

Sinon

Si (condition2) alors

InstructionsB

Sinon

Si (condition3) alors

InstructionsC

Sinon

InstructionsD

Finsi

Finsi

Finsi

Langage python

​

if condition1:

InstructionsA

elif condition2:

InstructionsB

elif condition3:

InstructionC

else :

InstructionD

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

30

Algorithme

Si (Moyenne=10) alors

Ecrire ("Juste la moyenne")

Sinon

Si (Moyenne<10) alors

Ecrire ("La moyenne est inferieure à 10")

Sinon

Ecrire ("La moyenne est supérieure à 10")

Finsi

Finsi

Langage python

if Moyenne= =10 :

print("Juste la moyenne")

elif Moy<10 :

print("La moyenne est inferieure à 10")

else :

print("La moyenne est supérieure à 10")

​

Exemple1 :

Exemple2 :

Algorithme

Algorithme Temperature_eau

Variable Temperature : Entier

Debut

Ecrire ("Entrez la température de l’eau :")

Lire (Temperature)

Si (Temperature<=0) Alors

Ecrire ("C’est de la glace")

Sinon

Si (Temperature<=100) Alors

Ecrire ("C’est du liquide")

Sinon

Ecrire ("C’est du vapeur")

Finsi

Finsi

Fin

Langage python

# Programme Temperature Eau

Temperature=input('Entrez la température de l’eau:')

Temperature=int(Temperature)

if Temperature<=0 :

print("C’est de la glace")

elif Temperature<=100 :

print("C’est du liquide")

else :

print("C’est du vapeur")

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

31

Exemple3 :

Algorithme

Algorithme gestion_feu

Variable Couleur : caractere

Debut

Ecrire ("De quelle couleur est le feu?")

Lire (Couleur)

Si ((Couleur = ‘V’)OU(Couleur = ‘v’)) Alors

Ecrire ("Je passe")

Sinon

Si ((Couleur = ‘O’)OU(Couleur = ‘o’)) Alors

Ecrire ("Je ralentis")

Sinon

Si ((Couleur = ‘R’)OU(Couleur = ‘r’)) Alors

Ecrire ("Je m’arrête")

Sinon

Ecrire ("Cette couleur n’est pas une couleur de feu")

Finsi

Finsi

Finsi

Fin

Code python

​

# Programme Gestion Feu

Couleur=input('De quelle couleur est le feu?')

if Couleur= ='V' or Couleur= ='v':

print("Je passe")

elif Couleur= ='O' or Couleur= ='o':

print("Je ralentis")

elif Couleur= ='R' or Couleur= ='r':

print("Je m’arrête")

else:

print("Cette couleur n’est pas une couleur de feu")

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

32

5) Structure de choix :

Cette structure permet d’effectuer un choix parmi plusieurs cheminement proposés.

Syntaxe :

Algorithme

​

Selon que identificateur vaut

Valeur 1 faire Instructions 1

Valeur 2 faire Instructions 2

Valeur n faire Instructions n

Autrement que Instructions n+1

Finselon

Langage python

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

33

Exemple :

Algorithme

Algorithme gestion_feu1

Variable Couleur : caractere

Debut

Ecrire ("De quelle couleur est le feu?")

Lire (Couleur)

Selon que Couleur vaut

‘V’ ‘v’ faire Ecrire ("Je passe")

‘O’ ‘o’ faire Ecrire ("Je ralentis")

‘R’ ‘r’ faire Ecrire ("Je m’arrête")

Autrement que Ecrire ("Cette couleur n’est pas une couleur de feu")

Finselon

Fin

Code python

​

# Programme Gestion Feu

Couleur=input('De quelle couleur est le feu?')

if Couleur= ='V' or Couleur= ='v':

print("Je passe")

elif Couleur= ='O' or Couleur= ='o':

print("Je ralentis")

elif Couleur= ='R' or Couleur= ='r':

print("Je m’arrête")

else:

print("Cette couleur n’est pas une couleur de feu")

​

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

34

II) Instructions itératives (les boucles) :

Les boucles servent à répéter l'exécution d'un groupe d'instructions un certain nombre de fois.

Langage python

​

for compteur in range(initiale,finale+1,pas) :

  suite d'instructions

Algorithme

​

Pour compteur allant de initiale à finale par pas Faire

Instructions

FinPour

1) Les boucles Pour ou avec compteur :

On distingue trois sortes de boucles en langages de programmation.

Syntaxe :

• Les boucles Tant que ;

• Les boucles Jusqu’à ;

• Les boucles Pour ;

On y répète des instructions en faisant évoluer un compteur (variable particulière) entre une valeur initiale et une valeur finale.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

35

Exemple :

Langage python

​

# Programme Compteur

for i in range(1,6) :

print("La valeur de i=",i)

Algorithme

​

Algorithme Compteur

Variable i : entier

Debut

Pour i allant de 1 à 5 par pas 1 Faire

Ecrire (" La valeur de i est : " ,i)

FinPour

Fin

Algorigramme :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

36

• Pas peut ne pas être mentionné, car par défaut sa valeur est égal à 1. Dans ce cas, le nombre d'itérations est égal à finale - initiale+ 1 ;

• Initiale et finale peuvent être des valeurs, des variables définies avant le début de la boucle ou des expressions de même type que compteur.

Remarque :

• Le nombre d'itérations dans une boucle Pour est connu avant le début de la boucle ;

• Il faut éviter de modifier la valeur du compteur (et finale) à l'intérieur de la boucle. En effet, une telle action :

• perturbe le nombre d'itérations prévu par la boucle Pour ;

• rend difficile la lecture de l'algorithme ;

• présente le risque d'aboutir à une boucle infinie.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

37

Exemple :

Langage python

​

# Programme Compteur

for i in range(1,6) :

i=i-1

print("La valeur de i=",i)

Algorithme

​

Algorithme Compteur

Variable i : entier

Debut

i←0

Pour i allant de 1 à 5 Faire

i←i-1

Ecrire (" La valeur de i est : " ,i)

FinPour

Fin

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

38

Langage python

​

while condition :

  suite d'instructions

Algorithme

​

TantQue condition Faire

instructions

FinTantQue

2) Les boucles Tant que :

Syntaxe :

On y répète des instructions tant qu'une certaine condition est réalisée.

Exemple :

Langage python

# Programme Compteur

i=0

while i<6 :

print("La valeur de i=",i)

i=i+1

Algorithme

Algorithme Compteur

Variable i : entier

Debut

i←0

TantQue i<=5 Faire

Ecrire (" La valeur de i est : " ,i)

i←i+1

FinTantQue

Fin

i) boucle Tant que … Faire :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

39

Langage python

​

Algorithme

​

Faire

instructions

TantQue condition

Syntaxe :

Exemple :

Langage python

​

Algorithme

​

Algorithme Compteur

Variable i : entier

Debut

i←0

Faire

Ecrire (" La valeur de i est : " ,i)

i←i+1

TantQue i<=5

Fin

i) boucle Faire…Tant que :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

40

Algorigramme :

• La condition (dite condition de contrôle de la boucle) est évaluée avant chaque itération ;

• Tant que la condition est vraie, on exécute les actions ;

• Si la condition est fausse, on sort de la boucle et on exécute l'instruction qui est après FinTantQue.

Remarques :

• Le nombre d'itérations dans une boucle TantQue n'est pas connu au moment d'entrée dans la boucle. Il dépend 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 (après un certain nombre d'itérations), sinon le programme tourne indéfiniment ;

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

41

Exemple de boucle infinie  :

Attention aux boucles infinies !!!!

Langage python

​

# Programme Compteur

i=1

while i>0 :

print("La valeur de i=",i)

i=i+1

​

Algorithme

​

Algorithme Infinie

Variable i : entier

Debut

i ← 1

TantQue i>0 Faire

Ecrire("La valeur de i=",i)

i ← i+1

FinTantQue

Fin

• Si on peut déterminer le nombre d'itérations avant l'exécution de la boucle, il est plus naturel d'utiliser la boucle Pour ;

• S'il n'est pas possible de connaître le nombre d'itérations avant l'exécution de la boucle, on fera appel à TantQue.

Choix d'un type de boucle :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

42

Langage python

Algorithme

​

Faire

Instructions

Jusqua condition

Syntaxe :

Exemple :

Langage python

Algorithme

​

Algorithme Compteur

Variable i : entier

Debut

Faire

Ecrire (" La valeur de i est : " ,i)

Jusqua i>5

Fin

3) Boucle Faire…Jusqu’à :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

43

La boucle Pour est un cas particulier de TantQue (cas où le nombre d'itérations est connu et fixé). Tout ce qu'on peut écrire avec Pour peut être remplacé avec TantQue (la réciproque est fausse).

Lien entre Pour et TantQue :

Langage python

​

for compteur in range(initiale,finale+1,pas) :

  suite d'instructions

Algorithme

​

Pour compteur allant de initiale à finale par pas Faire

Instructions

FinPour

Peut être remplacé par :

Exemple :

Langage python

# Programme Compteur

compteur =initiale

while compteur <= finale :

  Instructions

compteur = compteur+1

Algorithme

Algorithme Compteur

Variable compteur : entier

Début

compteur ← initiale

TantQue compteur <= finale Faire

Instructions

compteur ← compteur+1

FinTantQue

Fin

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

44

Algorithme

Algorithme Boucle Imbriquée

Variable A,B,Moy : Reels

Reponse : caractère

Début

Reponse=‘o’

TantQue Reponse=‘O’ OU Reponse=‘o’ Faire

Ecrire (" Donner A et B :")

Lire(A,B)

Moy=(A+B)/2

Ecrire("La moyenne de ",A, "et",B, "est",Moy)

Si (Moy=10) alors

Ecrire ("Juste la moyenne")

Sinon

Si (Moy<10) alors

Ecrire ("La moyenne est inferieure à 10")

Sinon

Ecrire ("La moyenne est supérieure à 10")

Finsi

Finsi

Ecrire(" Voulez -Vous Continuer à exécuter ce programme? O/N ")

Lire(Reponse)

TantQue Reponse<>‘O’ ET Reponse<> ‘o’ ET Reponse<> ‘N’ ET Reponse<> ‘n’ Faire

Ecrire(" Donner une réponse O/N ")

Lire(Reponse)

FinTantQue

FinTantQue

Ecrire("Merci, Au revoir!!!!")

Fin

3) Boucle imbriquées  :

Les instructions d'une boucle peuvent être des instructions itératives. Dans ce cas, on aboutit à des boucles imbriquées.

Exemple :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

45

Langage python

# Programme Boucle Imbriquée

Reponse='o'

while Reponse=='o' or Reponse=='O' :

A=input('Donner A:')

B=input('Donner B:')

A=int(A)

B=int(B)

Moy=(A+B)/2

print('La moyenne de',A,'et',B,'est',Moy)

if Moy==10:

print("Juste la moyenne")

elif Moy<10:

print("La moyenne est inferieure à 10")

else:

print("La moyenne est supérieure à 10")

print(" Voulez -Vous Continuer à exécuter ce programme? O/N")

Reponse=input()

while Reponse!='o' and Reponse!='O' and Reponse!='N' and Reponse!='n':

print("Donner une réponse O/N")

Reponse=input()

print("Merci, Au revoir!!!!")

Imbrications autorisées

Imbrications interdites

Imbrications de boucles :

*

46

Ingénierie numérique et simulation-MPSI/TSI/PCSI

L’instruction break :

Elle sert à interrompre le déroulement d’une boucle.

L’instruction Continue :

Elle permet de passer au tour de boucle suivant.

47

Un algorithme qui détermine le premier nombre entier N tel que la somme de 1 à N dépasse strictement 100.

Algorithme

Algorithme somme2

Variables som, i : entier

Debut

som ← 0

i ← 1

TantQue (som <=100) Faire

     som ← som + i

i ← i+1

FinTantQue

Ecrire ("La valeur cherchée est N= ",i-1)

Fin

Langage python

# Programme Somme100

i=0

Som=0

while Som<=100:

Som=Som+i

i=i+1

print("La valeur cherchée est N =",i-1)

Exercice1 :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

48

Algorithme

​

Algorithme puissance

Variables x, puiss : réel

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 Faire

puiss← puiss*x

FinPour

Ecrire (x, " à la puissance ", n, " est égal à ", puiss)

Fin

Langage python

​

# Programme Puissance

x=int(input("Entrez la valeur de x:"))

n=int(input("Entrer la valeur de n:"))

puiss=1

for i in range(1,n+1):

puiss=puiss*x

print(x,"à la puissance",n,"est égal à",puiss)

Exercice2 :

Donner un programme qui Calcul x à la puissance n où x est un réel non nul et n un entier positif ou nul.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

49

Algorithme

​

Algorithme factorielle

Variables n,fact : entier

Debut

Ecrire (" Entrez la valeur de n")

Lire (n)

fact← 1

Pour i allant de 1 à n Faire

fact← fact*i

FinPour

Ecrire (" La factorielle de", n ,"est :", fact)

Fin

Langage python

​

# Programme Puissance

n=int(input("Entrer la valeur de n:"))

fact=1

for i in range(1,n+1):

fact=fact*i

print("La factorielle de",n,"est:",fact)

input()

Exercice3 :

Donner un programme qui Calcul la factorielle d’un nombre entier n.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

50

Algorithme

Algorithme Fibonacci

Variables n, j, A,B,C : entier

Debut

B ← 1

C ← 1

Ecrire (" Donner La valeur de n ")

Lire (n)

Si (n=0 OU n=1) alors

Ecrire (" La valeur Un=1")

Sinon

Pour j allant de 2 à n Faire

A ←B + C

C ← B

B ← A

FinPour

Ecrire (" La valeur Un=",A)

Finsi

Fin

Langage python

# Programme Fibonacci

n=int(input("Entrer la valeur de n:"))

B=1

C=1

if n= =0 or n= =1 :

print("La valeur U",n,"=1")

else:

for j in range(2,n+1):

A=B+C

C=B

B=A

print("La valeur U",n,"=",A)

input()

Exercice4 :

Déterminez un algorithme permettant de calculer le terme de rang n de la suite de. Fibonacci. Avec : U₀=U₁=1 et U_n=U_n-1+U_n-2.

​

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

51

Analyse descendante : Diviser pour régner

Diviser pour régner consiste à décomposer le problème complexe à résoudre en plusieurs sous problèmes moins complexes. A refaire cette décomposition sur les sous problèmes jusqu’à obtenir des sous problèmes faciles à résoudre.

Conclusion :

La solution à un problème bien défini peut être formulée comme une suite des trois énoncés suivants :

• Séquentiel : suite d’étapes
• Conditionnel : choix entre deux étapes suivant une condition
• Répétitif (itératif) : répétition d’une étape

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

52

Actions mois

abstraites

Actions concrètes

Exemple :

Algorithme de résolution d'équation de second degré :

a x² + b x + c = 0

53

ax²+bx+c=0

bx+c=0

ax²+bx+c=0

c=0

Infinités de solutions

Pas de solutions

x=-c/b

Δ=b²-4ac

Δ=0

x=-b/2a

Δ≠0

Δ<0

Pas de solutions réelles

Δ>0

x₁=-b-(Δ)^1/2/2a

x₂=-b+(Δ)^1/2/2a

a=0

a≠0

b=0

c=0

b≠0

c≠0

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

54

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

55

Algorithme Eq_Second_Degré

Réel a, b, c , Delta

​

Début

Ecrire ("Donner les coefficients : ")

Lire(a,b,c)

Si (a = 0) alors

Si (b = 0) alors

Si (c = 0) alors

Ecrire ("Infinités de solutions")

Sinon

Ecrire ("Pas de solutions")

FSi

Sinon

Ecrire ("Equation de 1er degré, une racine réelle : ",-c/b)

FSi

Sinon

Delta ← b*b –4*a*c

Si (Delta = 0) Alors

Ecrire ("Une racine réelle double : " , -b/(2*a))

Sinon

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

56

Si (Delta > 0) Alors

Ecrire("Deux racines réelles :  x1 = ", (-b + racine(Delta)) /(2*a) , " x2 = ", (-b + racine(Delta)) /(2*a) )

Sinon

Ecrire("Pas de solutions réelles ")

FSi

FSi

FSi

Fin

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

57

Complexités :

C’est l’étude de l’efficacité comparée des algorithmes. On mesure ainsi le temps et aussi l’espace nécessaire à un algorithme pour résoudre un problème.

• Complexité temporelle : (ou en temps) : temps de calcul ;

• Complexité spatiale : (ou en espace) : l’espace mémoire

requis par le calcul.

• Complexité pratique : est une mesure précise des complexités

temporelles et spatiales pour un modèle de machine donné ;

• Complexité théorique : est un ordre de grandeur de ces couts,

exprimé de manière la plus indépendante possible des conditions

pratiques d’exécution.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

58

• O(1) constant ;
• O(log n) logarithmique;
• O(n) linéaire;
• O(n×log n) quasi-linéaire;
• O(n²) quadratique;
• O(n^p) polynomial;
• O(aⁿ) exponentiel (problèmes très difficiles).

Les principales classes de complexité :

Langage C :

• Le résultat d’une fonction peut ne pas être utilisé

​

• Une fonction peut ne pas fournir aucun résultat

​

• Une fonction peut fournir un résultat non scalaire

​

• Un programme C est un ensemble de fonctions contenant au moins la fonction main (fonction obligatoire). Toutes ces fonctions sont au même niveau(pas d’imbrication de fonctions).

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

59

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

60

Liste des caractères non imprimables et des caractères spécifiques :

Remarque :

• Les codes de format :

Bibliothèques :

Une bibliothèque est un ensemble de fonctions. Celles-ci sont regroupées et mises à disposition afin de pouvoir être utilisées sans avoir à les réécrire.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

61

Liste des caractères non imprimables et des caractères spécifiques :

Programmation modulaire

Fonctions et procédures

62

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

ALGORITHMIQUE

Fonctions et procédures :

• Certains problèmes conduisent à des programmes longs, difficiles à écrire et à comprendre. On les découpe en des parties appelées sous-programmes ou modules ;

​

• Les fonctions et les procédures sont des modules (groupe d'instructions) indépendants désignés par un nom. Elles ont plusieurs intérêts :

​

• permettent de "factoriser" les programmes, càd de mettre en commun les parties qui se répètent ;

​

• permettent une structuration et une meilleure lisibilité des programmes ;

​

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

​

• ces procédures et fonctions peuvent éventuellement être réutilisées dans d'autres programmes.

63

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Fonctions :

• Le rôle d'une fonction en programmation est similaire à celui d'une fonction en mathématique : elle retourne un résultat à partir des valeurs des paramètres ;

​

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

Fonction nom_fonction (paramètres 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 mêmes règles que celles pour les noms de variables ;
• Type_fonction est le type du résultat retourné ;
• L'instruction Retourne sert à retourner la valeur du résultat.

64

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

• La fonction SommeCarre suivante calcule la somme des carrées de deux réels x et y :

Fonction SommeCarre (x : réel, y: réel ) : réel

variable z : réel

z ←x^2+y^2

Retourne (z)

FinFonction

​

• La fonction Pair suivante détermine si un nombre est pair :

​

Fonction Pair (n : entier ) : booléen

Retourne (n mod 2=0)

FinFonction

65

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Exemple :

Utilisation des fonctions :

• L'utilisation d'une fonction se fera par simple écriture de son nom dans le programme principale. Le résultat étant une valeur, devra être affecté ou être utilisé dans une expression, une écriture, ...

​

• Exepmle :Algorithme exepmleAppelFonction

variables z : réel, b : booléen

Début

b ←Pair(3)

z ←5*SommeCarre(7,2)+1

Ecrire("SommeCarre(3,5)= ", SommeCarre(3,5))

Fin

​

• Lors de l'appel Pair(3) le paramètre formel n est remplacé par le paramètre effectif 3

66

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Arguments d'une fonction :

• Les paramètres servent à échanger des données entre le programme principale (ou le module appelant) et la fonction appelée ;

​

• Les arguments placés dans la déclaration d'une fonction sont appelés argument formels. Ces paramètres peuvent prendre toutes les valeurs possibles mais ils sont abstraits (n'existent pas réellement) ;

​

• Les argument placés dans l'appel d'une fonction sont appelés argument effectifs.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

67

Procédures :

• Dans certains cas, on peut avoir besoin de répéter une tâche dans plusieurs endroits du programme, mais que dans cette tâche on ne calcule pas de résultats ou qu'on calcule plusieurs résultats à la fois ;

​

• Dans ces cas on ne peut pas utiliser une fonction, on utilise une procédure ;

​

• Une procédure est un sous-programme semblable à une fonction mais qui ne retourne rien ;

​

• Une procédure s'écrit en dehors du programme principal sous la forme :

Procédure nom_procédure (paramètres et leurs types)

​

Instructions constituant le corps de la procédure

FinProcédure

​

• Remarque : une procédure peut ne pas avoir de paramètres.

68

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Appel d'une procédure :

• L'appel d'une procédure, se fait dans le programme principale ou dans une autre procédure par une instruction indiquant le nom de la procédure :

​

Procédure exemple_proc (…)

…

FinProcédure

​

Algorithme exepmleAppelProcédure

Début

exemple_proc (…)

…

Fin

​

• Remarque : contrairement à l'appel d'une fonction, on ne peut pas affecter la procédure appelée ou l'utiliser dans une expression. L'appel d'une procédure est une instruction autonome.

69

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Paramètres d'une procédure :

• Les paramètres servent à échanger des données entre le programme principal (ou la procédure appelante) et la procédure appelée ;

​

• Les paramètres placés dans la déclaration d'une procédure sont appelés paramètres formels. Ces paramètres peuvent prendre toutes les valeurs possibles mais ils sont abstraits (n'existent pas réellement) ;

​

• Les paramètres placés dans l'appel d'une procédure sont appelés paramètres effectifs. ils contiennent les valeurs pour effectuer le traitement ;

​

• Le nombre de paramètres effectifs doit être égal au nombre de paramètres formels. L'ordre et le type des paramètres doivent correspondre.

70

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Variables locales et globales :

• On peut manipuler 2 types de variables dans un module (procédure ou fonction) : des variables locales et des variables globales. Elles se distinguent par ce qu'on appelle leur portée (leur "champ de définition", leur "durée de vie") ;

​

• Une variable locale n'est connue qu'à l'intérieur du module ou elle a été définie. Elle est crée à l'appel du module et détruite à la fin de son exécution ;

​

• Une variable globale est connue par l'ensemble des modules et le programme principale. Elle est définie durant toute l’application et peut être utilisée et modifiée par les différents modules du programme.

71

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Variables locales et globales :

• La manière de distinguer la déclaration des variables locales et globales diffère selon le langage :

​

• En général, les variables déclarées à l'intérieur d'une fonction ou procédure sont considérées comme variables locales

​

• En pseudo-code, on va adopter cette règle pour les variables locales et on déclarera les variables globales dans le programme principale ;

​

• Conseil : Il faut utiliser autant que possible des variables locales plutôt que des variables globales. Ceci permet d'économiser la mémoire et d'assurer l'indépendance de la procédure ou de la fonction.

72

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

73

Langage python

def nom_fonction (paramètres) :

" Commentaire "

Instructions constituant le corps de la fonction

return (…)

Transmission des paramètres : exemples :

Procédure incrementer1 (x : entier par valeur, y : entier par adresse)

x ← x+1

y ← y+1

FinProcédure

​

Algorithme Test_incrementer1

variables n, m : entier

Début

n ← 3

m ← 3

incrementer1(n, m) résultat :

é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

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

74

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

75

Langage python

​

#Programme Incremetation1

#Definition de la Procédure Incremetation

def Incremetation(x) :

"Echange le contenu de deux variables"

global y

x=x+1

y=y+1

�

#Programme principale

x=float(input('Donner x:'))

y=float(input('Donner y:'))

print("x=",x,"et y=",y)

Incremetation(x)

print("x=",x,"et y=",y)

input()

Transmission des paramètres : exemples :

Procédure qui échange le contenu de deux variables :

Procédure Echange (x : réel par adresse, y : réel par adresse)

variables z : réel

z ← x

x ← y

y ← z

FinProcédure

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

76

Langage python

#Definition de la Procédure Permutation

def Echange() :

"Echange le contenu de deux variables"

global x

global y

z=x

x=y

y=z

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

77

Remarque :

• Les codes de format :

Bibliothèques :

Une bibliothèque est un ensemble de fonctions. Celles-ci sont regroupées et mises à disposition afin de pouvoir être utilisées sans avoir à les réécrire.

from math import sqrt

import math as ma

Exemple :

from math import *

import math

Exemple :

print(‘la racine carrée de %d est %f' % (n,sqrt(n)))

Les tableaux

78

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

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 supérieure à 10
• Le seul moyen dont nous disposons actuellement consiste à déclarer 30 variables, par exemple N1, …, N30. Après 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 donnée appelée tableau

79

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Tableaux

• Un tableau est un ensemble d'éléments de même type désignés par un identificateur unique ;
• Une variable entière nommée indice permet d'indiquer la position d'un élément donné au sein du tableau et de déterminer sa valeur ;
• La déclaration d'un tableau s'effectue en précisant le type de ses éléments et sa dimension (le nombre de ses éléments) ;
• En pseudo code :

variable tableau identificateur[dimension] : type

• Exemple :

variable tableau notes[30] : réel

​

​

​

​

• On peut définir des tableaux de tous types : tableaux d'entiers, de réels, de caractères, de booléens, de chaînes de caractères, …

80

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Remarques :

• L'accès à un élément du tableau se fait au moyen de l'indice. Par exemple, notes[i] donne la valeur de l'élément 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] désigne l'élément i+1 du tableau notes ;

​

• Il est possible de déclarer un tableau sans préciser au départ sa dimension. Cette précision est faite ultérieurement ;

​

• Un grand avantage des tableaux est qu'on peut traiter les données qui y sont stockées de façon simple en utilisant des boucles.

81

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Saisie et Affichage :

• Méthodes qui permettent de saisir et d'afficher les éléments d'un tableau :

Algorithme SaisieTab� variable i: entier

Tableau T[n] :reel

Debut

Pour i allant de 0 à n-1�     Ecrire ("Saisie de l'élément ", i + 1)

     Lire (T[i] )

FinPour

Fin

​

​

Algorithme AfficheTab� variable i: entier

Tableau T[n] :reel

Debut

Pour i allant de 0 à n-1�     Ecrire ("T[",i, "] =", T[i])

FinPour

Fin

82

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Exemples :

• Pour le calcul du nombre d'étudiants ayant une note supérieure à 10 avec les tableaux, on peut écrire :

Algorithme Moyenne

Variables i ,nbre : entier

tableau notes[30] : réel

Début� nbre ← 0

Pour i allant de 0 à 29 � Ecrire ("Saisie de l'élément ", i + 1)

     Lire (notes[i])

Si notes[i] >10 alors

nbre ← nbre+1

FinSi

FinPour

Ecrire (" Le nombre de notes supérieures à 10 est : ", nbre)

Fin

83

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

84

• Notation en Python :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

En python les tableaux peuvent être représentés par des listes:

Une liste est une collection modifiable d’éléments éventuellement hétérogènes.

>>> T= [5, 38, 10, 25]

>>> T

[17, 38, 10, 25]

Voir cours : les liste en python

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

85

T=10*[0] #initialisation de la liste

for i in range(10):

T[i]=int(input(‘Donner T[%d]:' % (i)))

s=0

for i in range(10):

s+=T[i]

print ('s=',s)

Exemple 1 : Version1

Saisir 10 nombres entiers dans un tableau T, puis afficher leur somme.

T=10*[0] #initialisation de la liste

s=0

for i in range(10):

T[i]=int(input(‘Donner T[%d]:' % (i)))

s+=T[i]

print ('s=',s)

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

86

T=[] #liste vide

for i in range(10):

e=int(input(‘Donner T[%d]:' % (i)))

T+=[e]

Exemple 1 : Version2

s=0

for x in T:

s+=x

print ('s=',s)

T=[] #liste vide

s=0

for i in range(10):

e=int(input(‘Donner T[%d]:' % (i)))

T+=[e]

s+=e

print ('s=',s)

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

87

Chaînes de caractères : strings

• Une chaîne de caractères est une suite finie de caractères consécutifs, qu’on note entre apostrophes ou guillemets ;

​

• La chaîne vide se note ' ' ou " ".

Accès à un caractère:

• On peut stocker une chaîne dans une variable :

>>> s = 'Bonjour'

​

• Pour accéder à chacun des caractères on utilise la construction s[i] :

>>> s[2]

>>> 'n'

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

88

Concaténation :

• On concatène deux chaînes à l’aide de l’opérateur + :

>>> s = 'Bonjour '+ 'lecteur !'

>>> s = 'Bonjour lecteur !‘

Longueur :

• On utilise len pour obtenir la longueur d’une chaîne :

>>> len('Bonjour')

>>> 7

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

89

Sous-chaînes :

Un ensemble de caractères consécutifs à l’intérieur d’une chaîne s’appelle une sous-chaîne. Ainsi, 'lecteur' ou 'jour lec' sont des sous-chaînes de 'Bonjour lecteur !'. Pour extraire une sous-chaîne de s, on écrit s[i:j] où i est l’indice du premier caractère de la sous-chaîne et j est l’indice du dernier caractère plus un.

• >>> s = 'Bonjour lecteur !'

• >>> s[0:7]

>>> 'Bonjour'

• >>> s[8:15]

>>> 'lecteur'

• Si j ⩽ -len(ch)+i il n’y a pas de sous-chaîne correspondante. Python renvoie alors la chaîne vide : ' '

• Si j dépasse la longueur de la chaîne, la sous-chaîne s’arrête au dernier caractère de la chaîne.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

90

• Il est à noter qu’il est également possible de tester la présence d’une sous-chaîne dans une chaîne avec la même construction :

>>> 'lecteur' in 'Bonjour lecteur !'

>>> True

>>> 'Bjr' in 'Bonjour lecteur !'

>>> False

Test d’appartenance :

• l’opérateur in sert à tester l’appartenance d’un caractère à une chaîne :

>>> 'o' in 'Bonjour'

>>> True

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

91

• Il est possible de reconvertir une telle chaîne vers une valeur d’un type simple :

>>> int('123')

>>> 123

>>> float('1.2')

>>> 1.2

>>> bool('True')

>>> True

Conversion vers des types simples :

• On peut convertir une valeur d’un type simple vers une chaîne de caractères à l’aide de la construction str(e) :

>>> str(1.2)

>>> '1.2'

92

# Valeur maximale

def Maximum(T):

Max=T[0]

for i in range(1,len(T)):

if T[i]>Max:

Max=T[i]

return(Max)

• Ecrire une fonction qui retourne la valeur maximale d’une liste .

Exercice 1 :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

• Ecrire une fonction qui retourne l’indice de la valeur maximale d’une liste .

#Indice de la valeur maximale

def Indice_Maximum(T):

Max=T[0]

p=0

for i in range(1,len(T)):

if T[i]>Max:

Max=T[i]

p=i

return(p)

93

# Valeur minimale

def Minimum(T):

Min=T[0]

for i in range(len(T)):

if T[i]<Min:

Min=T[i]

return(Min)

• Ecrire une fonction qui retourne la valeur minimale d’une liste .

Exercice 2 :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

• Ecrire une fonction qui retourne l’indice de la valeur minimale d’une liste .

#Indice de la valeur minimale

def Indice_Minimum(T):

Min=T[0]

p=0

for i in range(len(T)):

if T[i]<Min:

Min=T[i]

p=i

return(p)

Tri d'un tableau

• Le tri consiste à ordonner les éléments du tableau dans l’ordre croissant ou décroissant

​

• Il existe plusieurs algorithmes connus pour trier les éléments d’un tableau :

​

• Le tri par sélection
• Le tri par insertion
• Le tri à bulles
• …

​

• Nous verrons dans la suite le programme de tri par sélection, le programme de tri par insertion et le programme de tri à bulles. Le tri sera effectué dans l'ordre croissant

94

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Tri par sélection

• Principe : On cherche le plus petit élément du tableau et on le place en premier, puis on cherche le plus petit dans ce qui reste et on le met en second, etc…

​

• Exemple :
• Étape 1: on cherche le plus petit parmi les 5 éléments du tableau. On l’identifie en troisième position, et on l’échange alors avec l’élément 1 :

​

​

• Étape 2: on cherche le plus petit élément, mais cette fois à partir du deuxième élément. On le trouve en dernière position, on l'échange avec le deuxième:

​

• Étape 3:

​

95

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

Tri par sélection : version1

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

96

Langage python

#Fonction de la position du Minimum

def position_Minimum(T,debut,Fin) :

position=debut

Minimum=T[debut]

debut+=1

while debut<=Fin :

if T[debut]<Minimum : # on a trouvée plus petit

Minimum=T[debut] # mettre à jour la valeur ...

position=debut # ... et sa position

debut+=1

return(position)

# Procédure du Tri par sélection

def tri_Selection(T):

n=len(T)

debut=0

while debut<n-1: # pour chaque position de la liste trouver le minimum de T[i], ..., T[n - 1]

p=position_Minimum(T,debut,n-1)

# Echanger ce minimum avec T[i]

T[debut],T[p]=T[p],T[debut]

debut+=1

Tri par sélection : version2

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

97

Langage python

def Tri_Selection(T) :

n=len(T)

for i in range(0,n-1) :

pmin=i #position du minimum

for j in range(i+1,n) :

if T[j]<T[pmin] :

pmin=j

T[i],T[pmin]=T[pmin],T[i]

​

#Programme tri par sélection

n=int(input("Donner le nombre d'éléments de la liste T:"))

T=[]

for i in range(n) :

e=int(input('Donner T[%d]='%(i)))

T=T+[e]

print(T)

Tri_Selection(T)

print(T)

input()

​

Tri par insertion

• Principe : dans cet algorithme, on peut considérer qu’à chaque etape, la suite à trier est constituée de deux sous-suites :la sous-suites D (destination) des éléments déjà triés et la sous-suites S (source) des éléments restant à trier

​

​

​

​

• Le 1^er élément de S (ième élément du tableau) doit être inséré dans D à la bonne place :

​

​

​

• La situation initiale est la suivante :

​

​

98

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

99

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

100

Tri par insertion : version1

Langage python

#Programme et Procédure du Trie Par insertion

# Procédure du réinsertion de i dans j

def reinsertion(T,i,j):

# Sauvegarder l’élément à déplacer

e=T[i]

# Faire remonter d'une position les éléments entre i et j

k=i

while k>j:

T[k]=T[k-1]

k=k-1

# Copier l’élément à déplacer en position j

T[j]=e

# Procédure du Trie Par insertion

def tri_Insertion(T):

n=len(T)

i=1

while i<n: # Pour chaque position de la liste chercher à quelle position réinsérer T[i]

j=i-1

while j>=0 and T[j]>T[i]:

j=j-1

# Effectuer la réinsertion

reinsertion(T,i,j+1)

i=i+1

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

101

Tri par insertion : version2

Langage python

def Tri_Insertion(T):

n=len(T)

for i in range(1,n):

e=T[i]

j=i

while j>0 and T[j-1]> e:

T[j]=T[j-1]

j-=1

T[j]=e

​

#Programme par insertion

n=int(input("Donner le nombre d'éléments de la liste T:"))

T=[]

for i in range(n) :

e=int(input('Donner T[%d]='%(i)))

T=T+[e]

print(T)

Tri_Insertion(T)

print(T)

input()

Tri à bulles

• Principe : L’algorithme consiste à comparer chaque paire d’éléments consécutifs, si ces éléments sont dans l’ordre, on passe à la paire suivante, sinon on procède à leur échange avant de traiter la paire suivante.

​

​

​

​

102

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

103

Tri à bulles : version1

Langage python

#Programme et Procédure du Trie à Bulles

# Procédure du Trie à Bulles

def Tri_bulle(T):

n=len(T)

change=True

while change :

change=False

for i in range(n-1) :

if T[i]>T[i+1] :

T[i],T[i+1]=T[i+1],T[i]

change = True

​

#Programme du Trie à Bulles

n=int(input("Donner le nombre d'éléments de la liste T:"))

T=[]

for i in range(n) :

e=int(input('Donner T[%d]='%(i)))

T=T+[e]

print(T)

Tri_bulle(T)

print(T)

input()

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

104

Tri à bulles : version2

Langage python

def Tri_Bulle(T):

n=len(T)

i=1

Trier=False

while not Trier :

Trier = True #on suppose que le tableau est trié

for i in range(0,n-1) :

if T[i]>T[i+1] :

T[i],T[i+1]=T[i+1],T[i]

Trier=False #le tableau n'est plus trié

#Programme du Tri à Bulles

n=int(input("Donner le nombre d'éléments de la liste T:"))

T=[]

for i in range(n) :

e=int(input('Donner T[%d]='%(i)))

T=T+[e]

print(T)

Tri_Bulle(T)

print(T)

input()

​

​

Tri par sélection : complexité

• On effectue N-1 tests pour trouver le premier élément du tableau trié, N-2 tests pour le deuxième, 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 sélection est d'ordre N² (O(N²))

​

• Pour un ordinateur qui effectue 10⁹ tests par seconde on a :

105

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

106

​

• Recherche d’un élément dans une liste :

• Recherche séquentielle (linéaire) :

• Recherche dichotomique :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

107

Recherche séquentielle (linéaire) :

Exploration séquentielle de la liste.

Condition d’arrêt :

• On a trouvé l’élément ;

• On a parcouru toute la liste sans trouver l’élément.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

108

Langage python

#Programme et Fonction Recherche linéaire

#Fonction Recherche linéaire

def Recherche_lineaire(L,X):

for t in L:

if X= =t:

return(True)

return(False)

​

#Programme Recherche linéaire

n=int(input("Donnez le nombre d'éléments de la liste T:"))

X=int(input("Donnez l'élement chercher dans la liste T:"))

T=[]

for i in range(n):

e=int(input('Donnez T[%d]='%(i)))

T=T+[e]

print(T)

if Recherche_lineaire(T,X):

print(X,"appartient à la liste T")

else:

print(X,"n'appartient pas à la liste T")

​

Recherche séquentielle (linéaire) :

#Fonction Recherche linéaire1

def Recherche_lineaire1(L,X):

return(t in L)

109

Complexité :

• Pour évaluer l’efficacité de l'algorithme de recherche séquentielle, on va calculer sa complexité dans le pire des cas. Pour cela on va compter le nombre de tests effectués ;

​

• Le pire des cas pour cet algorithme correspond au cas où X n'est pas dans la liste T ;

​

• Si X n’est pas dans la liste , on effectue N tests : on répète N fois les tests X==t ;

​

• La complexité dans le pire des cas est d'ordre N, (on note O(N)) ;

​

• Pour un ordinateur qui effectue 10⁹ tests par seconde on a :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

110

Recherche dichotomique :

• Dans le cas où la liste est ordonnée, on peut améliorer l'efficacité de la recherche en utilisant la méthode de recherche dichotomique;

• Principe : diviser par 2 le nombre d'éléments dans lesquels on cherche la valeur X à chaque étape de la recherche. Pour cela on compare X avec T[milieu] :

• Si X < T[milieu], il suffit de chercher X dans la 1^ère moitié de la liste entre

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

• Si X > T[milieu], il suffit de chercher X dans la 2^ème moitié de la liste entre (T[milieu+1] et T[N-1]).

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

111

Exemple :

​

​

• Considérons la liste T :

• Si la valeur cherché est 20 alors les indices debut, fin et milieu vont évoluer comme suit :

• Si la valeur cherché est 10 alors les indices debut, fin et milieu vont évoluer comme suit :

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

112

Langage python

#Programme et Fonction Recherche dichotomique

#Fonction Recherche dichotomique

def Recherche_dichotomique(L,X):

N=len(L)

Debut=0

Fin=N-1

while Debut<=Fin:

Milieu=(Debut+Fin)//2

if X= =L[Milieu]:

return(True)

elif X>L[Milieu]:

Debut=Milieu+1

else:

Fin=Milieu-1

return(False)

#Programme Recherche dichotomique

n=int(input("Donnez le nombre d'éléments de la liste T:"))

X=int(input("Donnez l'élement chercher dans la liste T:"))

T=[]

for i in range(n):

e=int(input('Donnez T[%d]='%(i)))

T=T+[e]

print(T)

if Recherche_dichotomique(T,X):

print(X,"appartient à la liste T")

else:

print(X,"n'appartient pas à la liste T")

Recherche dichotomique :

113

Complexité :

• La complexité dans le pire des cas est d'ordre log₂ N ;

• L'écart de performances entre la recherche séquentielle et la recherche dichotomique est considérable pour les grandes valeurs de N.

Exemple :

Au lieu de N=1milion ≈2²⁰ opérations à effectuer avec une recherche séquentielle il suffit de 20 opérations avec une recherche dichotomique.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

114

TABLEAUX DOUBLE DIMENSION

• Un tableau double dimension est un tableau dont chaque élément est un tableau ;

​

• On appelle L le nombre de lignes du tableau et C le nombre de colonnes du tableau. L et C sont alors les deux dimensions du tableau. Un tableau à deux dimensions contient donc L*C composantes.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

115

• Deux variables entières nommées indices permettent d'indiquer la position d'un élément donné au sein du tableau à deux dimensions et de déterminer sa valeur ;

(i.e. : L'accès à un élément du tableau à deux dimensions se fait au moyen de deux indices.)

Exemple : T[i][j] donne la valeur de l'élément de la ligne i+1 et de la colonne j+1.

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

116

• La déclaration d'un tableau à deux dimensions s'effectue en précisant le type et le nombre de lignes et de colonnes ;

​

Syntaxe :

Variable Tableau identificateur[Nombre_lignes][Nombre_colonnes] : type

Exemple :

Variable Tableau T[30][50] : réel

• Il est possible de déclarer un tableau à deux dimensions sans préciser au départ le nombre de lignes et de colonnes. Cette précision est faite ultérieurement.

​

Exemple :

Variable Tableau T[n][m] : réel

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

117

• Saisie et Affichage :

Algorithme :

​

​

Algorithme SaisieMatrice

Variables i , j , n, m : entier

Tableau A[n][m] : réel

Debut

Ecrire("Donner le nombre de lignes et de colonnes :")

Lire(n,m)

Pour i allant de 0 à n-1 faire

Pour j allant de 0 à m-1 faire

Ecrire ("Entrez l'élément de la ligne", i + 1,"et de la colonne", j+1)

Lire (A[i][j])

FinPour

FinPour

Fin

Saisir les éléments d’un Tableau 2D (Matrice)

*

Ingénierie numérique et simulation-MPSI/TSI/PCSI

118

Algorithme :

​

​

Algorithme AffichageMatrice

Variables i , j , n, m : entier

Tableau A[n][m] : réel

Debut

Ecrire("Donner le nombre de lignes et de colonnes :")

Lire(n,m)

Pour i allant de 0 à n-1 faire

Pour j allant de 0 à m-1 faire

Ecrire (A[i][j])

FinPour

FinPour