Algorithmique

Lycée Jean Moulin : NSI

Algorithmique Lycée Jean Moulin : NSI 1/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme :

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine :

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.
• Le langage :

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.
• Le langage : moyen de communication entre l’informaticien et
la machine.

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.
• Le langage : moyen de communication entre l’informaticien et
la machine.
• L’information :

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.
• Le langage : moyen de communication entre l’informaticien et
la machine.
• L’information : données symboliques susceptibles d’être
traitées par une machine.

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Introduction

L’informatique est structurée par quatre concepts :

• L’algorithme : méthode opérationnelle permettant de résoudre
un problème.
• La machine : système physique doté de fonctionnalités.
• Le langage : moyen de communication entre l’informaticien et
la machine.
• L’information : données symboliques susceptibles d’être
traitées par une machine.
On se propose de mettre en place une méthodologie permettant
de mettre sur le papier la résolution d’un problème bien posé.

Algorithmique Lycée Jean Moulin : NSI 2/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Algorithmique Lycée Jean Moulin : NSI 3/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) :

Algorithmique Lycée Jean Moulin : NSI 3/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) :

• déplacer la voiture B de P3 à
P1 .

Algorithmique Lycée Jean Moulin : NSI 3/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) :

• déplacer la voiture B de P3 à
P1 .
• déplacer la voiture A de P2 à
P3 .

Algorithmique Lycée Jean Moulin : NSI 3/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) :

• déplacer la voiture B de P3 à
P1 .
• déplacer la voiture A de P2 à
P3 .
• déplacer la voiture B de P1 à
P2 .
Algorithmique Lycée Jean Moulin : NSI 3/29
Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) : Des imprévus

• déplacer la voiture B de P3 à
P1 .
• déplacer la voiture A de P2 à
P3 .
• déplacer la voiture B de P1 à
P2 .
Algorithmique Lycée Jean Moulin : NSI 3/29
Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) : Des imprévus

• déplacer la voiture B de P3 à • P1 est-il libre ?
P1 .
• déplacer la voiture A de P2 à
P3 .
• déplacer la voiture B de P1 à
P2 .
Algorithmique Lycée Jean Moulin : NSI 3/29
Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) : Des imprévus

• déplacer la voiture B de P3 à • P1 est-il libre ?
P1 .
• les voitures sont-elles en état
• déplacer la voiture A de P2 à
de marche ?
P3 .
• déplacer la voiture B de P1 à
P2 .
Algorithmique Lycée Jean Moulin : NSI 3/29
Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème : Permuter deux voitures sur un parking de trois
places numérotées P1 , P2 et P3 , sans gêner la circulation. La voiture
A est sur l’emplacement P2 , la voiture B est sur l’emplacement P3 .

Un premier algorithme (naïf ) : Des imprévus

• déplacer la voiture B de P3 à • P1 est-il libre ?
P1 .
• les voitures sont-elles en état
• déplacer la voiture A de P2 à
de marche ?
P3 .
• déplacer la voiture B de P1 à • P3 est-il libre pendant
P2 . l’échange ? etc.
Algorithmique Lycée Jean Moulin : NSI 3/29
Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données :

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données : Parking de trois emplacements, numérotés P1 , P2 et

P3 . Deux voitures en état de marche : A sur P3 et B sur P2 .

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données : Parking de trois emplacements, numérotés P1 , P2 et

P3 . Deux voitures en état de marche : A sur P3 et B sur P2 .
• Hypothèses générales :

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données : Parking de trois emplacements, numérotés P1 , P2 et

P3 . Deux voitures en état de marche : A sur P3 et B sur P2 .
• Hypothèses générales : Un seul conducteur réalise la
permutation. Celui-ci a son permis de conduire et les clés des
deux voitures. Lorsqu’une voiture est en mouvement, aucune
autre voiture ne vient sur le parking. Une éventuelle autre voiture
ne reste qu’un temps fini sur un emplacement.

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données : Parking de trois emplacements, numérotés P1 , P2 et

P3 . Deux voitures en état de marche : A sur P3 et B sur P2 .
• Hypothèses générales : Un seul conducteur réalise la
permutation. Celui-ci a son permis de conduire et les clés des
deux voitures. Lorsqu’une voiture est en mouvement, aucune
autre voiture ne vient sur le parking. Une éventuelle autre voiture
ne reste qu’un temps fini sur un emplacement.
• Résultats :

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Poser proprement le problème

Le problème est en partie mal posé, il faut préciser les choses :

• Données : Parking de trois emplacements, numérotés P1 , P2 et

P3 . Deux voitures en état de marche : A sur P3 et B sur P2 .
• Hypothèses générales : Un seul conducteur réalise la
permutation. Celui-ci a son permis de conduire et les clés des
deux voitures. Lorsqu’une voiture est en mouvement, aucune
autre voiture ne vient sur le parking. Une éventuelle autre voiture
ne reste qu’un temps fini sur un emplacement.
• Résultats : La voiture B est sur l’emplacement P2 . La voiture A
est sur l’emplacement P3 .

Algorithmique Lycée Jean Moulin : NSI 4/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B

(emplacement P3 ).

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B

(emplacement P3 ).
• Répéter attendre jusqu’à
emplacement P1 libre.

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B

