Université Sidi Mohamed Ben Abdellah
Faculté Polydisciplinaire Taza
Filière Licence Fondamentale
SMI
Algorithmique II
Semestre 3
Prof: Chakir EL-KASRI
Email: [Link]@[Link]
C. EL-KASRI Année universitaire 2019/2020
Introduction aux réseaux informatiques
M15: Algorithmique II
Algorithmique II
Introduction générale
Fonctions et Procédures
La récursivité
Enregistrements et fichiers
La complexité
Preuves d'algorithmes
C. EL-KASRI 2
M15: Algorithmique II
Objectifs du module
Approfondir les concepts fondamentaux de
l'algorithmique
Analyser un problème et construire la ou les algorithmes
pour le résoudre
Découvrir et maitriser de nouvelle concepts en
algorithmique
Evaluer les différentes solutions en termes de calcul de
complexité
Choisir la meilleure solution
3 C. EL-KASRI
Objectifs du cours
Au cours de ce semestre, nous nous positionnerons sur les 6 niveaux
de la taxonomie de Bloom1 :
1. Connaissance : mémorisation et restitution d’informations dans les
mêmes termes.
2. Compréhension : restitution du sens des informations dans d’autres
termes.
3. Application : utilisation de règles, principes ou algorithmes pour
résoudre un problème, les règles n’étant pas fournies dans l’énoncé.
4. Analyse : identification des parties constituantes d’un tout pour en
distinguer les idées.
5. Synthèse : réunion ou combinaison des parties pour former un tout.
6. Evaluation : formulation de jugements qualitatifs ou quantitatifs.
1: référence pédagogique pour la classification des niveaux d’apprentissage
4 C. EL-KASRI
Objectifs du cours
Durant ce cours nous cherchons à développer trois « qualités »
comportementales chez l’informaticien (débutant) : la rigueur, la
persévérance et l’autonomie.
Rigueur : La respect des consignes, la précision et l’exactitude sont
donc de rigueur en informatique !.
Persévérance : le débutant est confronté à de
nombreuses erreurs, et sa tendance naturelle est de
passer à autre chose. Mais le zapping est une très
mauvaise stratégie en informatique : pour s’exécuter
correctement, un programme doit être finalisé.
L’informatique nécessite d’« aller au bout des choses
».
5 C. EL-KASRI
Objectifs du cours
Autonomie : Programmer soi-même les algorithmes qu’on
a définis. Par ailleurs, l’évolution continuelle et soutenue
des langages de programmation et des ordinateurs
nécessitent de se tenir à jour régulièrement et seule
l’autoformation systématique permet de « ne pas perdre
pied ».
Pratique personnelle et autoformation constituent ainsi deux piliers
de l’autonomisation nécessaire de l’apprenti informaticien.
6 C. EL-KASRI
Chapitre 1
Introduction générale
7 C. EL-KASRI
Algorithmes classiques
Chemin dans un graphe : GPS, IP, acheminement (la Poste) …
Flots : affectations, emploi du temps, bagages (aéroport), portes
d’embarquement
Scheduling (ordonnancement) fabrication de matériel dans les
usines, construction automobiles
Coupes : coupes d’acier, poterie …
Compression/Décompression : MP3, xvid, divx, h264 codecs
audio et vidéo tar zip.
Cryptage : RSA (achat électronique)
Internet : Routage des informations, moteurs de recherche
Simulation : Prévision météo, Explosion nucléaire
Traitement d’images (médecine) , effets spéciaux (cinéma)
8 C. EL-KASRI
Algorithmique
L’aspect scientifique de l’informatique
L'algorithmique est la partie conceptuelle d'un
programme d'ordinateur.
« L'informatique n'est pas plus la science des
ordinateurs que l'astronomie n'est celle des
télescopes »
E. Dijkstra, Turing award 1972
9 C. EL-KASRI
Algorithme
Un algorithme prend en entrée des données et fournit un
résultat permettant de donner la réponse à un problème
Un algorithme = une série d’opérations à effectuer :
Opérations exécutées en séquence ⇒ algorithme séquentiel.
Opérations exécutées en parallèle ⇒ algorithme parallèle.
Opérations exécutées sur un réseau de processeurs ⇒ algorithme
réparti ou distribué.
Mise en œuvre de l’algorithme
implémentation (plus général que le codage)
écriture de ces opérations dans un langage de programmation.
Donne un programme.
10 C. EL-KASRI
Algorithme versus programme
Un programme implémente un algorithme
Les problèmes ayant une solution algorithmique
sont ceux résolvables par une machine par une
machine de Turing (théorie de la calculabilité)
On ne peut pas résoudre tous les problèmes avec
des algorithmes
Savoir de façon indépendante si un algorithme est
juste
11 C. EL-KASRI
Algorithme
Tous les algorithmes ne sont pas équivalents.
On les différencie selon 2 critères
Temps de calcul : lents vs rapides
Mémoire utilisée : peu vs beaucoup pp
On parle de complexité en temps (vitesse) ou
en espace (mémoire utilisée)
12 C. EL-KASRI
Algorithme
Etapes de rédaction d'un algorithme :
Décrire clairement le problème
Comprendre le problème
Spécifier le problème
Identifier les résultats souhaités
Identifier les données
Déterminer les transformations à faire sur ces
données pour obtenir les résultats
13 C. EL-KASRI
Algorithme
Composantes d'un l'algorithme :
Des objets représentés par des symboles et définis
par un nom, un type et une valeur.
Les variables
Les constantes
Des actions représentées par des symboles ou des
verbes à l'infinitif.
lire,
écrire
14 C. EL-KASRI
Algorithme
Exemple : On souhaite calculer la surface d'un
cercle
Spécification du problème :
Données :
Résultats souhaités :
Traitement à faire sur ces données :
15 C. EL-KASRI
Chapitre 2
Les procédures et les fonctions
16 C. EL-KASRI
Plan
Pourquoi les procédures et les fonctions?
Les procédures
Les fonctions
17 C. EL-KASRI
Pourquoi les procédures et les fonctions?
Deux raisons:
R1
Algorithme de grande taille => plus de complexité
Difficile à gérer => découper le en sous-algorithme (solution!)
R2
Une suite d'actions se répète plusieurs fois.
Ce bloc d'instruction sera réutilisé dans plusieurs endroits pour effectuer
les mêmes calculs avec des données différentes.
Solution
Il serait donc très judicieux de n'écrire ce bloc d'instructions
qu'une seule fois, et de l’utiliser autant de fois que c'est
nécessaire.
Il existe deux sorte de sous-algorithme : les procédures et les fonctions
18 C. EL-KASRI
Pourquoi les procédures et les fonctions?
Exemple : calcul de
Commet découper l’exemple précédent en sous-
algorithme?
Trois bénéfices :
améliorer la lisibilité des programmes,
optimiser le nombre d'instructions dans un
programme,
faciliter la mise au point et la correction des
erreurs.
19 C. EL-KASRI
les procédures
Définition et syntaxe
Définition:
Une procédure est une série d’instructions regroupées sous un nom, qui
permet d’effectuer des actions par un simple appel de la procédure dans un
algorithme ou dans un autre sous-algorithme
Une procédure renvoie plusieurs valeurs (pas une) ou aucune valeur
Syntaxe:
Procédure nom_proc (liste de paramètres)
Variables identificateurs: type
Debut
Instruction(s)
FinProc
Apres le nom de la proc, il faut donner la liste des paramètres (s’il y en a) avec leur
type respectif. Ces paramètres sont appelés paramètres formels. Leur valeur n’est
pas connue lors de la création de la procédure.
20 C. EL-KASRI
les procédures
Définition et syntaxe : Exemple
Exemple
Ecrire une procédure qui affiche à l’écran une ligne de 15 étoiles
puis passe à la ligne suivante.
Procédure Etoiles()
Variables i: entier
Début
Pour i 1 jusqu’à 15 Faire
Ecrire("*");
FinPour
Ecrire("\n");
FinProc
21 C. EL-KASRI
les procédures
l’appel d’une procédure
Pour déclencher l’exécution d’une procédure dans un
programme, il suffit de l’appeler.
L’appel de procédure s’écrit en mettant le nom de la procédure,
puis la liste des paramètres, séparés par des virgules.
A l’appel d’une procédure, le programme interrompt son déroulement
normal, exécute les instructions de la procédure, puis retourne au
programme appelant et exécute l’instruction suivante.
Syntaxe:
Nom_Proc( liste de parametres );
Les paramètres utilisés lors de l’appel d’une procédure
sont appelés paramètres effectifs. Ces paramètres
donneront leurs valeurs aux paramètres formels
22 C. EL-KASRI
les procédures
l’appel d’une procédure : Exemple
Exemple:
En utilisant la procédure Etoiles, Ecrire un algorithme permettant de dessiner un carré
d’étoiles de 15 lignes et de 15 colonnes.
Algorithme carre_etoiles
// declaration de la proc
Procédure Etoiles()
Variables i: entier
Début
Pour i 1 jusqu’à 15 Faire
Ecrire("*");
FinPour
Ecrire("\n");
FinProc
// algo principal
Début
Pour i 1 jusqu’à 15 Faire
Etoiles();
FinPour
Fin
23 C. EL-KASRI
les procédures
l’appel d’une procédure: Remarques
Remarque 1
Pour exécuter un algo qui contient des procédures et des
fonctions, il faut commencer l’exécution à partir de la partie
principale
Remarque 2
Lors de la conception d’un algo deux aspects
apparaissent :
La définition (déclaration) de la procédure ou fonction
L’appel de la procédure ou fonction au sein de l’algorithme
principal
24 C. EL-KASRI
les procédures
passage de paramètres
C’est quoi?
Les échanges d’informations entre une procédure et
l’algorithme appelant se font par l’intermédiaire de
paramètres.
Les paramètres formels déclarés dans une procédure doivent
être représentés leurs noms et leurs types.
Avant l'appel de la procédure dans le programme principal on
doit déclarer une liste de paramètres effectifs correspondant
(en nombre, rang, et type) à la liste des paramètres formels.
Deux types de passage
Passage par valeur
Passage par référence ou adresse
25 C. EL-KASRI
les procédures
passage de paramètres (par valeur)
Passage par valeur
Le paramètre formel reçoit uniquement une copie de la
valeur du paramètre effectif.
C'est le mode de passage par défaut.
La valeur du paramètre effectif ne sera jamais modifiée
Exemple (TD)
Définir/proposer une procédure proc1 pour laquelle on utilise le
passage de paramètres par valeur.
Faire une exécution en discutant le principe de passage de
paramètres par valeur.
26 C. EL-KASRI
les procédures
passage de paramètres (par valeur)
Exemple (TD) suite
Algorithme passage_par_valeur Appel de Proc1:
Variables n: entier
La valeur du paramètre effectif n est
// declaration de la proc
Procédure Proc1(a: entier)
recopié dans le paramètre formel a.
Variables i: entier Proc1 effectue alors le traitement et
Début
a a*2; affiche la valeur de a. Dans ce cas
Ecrire(a); 10
FinProc
// algo principal Apres l’appel de Proc1, l’algo
Début
n 5;
affiche la valeur de n. dans ce cas 5.
Proc1(n); La procédure ne modifie pas le
Ecrire(n);
Fin paramètre qui est passé par valeur.
les procédures
passage de paramètres (par valeur)
Algorithme Echange
Variables a, b, i: entiers
Exemple 2 (TD) si on donne respectivement aux
// declaration de la proc variables a et b les valeurs 8 et 3.
Procédure Proc2(x: entier, y: entier)
Variables tampon: entier
Le programme
Début affiche I=5 (le résultat de a-b).
tampon x;
Après l'appel de la procédure Proc2
x y;
y tampon; normalement a devient 3 et b
FinProc
// algo principal
devient 8 après permutation et I
Début devient -5.
Lire(a);
Mais comme le passage utilisé dans
Lire(b);
i a-b; cet exemple est un passage par
Ecrire(i);
valeur a et b reste sans
Proc2(a,b);
i a-b; changement.
Ecrire(i);
I=a-b reste tel qu'il est aussi.
Ecrire(a);
Ecrire(b);
28 C. EL-KASRI
les procédures
passage de paramètres
Le paramètre formel "i" est une variable
Exemple 3 (TD) simple.
Algorithme Passage_par_val3 Le paramètre effectif correspondant "x"
Variables x: entiers est une expression de même type.
// declaration de la proc Avant d'exécuter les instructions de la
Procédure Proc3(i: entier) procédure la valeur du paramètre effectif
Début
est affectée au paramètre formel.
i 3* i;
Ecrire (" val de i =", i); Dans ce cas, le paramètre formel est
considéré comme une variable locale qui
FinProc
est initialisée lors de l'appel. Compléter
// algo principal
Début le tableau suivant :
Ecrire (" x :");
Lire(x);
Ecrire (" Avant appel x =", x);
Proc3(x);
Ecrire (" apres appel x =", x);
Fin
29 C. EL-KASRI
les procédures
passage de paramètres (par valeur)
Remarques
Les paramètres effectifs et les paramètres formels
doivent s'accorder du point de vue nombre et ordre.
Leurs types doivent être identiques selon le mode de
passage des paramètres
Le transfert d'information est effectué dans un seul sens,
du programme principal vers la procédure.
Toute modification du paramètre formel est sans
conséquence sur le paramètre effectif.
30 C. EL-KASRI
les procédures
passage de paramètres
Passage par référence ou par adresse
Dans ce mode, la procédure utilise l’adresse du
paramètre effectif.
Lorsqu’on utilise l’adresse du paramètre, on accède
directement à son contenu.
La valeur de la variable effectif sera donc modifiée.
Les paramétres passés par adresse sont précédés du mot
clé Var
31 C. EL-KASRI
les procédures
passage de paramètres
Exemple
Algorithme passage_par_valeur
Variables n: entier
Appel de Proc1:
Affiche 10 : de la procédure
// declaration de la proc
Procédure Proc1(Var a: entier) Dans le PP affiche aussi 10
Variables i: entier Passage par référence (adresse).
Début
a a*2;
Ecrire(a);
FinProc
// algo principal
Début
n 5;
Proc1(n);
Ecrire(n);
Fin
32 C. EL-KASRI
les procédures
passage de paramètres
Exemple 2
Faire une exécution avec a=8 et
b=3
Interprétation :
le programme affiche les
résultats suivants :
I=5
I= -5
a=3
b=8
Ce qui explique le changement
réel des valeurs de a et b.
33 C. EL-KASRI
les procédures
passage de paramètres
Exercice
Qu’affiche à l’ecran l’algorithme
suivant?
Eléments de réponse
La présence du mot clé Var
passage de paramètre par adresse
Résultat
Avant l’appel 10 20
Début echange 10 20
Fin echange 20 10
Fin echange 20 10
Exercice 2
Enlever le mot Var et faire une
comparaison des deux algo
34 C. EL-KASRI
Les fonctions
Définition
Une fonction est une procédure particulière.
Les fonctions sont des sous algorithmes admettant des
paramètres et retournant un seul résultat de type simple
qui peut apparaitre dans une expression, dans une
comparaison, à la droite d’une affectation.
Il est obligatoire de préciser le type de la fonction(type du
résultat à retourner).
35 C. EL-KASRI
Les fonctions
Déclaration
Syntaxe
Proche de celle d’une procédure
On ajoute un type qui représente le type de retour de la
fonction.
La dernière instruction renvoie au programme appelant le
résultat de l’expression placée à la suite du mot clé Retourner.
Fonction nom_Fonction (liste de paramètres): type
Variables identificateurs: type
Debut
Instruction(s)
Retourner Expression
FinFonct
36 C. EL-KASRI
Les fonctions
Déclaration
Exemple:
Définir une fonction qui renvoie la plus grand de deux nombres différents.
// declaration de la fonction
Fonction Max (x: réel, y: réel): réel
Début
Si x > y Alors
Retourner x;
SiNon
Retourner y;
FinSi
FinFonction
37 C. EL-KASRI
Les fonctions
Appel d’une fonction
Syntaxe
Via son nom suivi des paramètres effectifs.
nom_Fonction (liste de paramètres)
Exemple: Algorithme Appel_FctMax
Variable a, b, m : Réels
Ecrire un algorithme appelant, Fonction Max (x: réel, y: réel): réel
utilisant la fonction Max (exemple Début
précédent). Si x > y Alors
Retourner x;
SiNon
Retourner y;
FinSi
FinFonction
// P.P
Debut
Lire(a);
Lire(b);
M Max(a,b);
Ecrire ("le Max est :",m);
Fin
38 C. EL-KASRI
Variables locales et globales (1)
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
29/10/2019 39
Variables locales et globales (2)
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
Accessible qu’à la procédure au sein de laquelle elle est définie
Les autres procédures n’y ont pas accès
Le durée de vie d’une variable locale est limité à la durée de l’exécution de la
procédure.
• En pseudo-code, on va adopter cette règle pour les variables locales et on déclarera
les variables globales dans le programme principale
Accessible de n’importe où dans l’algorithme, même depuis les procédures et les
fonction
Il existe pendant toute la durée de vie du programme
• 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
29/10/2019 40
Les fonctions
Portée des variables
Exemple
Algorithme Portee x et y sont des variables
Variable x, y : Entiers globales visibles dans tout
Procedure P1 () l’algorithme
Variables a: Entier
Début
…
a est une variables locale
…
visible uniquement à l’intérieur
FinProc de la procédure
// Algorithme principal
Debut
Remarque:
…
… Les variables globales sont à
…
éviter pour la maintenance des
Fin
programmes
41 C. EL-KASRI
