Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [email protected]
Département : Informatique FSSM
Université Cadi Ayyad
Filière SMI S3
1
Année universitaire : 2023/2024
Plan du cours
Rappel (Algorithmique I)
Tableaux
Fonctions et procédures
Récursivité
Algorithmes de tri
Pointeurs et Enregistrements
Fichiers
Complexité et preuve d’algorithme
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 2
Plan du cours
CHAPITRE 0 : RAPPEL (ALGORITHMIQUE I)
1. Notion d’algorithme
2. Du problème au résultat
3. Représentation d’un algorithme
4. Notion de donnée
5. Instructions de base
6. Structures de contrôle
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 3
Rappel (Algorithmique I)
1. Notion d’algorithme
Un algorithme correspond à la description d’une méthode de résolution pour un
problème donné ( Algorithme = méthode de résolution).
Cette description est effectuée par une suite d’instructions d’un langage humain.
Ces instructions permettent de traiter et de transformer les données (entrées) du
problème à résoudre pour aboutir à des résultats (sorties).
Un algorithme n’est pas une solution en soi, mais une méthode à suivre pour trouver les
solutions.
Une bonne connaissance de l’algorithmique permet d’écrire des algorithmes exacts et
efficaces.
4
Rappel (Algorithmique I)
1. Notion d’algorithme
Un algorithme doit:
avoir un nombre fini d’étapes (instructions);
avoir un nombre fini d’opérations par étape;
se terminer après un nombre fini d’opérations;
fournir un résultat.
Chaque opération doit être:
définie rigoureusement et sans ambiguïté;
effective, c-à-d réalisable par une machine.
Un algorithme est une suite finie d’instructions à appliquer, dans un ordre déterminé, sur
des données afin d'aboutir à un certain résultat en un temps fini.
5
Rappel (Algorithmique I)
2. Du problème au résultat
Phase de Phase de
Phase Phase
Problème conception traduction Résultat
d’analyse d’exécution
(Algorithme) (Programme)
Sur papier Sur machine
6
Rappel (Algorithmique I)
3. Représentation d’un algorithme
Algorithme Nom_algorithme
Constantes /*Déclaration des constantes*/
Variables /*Déclaration des variables*/
Début
/*commentaire
sur plusieurs lignes */
//commentaire sur une seule ligne
Instruction1
Instruction2
…
Instructions n
Fin
Pseudo-code Organigramme
7
Rappel (Algorithmique I)
4. Notion de donnée
Les données sont les objets manipulés par les instructions d'un algorithme. Elles peuvent
être des variables ou des constantes.
Une variable est le nom d’un espace mémoire dont le contenu peut changer pendant
l’exécution d'un algorithme.
Une constante est le nom d’un espace mémoire dont le contenu ne change jamais,
contrairement à une variable il garde la même valeur pour un algorithme.
Chaque donné est caractérisée par :
Un identificateur (nom);
Un type (entier, réel, caractère, chaîne de caractères, booléen,…);
Une valeur.
8
Rappel (Algorithmique I)
4. Notion de donnée
La première chose à faire avant de pouvoir utiliser une donnée (variable ou constante) est
de lui réserver l’espace mémoire nécessaire. Ceci se fait tout au début de l’algorithme,
avant même les instructions proprement dites. C’est ce qu’on appelle la déclaration des
données.
Déclaration : Exemple :
Constante nomConstante = valeur; Constante pi = 3.14;
Variable nomVariable : Type; Variable rayon : réel;
9
Rappel (Algorithmique I)
4. Notion de donnée
Exemple :
L’en-tête Algorithme Exemple;
Constantes
PI = 3.14;
Message = "Bonjour";
La partie déclarative Variables
A1: Entier;
A2 : Chaine de caractères;
Début
Instruction_1;
Le corps de l’algorithme …
Instruction_N;
Fin.
10
Rappel (Algorithmique I)
5. Instructions de base
Affectation : c’est l’opération qui permet de ranger la valeur d’une expression dans une
variable. Elle se note généralement en algorithmique avec le signe .
Syntaxe : Exemple:
Nom_variable valeur ou expression; age 20;
Lecture : L’instruction de lecture permet de lire des valeurs à partir du clavier et les
affecter aux variables.
Syntaxe : Exemple:
Lire(var1, var2, …); Lire(nom, age);
Ecriture : L’instruction d'écriture permet d'afficher les valeurs des variables ou expressions
à l'écran.
Syntaxe : Exemple:
Ecrire(expression_1, expression_2,…); Ecrire(“La surface est : ”, surface);
11
Rappel (Algorithmique I)
6. Structures de contrôle
Structure
Séquentielle Conditionnelle Itérative
12
Rappel (Algorithmique I)
6. Structures de contrôle – Séquentielle –
La structure séquentielle est une structure dont les instructions s’enchaînent les unes après les
autres et s’exécutent une seule fois au cours de l’algorithme. C'est la structure la plus simple
d'un algorithme.
Exemple :
Algorithme surfaceRectangle;
Variables
longueur, largeur, surface : Réel;
Début
Ecrire (“Veuillez saisir la longueur et la largeur du rectangle : ”);
Lire (longueur, largeur);
surface longueur*largeur;
Ecrire (“La surface du rectangle est : ”, surface);
Fin
13
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle –
Structure
conditionnelle
A choix
Simple Alternative
multiple
14
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle simple –
Syntaxe :
Si (condition) Alors
Instruction(s);
FinSi
Pseudo-code Organigramme
La condition est nécessairement une expression booléenne.
15
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle simple –
Exemple :
Algorithme quotientDeuxEntiers;
Variables
nombre1, nombre2 : Entier;
quotient : Réel;
Début
Ecrire (“Veuillez saisir deux entiers :”);
Lire (nombre1, nombre2);
Si (nombre2 <> 0) alors
quotient nombre1/nombre2;
Ecrire (nombre1,“ / ”, nombre2, “ = ”, quotient);
FinSi
Fin
16
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle alternative –
Syntaxe :
Si (condition) Alors
Instruction(s)_1;
Sinon
Instruction(s)_2;
FinSi
Pseudo-code Organigramme
17
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle alternative –
Exemple :
Algorithme pair;
Variable a : entier ;
Début
Ecrire("Entrez un nombre entier : ") ;
Lire(a );
Si ( ( a % 2 ) = 0 ) alors
Ecrire("Le nombre " , a , " est pair." ) ;
Sinon
Ecrire("Le nombre " , a , " est impair." ) ;
Finsi
Fin.
18
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle alternative –
La clause SinonSi
On peut ajouter autant de clause SinonSi que de conditions à tester.
Syntaxe : Si (condition1) Alors
Instruction(s)_1;
SinonSi (condition2) Alors
Instruction(s)_2;
…
SinonSi (conditionN) Alors
Instruction(s)_N;
Sinon
Instruction(s);
FinSi
Pseudo-code Organigramme 19
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle alternative –
Exemple (Clause SinonSi):
Algorithme signe ;
Variable nombre : réel ;
Début
Ecrire("Entrez un nombre réel") ;
Lire(nombre);
Si ( nombre < 0 ) alors
Ecrire("Le nombre : " , nombre , " est négatif." ) ;
SinonSi ( nombre > 0 ) alors
Ecrire("Le nombre : " , nombre , " est positif." ) ;
Sinon
Ecrire("Le nombre : " , nombre , " est nul." ) ;
Finsi
Fin.
20
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle à choix multiples –
La structure conditionnelle à choix multiples permet une programmation plus claire en
évitant une trop grande imbrication de Si successifs. Elle permet de choisir le traitement à
effectuer en fonction de la valeur ou de l'intervalle de valeurs d'une variable ou d'une
expression.
Syntaxe :
Selonque variable_selecteur vaut
Liste_Valeurs_1 : Instruction(s)_1;
Liste_Valeurs_2 : Instruction(s)_2;
...
Liste_Valeurs_n : Instruction(s)_n;
Sinon Instruction(s)_m;
FinSelon
21
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle à choix multiples –
Exemple : Algorithme jours;
Variable n: entier ;
Début
Ecrire(“Donner un numéro de jour entre 1 et 7 :”) ;
Lire(n) ;
SelonQue n Vaut
1 : Ecrire(“Lundi”) ;
2 : Ecrire(“Mardi”) ;
3 : Ecrire(“Mercredi”) ;
4 : Ecrire(“Jeudi”) ;
5 : Ecrire(“Vendredi”) ;
6 : Ecrire(“Samedi”) ;
7 : Ecrire(“Dimanche”) ;
Sinon : Ecrire (“ il faut choisir un nombre entre 1 et 7!! ”) ;
FinSelon
Fin. 22
Rappel (Algorithmique I)
6. Structures de contrôle – Conditionnelle –
Imbrication de SI
Naturellement, il est possible d’imbriquer les structures de contrôle conditionnelles les unes
à l’intérieur des autres, comme ceci : Si (condition1) Alors
Si (condition2) Alors
Instruction(s)1;
Sinon Instruction(s);
FinSi
Sinon
Si (condition3) Alors
Instruction(s);
Sinon Instruction(s);
FinSi
FinSi
23
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative –
Structure itérative
À condition
À condition
Complète (Pour) d’arrêt
d’arrêt (TantQue)
(Répéter…jusqu’à)
24
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative Complète (Pour) –
Syntaxe :
Pour i de initiale à finale [Pas de p] faire
Instruction(s);
FinPour
Pseudo-code Organigramme
Remarques :
i est une variable de type entier (ou caractère). Elle doit être déclarée.
p est un entier qui peut être positif ou négatif. p peut ne pas être mentionné, car par
défaut sa valeur est égal à 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 i.
25
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative Complète (Pour) –
Exemple :
Algorithme bonjour100Fois;
Variable i : Entier;
Début
Pour i de 1 à 100 Faire
Ecrire ("Bonjour chers étudiants !! ") ;
FinPour
Fin
26
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative à condition d’arrêt (TantQue) –
Syntaxe :
TantQue (condition) faire
Instruction(s);
FinTantQue
Pseudo-code Organigramme
Remarques :
Le contenu de la structure TantQue peut ne jamais être exécuté. Donc cette structure permet en réalité
de répéter un traitement 0 ou plusieurs fois.
La condition étant évaluée au début, les variables utilisées dans la condition doivent avoir été initialisées.
On doit s'assurer de la terminaison (sinon l’algorithme ne se termine jamais). Pour cela, il faut
nécessairement que dans le corps de la structure, la condition soit modifiée quelque part.
27
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative à condition d’arrêt (TantQue) –
Exemple :
Algorithme saisirEntierPositif;
Variable valeur : Entier;
Début
Ecrire ("Veuillez saisir un entier positif :");
Lire(valeur);
TantQue valeur < 0 faire
Ecrire ("Erreur : Veuillez saisir un entier positif");
Lire(valeur);
FinTantQue
Fin.
28
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative à condition d’arrêt (Répéter… jusqu’à) –
Syntaxe :
Répéter
Instruction(s);
Jusqu’à (condition);
Pseudo-code Organigramme
Remarques :
Il y a toujours au moins une exécution du bloc d’instructions. La structure Répéter… jusqu’à permet de
répéter un traitement 1 ou plusieurs fois.
Pour choisir entre Répéter… jusqu’à et TantQue il faut se poser la question : faut-il éventuellement ne
jamais faire le traitement ? Si oui : il faut utiliser TantQue , sinon utiliser la structure Répéter… jusqu’à qui
exécute au moins une fois le traitement.
29
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative à condition d’arrêt (Répéter… jusqu’à) –
Exemple :
Algorithme saisirEntierPositif;
Variable valeur : Entier;
Début
Ecrire ("Veuillez saisir un entier positif :");
Répéter
Lire(valeur);
Si valeur < 0 alors
Ecrire ("Erreur : Veuillez saisir un entier positif");
Jusqu’à valeur >= 0;
Fin.
30
Rappel (Algorithmique I)
6. Structures de contrôle – Itérative –
Nombre
Conclusion: d’itérations
connu?
Oui Non
Traitement
Structure itérative
exécuté au moins
POUR
une fois ?
Oui Non
Structure itérative Structure itérative
Répéter…Jusqu’à TantQue
31
Merci pour votre
attention
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 32
Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Informatique 2 : Algorithmique I
Pr. Ilyass OUAZZANI TAYBI
E-mail : [email protected]
Département : Informatique FSSM
Université Cadi Ayyad
Filière SMI S3
Année universitaire : 2023/2024