(emplacement P3 ).
• Répéter attendre jusqu’à
emplacement P1 libre.
• Déplacer la voiture B de P3 à
P1 .

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B

(emplacement P3 ).
• Répéter attendre jusqu’à
emplacement P1 libre.
• Déplacer la voiture B de P3 à
P1 .
• Aller au volant de la voiture
A (emplacement P2 ).

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B

(emplacement P3 ).
• Répéter attendre jusqu’à
emplacement P1 libre.
• Déplacer la voiture B de P3 à
P1 .
• Aller au volant de la voiture
A (emplacement P2 ).
• Répéter attendre jusqu’à
emplacement P3 libre.

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B • Déplacer la voiture A de P2 à

(emplacement P3 ). P3 .
• Répéter attendre jusqu’à
emplacement P1 libre.
• Déplacer la voiture B de P3 à
P1 .
• Aller au volant de la voiture
A (emplacement P2 ).
• Répéter attendre jusqu’à
emplacement P3 libre.

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B • Déplacer la voiture A de P2 à

(emplacement P3 ). P3 .
• Répéter attendre jusqu’à
emplacement P1 libre. • Aller au volant de la voiture B
• Déplacer la voiture B de P3 à (emplacement P1 ).
P1 .
• Aller au volant de la voiture
A (emplacement P2 ).
• Répéter attendre jusqu’à
emplacement P3 libre.

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B • Déplacer la voiture A de P2 à

(emplacement P3 ). P3 .
• Répéter attendre jusqu’à
emplacement P1 libre. • Aller au volant de la voiture B
• Déplacer la voiture B de P3 à (emplacement P1 ).
P1 . • Répéter attendre jusqu’à
• Aller au volant de la voiture emplacement P2 libre.
A (emplacement P2 ).
• Répéter attendre jusqu’à
emplacement P3 libre.

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un algorithme possible

• Aller au volant de la voiture B • Déplacer la voiture A de P2 à

(emplacement P3 ). P3 .
• Répéter attendre jusqu’à
emplacement P1 libre. • Aller au volant de la voiture B
• Déplacer la voiture B de P3 à (emplacement P1 ).
P1 . • Répéter attendre jusqu’à
• Aller au volant de la voiture emplacement P2 libre.
A (emplacement P2 ).
• Répéter attendre jusqu’à • Déplacer la voiture B de P1 à
emplacement P3 libre. P2 .

Algorithmique Lycée Jean Moulin : NSI 5/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution
Là encore, l’énoncé n’est pas satisfaisant :

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution
Là encore, l’énoncé n’est pas satisfaisant :
• Les variables x, a et b sont-elles réelles, des vecteurs, des objets ?

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution
Là encore, l’énoncé n’est pas satisfaisant :
• Les variables x, a et b sont-elles réelles, des vecteurs, des objets ?
• Qui est l’inconnue ?

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution
Là encore, l’énoncé n’est pas satisfaisant :
• Les variables x, a et b sont-elles réelles, des vecteurs, des objets ?
• Qui est l’inconnue ?
Reformulons le problème :

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Un autre exemple

Le problème : Résoudre l’équation ax = b.

L’algorithme qui nous vient à l’esprit :
Si a n’est pas nul alors
la solution est x = ba
Sinon
Il n’y a pas de solution
Là encore, l’énoncé n’est pas satisfaisant :
• Les variables x, a et b sont-elles réelles, des vecteurs, des objets ?
• Qui est l’inconnue ?
Reformulons le problème :
Soient a ∈ R∗ et b ∈ R, trouver x tel que ax = b

Algorithmique Lycée Jean Moulin : NSI 6/29

Algorithmique Analyse des algorithmes

Méthodologie

Un bon algorithme doit :

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Un bon algorithme doit :

• être clair

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Un bon algorithme doit :

• être clair
• fournir un résultat satisfaisant

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Un bon algorithme doit :

• être clair
• fournir un résultat satisfaisant
• être adapté au public visé

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Pour cela, il est nécessaire de :

Un bon algorithme doit :
• être clair
• fournir un résultat satisfaisant
• être adapté au public visé

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Pour cela, il est nécessaire de :

Un bon algorithme doit : • poser correctement le
• être clair problème
• fournir un résultat satisfaisant
• être adapté au public visé

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Pour cela, il est nécessaire de :

Un bon algorithme doit : • poser correctement le
• être clair problème
• fournir un résultat satisfaisant • rechercher une méthode de
résolution
• être adapté au public visé

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Méthodologie

Pour cela, il est nécessaire de :

Un bon algorithme doit : • poser correctement le
• être clair problème
• fournir un résultat satisfaisant • rechercher une méthode de
résolution
• être adapté au public visé
• écrire l’algorithme par
raffinements successifs

Algorithmique Lycée Jean Moulin : NSI 7/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

• Des variables :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

• Des variables :

• Des opérateurs :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

• Des variables :

• Des opérateurs :

• Des expressions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

• Des variables :

• Des opérateurs :

• Des expressions :

• Des instructions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
Afin d’uniformiser l’écriture des algorithmes, un pseudo-langage
(non normalisé) contenant l’indispensable est utilisé :
• Des données :

