Cours Algo [PDF]

Zitiervorschau

CH1 : ELEMENTS D’ALGORITHMIQUE I/Quelques définitions Définition 1 (Algorithme). Un algorithme est suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème. Historique : Le mot « algorithme » provient de la forme latine (Algorismus) du nom du mathématicien arabe ALKHAREZMI Thèse de Turing-Church: les problèmes ayant une solution algorithmique sont ceux résolubles par une machine de Turing (théorie de la calculabilité) Troisième loi de Greer : un programme informatique ne fait jamais ce que vous voudriez qu’il fasse …, il fait seulement ce que vous lui dites de faire. 

Un algorithme est un procédé calculatoire sur un problème donné en nombre fini d’instructions pour obtenir des résultats.



La programmation est l’activité de traduire dans un langage de programmation un algorithme.

L’activité de programmation se résume aux étapes suivantes : -la présentation d’un problème concret -l’analyse du problème -l’écriture d’algorithmes -le codage dans un langage de programmation Différences entre algorithmes et programmes Un programme est la réalisation (l’implémentation) d’un algorithme au moyen d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre du principe. Par exemple, lors de la programmation on s’occupera parfois explicitement de la gestion de la mémoire (allocation dynamique en C) qui est un problème d’implémentation ignoré au niveau algorithmique.

II /Structure générale d’un algorithme ALGORITHME identificateur ; CONST(constante) Nom_constante=valeur ;

TYPE(type) Nom_type=définition ; VAR(variable) Description des ressources manipulées dans l’algorithme

DEBUT(programme principal) Description du processus opératoire

FIN. Dans la rubrique des constantes il s’agit de déclarer des constantes qui peuvent être manipulées par le programme. Ex  : taille d’un tableau Au niveau de la rubrique type, il s’agit de définir des types pouvant être utilisés. Généralement ce sont des types construits par le concepteur. Ex  : un enregistrement de type « étudiant » défini par les champs matricule, nom, classe et solde. Dans la partie variable il s’agit de déclarer toutes les ressources manipulées dans le programme. Ces ressources peuvent être des ressources données, des fonctions ou des procédures. Enfin dans le programme principal on décrit le processus opératoire. III / Structures de données simples 1. Syntaxe d’un identificateur Un identificateur est le nom donné par le programmeur à tout objet manipulé dans l’algorithme. Il permet de nommer un objet informatique appelé ressource donnée ou ressource action. La règle syntaxique utilisée est qu’un identificateur est une suite de caractères alphanumériques avec le premier étant un caractère. Ex  : salaire2007 ; salaire_juin ; SalaireJuin ; Salaire13ememois ;

identificateurs valides

13ememois ; Salaire juin ;

identificateurs non valides

Remarques : -

Il n’y a pas de limitation du nombre de caractères pour l’écriture d’un identificateur.

-

Il faut choisir au mieux un nom très proche de la réalité.

-

faire attention à la casse des caractères car en général, les langages de programmation sont sensibles à la casse.

Notion de Variable Une variable est une donnée que l’on est appelé à manipuler dans l’algorithme. Elle peut être de plusieurs types. VAR Nom : chaîne de caractères[20] ; Age : entier ; 2. Le type entier Le type entier est utilisé pour les identificateurs appartenant à l’ensemble des entiers relatifs. Ex  : VAR X : ENTIER ;

XЄZ

3 . Le type réel Le type réel est utilisé pour les identificateurs appartenant à l’ensemble des réels. Ex  : VAR X : REEL ;

XЄR

4 . Le type caractère Le type caractère est utilisé pour les identificateurs appartenant à l’ensemble des caractères. Ex  : VAR X : CARACTERE ; x Є { A,…,Z,0,…,9,caractères spéciaux}

