COUR D’ALGORITHMIQUE
Notions fondamentales d’Algorithmique
Moussa Djiriba Traore
Un cour conçu pour AEL1S2
DER d’Agroéconomie
Faculté d’Agronomie et de Médecine Animale(FAMA)
Université de Ségou
Mali
20 juillet 2024
L’ALGORITHMIQUE
§0 AVANT PROPOS
L’algorithmique est une branche de l’informatique, elle entre dans la formation de base de toutes les
disciplines qui nécessitent de l’informatique-mathématique. Le volume horaire général de l ?UE est de 40
heures, dont 15 heures de CM, 20 heures de TDs, et 15 heures de TPE. Dans l ?UE les questions suivantes
sont examinées : les types, les entées-sorties, la syntaxe, les fonctions et procédures, les enregistrements, les
pointeurs, adresses et allocation, notion de complexité d’un algorithme.
§1 LANGAGE ALGORITHMIQUE ET COMPLEXITE
§1.1 POURQUOI CET AUTRE LANGAGE
L’informatique comprend de nombreux langages de programmation (C, C++, Java, javascript, Caml,
Fortran, Pascal, Basic, Lisp, Prolog, Cobol, etc.).
Programmer dans tous ces langage requiert une connaissance de base qui est indépendante du langage
de programmation : l ?algorithmique. Pour cela, on doit distinguer les algorithmes, qui sont des méthodes
applicables par des ordinateurs pour résoudre différents problèmes, de leur implémentation dans tel ou tel
langage particulier.
Nous étudions dans ce chapitre un langage algorithmique qui n ?est pas un langage de programmation. Ce
langage n ?est pas très éloigné conceptuellement du langage C que l’on étudiera un peu plus tard. Il permet
à priori de concevoir les algorithmes indépendamment de leur implémentation en C.
§1.2 TYPES
Les types de base du langage sont :
• entier : c’est le type nombre entier, correspondant au type int du C, sauf qu’il n’est pas nécessairement
codé sur 4 octets.
• reel : c’est le type nombre réel, pouvant correspondre avec les types double ou float du C.
• caractere : c’est le type caractère, correspondant au type char du C. Pour un tel caractere c, la fonction
ASCII(c) donnera le code ASCII de c.
§1.3 ENTREES-SORTIES
Clavier et écran
La fonction lire permet de lire une variable. Si x est une variable (de type entier, réel, caractère ou
chaîne de caractères), l ?instruction :
Lire(x) ; permet de lire au clavier la valeur de x.
La fonction ecrire permet d ?écrire le contenu d ?une variable à l ?écran. Si x est une variable (de type entier,
réel, caractère ou chaîne de caractères), l ?instruction :
ecrire(x) ;
permet d ?afficher la valeur de x.
Fichiers texte
Le type fichier permet de lire et d ?écrire dans un fichier. Pour cela, il faut d’abord déclarer et ouvrir
un fichier :
Fichier f ;
f ← ouvrir("[Link]", "lect") ;
Les modes d ?ouverture de fichiers peuvent être "lect" (lecture seule), "ecr" (écriture seule), ou bien le mode
lecture-écriture "lectEcr".
La fonction lireF permet de lire une variable dans un fichier. Si x est de type entier, réel, caractère ou chaîne
de caractères, et f un fichier ouvert en lecture, l ?instruction :
lireF(x, f) ;
met dans x la première valeur lue dans le fichier (et avance la position courante dans le fichier).
La fonction ecrireF permet d ?écrire une variable dans un fichier texte. Si x est de type entier, réel, caractère
ou chaîne de caractères, et f un fichier ouvert en écriture, l ?instruction :
ecrireF(x, f) ;
permet d ?écrire la valeur de x dans le fichier (et avance la position courante dans le fichier).
§1.4 SYNTAXE
L’affectation est notée ←, le test d’égalité est noté =.
Exemple 1
L’algorithme suivant calcule et affiche 2n, où n est saisi au clavier.
Algorithme
début
entier i, n, puiss ;
puiss ← 1 ;
lire(n) ;
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2 ;
fin faire
ecrire(puiss) ;
fin
Exemple 2
Voici une version interactive de l’algorithme précédent :
Algorithme
début
entier i, n, puiss ;
caractere choix ;
ecrire("Voulez-vous calculer une puissance de 2 ? ")
lire(choix) ;
si choix = ’y’ faire
puiss ← 1 ;
i ← 0;
lire(n) ;
tant que i<n faire
puiss ← puiss * 2 ;
i ← i+1
fin faire
ecrire(puiss) ;
fin faire
fin
§1.5 FONCTIONS ET PROCÉDURES
Fonctions
Une fonction en langage algorithmique aura un prototype de la forme :
FONCTION NomFonction(Type1 nom1, type2 nom2,...) : TypeRetour
où :
• TypeRetour est le type de la valeur retournée par la fonction ;
• NomFonction est le nom de la fonction ;
• Type1, Type2... sont les types respectifs des paramètres ;
• nom1, nom2... sont les identificateurs respectifs des paramètres.
Exemple 3
L’algorithme ci-dessus calculant 2n peut être restructuré à l ?aide d ?une fonction : FONCTION DeuxPuiss(entier
n) : entier
début
entier i, puiss ;
puiss ← 1 ;
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2 ;
fin faire
retourner puiss ;
fin
Algorithme
début
entier n, puiss ;
lire(n) ;
puiss ← DeuxPuiss(n) ;
ecrire(puiss) ;
fin
Procédures
Une procédure est similaire à une fonction, mais elle ne retourne aucune valeur. Une procédure aura un
prototype de la forme :
PROCEDURE NomFonction(Type1 nom1, typ2 nom2,...)
Exemple 4
Dans l’exemple suivant, la procédure Affiche permet l’affichage d’une donnée de type entier.
FONCTION DeuxPuiss(entier n) : entier
début
entier i, puiss ;
puiss ← 1 ;
pour i ← 0 à n-1 pas 1 faire
puiss ← puiss * 2 ;
fin faire
retourner puiss ;
fin
PROCEDURE Affiche(entier a)
début
ecrire("l’entier vaut : ") ;
ecrire(a) ;
fin
Algorithme
début
entier n, puiss ;
lire(n) ;
puiss ← DeuxPuiss(n) ;
Affiche(puiss) ;
fin