• Des variables :

• Des opérateurs :

• Des expressions :

• Des instructions :

• Des fonctions :
Algorithmique Lycée Jean Moulin : NSI 8/29
Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables :

• Des opérateurs :

• Des expressions :

• Des instructions :

• Des fonctions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables : Elles sont modifiables, elles possèdent un type,
contiennent une valeur et sont identifiées par un nom explicite
• Des opérateurs :

• Des expressions :

• Des instructions :

• Des fonctions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables : Elles sont modifiables, elles possèdent un type,
contiennent une valeur et sont identifiées par un nom explicite
• Des opérateurs : Chaque type de donnée admet un jeu
d’opérateurs adapté (arithmétiques (+,-..), relationnels (==,>,..)
et logiques (et, ou,..)
• Des expressions :

• Des instructions :

• Des fonctions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables : Elles sont modifiables, elles possèdent un type,
contiennent une valeur et sont identifiées par un nom explicite
• Des opérateurs : Chaque type de donnée admet un jeu
d’opérateurs adapté (arithmétiques (+,-..), relationnels (==,>,..)
et logiques (et, ou,..)
• Des expressions : b/a est une expression numérique et a , 0 est
une expression booléenne
• Des instructions :

• Des fonctions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables : Elles sont modifiables, elles possèdent un type,
contiennent une valeur et sont identifiées par un nom explicite
• Des opérateurs : Chaque type de donnée admet un jeu
d’opérateurs adapté (arithmétiques (+,-..), relationnels (==,>,..)
et logiques (et, ou,..)
• Des expressions : b/a est une expression numérique et a , 0 est
une expression booléenne
• Des instructions : Elles peuvent être simples comme l’affectation
(x← b/a) ou structurées comme les instructions conditionnelles
(if, else) et répétitives(for ou while)
• Des fonctions :

Algorithmique Lycée Jean Moulin : NSI 8/29

Algorithmique Analyse des algorithmes

Pseudo-langage
• Des données : Ce sont des valeurs extérieures introduites dans
l’algorithme. Une constante est une valeur non modifiable (π,...)
• Des variables : Elles sont modifiables, elles possèdent un type,
contiennent une valeur et sont identifiées par un nom explicite
• Des opérateurs : Chaque type de donnée admet un jeu
d’opérateurs adapté (arithmétiques (+,-..), relationnels (==,>,..)
et logiques (et, ou,..)
• Des expressions : b/a est une expression numérique et a , 0 est
une expression booléenne
• Des instructions : Elles peuvent être simples comme l’affectation
(x← b/a) ou structurées comme les instructions conditionnelles
(if, else) et répétitives(for ou while)
• Des fonctions : Elles permettent d’automatiser des tâches
répétitives, d’ajouter de la clarté et d’être utilisées dans d’autres
algorithmes
Algorithmique Lycée Jean Moulin : NSI 8/29
Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)
Toute la difficulté réside dans l’écriture de programmes sûrs.

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)
Toute la difficulté réside dans l’écriture de programmes sûrs. On
constate que lorsqu’un algorithme est simple, le risque d’erreur
est moindre..

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)
Toute la difficulté réside dans l’écriture de programmes sûrs. On
constate que lorsqu’un algorithme est simple, le risque d’erreur
est moindre..
C’est avec ce principe essentiel que se basent les bonnes méthodes

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)
Toute la difficulté réside dans l’écriture de programmes sûrs. On
constate que lorsqu’un algorithme est simple, le risque d’erreur
est moindre..
C’est avec ce principe essentiel que se basent les bonnes méthodes

Ainsi, tout problème compliqué doit être découpé en

sous-problèmes simples

Algorithmique Lycée Jean Moulin : NSI 9/29

Algorithmique Analyse des algorithmes

Principe de bonne programmation

Tous les algorithmes que nous avons vus sont assez courts
Dans l’industrie, il arrive que des équipes produisent des codes de
millions de lignes, dont certains mettent en jeux des vies
(aéronautique, nucléaire...)
Toute la difficulté réside dans l’écriture de programmes sûrs. On
constate que lorsqu’un algorithme est simple, le risque d’erreur
est moindre..
C’est avec ce principe essentiel que se basent les bonnes méthodes

Ainsi, tout problème compliqué doit être découpé en

sous-problèmes simples

Chaque module ou sous-programme est alors testé et validé

séparément.
Tous les modules doivent aussi être largement documentés.
Algorithmique Lycée Jean Moulin : NSI 9/29
Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Problème : Étant donné deux entiers naturels non nuls,

déterminer leur PGCD

Algorithmique Lycée Jean Moulin : NSI 10/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Il existe plusieurs méthodes pour déterminer le PGCD de deux

entiers :

Algorithmique Lycée Jean Moulin : NSI 10/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Par soustractions :
385-210=175
210-175=35
175-35=140
140-35=105
105-35=70
70-35=35
35-35=0
PGCD→ 35

Algorithmique Lycée Jean Moulin : NSI 10/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Par soustractions :
385-210=175
Avec leur
210-175=35
décomposition en
175-35=140
produit :
140-35=105
385 = 7 × 6 × 5
105-35=70
210 = 7 × 5 × 11
70-35=35
PGCD→ 7 × 5 = 35
35-35=0
PGCD→ 35