5 . Le type chaîne de caractères Le type chaîne de caractères est utilisé pour les identificateurs appartenant à l’ensemble des mots. Ex  : VAR X : CHAINE DE CARACTERES[taille] ; (ou CHAINE) Généralement sur plusieurs plateformes de développement, les chaînes de caractères sont simulées par les tableaux de caractères. 6. Le type logique Le type logique est utilisé pour des identificateurs appartenant à l’espace de valeur « vrai » ou «faux ». Ex  : VAR L : logique ; L Є {V,F} 7. Les tableaux Un tableau est un objet organisé ou structuré permettant de manipuler plusieurs informations de même type en nombre fixe durant la vie de l’algorithme. Chaque élément du tableau est appelé composante. Les tableaux sont stockés en mémoire centrale comme les autres variables contrairement aux fichiers qui sont stockés sur disque. Une propriété importante des tableaux est de permettre un accès direct aux données grâce à l’indice. On appelle vecteur un tableau à une seule dimension. La syntaxe de déclaration d’un tableau est : Identificateur :TABLEAU[Vi..Vf] DE TYPE ; Ici Vi représente la valeur initiale et Vf la valeur finale, ce sont des constantes de tout type. Ex  : T : TABLEAU[1..5] DE ENTIER Remarque : Pour parcourir un tableau on utilise un indice de parcours. Ex  : POUR I ← 1 JUSQU'A N FAIRE LIRE(T[I]) ; Les matrices

Les matrices sont faites pour simuler des tableaux de tableaux. Soit A une matrice à n lignes et p colonnes ou chaque composante a i,j est d’un type donné. La syntaxe de déclaration est : VAR A : TABLEAU[1..N ,1..P] DE TYPE ;

N lignes

A[I,J]

P colonnes

Pour manipuler la matrice A l’on peut utiliser 2 indices de parcours I et J. Ex  : A :TABLEAU[1..N] DE TABLEAU[1..P] DE T. POUR I ← 1 JUSQU'A N FAIRE POUR J ← 1 JUSQU'A P FAIRE LIRE(A[I,J]) ;

IV/ les actions Les actions concernent les opérations décrivant le processus opératoire. 1. Les expressions arithmétiques EXPRESSION Addition Soustraction Multiplication Division réelle Division entière Modulo

SYMBOLE + * / DIV MOD

2. Les expressions logiques

EXEMPLE 7+2 = 9 7-2 = 5 7*2 = 14 7/2 = 3.5 7 DIV 2 = 3 7 MOD 2 = 1

Les expressions logiques sont données par : -la négation (NON) -la conjonction (ET) -la disjonction (OU) L1 V V F F

L2 V F V F

NON L1 F F V V

L1 OU L2 V V V F

L1 ET L2 V F F F

3. Les expressions relationnelles Elles concernent les variables appartenant à des ensembles ordonnés et le résultat est logique. Les opérateurs relationnels sont : EXPRESSION Supérieur Supérieur ou égal Inférieur Inférieur ou égal Egal Différent

SYMBOLE > ≥ < ≤ = ≠

4. L’affectation Le symbole utilisé pour l’affectation est : «  ← » et la règle syntaxique est la suivante : Identificateur ← expression ; Remarque : Dans un problème d’affectation les règles de compatibilité de type exigent que l’expression et l’identificateur soient du même type ou que l’expression soit d’un type contenu dans celui de l’identificateur. Ex  : disc ← b*b-4*a*c ; 5. Les entrées sorties Pour les entrées, la lecture se fait à partir d’une unité périphérique quelconque. Dans notre cas, il s’agira souvent du clavier. La syntaxe utilisée est :

LIRE(liste identificateurs) ; Ex  : LIRE (A,B) ; Pour la sortie, l’affichage se fait sur une unité périphérique quelconque. Dans notre cas il s’agira souvent de l’écran. La syntaxe utilisée est : ECRIRE(liste identificateurs ou expression) ; Ex  : ECRIRE(‘somme de’, A ,’et’, B, ’est :’, A + B) ; V / Les structures de contrôle 1. La séquence Ex  : disc←b*b – 4*a*c ; x1←(-b- racine(disc))/(2*a) ; x2←(-b+racine(disc))/(2*a) ; 2. Primitive de blocage Les primitives de blocage sont utilisées pour un bloc d’actions. La primitive est ouverte avec l’instruction « DEBUT » et fermée avec l’instruction « FIN ». Ex  : DEBUT A ← 3 ; B ← 5 ; C ← A + B ; ECRIRE(C) ; FIN ; 3. L’alternative L’alternative c’est nous donner la possibilité d’exécuter une action si une condition est réalisée ou non. La règle syntaxique utilisée est la suivante : SI (expression logique) ALORS Action1 SINON Action2 ; Remarque : Au cas où Action1 ou Action2 sont composées d’actions élémentaires, il faut utiliser la primitive de blocage (début et fin).