Algorithmique Lycée Jean Moulin : NSI 10/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Par soustractions :
385-210=175
Avec leur L’algorithme
210-175=35
décomposition en d’Euclide :
175-35=140
produit : 385 = 1 × 210 + 175
140-35=105
385 = 7 × 6 × 5 210 = 1 × 175 + 35
105-35=70
210 = 7 × 5 × 11 175 = 5 × 35 + 0
70-35=35
PGCD→ 7 × 5 = 35 PGCD → 35
35-35=0
PGCD→ 35

Algorithmique Lycée Jean Moulin : NSI 10/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Algorithme de la 1ère méthode :
Données : :(a,b)∈ N∗ × N∗

fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 11/29

Algorithmique Analyse des algorithmes

Exemple : PGCD de deux entiers

Algorithme de la 1ère méthode :
Données : :(a,b)∈ N∗ × N∗ Sa traduction en Python :

fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 11/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Problème : Comment s’assurer qu’un algorithme se termine,

donne des résultats corrects et est efficace ?

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Problème : Comment s’assurer qu’un algorithme se termine,

donne des résultats corrects et est efficace ?
L’analyse des algorithmes peut se faire suivant trois axes :

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Problème : Comment s’assurer qu’un algorithme se termine,

donne des résultats corrects et est efficace ?
L’analyse des algorithmes peut se faire suivant trois axes :
• La terminaison : il s’agit de vérifier que l’algorithme ne tourne
pas de manière infinie

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Problème : Comment s’assurer qu’un algorithme se termine,

donne des résultats corrects et est efficace ?
L’analyse des algorithmes peut se faire suivant trois axes :
• La terminaison : il s’agit de vérifier que l’algorithme ne tourne
pas de manière infinie
• La correction : il faut s’assurer que le résultat renvoyé est le bon

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Analyse des algorithmes

Problématique

Problème : Comment s’assurer qu’un algorithme se termine,

donne des résultats corrects et est efficace ?
L’analyse des algorithmes peut se faire suivant trois axes :
• La terminaison : il s’agit de vérifier que l’algorithme ne tourne
pas de manière infinie
• La correction : il faut s’assurer que le résultat renvoyé est le bon
• La complexité : on spécifie le temps d’exécution en fonction de
la taille des données en entrée

Algorithmique Lycée Jean Moulin : NSI 12/29

Algorithmique Analyse des algorithmes

Pourquoi faire ?

Pourquoi ces études sont-elles intéressantes ?

On ne peut prouver un théorème par des exemples.

Algorithmique Lycée Jean Moulin : NSI 13/29

Algorithmique Analyse des algorithmes

Pourquoi faire ?

Pourquoi ces études sont-elles intéressantes ?

On ne peut prouver un théorème par des exemples.

Exemple :affirmer que les nombres se terminant par 9 sont
divisibles par 3 est faux.

Algorithmique Lycée Jean Moulin : NSI 13/29

Algorithmique Analyse des algorithmes

Pourquoi faire ?

Pourquoi ces études sont-elles intéressantes ?

On ne peut prouver un théorème par des exemples.

Exemple :affirmer que les nombres se terminant par 9 sont
divisibles par 3 est faux.
c’est vrai pour 9, 39, 69 et 1239 mais faux pour 19

Algorithmique Lycée Jean Moulin : NSI 13/29

Algorithmique Analyse des algorithmes

Pourquoi faire ?

Pourquoi ces études sont-elles intéressantes ?

La preuve de programme n’est pas encore très développée en

informatique industrielle. Le logiciel de vol de l’A380 (premier vol
en 2005) est le premier à avoir été prouvé : on sait de façon
certaine que les commandes de vol font ce qu’elles doivent faire.
Ce n’était pas le cas sur les avions précédents.

Algorithmique Lycée Jean Moulin : NSI 13/29

Algorithmique Analyse des algorithmes

Quelques anecdotes...

On trouve toutes sortes d’anecdotes sur Internet :

Algorithmique Lycée Jean Moulin : NSI 14/29

Algorithmique Analyse des algorithmes

Quelques anecdotes...

On trouve toutes sortes d’anecdotes sur Internet :

• Problème de terminaison : Le livre qui valait 23,7 million de
dollars (Amazon)

Algorithmique Lycée Jean Moulin : NSI 14/29

Algorithmique Analyse des algorithmes

Quelques anecdotes...

On trouve toutes sortes d’anecdotes sur Internet :

• Problème de terminaison : Le livre qui valait 23,7 million de
dollars (Amazon)
• Problème de correction : Le crash de la sonde Mars Climate
Orbiter (problème d’unité de mesure entre deux parties du
programme)

Algorithmique Lycée Jean Moulin : NSI 14/29

Algorithmique Analyse des algorithmes

Quelques anecdotes...

On trouve toutes sortes d’anecdotes sur Internet :

• Problème de terminaison : Le livre qui valait 23,7 million de
dollars (Amazon)
• Problème de correction : Le crash de la sonde Mars Climate
Orbiter (problème d’unité de mesure entre deux parties du
programme)
• Problème de complexité : Lors de sa mise en ligne le portail
France.fr n’avait pas prévu l’afflux de visiteurs...

Algorithmique Lycée Jean Moulin : NSI 14/29

Algorithmique Analyse des algorithmes

La terminaison d’un algorithme

Définition : Terminaison d’un algorithme

Un algorithme se termine, si son exécution sur machine s’arrête
toujours quelque soit la nature des données en entrée

Algorithmique Lycée Jean Moulin : NSI 15/29

Algorithmique Analyse des algorithmes

La terminaison d’un algorithme

Définition : Terminaison d’un algorithme

Un algorithme se termine, si son exécution sur machine s’arrête
toujours quelque soit la nature des données en entrée

Certaines instructions se terminent sans même que l’on ait besoin

de se poser de question. C’est le cas par exemple de l’affectation et
de la boucle bornée for.

Algorithmique Lycée Jean Moulin : NSI 15/29

Algorithmique Analyse des algorithmes

La terminaison d’un algorithme

Définition : Terminaison d’un algorithme

Un algorithme se termine, si son exécution sur machine s’arrête
toujours quelque soit la nature des données en entrée

Certaines instructions se terminent sans même que l’on ait besoin

de se poser de question. C’est le cas par exemple de l’affectation et
de la boucle bornée for.
Le problème vient des boucles «Tant que», il faut s’assurer qu’elles
se terminent et nous verrons que ce n’est pas toujours faisable...

Algorithmique Lycée Jean Moulin : NSI 15/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 1

Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 16/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 1

Données : n ∈ N
La terminaison :
S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 16/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 1

Données : n ∈ N
La terminaison :
S← 0
Les affectations ne posent pas de
Pour i allant de 0 à n faire
problème et la boucle est bornée
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 16/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 1

Données : n ∈ N
La terminaison :
S← 0
Les affectations ne posent pas de
Pour i allant de 0 à n faire
problème et la boucle est bornée
S=S+i
L’algorithme se termine bien...

retourner S

Algorithmique Lycée Jean Moulin : NSI 16/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2

Données : n ∈ N

S←0
i←0
Tant que i <= n faire
S=S+i
i=i+1

retourner S

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2
La terminaison :

Données : n ∈ N

S←0
i←0
Tant que i <= n faire
S=S+i
i=i+1

retourner S

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2
La terminaison :
Les affectations ne posent pas de
Données : n ∈ N problème

S←0
i←0
Tant que i <= n faire
S=S+i
i=i+1

retourner S

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2
La terminaison :
Les affectations ne posent pas de
Données : n ∈ N problème
Pour savoir si la boucle Tant que se
S←0 termine, il faut exhiber ce que l’on
i←0 appelle un variant de boucle, c’est à
Tant que i <= n faire dire une suite d’entiers strictement
S=S+i croissante majorée (ou strictement
i=i+1 décroissante minorée)

retourner S

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2
La terminaison :
Les affectations ne posent pas de
Données : n ∈ N problème
Pour savoir si la boucle Tant que se
S←0 termine, il faut exhiber ce que l’on
i←0 appelle un variant de boucle, c’est à
Tant que i <= n faire dire une suite d’entiers strictement
S=S+i croissante majorée (ou strictement
i=i+1 décroissante minorée)
La suite des itérateurs i fera l’affaire, à
retourner S chaque tour de boucle, i est incrémenté
de 1 et ne peut dépasser n

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 2
La terminaison :
Les affectations ne posent pas de
Données : n ∈ N problème
Pour savoir si la boucle Tant que se
S←0 termine, il faut exhiber ce que l’on
i←0 appelle un variant de boucle, c’est à
Tant que i <= n faire dire une suite d’entiers strictement
S=S+i croissante majorée (ou strictement
i=i+1 décroissante minorée)
La suite des itérateurs i fera l’affaire, à
retourner S chaque tour de boucle, i est incrémenté
de 1 et ne peut dépasser n
L’algorithme se termine bien...

Algorithmique Lycée Jean Moulin : NSI 17/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗
La terminaison :
fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗
La terminaison :
Les affectations ne posent pas de
fonction pgcd(a,b)
problème
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗
La terminaison :
Les affectations ne posent pas de
fonction pgcd(a,b)
problème
u←a
À chaque tour de boucle, on calcule la
v←b
différence u − v ou v − u.
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗
La terminaison :
Les affectations ne posent pas de
fonction pgcd(a,b)
problème
u←a
À chaque tour de boucle, on calcule la
v←b
différence u − v ou v − u.
Tant que u , v faire
La suite abs(u-v) est une suite d’entiers
Si u > v alors
strictement décroissante et positive
u ← u-v
(donc minorée par 0) et comme elle ne
Sinon peut décroître indéfiniment, elle
v ← v-u
atteindra donc 0

retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 3

Données : (a,b)∈ N∗ × N∗
La terminaison :
Les affectations ne posent pas de
fonction pgcd(a,b)
problème
u←a
À chaque tour de boucle, on calcule la
v←b
différence u − v ou v − u.
Tant que u , v faire
La suite abs(u-v) est une suite d’entiers
Si u > v alors
strictement décroissante et positive
u ← u-v
(donc minorée par 0) et comme elle ne
Sinon peut décroître indéfiniment, elle
v ← v-u
atteindra donc 0
L’algorithme se termine bien...
retourner u