Ex  :

SI(expression logique) ALORS DEBUT Action11 ; Action1n ; FIN ; SINON DEBUT Action21 ; Action2n ; FIN ;

Ex  : SI(total≥200) ALORS DEBUT ECRIRE(‘admis’) ; ECRIRE(‘s’inscrire INPHB’) ; FIN ; SINON DEBUT ECRIRE(‘échoué’) ; ECRIRE(‘reprendre la terminale’) ; FIN ; 4. La conditionnelle La conditionnelle est une variante de l’alternative. La syntaxe est la suivante : SI(expression logique) ALORS Action ; Ex  :

SI(moy≥10) ALORS ECRIRE(‘me marier’) ;

5. La structure itérative (répétitive) La structure itérative c’est le fait de répéter une action tant qu’une condition reste vraie. La syntaxe utilisée est : TANTQUE (expression logique) FAIRE

Action ; Remarque : Action doit contenir un moyen de gérer l’expression logique afin que l’algorithme s’arrête. Ex  :

Fact ← 1 ; I ← 1 ; TANT QUE (I≤N) FAIRE DEBUT Fact ← Fact*I ; I ← I + 1 ; FIN ;

Une variante de la structure itérative est la boucle POUR que l’on utilise quand on connaît le nombre d’itérations. Syntaxe : POUR (identificateur ← valeur_début) JUSQU'A valeur_fin FAIRE Action ; Ex  :

Fact ← 1 ; POUR I ← 1 JUSQU'A N FAIRE Fact ← Fact*I ;

Une autre variante de la structure itérative est la répétitive dont la syntaxe est : REPETER Action JUSQU'A (condition) ; Ex  :

REPETER DEBUT ECRIRE(‘entrer code’) ; LIRE(code) ; FIN JUSQU'A (code = ‘inphb’) ;

6. La structure de choix multiples Une donnée est successivement comparée à des valeurs constantes. Cas Ou Donnée Vaut Valeur1 : Actions1 Valeur2 : Actions2 ... ValeurN : ActionsN Autre : ActionsDéfaut FinCas Remarque : la partie ActionsDéfaut peut ne pas exister.

Plusieurs valeurs différentes peuvent être regroupées sur une même ligne si les actions correspondantes sont identiques. Exemple : affichage de la nature d’un caractère. Var C : caractère ; Début Ecrire(‘Donner un caractère’) ; Lire(c ) ; Cas Ou c vaut ‘A’..’Z’ : écrire(‘Lettre majuscule) ; ‘a’..’z’ : écrire(‘Lettre minuscule) ; ‘0’..’9’ : écrire(‘Chiffre’) ; autre : écrire(‘Ni lettre ni chiffre’) ; Fin Cas fin

CH2 : FONCTIONS ET PROCEDURES I / Notion de modularité Lorsqu’un problème s’avère complexe on le découpe en petits problèmes de complexité moindre pour faciliter sa résolution. En informatique, généralement lorsqu’un programme est grand, on le découpe en sousprogrammes : c’est la notion de modularité. Les différents modules peuvent être des fonctions ou des procédures. Cela a offert de nombreux avantages à la programmation dont : -la réutilisation des sous-programmes -le gain de temps -une maintenance plus facile des logiciels II/ Les procédures Une procédure est un sous-programme qui permet de découper un programme en plusieurs morceaux. Chaque procédure définit une nouvelle instruction que l’on peut appeler en tout endroit du programme. Le découpage d’un problème en procédures qu’on implémente relève d’une analyse descendante, c’est à dire aller du général au spécifique. Ecrire une procédure c’est tout simplement donner un nom à un groupe d’instructions. L’appel de ce nom à divers endroits du programme provoque à chaque fois l’exécution de ce groupe d’instructions. 1. Procédure sans paramètre Une ressource action est appelée procédure et a la même structure qu’un algorithme, c’est à dire qu’elle est identifiée par un nom et se décrit formellement dans le niveau VAR de la ressource mère après celle, généralement, des données. ALGORITHME identificateur ; CONST Déclaration des constantes TYPES Déclarations des types VAR Déclaration des variables PROCEDURE identificateur ; VAR Ressources propres à la procédure DEBUT