Algorithmique Lycée Jean Moulin : NSI 18/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 4 (la suite de Syracuse)

La
 suite de Syracuse d’un nombre entier N > 0 est définie par :

 u0 = N > 0

 un
un+1 = si un est pair

2



n+1 = 3un + 1 sinon
 u

La conjecture de Syracuse, affirme que quelque soit l’entier N > 0
la suite aboutit sur le nombre 1 !
Il n’existe aucune preuve mathématique de ce résultat

Algorithmique Lycée Jean Moulin : NSI 19/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 4 (la suite de Syracuse)

Données : :N ∈ N∗

fonction syracuse(N)
u←N
Tant que u , 1 faire
Si u est pair alors
u ← u/2
Sinon
u ← 3*u+1

retourner u

Algorithmique Lycée Jean Moulin : NSI 20/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 4 (la suite de Syracuse)

Données : :N ∈ N∗

fonction syracuse(N)
u←N La terminaison :
Tant que u , 1 faire
Si u est pair alors
u ← u/2
Sinon
u ← 3*u+1

retourner u

Algorithmique Lycée Jean Moulin : NSI 20/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 4 (la suite de Syracuse)

Données : :N ∈ N∗

fonction syracuse(N)
u←N La terminaison :
Tant que u , 1 faire Comme il n’existe pas de preuve
Si u est pair alors mathématique, et même si tous les
u ← u/2 nombres testés aboutissent bien sur 1
Sinon
u ← 3*u+1

retourner u

Algorithmique Lycée Jean Moulin : NSI 20/29

Algorithmique Analyse des algorithmes

Terminaison : exemple 4 (la suite de Syracuse)

Données : :N ∈ N∗

fonction syracuse(N)
u←N La terminaison :
Tant que u , 1 faire Comme il n’existe pas de preuve
Si u est pair alors mathématique, et même si tous les
u ← u/2 nombres testés aboutissent bien sur 1
Sinon On ne peut prouver la terminaison...
u ← 3*u+1

retourner u

Algorithmique Lycée Jean Moulin : NSI 20/29

Algorithmique Analyse des algorithmes

La correction d’un algorithme

Définition : Correction d’un algorithme

Un algorithme est correct, si son exécution sur machine donne
toujours le bon résultat quelque soit l’entrée

Algorithmique Lycée Jean Moulin : NSI 21/29

Algorithmique Analyse des algorithmes

La correction d’un algorithme

Définition : Correction d’un algorithme

Un algorithme est correct, si son exécution sur machine donne
toujours le bon résultat quelque soit l’entrée

Pour montrer qu’un algorithme est correct, on utilise ce que l’on

appelle un invariant de boucle

Algorithmique Lycée Jean Moulin : NSI 21/29

Algorithmique Analyse des algorithmes

La correction d’un algorithme

Définition : Correction d’un algorithme

Un algorithme est correct, si son exécution sur machine donne
toujours le bon résultat quelque soit l’entrée

Pour montrer qu’un algorithme est correct, on utilise ce que l’on

appelle un invariant de boucle
Un invariant de boucle est une propriété :
• Qui est vérifiée après l’initialisation

Algorithmique Lycée Jean Moulin : NSI 21/29

Algorithmique Analyse des algorithmes

La correction d’un algorithme

Définition : Correction d’un algorithme

Un algorithme est correct, si son exécution sur machine donne
toujours le bon résultat quelque soit l’entrée

Pour montrer qu’un algorithme est correct, on utilise ce que l’on

appelle un invariant de boucle
Un invariant de boucle est une propriété :
• Qui est vérifiée après l’initialisation
• Qui reste vraie après l’exécution d’une itération

Algorithmique Lycée Jean Moulin : NSI 21/29

Algorithmique Analyse des algorithmes

La correction d’un algorithme

Définition : Correction d’un algorithme

Un algorithme est correct, si son exécution sur machine donne
toujours le bon résultat quelque soit l’entrée

Pour montrer qu’un algorithme est correct, on utilise ce que l’on

appelle un invariant de boucle
Un invariant de boucle est une propriété :
• Qui est vérifiée après l’initialisation
• Qui reste vraie après l’exécution d’une itération
• Qui permet de montrer que le résultat attendu est bien celui qui
est calculé
Algorithmique Lycée Jean Moulin : NSI 21/29
Algorithmique Analyse des algorithmes

Correction : exemple 1

Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 22/29

Algorithmique Analyse des algorithmes

Correction : exemple 1
La correction :

Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 22/29

Algorithmique Analyse des algorithmes

Correction : exemple 1
La correction :
On considère la propriété : S
contient la somme des entiers
jusqu’à n
Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 22/29

Algorithmique Analyse des algorithmes

Correction : exemple 1
La correction :
On considère la propriété : S
contient la somme des entiers
jusqu’à n
Données : n ∈ N Lors de l’initialisation, S contient
0 donc S contient bien la somme
S← 0 des entiers jusqu’à 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 22/29

Algorithmique Analyse des algorithmes

Correction : exemple 1
La correction :
On considère la propriété : S
contient la somme des entiers
jusqu’à n
Données : n ∈ N Lors de l’initialisation, S contient
0 donc S contient bien la somme
S← 0 des entiers jusqu’à 0
Pour i allant de 0 à n faire Pour i=k, S contient la somme
S=S+i des k premiers entiers, à l’étape
suivante i=k+1 S contiendra la
retourner S somme des k+1 premiers entiers

Algorithmique Lycée Jean Moulin : NSI 22/29

Algorithmique Analyse des algorithmes

Correction : exemple 1
La correction :
On considère la propriété : S
contient la somme des entiers
jusqu’à n
Données : n ∈ N Lors de l’initialisation, S contient
0 donc S contient bien la somme
S← 0 des entiers jusqu’à 0
Pour i allant de 0 à n faire Pour i=k, S contient la somme
S=S+i des k premiers entiers, à l’étape
suivante i=k+1 S contiendra la
retourner S somme des k+1 premiers entiers
Puisque l’algorithme se termine
pour k=n, et que S contient la
somme des n premiers entiers,
l’algorithme est donc correct
Algorithmique Lycée Jean Moulin : NSI 22/29
Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗
La correction :
fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗
La correction :
On considère la propriété :
fonction pgcd(a,b)
pgcd(a,b)=pgcd(u,v)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗
La correction :
On considère la propriété :
fonction pgcd(a,b)
pgcd(a,b)=pgcd(u,v)
u←a
Un théorème de mathématique nous
v←b
assure que :
Tant que u , v faire
pgcd(u, v) = pgcd(u−v, v) = pgcd(u, v−u)
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗
La correction :
On considère la propriété :
fonction pgcd(a,b)
pgcd(a,b)=pgcd(u,v)
u←a
Un théorème de mathématique nous
v←b
assure que :
Tant que u , v faire
pgcd(u, v) = pgcd(u−v, v) = pgcd(u, v−u)
Si u > v alors
Comme c’est exactement ce qu’il se
u ← u-v
passe à chaque itération et que celle-ci
Sinon se termine sur pgcd(u, u)
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Correction : exemple 2

Données : (a,b)∈ N∗ × N∗
La correction :
On considère la propriété :
fonction pgcd(a,b)
pgcd(a,b)=pgcd(u,v)
u←a
Un théorème de mathématique nous
v←b
assure que :
Tant que u , v faire
pgcd(u, v) = pgcd(u−v, v) = pgcd(u, v−u)
Si u > v alors
Comme c’est exactement ce qu’il se
u ← u-v
passe à chaque itération et que celle-ci
Sinon se termine sur pgcd(u, u)
v ← v-u
L’algorithme calcule bien ce qu’il
promet...
retourner u

Algorithmique Lycée Jean Moulin : NSI 23/29

Algorithmique Analyse des algorithmes

Complexité d’un algorithme

En plus d’être correct, on demande à un algorithme d’être efficace.

Algorithmique Lycée Jean Moulin : NSI 24/29

Algorithmique Analyse des algorithmes

Complexité d’un algorithme

En plus d’être correct, on demande à un algorithme d’être efficace.

Cette efficacité peut être évaluée par :

Algorithmique Lycée Jean Moulin : NSI 24/29

Algorithmique Analyse des algorithmes

Complexité d’un algorithme

En plus d’être correct, on demande à un algorithme d’être efficace.

Cette efficacité peut être évaluée par :
• le temps que prend l’exécution de l’algorithme : c’est la
complexité en temps. Le temps d’exécution dépend de la taille
des données fournies en entrée.

Algorithmique Lycée Jean Moulin : NSI 24/29

Algorithmique Analyse des algorithmes

Complexité d’un algorithme

En plus d’être correct, on demande à un algorithme d’être efficace.

Cette efficacité peut être évaluée par :
• le temps que prend l’exécution de l’algorithme : c’est la
complexité en temps. Le temps d’exécution dépend de la taille
des données fournies en entrée.
• les ressources nécessaires à son exécution : c’est la complexité
en mémoire

Algorithmique Lycée Jean Moulin : NSI 24/29

Algorithmique Analyse des algorithmes

Complexité d’un algorithme

En plus d’être correct, on demande à un algorithme d’être efficace.

Cette efficacité peut être évaluée par :
• le temps que prend l’exécution de l’algorithme : c’est la
complexité en temps. Le temps d’exécution dépend de la taille
des données fournies en entrée.
• les ressources nécessaires à son exécution : c’est la complexité
en mémoire
On s’intéressera à la complexité en temps qui correspond au
nombre d’opérations élémentaires

Algorithmique Lycée Jean Moulin : NSI 24/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants
• affectation simple

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants
• affectation simple
• accès aux éléments d’un tableau, modification d’un éléments
d’un tableau et taille d’un tableau

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants
• affectation simple
• accès aux éléments d’un tableau, modification d’un éléments
d’un tableau et taille d’un tableau
• La méthode append sur une liste Python peut être considérée
comme une opération basique

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants
• affectation simple
• accès aux éléments d’un tableau, modification d’un éléments
d’un tableau et taille d’un tableau
• La méthode append sur une liste Python peut être considérée
comme une opération basique
• la gestion de la variable de boucle d’une boucle Pour

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - opérations élémentaires