FIN ; DEBUT(programme principal) FIN. L’activation d’une procédure se fait dans la partie principale par un appel à l’exécution en la nommant. Dans le corps d’une procédure deux sortes de ressources peuvent être manipulées : -les ressources locales définies dans la partie description des ressources de la procédure et leur domaine de validité se limite strictement à cette procédure, donc à sa durée de vie. -les ressources non locales définies dans la partie description des ressources de la procédure mère. De la même manière ces ressources sont aussi accessibles par toutes les procédures internes à la procédure en question. Remarque : -les ressources déclarées au niveau de l’algorithme sont dites ressources globales et leur durée de vie est égale au temps d’exécution de l’algorithme. -Quand une variable est locale à une procédure, il n’y a pas d’inconvénient que le même identificateur soit utilisé pour une variable de la procédure mère, la règle étant que celle qui est la plus directement visible est prise en compte.

ALGORITHME Essai ; VAR X,Y :ENTIER ; PROCEDURE Echange ; VAR T : ENTIER ; DEBUT T ← X ; X ← Y ; Y ← T ; ECRIRE(X,Y) ; FIN ; DEBUT(programme principal) ECRIRE(‘1er programme procédure’) ; X ← 2 ; Y ← -1 ; Echange ; FIN .

Echange est une procédure sans paramètre car lors de l’appel elle n’a pas besoin d’informations d’appel. 2. Procédure avec paramètres A l’activation d’une procédure les seules informations concernées sont celles qui lui sont locales et toutes celles qui lui sont globales. De ce fait, la seule possibilité de faire parvenir des informations à l’entrée d’une autre procédure ou de faire communiquer des informations résultats après son activation est de les déclarer au niveau global. Quelques fois, le besoin de paramétrer une procédure s’impose car généralement les procédures ou fonctions communiquent entre elles. Lors de la manipulation d’une procédure, il faudrait faire le distinguo entre les paramètres formels et les paramètres effectifs. Un paramètre est dit formel lorsqu’il est décrit lors de la description d’une procédure. Un paramètre est dit réel ou effectif lorsqu’il est fourni par la procédure appelant et il peut varier d’un appel à l’autre lors de l’activation de la procédure. Remarque : Les paramètres réels indiqués dans l’appel se substituent aux paramètres formels en respectant l’ordre dans lequel ils ont été déclarés ainsi que leur type. ALGORITHME Essai ; VAR X,Y :ENTIER ;(Variable globale) PROCEDURE Echange(I,J :ENTIER) ; VAR T :ENTIER.(Variable locale) DEBUT T ← I ; I ← J ; J← T ; ECRIRE(I,J) ; FIN ; DEBUT (Programme principal) ECRIRE(‘1er programme procédure’) ; X ← 2 ; Y ← -1 ; ECRIRE(X,Y) ; Echange(X,Y) ; FIN. Puisque les procédures et fonctions communiquent entre elles, il se pose la problématique de transmission de paramètres. Une variable se définit comme un contenu et un contenant auxquels il va falloir faire attention au mode de transmission. a) Mode de transmission par valeur Un paramètre est dit passé par valeur si c’est le contenu qui est passé, donc accessible dans la procédure indépendamment de son contenant. La syntaxe utilisée pour une procédure quand les paramètres sont passés par valeur est :

PROCEDURE identificateur (liste identificateur :type1,…, liste identificateur :typeN) ; VAR Description des ressources locales

DEBUT Description action de la procédure