Nous étudions donc le nombre d’opérations élémentaires
On considère comme élémentaire les opérations :
• addition, soustraction, multiplication, division, modulo sur des
entiers ou des flottants
• affectation simple
• accès aux éléments d’un tableau, modification d’un éléments
d’un tableau et taille d’un tableau
• La méthode append sur une liste Python peut être considérée
comme une opération basique
• la gestion de la variable de boucle d’une boucle Pour
• les tests élémentaires, utilisés principalement dans les boucles
Tant que et les structures conditionnelles

Algorithmique Lycée Jean Moulin : NSI 25/29

Algorithmique Analyse des algorithmes

Complexité - Les types de complexité

Notation : O(n) ou Θ(n)

Algorithmique Lycée Jean Moulin : NSI 26/29

Algorithmique Analyse des algorithmes

Complexité - Les types de complexité

En s’appuyant sur une base de 109 opérations par secondes, le

tableau ci-dessous donne le temps d’exécution des différentes
complexités citées précédemment.

Il faut donc éviter les complexités supérieures à la complexité

polynomiale d’ordre 2...

Algorithmique Lycée Jean Moulin : NSI 26/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

La complexité :
Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

La complexité :
S ← 0 une opération
Données : n ∈ N

S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

La complexité :
S ← 0 une opération
Données : n ∈ N
Il y a n + 1 additions et n + 1
affectations
S← 0
Pour i allant de 0 à n faire
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

La complexité :
S ← 0 une opération
Données : n ∈ N
Il y a n + 1 additions et n + 1
affectations
S← 0
Il y a également les n
Pour i allant de 0 à n faire
incrémentations de la boucle for
S=S+i

retourner S

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 1

La complexité :
S ← 0 une opération
Données : n ∈ N
Il y a n + 1 additions et n + 1
affectations
S← 0
Il y a également les n
Pour i allant de 0 à n faire
incrémentations de la boucle for
S=S+i
Il y a au total 3n + 3 opérations
élémentaires. Dans ce cas on dira
retourner S que la complexité est linéaire et
cela se note : O(n) ou Θ(n)

Algorithmique Lycée Jean Moulin : NSI 27/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b)
u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b) La complexité :

u←a
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b) La complexité :

u←a 2 affectations
v←b
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b) La complexité :

u←a 2 affectations
v←b Le pire des cas possible est a = n et b = 1
Tant que u , v faire
Si u > v alors
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b) La complexité :

u←a 2 affectations
v←b Le pire des cas possible est a = n et b = 1
Tant que u , v faire Il y aura n tests (Tant que), n test (Si), n
Si u > v alors soustractions et n affectations
u ← u-v
Sinon
v ← v-u

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 2

Données : (a,b)∈ N∗ × N∗

fonction pgcd(a,b) La complexité :

u←a 2 affectations
v←b Le pire des cas possible est a = n et b = 1
Tant que u , v faire Il y aura n tests (Tant que), n test (Si), n
Si u > v alors soustractions et n affectations
u ← u-v Au total 4n + 2 opérations élémentaires
Sinon soit une complexité linéaire notée Θ(n)
v ← v-u ou O(n)

retourner u

Algorithmique Lycée Jean Moulin : NSI 28/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3

Données : n n ∈ N

S← 0
Pour i allant de 1 à n faire
Pour j allant de 1 à n faire
S=S+i+j
retourner S

Algorithmique Lycée Jean Moulin : NSI 29/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3
La complexité :

Données : n n ∈ N

S← 0
Pour i allant de 1 à n faire
Pour j allant de 1 à n faire
S=S+i+j
retourner S

Algorithmique Lycée Jean Moulin : NSI 29/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3
La complexité :
1 affectation

Données : n n ∈ N

S← 0
Pour i allant de 1 à n faire
Pour j allant de 1 à n faire
S=S+i+j
retourner S

Algorithmique Lycée Jean Moulin : NSI 29/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3
La complexité :
1 affectation
Pour chaque i on fait 2n
Données : n n ∈ N additions et n affectations

S← 0
Pour i allant de 1 à n faire
Pour j allant de 1 à n faire
S=S+i+j
retourner S

Algorithmique Lycée Jean Moulin : NSI 29/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3
La complexité :
1 affectation
Pour chaque i on fait 2n
Données : n n ∈ N additions et n affectations
Il y aura donc n × (3n) + 1
S← 0 opérations élémentaires
Pour i allant de 1 à n faire
Pour j allant de 1 à n faire
S=S+i+j
retourner S

Algorithmique Lycée Jean Moulin : NSI 29/29

Algorithmique Analyse des algorithmes

Complexité : exemple 3
La complexité :
1 affectation
Pour chaque i on fait 2n
Données : n n ∈ N additions et n affectations
Il y aura donc n × (3n) + 1
S← 0 opérations élémentaires
Pour i allant de 1 à n faire De plus chaque incrémentation
Pour j allant de 1 à n fairede i ou j compte pour une
S=S+i+j opération élémentaire soit : n × n
opérations supplémentaires
retourner S Au total il y a : 4n2 + 1 opérations
élémentaires. Soit une
complexité quadratique notée
Θ(n2 ) ou O(n2 )

Algorithmique Lycée Jean Moulin : NSI 29/29