FIN ; Ex  : ALGORITHME MTN ; VAR R : ENTIER ; PROCEDURE Bonus(PCT :ENTIER) ; DEBUT PCT ← 1,1*PCT ; ECRIRE(PCT) ; FIN ; DEBUT R ← 5000 ; ECRIRE(R) ; Bonus(R) ; ECRIRE(R) ; FIN. Quelles que soient les modifications opérées sur les paramètres formels passés par valeur, après exécution de la procédure, le paramètre effectif retrouve sa valeur d’avant appel. b) Mode de transmission par adresse Un paramètre est dit passé par adresse si toute modification du paramètre effectif dans la procédure appelée se retrouve après son activation. En d’autres termes c’est l’adresse du paramètre représentée par l’identificateur c’est à dire le contenant qui est passé comme argument contrairement au passage par valeur où c’est le contenu. La syntaxe de déclaration d’une procédure dont les paramètres sont passés par adresse est : PROCEDURE(VAR liste ident :type1,…,VAR liste ident :typeN) ; VAR Description ressources locales

DEBUT Description processus opératoire

FIN ;

Ex  : ALGORITHME MTN_ADRESSE ; VAR R : ENTIER ; PROCEDURE Bonus(VAR PCT :ENTIER) ; DEBUT PCT ← 1,1*PCT ; ECRIRE(PCT) ; FIN ; DEBUT R ← 5000 ; ECRIRE(R) ; Bonus(R) ; ECRIRE(R) ; FIN. Une utilisation du paramètre passé par adresse est la récupération du résultat après l’activation de la procédure. III/ Les fonctions Une fonction est une procédure particulière ou on privilégie un résultat particulier à condition qu’il soit unique et qu’il soit aussi de type simple. Une fonction est une procédure qui renvoie un résultat de manière à ce qu’on puisse l’appeler dans une expression. Une fonction peut être sans paramètre ou avec paramètres. Lorsqu’elle a des paramètres les arguments sont passés par valeur. La syntaxe de déclaration d’une fonction sans paramètres est : FONCTION identificateur : type ; VAR Description des ressources locales

DEBUT Description du processus opératoire

FIN ;

Identificateur ← expression du même type que la fonction

La syntaxe de déclaration d’une fonction avec paramètres est : FONCTION identificateur(liste ident :type) :type ; VAR Description des ressources locales

DEBUT Description du processus opératoire

FIN ;

Identificateur ← expression de même type que la fonction

Ex  : ALGORITHME TEST_SOMME ; VAR A,B :ENTIER ; FONCTION Somme(I,J :ENTIER) :ENTIER ; VAR Som,K : ENTIER; DEBUT K ← 5 ; ECRIRE(‘merci’,K,’fois pour l’addition’) ; Som ← I + J ; Somme ← Som ; FIN ; DEBUT ECRIRE(‘essai d’une fonction’) ; A ← 3 ; B ← -15 ; ECRIRE(‘la somme est :’,Somme(A,B)) ; FIN .

CH3 : LES TYPES COMPOSES A côté des types prédéfinis comme ENTIER, REEL, CARACTERE etc… le concepteur peut construire d’autres types qu’il fait admettre au compilateur et à ce moment-là, l’on pourra utiliser des variables de ce type. 1. Types intervalles Un intervalle est un sous ensemble de valeurs consécutives de types hôtes. La syntaxe de déclaration est : N..M Où N et M sont des constantes du même type, et sont les bornes inférieures et supérieures de l’intervalle avec N et M inclus. Ex  : VAR Age : 0..150 ; 2. Type énuméré En général l’on utilise le type énuméré pour créer un espace de valeurs où toutes les valeurs sont connues. Ex  : VAR Feux : (orange, rouge, vert) ; Illustration : Type Mois = (JANVIER, FÉVRIER, ..., DÉCEMBRE) ; --- Attention : une machine ne comprend pas les « ... ». Il faut donc lister --- explicitement toutes les valeurs possibles. Jour = (LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI, SAMEDI, DIMANCHE) ; Couleur = (ROUGE, JAUNE, VERT, BLEU, VIOLET) ; -- quelques couleurs Variable M : Mois ; C : Couleur ; Debut m