COMRECIT

Ce complément de cours s’articule autour d’un langage algorithmique objet (noté L.A.O.) inspiré du langage Java qui est le langage d’application des trois premières années ESSTIN en informatique. Son avantage est double :

- il oblige le programmeur à travailler sur papier afin de minimiser la durée de développement et surtout d’éviter des erreurs grossières d’analyse;

- il facilite aussi le déboguage du logiciel en cours d’implémentation via un langage de programmation comme Java, C#... En effet, il permet de se libérer des contraintes techniques liées à de tels langages.

1.1 - Structure générale d’un algorithme

Un algorithme est une succession séquentielle d’opérations élémentaires (ou bloc d’instructions) permettant d’obtenir le résultat final désiré pour un problème donné. Ainsi, un algorithme bien conçu, dans des conditions identiques de données d’entrée, doit toujours fournir le même résultat. La structure générale d’un algorithme est donnée par les trois mots clés en majuscule :

ALGORITHME nom_de_l’algorithme // partie en-tête

DEBUT // partie traitement

un_ou_plusieurs_blocs_d’instructions;

FIN

Remarque: Il est vivement conseillé d’adopter les conventions ci-dessous:

- les mots-clés du langage algorithmique sont toujours en MAJUSCULES sinon ils doivent être soulignés. Ici, ce sont les délimiteurs DEBUT (ou DEB) et FIN. Les mots-clés ‘DEBUT’ et ‘FIN’ peuvent être remplacés respectivement par ‘{’ et ‘}’.

- un bloc d’instructions est un tout ou une partie du traitement d’un algorithme entre DEB et FIN ou entre des accolades: accolade ouvrante (‘{‘) et fermante (‘}’).

- Les commentaires sont des explications textuelles à la suite des deux caractères: // ou entre les délimiteurs:

/**

une_ou_plusieurs_lignes_de_commentaires_ici

L’algorithme ci-après illustre l’affichage du message «Salut 2A & 2A+ !» en deux versions:

ALGORITHME bonjour0 | ALGORITHME bonjour1

DEBUT | DEBUT

ECRIRE(«Salut ») | ECRIRE(«Salut 2A & 2A+ !\n»)

ECRIRE(«2A & 2A+ !») | FIN

ECRIRE() // pour passer à la ligne. | // le caractère ‘\n’ le permet aussi.

FIN |

Ainsi, via cet exemple, on constate qu’il y a souvent plusieurs solutions équivalentes possibles pour résoudre un problème donné. La version ‘bonjour0’ va afficher le message en deux lignes puis descendre à la ligne alors que la seconde version fera la même chose mais en une seule instruction. Il est donc préférable de choisir le plus simple ici (‘bonjour1’).

Le mot-clé ECRIRE

-----------------

Il permet l’affichage, sur le périphérique standard de sortie (i.e. la console de visualisation), des données textuelles (i.e. une ou plusieurs phrases) appelées aussi CONSTANTES de CHAINES de caractères. C’est aussi une procédure d’écriture pour des données numériques (i.e. format à virgule flottante et scientifique …). Elle peut être représentée aussi par le mot-clé ‘AFF’ comme abréviation de «AFFICHER».

Le mot-clé LIRE

---------------

Il permet la saisie de données par l’utilisateur via le périphérique standard d’entrée (i.e. le clavier). Il est équivalent au mot-clé ‘SAISIR’. Dans la version simplifiée en tant que procédure de lecture, il doit comporter au moins un argument désignant une variable de l’algorithme. Exemple d’emploi:

LIRE(uneVariable) // <=> uneVariable <-- Type.convType(SAISIR_CHAINE()).

En Java, le mot-clé LIRE sera traduit comme une fonction de lecture d’une chaîne de caractères («SAISIR_CHAINE()»), qui sera convertie au format correspondant (‘Type’) à la variable étudiée nommée ‘uneVariable’ ici. Mais, qu’est-ce que c’est une variable en informatique ?

1.2 - Les variables et les constantes

Une VARIABLE désigne une place mémoire qui permet de stocker une valeur à manipuler dans l’algorithme. Elle est définie par :

- un identificateur ou nom unique qui la désigne;

- un domaine de définition unique appelé aussi TYPE (ou Type);

- une valeur attribuée au départ et modifiable au cours du déroulement de l’algorithme. Dans le cas contraire, c’est une CONSTANTE et sa valeur doit rester inchangée pendant l’exécution de l’algorithme.

En général, les variables sont déclarées juste après la partie en-tête de l’algorithme. La syntaxe de déclaration est :

identificateur : TypeC //<=> Type Courant tel que ENTIER, REEL, BOOL ...

Les variables changent de valeur grâce à l’opération d’affectation (‘<-‘).

Exemple de l’algorithme simplifié de résolution de l’équation du 1^er degré:

ALGORITHME equation1

VARIABLES

a, b : REEL

DEBUT

a <- 2.0 // on affecte la valeur 2,0 dans la variable ‘a’

b <- 18.5 // on affecte la valeur 18,5 dans la variable ‘b’

ECRIRE(«Solution de A x + B = 0: », (-b)/a, «\n»)

FIN

// L’exécution (i.e. déroulement) de cet algorithme doit fournir l’affichage:

// Solution de A x + B = 0 : -9,25

CONVENTION pour nommer les variables :

- l’identificateur commence par une minuscule;

- le nom ne doit pas comporter d’espace;

- si le nom est constitué de plusieurs mots, éviter les traits d’union en commençant chacun d’eux par une majuscule (Ex. : lePoint, valeurMaximale);

- il faut bien donner des noms explicites car un algorithme se lit comme un texte normal (proscrire : i1, j2, z3 ... sauf pour des cas triviaux).

Exemple de déclaration d’une constante:

ALGORITHME nom_de_l’algorithme

CONSTANTES

Pi = 3.14159; // Pi sera déclarée comme une constante de type REEL

// Noter l’emploi de ‘=’ au lieu du symbole de l’affectation ‘<-‘

DEBUT

bloc_instructions

FIN

CONVENTION pour nommer les constantes :

- l’identificateur commence au moins par une majuscule;

- le nom ne doit pas comporter d’espace;

- si le nom est constitué de plusieurs mots, éviter les traits d’union en commençant chacun d’eux par une majuscule (Ex. : NombreOr, CtePlank, ORIGINE etc...);

1.3- Les types de base ou types primitifs

Les domaines usuels de définition des variables sont appelés aussi des TYPES simples tels que:

- les entiers ENTIER (noté aussi ENT <=> une partie des entiers relatifs Z),

- les réels REEL ( <=> une partie du corps des réels R),

- les caractères alpha-numériques CARACTERE (noté aussi CAR),

- les booléens BOOL (ou BOOLEEN) qui ne prennent que des valeurs: ‘VRAI’ ou ‘FAUX’ appelées aussi constantes logiques prédéfinies.

Le tableau ci-dessous montre les seuls opérateurs utilisables pour ces types de base en L.A.O. (ou Langage Algorithmique Objet défini en 2A):

Opérateurs ENTIER REEL CAR BOOL

Moins unaire (-) Oui Oui Non Non

Plus unaire (+) Oui Oui Non Non

Négation logique (NON) Non Non Non Oui

Addition (+) Oui Oui Non Non

Soustraction (-) Oui Oui Non Non

Multiplication (*) Oui Oui Non Non

Division entière (DIV) Oui Non Non Non

Modulo entier (MOD) Oui Non Non Non

Division réelle (/) Non Oui Non Non

Plus grand strictement (>) Oui Oui Oui Non

Plus petit strictement (<) Oui Oui Oui Non

Plus grand ou égal (>=) Oui Oui Oui Non

Plus petit ou égal (<=) Oui Oui Oui Non

Egalité ( = ) Oui Oui Oui Oui

Différence ( <> ) Oui Oui Oui Oui

ET logique (ET) Non Non Non Oui

OU logique (OU) Non Non Non Oui

Les trois premières opérations sont appelées « opérateurs unaires » (noté ‘Op1’) alors que le reste du tableau ne concerne que des « opérateurs binaires » (noté ‘Op2’). Ces opérateurs peuvent être définis sous la forme suivante :

nomOpérateur : Domaine1 x ... x Domaine2 --> DomaineCible

Quelques exemples (A COMPLETER) :

-----------------

NON : BOOL --> BOOL

- (unaire) : REEL --> REEL

...

DIV (entière) : ENTIER x ENTIER --> ENTIER // Ex. : 19 DIV 2 = 9

MOD (reste de DIV) : ENTIER x ENTIER --> ENTIER // Ex. : 19 MOD 2 = 1

...

/ (div. réelle) : REEL x REEL --> REEL // Ex. : 19./2. = 9.5

* (mult. réelle) : REEL x REEL --> REEL // Ex. : 19.*2. = 38.0

...

= (Egalité) : ENTIER x ENTIER --> BOOL // «10 = 10»? C’est VRAI.)

>= : REEL x REEL --> BOOL // «10. >= 11.»? C’est FAUX.)

<> (Non égal) : ENTIER x ENTIER --> BOOL // «10 <> 10»? C’est FAUX.)

< (Inférieur strict) : CAR x CAR --> BOOL // «‘A’ < ‘a’»? C’est VRAI.)

Le type ENTIER et le type REEL

------------------------------

Leur emploi est assez intuitif. Dans un premier temps, on ne s’occupera pas des seuils numériques maximaux et minimaux compte tenu de leur représentation sur machine via des registres mémoires à taille limitée en bits.

Le type CARACTERE

-----------------

La lettre ‘A’ a la valeur entière égale à 65 (code ASCII en décimal) ou ‘\u0041’ (code UNICODE en hexadécimal) alors que ‘a’ prend la valeur 97 (ou ‘\u0061’). On fera donc attention à la différence entre le caractère ‘5’ et l’entier 5. D’après la table des codes UNICODE (i.e. extension des codes ASCII - cf. menu ‘tpp’ sous Linux), on ne retiendra que les trois propriétés suivantes :

- les codes des caractères majuscules ‘A’, ... ‘Z’ se suivent dans cet ordre;

- les codes des caractères minuscules ‘a’, ... ‘z’ se suivent dans cet ordre;

- de même, les entiers associés aux dix caractères numériques ‘0’ (code 48 ou ‘\u0030’), ..., ‘9’ (code 57 ou ‘\u0039’) se suivent aussi.

Ainsi, pour convertir un caractère minuscule en majuscule, on peut lui ajouter la différence qui les sépare:

(CAR) ((ENTIER) ‘b’ + (‘A’ – ‘a’)) vaut ‘B’ <==> 98 + (65 – 97)= 66 = code ASCII de ‘B’

De même, pour convertir un caractère majuscule en minuscule, on peut lui ajouter la différence qui les sépare:

(CAR) ((ENTIER) ‘B’ + (‘a’ – ‘A’)) vaut ‘b’ <==> 66 + (97 – 65) = 98 = code ASCII de ‘b’

Conversions entre CAR et ENTIER: Dérouler les algorithmes de conversion ci-dessous via un exemple au choix:

ALGORITHME carVersEntier // car. num. | ALGORITHME entierVersCar

VARIABLES | VARIABLES

car : CAR; nb : ENTIER | car : CAR; nb : ENTIER

DEBUT | DEBUT

LIRE(car) // parmi ‘0’, ..., ‘9’ ici. | LIRE(nb) //entre 0 et 127 par ex.

nb <- (ENTIER) car - (ENTIER) ‘0’ | car <- (CAR) nb

// transtypages explicites ici !

ECRIRE(nb) | ECRIRE(car)

FIN | FIN

Conversions entre ENTIER et REEL: Dérouler les algorithmes de conversion ci-dessous via un exemple au choix :

ALGORITHME reelVersEntier | ALGORITHME entierVersReel

VARIABLES | VARIABLES

r : REEL; nb : ENTIER | r : REEL; nb : ENTIER

DEBUT | DEBUT

LIRE(r) // Ex. : -3.14159 | LIRE(nb) // Ex.: -32768,...+32767

nb <- (ENTIER) r | r <- (REEL) nb

// autre trans-typage explicite | //toujours trans-typage explicite

ECRIRE(nb) | ECRIRE(r)

FIN // Qu’obtient-on avec r = -3.14159 ? | FIN //Pas de perte d’information ici

En effet, certains langages de programmation comme Java pratiquent la conversion implicite entre les types primitifs avec le risque de perte de données (conversion de REEL vers ENTIER par exemple). Il est donc conseillé d’effectuer des transtypages explicites en connaissance de cause.

Le type logique booléen : BOOL

------------------------------

La négation logique (NON) retourne toujours l’autre valeur logique par rapport à celle de l’opérande courante. Les tables de vérité ci-après donnent la réponse «VRAI» ou «FAUX» des opérations logiques fondamentales ‘ET’, ‘OU’:

‘ET’ FAUX VRAI ‘OU’ FAUX VRAI

FAUX FAUX FAUX FAUX FAUX VRAI

VRAI FAUX VRAI VRAI VRAI VRAI (*)

(*) signifie : «VRAI» OU «VRAI» vaut «VRAI».

Exercice 1: Démontrer les règles de MORGAN via les tables de vérité (A FAIRE):

Si A, B : BOOL

Alors NON(A ET B) = NON(A) OU NON(B);

NON(A OU B) = NON(A) ET NON(B);

Il existe aussi d’autres opérateurs logiques binaires tels que :

=> (Implication) : BOOL x BOOL --> BOOL

<=> (Equivalence) : BOOL x BOOL --> BOOL

Exercice 2: Compléter les tables de vérité ci-dessous (cf. internet):

‘=>’ FAUX VRAI ‘<=>’ FAUX VRAI

FAUX VRAI ... FAUX VRAI ...

VRAI ... VRAI VRAI ... VRAI

Erreur courante (A EVITER) - Analyser et corriger l’algorithme ci-dessous :

---------------

ALGORITHME conv_err1

VARIABLES

c : CAR

DEBUT

c <- ‘A’ // OK : c’est correct !

c <- 18.5 // KO : ‘c’ n’est pas une variable REELLE

c <- (5 <= 8) // KO aussi : et pourquoi ?

FIN

EXPRESSIONS arithmétiques et booléennes

On pratique, en général, la notation infixée selon la syntaxe :

Expression <- Opérande1 OPERATEUR Opérande2

Expression <- Opérande1 OPERATEUR Opérande2 ... OPERATEUR OpérandeN

Exemples : x <- (-b)/a

som <- note1 + note2 + note3

On distingue aussi deux autres notations: préfixée (i.e. notation polonaise) et suffixée (ou post-fixée i.e. notation polonaise inverse).

Exemples de notations préfixées: OU(VRAI, FAUX)

// <=> notation des fonctions habituelles

+(a, b) // <==> (a+b) en infixé

Exemples de notations suffixées: (A, B)OU // <==> (A OU B) en infixé

(a, b)+ // <==> (a+b) en infixé etc ...

PRIORITES entre les OPERATEURS booléens et arithmétiques

On suivra la convention suivante (priorité croissante dans le sens ascendant):

^ - ; + (unaires) ; NON

| * ; / ; DIV ; MOD

| - ; + (binaires)

| = ; < ; > ; <> ; <= ; >= // Noter les 6 opérateurs logiques de comparaison (‘Olc’)

| ET

| OU

Question : Y-t-il une erreur dans les instructions, ci-dessous, extraite d’un algorithme de résolution de l’équation « ax²+ bx+ c= 0 » ?

x1 <- (-b –(b²-4.*a*c)^0.5)/2.*a

x2 <- (-b +(b²-4.*a*c)^0.5)/2./a

Réponse :

x1 est incorrect alors que x2 est correct. Pour corriger x1, on peut ajouter des ‘()’ :

x1 <- (-b –(b²-4.*a*c)^0.5)/(2.*a)

Exercice 3: Qu’obtient – on, comme résultats, pour l’algorithme ci-après:

ALGORITHME bool1

VARIABLES

b : BOOL

DEBUT

b <- (5 <= 8) ; ECRIRELN(b) // <=> ECRIRE(b, «\n»)

b <- (VRAI OU VRAI ET FAUX) ; ECRIRELN(b)

b <- (VRAI ET VRAI OU FAUX) ; ECRIRELN(b)

b <- (VRAI OU VRAI) ET FAUX ; ECRIRELN(b)

b <- (VRAI ET FAUX OU FAUX) ; ECRIRELN(b)

b <- (10 >= 10) OU (‘f’ > ‘G’) ET (3.14 <> 3.14) ; ECRIRELN(b)

FIN // On peut modifier la priorité des opérateurs via l’emploi des parenthèses.

1.4 – Les premiers objets informatiques: ‘CHAINE’ et ‘DATE’

LA CLASSE ‘CHAINE’

On vient d’étudier les quatre types courants de base à savoir BOOL, CAR, ENTIER et REEL avec la notion de CONSTANTE de CHAINE de caractères lors des affichages via ‘ECRIRE’. Considérons, par exemple, une variable nommée ‘Ch’ associée au type spécial nommé «CHAINE» de caractères qui est muni d’un certain nombre d’opérations élémentaires propres appelées désormais METHODES selon l’interface utilisateur ci-dessous:

-------------------------------------------------------------------------------

| CHAINE // nom de l’ensemble des objets de type ‘Chaîne de caractères’ |

-------------------------------------------------------------------------------

|+ CHAINE() // méthode constructive permet de créer une chaîne en mémoire |

|+ CHAINE(uneCh : CHAINE) //méthode constructive avec un argument de même type|

|+ CHAINE(uneSuiteDeCaractères : TABLEAU de CAR) // autre méthode constructive|

| ... |

|+ versCHAINE(a : TypeC) : CHAINE // convertit un type de base en CHAINE |

|+ lireCHAINE() : CHAINE //fonction de lecture pour la CHAINE COURANTE |

|+ modifierIeme(i : ENTIER, c : CAR) // méthode modificatrice pour modifier |

| // le ième car. de la CHAINE COURANTE |

| ... |

|+ afficheCHAINE() // méthode d’écriture de la CHAINE COURANTE sur l’écran |

|+ longueurCHAINE() : ENTIER // calcule la longueur de l’instance courante |

|+ iemeCAR(i : ENTIER) : CAR // méthode d’extraction du ième caractère ... |

| etc ... |

-------------------------------------------------------------------------------

Ici CHAINE désigne le nom de l’ensemble des variables du type «Chaînes de caractères». Cet ensemble d’objets est appelé aussi classe. Et la notion de VARIABLE est généralisée maintenant en notion d’instance ou encore objet.

La figure ci-dessus montre la présence de trois groupes de méthodes :

1- Les méthodes constructives (ou constructeurs) permettent l’initialisation éventuelle de l’instance courante. Il y a trois constructeurs dans l’exemple précédent.

2- Les méthodes modificatrices (ou modifieurs) autorisent le changement du contenu de l’instance courante.

3- Les méthodes d’accès (ou accesseurs) ne modifient pas le contenu de l’objet courant tout en permettant de décrire certaines de leurs propriétés intrinsèques à savoir le nombre de caractères constitutifs (i.e. sa longueur), la valeur de la ième position (le premier caractère est situé à la position 1).

Question: Dans quel groupe de méthodes (parmi les trois définies précédemment) doit-on spécifier les nouvelles méthodes ci-dessous:

-------------------------------------------------------------------------------

| CHAINE // interface utilisateur de la classe CHAINE (suite) |

-------------------------------------------------------------------------------

|+ ajoutTete(d : CAR) // ajoute le caractère ‘d’ en tête de la CHAINE courante|

|+ ajoutQueue(f : CAR) // ajoute le caractère ‘f’ à la fin ... |

|+ concateneCHAINE(chaine2 : CHAINE) // concatène deux chaînes ... |

|+ extraitSousChaine(deb : ENT, fin : ENT) // entre 2 positions ‘deb’ et ‘fin’|

| ... |

|+ strictInferieur(CHAINE) // <=> Olc ‘<’ des TypeC |

|+ strictSuperieur(CHAINE) // <=> Olc ‘>’ des TypeC |

|+ inferieurOuEgal(CHAINE) // <=> Olc ‘<=’ des TypeC |

|+ superieurOuEgal(CHAINE) // <=> Olc ‘>=’ des TypeC |

|+ Egalite(CHAINE) // <=> Olc ‘=’ des TypeC |

|+ nonEgal(CHAINE) // <=> Olc ‘<>’ des TypeC |

|+ estVide() : BOOL // pour répondre à : «la CHAINE COURANTE est-elle vide ? »|

| etc ... |

-------------------------------------------------------------------------------

Réponse (A COMPLETER) :

Un exemple d’emploi de la classe CHAINE : Compléter les parties manquantes. Que fournit l’algorithme suivant ?

ALGORITHME string1

CONSTANTES

UnEspace = « »

// intialisation de la chaîne constante: un blanc <=> « une seule touche sur la barre-espace »

VARIABLES

nom, prenom, nomComplet : CHAINE

// trois déclarations (mais sans réservation d’emplacement mémoire)

DEBUT

nom <- RES CHAINE(«Poincaré»)

// Réserve (RES) des places mémoire pour ‘nom’ qui vaut « . . . »

prenom <- RES CHAINE(«Henri»)

// RES. des places mémoire pour ‘prenom’ qui vaut « . . . »

nomComplet.concateneCHAINE(prenom)

// Ici, l’instance courante est le chaîne ‘nomComplet’

nomComplet.concateneCHAINE(UnEspace) // . . .

nomComplet.concateneCHAINE(nom) // . . .

ECRIRE(«Contenu de la chaine courante : »)

nomComplet.afficheCHAINE() // . . .

ECRIRE(«Elle a pour longueur : », nomComplet.longueurCHAINE() )

FIN

D’après cet exemple, l’emploi d’une méthode doit toujours indiquer le nom de l’objet courant sur laquelle s’applique l’opération correspondante. La méthode est donc déclenchée par l’instance spécifiée devant le point ‘.’ qui joue le rôle de séparateur.

Exercice 4 (A FAIRE): Développer un algorithme permettant de lire une chaîne telle que « Dupond » et de modifier le iemeCar en 6ième position de cette chaîne pour obtenir « Dupont » en complétant ci-après :

ALGORITHME string2

VARIABLES

uneChaine : CHAINE

DEBUT

ECRIRE(«Algorithme ‘chaine2’ – Taper : Dupond »)

uneChaine <- uneChaine.lireCHAINE()

. . .

FIN

LA CLASSE ‘DATE’

On considère maintenant la classe DATE comme un ensemble d’objets constitués de triplets de trois entiers pour désigner le jour (jj), le mois (mm) et l’année (aa). Son interface utilisateur, un peu plus détaillée, appelée aussi notation selon la convention UML (« Unified Modeling Language », est décrite par :

-------------------------------------------------------------------------------

| DATE // nom de la classe ‘DATE’ |

-------------------------------------------------------------------------------

|~ annee : ENTIER // pour désigner une année selon le calendrier grégorien |

|~ mois : ENTIER // pour désigner un mois compris entre 01 et 12 au plus |

|~ jour : ENTIER // pour désigner un jour entre 01 et 31 au plus |

-------------------------------------------------------------------------------

|+ DATE() // méthode constructive permet de créer une date en mémoire |

|+ DATE(j : ENT, m : ENT, a : ENT) //méthode constructive avec trois arguments|

|+ DATE(uneDate : DATE) //première méthode constructive avec un seul paramètre|

|+ DATE(date: CHAINE) // convertit la chaîne ‘date’ («jj/mm/aaaa») en une DATE|

| ... |

|+ versCHAINE(): CHAINE //convertit la DATE COURANTE en format «jj/mm/aaaa» |

|+ estEgal(d : DATE) : BOOL // « l’instance courante a la même date que d ? » |

|+ estVide() : BOOL // répond à : « l’instance courante est – elle vide ? » |

|+ estBissextile() : BOOL // répond à : « ‘annee’ est une année bissextile ? »|

|+ jourSemaine() : CHAINE // retourne un jour de la semaine parmi {Lu,...,Di} |

|+ precede(d : DATE) : BOOL // la DATE COURANTE précède-t-elle ‘d’ ? |

|+ suit(d : DATE) : BOOL // la DATE COURANTE suit-t-elle ‘d’? Méthode utile ? |

|+ duree(d : DATE) : ENTIER //<=> la durée en jours en la DATE COURANTE et ‘d’|

|+ accesAnnee() : ENTIER // pour accéder à la donnée privée ‘annee’ |

|+ accesMois() : ENTIER // pour accéder à la donnée privée ‘mois’ |

|+ accesJour() : ENTIER // pour accéder à la donnée privée ‘jour’ |

| ... |

-------------------------------------------------------------------------------

On constate maintenant la présence d’un troisième bloc, appelé bloc des attributs, comportant trois données entières précédées par le symbole ‘~‘ pour indiquer qu’elles sont accessibles dans le paquet (ou dossier) courant. Les méthodes publiques (précédées par ‘+’) sont accessibles de partout; c’est le cas :

- des méthodes constructives (ou constructeurs) possédant le même nom que la classe,

- et des fonctions d’accès (les méthodes autres que les constructeurs) ici ?

Question : Classer les méthodes publiques ci-dessus parmi trois catégories de méthodes déjà introduites.

Réponse : On ne retrouve, en effet, que deux parmi les trois catégories de méthodes ici : (i) le bloc des constructeurs, (ii) le bloc des méthodes d’accès. Il manque donc le bloc des méthodes modificatrices de chaque champ que le lecteur peut développer à titre d’exercice via un travail personnel de programmation (TPP) ou via un TP-Projet...

Notons aussi que le L.A.O. accepte aussi le polymorphisme paramétrique; en effet, le constructeur à un seul paramètre possède ici deux signatures (ou deux versions ou encore deux facettes):

+ DATE(DATE) // premier constructeur avec un paramètre unique du type DATE

+ DATE(CHAINE) // second constructeur avec un seul paramètre du type CHAINE

Un exemple d’emploi de la classe DATE : Compléter les parties manquantes. Que fournit l’algorithme suivant ?

ALGORITHME date1

VARIABLES

d1, dN : DATE ; dateNais : CHAINE

// déclarations (mais sans réservation d’emplacement mémoire)

DEBUT

d1 <- RES DATE(3, 10, 2007) // A remplacer par la date du jour

// Réserve (RES) des places mémoire pour ‘d1’ qui vaut « . . . »

ECRIRE(«La date courante », d1.versCHAINE(), « est un : », d1.jourSemaine() )

dateNais <- RES CHAINE(« ../../.... ») // votre date de naissance par exemple

dN <- RES DATE(dateNais)

ECRIRE(«Votre date de naissance », dN.versCHAINE(), « est un : », dN.jourSemaine() )

ECRIRE(«Votre année de naissance », . . . , « est une année bissextile ? Rép. = », dN.estBissextile() )

ECRIRE(«BRAVO ! Jusqu’à aujourd’hui », d1.versCHAINE(), «, vous avez vécu », d1.duree(dN), « jours déjà ! »)

FIN

Exemple d’étude de cas (cf. TPP) : DEVELOPPER LES ALGORITHMES DES METHODES MANQUANTES et TRADUIRE toute la classe DATE en Java pour vérification via une classe séparée ‘date_t’.

1.5 – Les schémas mémoires

Le déroulement d’un algorithme, étape par étape, permet de suivre l’ensemble des variables et des instances ainsi que leurs valeurs respectives; c’est son schéma mémoire. En général, trois parties distinctes sont délimitées pour un schéma mémoire:

· Le titre de l’algorithme (encadré et centré au début);

· La partie gauche concerne toutes les variables qui seront représentées soit par une valeur (ou ‘?’ si inconnue) pour des types de base soit par une flèche pour les variables de type objet CHAINE ou DATE, désormais on désigne par références de telles variables de type objet;

· La partie droite concerne toutes les instances obtenues par la création via l’opérateur ‘RES’ du L.A.O. (autant de cases que d’opérations ‘RES’ pour le moment ...).

Exercice 5: Etablir le schéma mémoire pour l’algorithme ‘deuxReferencesPourUneDate’ (A COMPLETER).

ALGORITHME deuxReferencesPourUneDate

VARIABLES

d1, d2 : DATE

estBis, apres, idem : BOOL

DEBUT

d1 <- RES DATE(3, 10,2007)

d2 <- RES DATE(4, 10,2007)

idem <- d1.estEgal(d2)

estBis <- d1.estBissextile()

apres <- d1.precede(d2) // <=> apres <- d2.suit(d1)

d2 <- d1 // les références d2 et d1 pointent sur l’instance «06/09/2006»

idem <- d1.estEgal(d2) // c’est une égalité superficielle ici !

d2.versCHAINE().afficheCHAINE() // <=> ECRIRE( d2.versCHAINE() )

FIN

Exercice 6: Etablir le schéma mémoire pour l’algorithme ‘unObjetSansReference’ pour savoir lequel des objets n’est plus pointé par une référence (A COMPLETER).

ALGORITHME unObjetSansReference

VARIABLES

d1 : DATE

DEBUT

d1 <- RES DATE(3, 10, 2007)

d1 <- RES DATE(4, 10, 2007)

d1.versCHAINE().afficheCHAINE()

FIN

Exercice 7: Etablir le schéma mémoire pour l’algorithme ‘datesEgales’ (A COMPLETER).

ALGORITHME datesEgales

VARIABLES

d1, d2 : DATE

DEBUT

d1 <- RES DATE(3, 10, 2007)

d2 <- RES DATE(d1)

ECRIRE(«Les dates », (d1.estEgal(d2) ? « sont » : « ne sont pas »), « égales ! »)

// Qu’obtient-on ici ? Est-ce une égalité profonde ?

d1.versCHAINE().afficheCHAINE()

ECRIRE( d2.versCHAINE() )

FIN

Notons l’emploi du premier opérateur ternaire ( ... ? ... : ... ) d’impression de message qui se lit ici simplement: SI « d1.estEgal(d2) = VRAI » ALORS « sont » est affiché; SINON c’est « ne sont pas » qui sera pris en compte.

Cet opérateur sera détaillé dans la partie suivante sur les instructions conditionnelles.

Par ailleurs, l’emploi du séparateur ‘,’ est assez intuitif ici pour indiquer une concaténation des constantes de chaînes parmi les arguments de ‘ECRIRE’.

Exercice 8: Proposer un algorithme permettant de lire une date et d’afficher si elle est bissextile ou non.

Indication: Faire la rétro-analyse de la méthode correspondante du fichier ‘DATE.java’.

1.6 – Le type TABLEAU

Par définition, un tableau est une collection finie de valeurs de type homogène (i.e. même type) et accessibles directement par leur position. Le nombre maximal d’éléments du tableau est sa dimension. Pour accéder à un élément donné, un indice est utilisé pour indiquer son rang pour des tableaux unidimensionnels, appelés aussi vecteurs. Pour des tableaux à deux entrées (appelés aussi matrices si TypeC = BOOL, ENTIER ou REEL), on utilisera deux indices etc ...

Exemples de déclaration dans le bloc des VARIABLES:

---------------------------------------------------

T0 : TABLEAU(1...6) de ENTIER // En Java : int T0[] = new int[6];

Ici, dimension = 6 et l’indice part de 1 en L.A.O. mais, en Java, il peut partir de 0. C’est donc une source d’erreur très fréquente lors des implémentations sur machine !

T1 : TABLEAU(0...99) de REEL

Dans cet exemple de tableau unidimensionnel, on déclare et on réserve une dimension maximale de 100 réels et l’indice part de 0pour faciliter la traduction en Java. On peut séparer aussi la déclaration de la réservation des mémoires :

T1 : TABLEAU[] de REEL // float [] T1;

T1 <- RES REEL[100] // T1 = new float[10];

Pour des tableaux à deux dimensions maximales 8 x 8, la déclaration est :

T2 : TABLEAU(0...7)(0...7) de CHAINE

pour émuler un échiquier du jeu d’échecs par exemple.

Utilisation de tableaux

-----------------------

L’emploi d’une seule variable permet de stocker les six chiffres d’un tirage du Loto ainsi que le chiffre complémentaire dans l’algorithme ci-après.

Exercice 9 : Tracer le schéma mémoire du programme suivant:

ALGORITHME loto7

VARIABLES

loto : TABLEAU(1...7) de ENTIER

DEBUT

loto[] <- {35, 24, 13, 47, 8, 44, 2}

// on peut aussi affecter élément par élément [A EVITER si possible]:

// loto[1] <- 35; loto[2] <- 24; ... ; loto[7] <- 2

Tableaux.TOC(loto, 1, 6) // pour trier par ordre croissant les 6ers chiffres

// TOC : Tri par Ordre Croissant de la classe TABLEAU (‘Array’ en anglais)

ECRIRE(«Tirage trié : », loto[1], loto[2], loto[3], loto[4], loto[5], loto[6])

ECRIRE(«\nChiffre complémentaire du Loto = », loto[7])

FIN

Exercice 10 : Soit la matrice M1 définie par

{0 1 1 0}

{0 0 0 1}

M1 = {0 1 1 1}

{0 0 0 0}

Modifier l’algorithme ‘mat1c’ ci-après pour initialiser le tableau ‘m1’ associé à cette matrice par une affectation « élément par élément ». En général, on évitera de le faire car c’est fastidieux si la dimension du tableau est importante.

ALGORITHME mat1c // <=> matrice de 1-connexion des 1-graphes (cf. cours Info.-S3 2^nde partie)

VARIABLES

m1 : TABLEAU(0...3)(0...3) de ENTIER

DEBUT

m1 <- {

{0, 1, 1, 0},

{0, 0, 0, 1},

{0, 1, 1, 1},

{0, 0, 0, 0}

}

...

FIN

Exercice 11 : COMMENT ECHANGER DEUX VARIABLES ?

1. Tracer le schéma mémoire de l’algorithme d’échange entre deux variables de type ‘TypeC’.

2. Etendre le programme ‘loto7’ en effectuant un échange entre le 1^er et 6è chiffre en accord avec cet algorithme [A TERMINER].

ALGORITHME echangeTypeC

VARIABLES

val1, val2, temp : TypeC // TypeC = REEL par exemple

DEBUT

val1 <- 17,5; val2 <- 11,5

ECRIRE(“Avant échange : val1 et val2 = ”, val1 , val2, “\n”);

temp <- val1

val1 <- val2

val2 <- temp

ECRIRE(“Après échange : val1 et val 2 = ”, val1 , val2, “\n”);

FIN

Exercice 12 : COMMENT ECHANGER DEUX OBJETS ?

Compléter l’algorithme pour échanger deux objets CHAINE (ou DATE). Et tracer le schéma mémoire correspondant.

ALGORITHME echangeObjets

VARIABLES

val1, val2, temp : CHAINE

DEBUT

val1 <- RES CHAINE(“Dupond”); val2 <- RES CHAINE(“Dupont”);

. . .

FIN

1.7 – Exercices d’application (non corrigés)

Exercice 13 : Indiquer les valeurs prises par les constantes et les variables au cours de l’algorithme suivant.

ALGORITHME calculFacture

CONSTANTES REELLES

Tva1 = 1.055; Tva2 = 1.196

VARIABLES

valeur, prixHT, prixTTC : REEL

nombre : ENTIER

DEB

valeur <- 17.5; nombre <- 4

prixHT <- valeur * (REEL) nombre

ECRIRE(« Prix HT = », prixHT, « € \n»)

prixTTC <- prixHT * Tva2

ECRIRE(« Prix TTC= », prixTTC, « € dont le montantTVA= », prixTTC-prixHT ,«\n»)

FIN

Exercice 14 : Ecrire un algorithme qui prend une somme en € et la décompose en billets de 1OO, 50, 20 et 10€.

PARTIE II : STRUCTURES DE CONTROLE

2.1 – Instructions conditionnelles

Jusqu’à maintenant, l’exécution d’un algorithme est linéaire et se déroule du haut vers le bas et/ou de la gauche vers la droite si les instructions, séparées par le séparateur ‘;’, se situent sur la même ligne. Désormais, on peut ne faire exécuter que certains blocs d’instructions via les instructions conditionnelles.

Conditionnelle simple - Syntaxe d’utilisation :

SI (ConditionRéalisée) ALORS

BlocInstructions_1 // exécutée si c’est VRAI

SINON

BlocInstructions_2 // exécutée si c’est FAUX

FSI //ou FinSI – A ne pas oublier !

Notons que la partie ‘SINON’ peut être optionnelle et sera ainsi omise. Si chaque bloc se réduit à une instruction simple, on utilise l’opérateur { ... ? ... : ... } déjà introduit :

{ Condition ? Instruction1 : Instruction2 }

Exemple d’emploi

----------------

Soit un extrait de l’algorithme de résolution de « a x²+bx +c = 0 ».

SI (a = 0) ALORS

TraitementDeEquation1erDegré // Bloc_1 pour résoudre « bx + c = 0 »

SINON

TraitementDeEquation2ndDegré // Bloc_2 pour traiter les 3 cas classiques

FSI

Exercice 15 (A FAIRE) : Ré-écrire l’algorithme ‘valeurAbsolue’ en utilisant l’opérateur ternaire.

ALGORITHME valeurAbsolue

VARIABLES val, valAbs : REEL

DEBUT

LIRE(val); valAbs <- val

SI (val < 0) ALORS

valAbs <- -ValAbs

// Noter bien le décalage (ou indentation) pour la clarté de l’algo. !

FSI

ECRIRELN(«Valeur absolue = », valAbs)

FIN

Question : Peut-on écrire l’algorithme de calcul du minimum (ou maximum) de deux variables de type ‘TypeC’ en employant l’opérateur ternaire ( Condition ? ... : ... ) ? Si oui, expliquer comment via un exemple précis.

Réponse :

ALGORITHME calculMin

VARIABLES x1, x2, Min : TypeC // Ex. TypeC = CAR

DEBUT

LIRE(x1); LIRE(x2); // Ex. : x1 = ‘A’ et x2 = ’a’

Min <-- (x1 < x2 ? x1 : x2)

ECRIRE(«Min(x1, x2) = », Min, «\n»)

FIN

ALGORITHME calculMax

VARIABLES x1, x2, Max : TypeC // Ex. TypeC = CAR

DEBUT

LIRE(x1); LIRE(x2); // Ex. : x1 = ‘A’ et x2 = ’a’

Max <-- (x1 < x2 ? ... : ...) // A compléter

ECRIRELN(«Max(x1, x2) = », Max)

FIN

Choix multiples - Syntaxes d’utilisation :

On utilise de préférence CAS ... FCAS (FinCAS) dans la mesure du possible, sinon l’emploi des conditionnelles emboîtées est nécessaire. Exemple :

avec CAS ... FINCAS | avec des conditionnelles emboîtées

choix := CAS |

expr1 : Bloc_1; RUPTURE | SI choix = expr1 ALORS Bloc_1

// RUPTURE = ‘break;’ | SINON // A ne pas oublier !

expr2 : Bloc_2; RUPTURE | SI choix = expr2 ALORS Bloc_2

| SINON

... | ...

exprN : Bloc_N; RUPTURE | SI Choix= exprN ALORS Bloc_N

AUTRECAS : NOP (ou Bloc_N1) | SINON NOP (ou Bloc_N1)

// NOP : ‘No Operation’ | FSI

| FSI

FINCAS (ou FCAS) | FSI // Noter les indentations à chaque fois.

Remarques:

1- Ne pas oublier le mot clé 'AUTRECAS' (appelé aussi ' AUTREMENT' ou 'PAR

DEFAUT' dans la littérature informatique) pour assurer la complétude.

2- La traduction en Java/C++ de "CAS ... FCAS" n'est pas directe sauf si

'choix' et 'exprn ' sont des types simples tels que ENTIER ou CAR.

Exercice 16 (A FAIRE) : Développer l’algorithme ‘TraitementDeEquation2ndDegré’ proprement dit ( a <> 0) pour traiter les 3 cas classiques en fonction du discriminant et en minimisant le nombre total d’opérations arithmétiques (cf. complexité temporelle) et aussi en réduisant au minimum l’emploi des variables (cf. complexité spatiale).

2.2 – Instructions répétitives ou Boucles

On dispose de trois principales boucles itératives, à savoir : "TANT QUE ... FTQ", "POUR ... FPOUR", "REPETER ... JUSQU'A" ainsi que des schémas algorithmiques équivalents pour des conversions réciproques ci-après. Dans le cas d’une collection d’objets ou de tableaux, on utilisera de préférence la syntaxe suivante:

C : CollectionOuTABLEAU

x : C

POUR x PARMI C // « for ... each ... » en anglais

BlocInstructions

FPOUR

BOUCLE ITERATIVE I

Boucle "TANT QUE ... FTQ" | Boucle "POUR ... FPOUR"

(Itération conditionnelle) | (Itération bornée)

i <-- 1 |

TANTQUE (i <= n) FAIRE | POUR i DE 1 A n FAIRE

-Bloc d'instructions- | - Même bloc -

i <-- i + 1 | FPOUR

FTQUE

Remarque: La généralisation est possible avec la convention ci-dessous

- Bloc_initialisation - | POUR ( - Bloc_initialisation -;

TANTQUE (NON( Cond_arrêt)) | [TANT QUE] NON(Cond_arrêt) [= VRAI];

FAIRE - Trait_progressif- | - Trait_progressif -

FTQUE | ) [FPOUR]

Exemple (cf. retro_an.htm):

x <-- d/2 | POUR ( x<--d/2;

FAIRE x <-- (x+d/x)/2 | x <-- (x+d/x)/2 ;

FTQUE | )

BOUCLE ITERATIVE II

Boucle "REPETER ... JUSQU'A" | Boucle "FAIRE ... TANTQUE"

(Itération conditionnelle) | (convention acceptée en TDI)

REPETER | FAIRE

- Traitement itératif - | - Traitement itératif -

JUSQU'A ( Cond_arrêt) | TANT QUE (NON( Cond_arrêt))

Exemple: Lecture de donnée avec filtrage entre deux bornes Binf et Bsup

REPETER | FAIRE

ECRIRE('Taper a:') | ECRIRE('Taper a:')

LIRE(a) | LIRE(a)

JUSQU'A (a>=Binf ET a<=Bsup) | TANTQUE (a<Binf OU a> Bsup)

Remarque : Utiliser le théorème de MORGAN pour passer d'un schéma à l'autre ...

BOUCLE ITERATIVE III

Boucle "REPETER ... JUSQU'A" | Boucle "Init.; TANTQUE ... FTQUE"

(Itération conditionnelle) | (EMPLOI A EVITER)

| Cond_arrêt <-- FAUX

REPETER | TANT QUE (NON(Cond_arrêt ))

- Traitement itératif - | - Traitement itératif -

JUSQU'A ( Cond_arrêt) | FTQUE

Exercice 17 (A FAIRE) : Ecrire l’algorithme d’affichage de N premiers entiers naturels impairs en trois versions de boucles itératives : "TANT QUE ... FTQ", "POUR ... FPOUR", "REPETER ... JUSQU'A". Exemple : Simpair = 1 + 3 + 5 + 7 = 16 (N = 4 ici).

Exercice 18 (A FAIRE) : Ecrire l’algorithme de sommation des N premiers entiers naturels pairs non nuls en trois versions de boucles itératives : "TANT QUE ... FTQ", "POUR ... FPOUR", "FAIRE ... TANTQUE". Exemple : Spair = 2 + 4 + 6 = 12 (N = 3 ici).

2.3 – Les boucles emboîtées

Si un bloc d’instructions dans une boucle répétitive comporte au moins une boucle interne, on a affaire à des boucles emboîtées à la façon des poupées russes. Par abus de langage, certains ouvrages d’informatique parlent aussi de boucles imbriquées. On les utilise souvent pour manipuler les tableaux à dimension multiple via des boucles « POUR index DE ... A ... FPOUR » emboîtées.

Exercice 19 : Etendre l’algorithme ‘mat1c’ pour afficher proprement le contenu du tableau carré ‘m1’ (A TERMINER).

2.4 – Exercices d’application (non corrigés)

Exercice 20 : Développer un algorithme complet de résolution de « a x² + b x + c = 0 » en traitant aussi tous les cas particuliers selon les valeurs réelles des coefficients lus via le clavier et aussi via la ligne de commande.

Exercice 21 : Ecrire un algorithme de détermination si un entier lu sur clavier est un nombre parfait (Ex. 6 = 1 + 2 + 3 est un nombre parfait car il est divisible par tous les nombres de la décomposition).

Exercice 22 : Ecrire un algorithme qui effectue des conversions réciproques entre Euros et les anciennes monnaies nationales (€ <-> FF, € <-> FB, € <-> DM, ...) de la zone Euro à deux décimales près en arrondissant au plus proche. Les taux de conversions qui sont définis à six chiffres exacts près (Ex : 1 € = 6,55957 FF) peuvent être obtenus via internet ou via les pages économiques du Télétexte de France 2 ...

PARTIE III : LES FONCTIONS

Lors de l’étude des premiers objets informatiques, les méthodes qui ont été introduites, sont déjà des fonctions. De même, les opérations fondamentales d’entrée-sortie notées LIRE(...) et ECRIRE(...) sont aussi des fonctions. Cette partie va approfondir leur fonctionnement, leur syntaxe de déclarations des arguments (ou paramètres d’échange) ainsi que leur emploi.

3.1 - Les fonctions avec ou sans valeur retournée

Par définition, une FONCTION (ou FCT en abrégé) est un bloc indépendant, ré-utilisable d’instructions. L’appel de la fonction déclenche l’exécution de l’algorithme associé à ce bloc. Une fonction se termine en retournant ou non une valeur unique (i.e. un type précis). La structure générale d’une fonction est :

FONCTION nomFonction( [declarationsEventuellesdArguments] ) : TypeC // En-tête de la fonction

DEBUT

// Bloc_Instructions comportant au moins une instruction « RETOURNER uneValeur »

FIN

Trois étapes sont nécessaires à l’exécution d’une fonction :

- Le programme (ou module) appelant, qui peut être une autre fonction, interrompt d’abord son exécution.

- La fonction appelée exécute son (ses) bloc(s) d’instructions. Dès qu’une instruction « RETOURNER ... » (‘return’ en anglais) est exécutée, la fonction s’arrête.

- Le module appelant reprend alors son cours normal.

En effet, le contenu de la fonction doit comporter, au moins, une instruction appelée RETOURNER (ou retourne) qui permet l’arrêt de son exécution et le retour au programme appelant sauf pour une procédure dont la définition est donnée par :

Une PROCEDURE (ou PROC) est une fonction qui ne retourne aucune valeur (noté « : Vide » au lieu de « : TypeC »). D’où les deux en-têtes équivalentes d’une procédure;

c’est soit:

FONCTION nomProcedure( [declarationsEventuellesdArguments] ) : Vide // ‘void’ en anglais

soit

PROCEDURE nomProcedure( [declarationsEventuellesdArguments] )

En général, on préfère la seconde notation. Exemple d’une procédure d’affichage de la date du jour:

PROCEDURE attente() // <=> FONCTION attente() : Vide

DEBUT

today : Date

today <- RES Date() // Date du jour

c : CAR

ECRIRE("\n\n(c)~/2A env. - 'es' utility (current package) - ", today, "\tSee you !\n")

ECRIRE(("Press any key to quit ...\n")

LIRE(c)

FIN

Notons aussi la présence des caractères de contrôle ‘\n’ et ‘\t’ qui signifient respectivement « \nouvelle ligne » et « \tabulation (indentation) automatique » comme nouveaux arguments de la méthode ‘ECRIRE()’.

Exemple de fonction avec une valeur retournée : resolEquation1(...).

Compléter l’algorithme ci-dessous en fonction des valeurs des arguments venant de l’appelant :

FONCTION resolEquation1(D a : REEL, D b : REEL) : CHAINE // Soit à résoudre : a X + b = 0.

// ‘D’ : passage de paramètre par valeur peut être omis par défaut.

DEBUT

Ch : CHAINE

SI (a = 0) ALORS

SI ( b = 0 ) ALORS

Ch <- « Infinité de solutions (<=> 0/0 ou ‘NaN’ i.e. ‘Not a Number’ en anglais) ! »

SINON

SI ( b > 0 ) ALORS

Ch <- « +Infini. »

SINON

Ch <- « -Infini. »

FSI

SINON

Ch <- «Une solution unique est : »

Ch <- Ch.concateneCHAINE( . . . . . . . . . ) // A compléter !

FSI

RETOURNER Ch // Ici, ‘uneValeur’ est une CHAINE de caractères.

FIN

Exercice 23 (A FAIRE) :

1- Reprendre la résolution de l’équation du second degré « a2 x² + a1 x + a0 = 0 » (cf. Exercice 20) en utilisant une procédure nommée resolEquation2(D a2, a1, a0 : REELS) qui fait appel à la fonction resolEquation1 ci-dessus pour traiter le cas particulier où a2 = 0.

2- Ecrire le programme principal complet de test avec une lecture des données via la saisie par le clavier ou par la ligne de commande en Java.

3.2 - Les paramètres et leur passage

Un paramètre (ou argument) d’une fonction est aussi une variable locale de cette fonction. Il est affecté, grâce à une copie appropriée dès le début de l’appel, par la valeur passée par le module appelant. On parle alors du mécanisme de passage par valeur (utilisé en Java pour les types primitifs). La variable qui se situe sur la même place des arguments dans le programme appelant, appelée paramètre effectif, restera inchangé alors que le paramètre formel associé aura une copie de cette valeur et pourra être modifié éventuellement à l’intérieur de la fonction.

Exemple de la fonction ‘minimum’ qui retourne le minimum entre deux valeurs.

FONCTION minimum(D a : Typelt, D b : Typelt) : Typelt // Typelt est parmi {CAR, ENT, REEL}

DEBUT // Ici, a et b sont des paramètres formels de la fonction

SI ( a >= b ) ALORS

a <- b

FSI

RETOURNER a // On peut simplifier par : RETOURNER ( (a < b) ? a : b )

FIN

Question : Qu’obtient-on avec l’extrait du module appelant suivant :

...

note1, note2, min : REEL;

note1 <- 19,5; note2 <- 16,5;

min <- minimum(note1, note2) // note1 et note2 sont des paramètres effectifs

ECRIRE(« Valeur minimale entre », note1, « et », note2, « est : », min)

...

Réponse (A compléter):

D’après l’exemple ci-dessus, la fonction et le module appelant possèdent deux environnements de données totalement distincts même si les paramètres effectifs et formels portent le même type et le même nom. Si on souhaite modifier le contenu du paramètre d’échange au retour, il faut utiliser le mode de passsage par Donnée/Résultat (ou ‘D/R’).

Exemple de la procédure ‘maximum’ qui retourne le maximum entre deux valeurs.

PROCEDURE maximum(D a : Typelt, D b : Typelt, D/R max : Typelt)

DEBUT

max <- ( (a < b) ? b : a )

FIN

Question : Qu’obtient-on avec l’extrait du module appelant suivant :

...

c1, c2, maxi : CAR;

c1 <- ‘b’; c2 <- ‘B’; maxi <- ‘ ’

maximum(c1, c2, maxi)

ECRIRE(« Valeur maximale entre », c1, « et », c2, « est : », maxi)

...

Réponse (A compléter):

Bien entendu, comme le paramètre ‘D/R’ est unique ici, l’emploi d’une fonction est plus simple:

FONCTION maximum(D a : Typelt, D b : Typelt) : Typelt

DEBUT

RETOURNER ( (a < b) ? b : a )

FIN

Remarque : On peut imaginer aussi une variante du mode de passage d’argument ‘D/R’, appelée passage en mode Résultat seul (ou ‘R’). Exemple du calcul de moyenne de deux réels via une procédure (Emploi à éviter !) :

PROCEDURE moyenne(D a : REEL, D b : REEL, R moy : REEL)

DEBUT

moy <- (b + a )/2.

FIN

// On peut remplacer la procédure ‘moyenne(...)’ par une fonction plus élégante :

FONCTION moyenne(a, b : REELS) : REEL

DEBUT // Ici ‘D’ est omis car, par défaut, c’est le passage par valeur !

RETOURNER (b + a)/2.

FIN

En conclusion, la fonction d’entrée « LIRE(uneVariable) » est en effet une procédure avec un passage d’argument en mode ‘D/R’ dont le profil exact est :

FONCTION LIRE(D/R nomVar: TypeC): Vide // <=> PROCEDURE LIRE(D/R nomVar: TypeC)

De même, l’opération ECRIRE(...) est aussi une procédure avec comme signature :

PROCEDURE ECRIRE(D CteCHAINE1, D nomVar1, ..., D CteCHAINEs, D NomVars, ...)

En effet, la signature d’une fonction permet décrire précisément les éléments suivants:

- le nom de la fonction;

- le type et l’ordre exact de chaque argument;

- le type de la valeur retournée dont ‘Vide’ si c’est une procédure.

L’erreur algorithmique, fréquemment commise, est de permuter par inadvertance cet ordre dans le module appelant: dans le module d’appel de « resolEquation1(a, b) » par exemple, si on permute a et b, un compilateur, aussi sophistiqué soit-il, sera incapable de détecter cette erreur de permutation. On doit donc vérifier, scrupuleusement, la cohérence de l’ordre et du type des paramètres formels et effectifs de chaque fonction surtout lors de l’implémentation sur machine.

Exercice 24 : Compléter l’algorithme de la fonction qui convertit une chaîne de caractères en minuscules et tracer le schéma mémoire correspondant (A TERMINER):

FONCTION majVersMin(D ch : CHAINE) : CHAINE

VARIABLES

car : CAR;

indice : ENTIER;

result : CHAINE

DEBUT

result <- RES CHAINE(ch); indice <- 0

TANTQUE( indice < . . . . . . . . . . ) FAIRE

car <- result.iemeCAR(indice)

SI ((car >= ‘A’) ET (car <= ‘Z’)) ALORS

car <- (CAR) ((ENTIER) car + (‘a’ – ‘A’))

// transtypages explicites et implicites ici !

result.modifierIeme(indice, car)

FSI

indice <- indice + 1

FTQ

RETOURNER . . . .

FIN

// Et le module appelant est :

ALGORITHME v_majVersMin

VARIABLES

ch1, ch2 : CHAINE

DEBUT

ch1 <- RES CHAINE(« MarTin »)

ch2 <- majVersMin(ch1)

ch2.afficheCHAINE()

FIN

3.3 - Les paramètres instance

En Java, le passage par valeur des références d’objet appelés aussi paramètres instance est équivalent en principe au passage en mode ‘D/R’ pour les types primitifs dans d’autres langages comme C++. Etudions une autre version de la méthode de conversion d’une chaîne de caractères en minuscules. On cherche à convertir directement l’instance passée par la valeur de sa référence en paramètre. Le profil de la fonction devient :

FCT majusculeEnMinuscule(D/R ch: CHAINE): Vide //<=> PROC majusculeEnMinuscule(D/R ch : CHAINE)

VARIABLES

car : CAR;

indice : ENTIER;

DEBUT

indice <- 0

TANTQUE( indice < ch.longueurCHAINE() ) FAIRE

car <- ch........(indice) // A COMPLETER

SI ((car >= ‘A’) ET (car <= ‘Z’)) ALORS

car <- (CAR) ((ENTIER) car + (‘a’ – ‘A’))

ch..............(indice, car) // A COMPLETER

FSI

indice <- indice + 1

FTQ

// « RETOURNER Vide » est optionnel dans une procédure !

FIN

// Et le module appelant est :

ALGORITHME t_majVersMin

VARIABLES

str : CHAINE

DEBUT

str <- RES CHAINE(« MarTin »)

majusculeEnMinuscule(str)

str.afficheCHAINE()

FIN

// Question : Qu’obtient-on comme résultat lors de l’exécution de ce programme en Java ?

// Et pourquoi ? Comment y remédier ?

// Réponse [A compléter]:

3.4 – Introduction aux fonctions récursives

La séparation et la sauvegarde des environnements de données entre le module appelant et la fonction appelée permettent la conception des fonctions et des modules appelants identiques; autrement dit, une fonction appelée peut être son propre programme appelant. D’où la définition de fonctions récursives:

Une fonction est dite récursive si elle fait appel à elle-même.

La récursion (ou récursivité) est une approche algorithmique puissante et complémentaire de l’itération: elle permet souvent de trouver rapidement des solutions élégantes à des problèmes compliqués (Exemples classiques: Les tours de Hanoï ; les traitements de structures de données auto-référencées comme des listes, des arbres; les algorithmes récursifs de rétro-parcours ...).

Pour développer les fonctions récursives, deux conditions sont nécessaires:

- Connaître la (les) solution(s) triviale(s);

- Pouvoir décomposer un problème en sous-problèmes de même nature mais de taille plus réduite jusqu’à la condition d’arrêt où le traitement se fait d’une façon immédiate via la solution triviale.

La structure algorithmique générale d’une fonction récursive qui retourne une valeur est alors:

FONCTION fonctionRecursive(listeArguments): TypeC

DEBUT

SI ( ConditionArrêt ) ALORS

RETOURNER ... // traitement du cas trivial

SINON

// traitement du cas général puis ...

RETOURNER ... fonctionRecursive(nouvelleListeArguments)

FSI

FIN

La structure algorithmique générale d’une procédure récursive est [A compléter]:

PROCEDURE procedureRecursive(listeArguments)

DEBUT

FIN

Une analogie étroite s’opère, en effet, entre les algorithmes récursifs et les équations obtenues par récurrence telle que:

- la somme des n premiers entiers naturels S(n) = n + S(n-1) avec la cas trivial S(0) = 0.

- la fonction factorielle Fact(n) = n! où Fact(n) = n * Fact(n-1) avec Fact(0) = 0 ! = 1.

Ainsi il est assez simple de compléter la structure algorithmique générale ci-dessus par les fonctions:

FONCTION sommeNnombres(D n : ENTIER): ENTIER // n doit être positif ou nul lors de l’appel !

DEBUT

SI ( n = 0 ) ALORS

RETOURNER 0 // la solution du cas trivial S(0) = 0

SINON

RETOURNER n + sommeNnombres(n - 1)

FSI

FIN

FONCTION Fact(D n : REEL): REEL // n doit être positif ou nul lors de l’appel !

DEBUT

SI ( n = 0 ) ALORS

RETOURNER ... // la solution du cas trivial – A COMPLETER !

SINON

RETOURNER n ... Fact(n - 1) // traitement du cas général – A COMPLETER !

FSI

FIN

// Et le module appelant contient par exemple :

ECRIRE(sommeNnombres(3))

ECRIRE(Fact(3.))

Exercice 25 : Tracer les schémas mémoire pour les fonctions récursives ci-dessus (A TERMINER).

3.5 - Exercices d’application (A FAIRE)

Exercice 26 : Développer la fonction ‘minVersMaj(...)’ qui convertit une chaîne de caractères en majuscules et tracer le schéma mémoire correspondant. Développer aussi un module appelant ‘MAIN’ adéquat.

Exercice 27 : Reprendre les exercices de partie II et introduire les fonctions nécessaires.

Exercice 28 : Développer le schéma bloc d’une classe unique nommée ‘Entier’ comportant, entre autre, une méthode permettant l’échange de deux instances de cette classe via le passage par valeur des références d’objets avec clonage.

Exercice 29 : Développer le schéma bloc d’une classe unique nommée ‘Point2D’ (ensemble des points sur le plan R²) comportant, entre autre, une méthode permettant l’échange de deux instances de cette classe via le passage par valeur des références d’objets en effectuant des copies profondes (par clonage ou non).

Exercice 30 : Traduire en Java tous les algorithmes développés dans cette partie (Exercices 23 à 29).

PARTIE IV : BIBLIOGRAPHIE

LISTE NON EXHAUSTIVE :

======================

BASES MATHEMATIQUES POUR L'INFORMATIQUE

---------------------------------------

VELU J. "Méthodes mathématiques pour l'informatique", 3è édition, DUNOD, 1999;

ALGORITHMIQUE Niv. I

--------------------

AHO A. and ULLMAN J. "Concepts fondamentaux de l'Informatique", Dunod, 1993;

CARDON A. et DABANCOURT C. "Initiation à l'algorithmique objet" (modélisation avec UML et exemples de code en Java et C++), Eyrolles, 2001;

COURTIN J. et KOWARSKI I. "Initiation à l'algorithmique et aux structures de données", vol. 1 & 2, Nouvelle ed., Dunod, 1994, 1995 (cf. CDI de l'ESSTIN: 10 exemplaires);

DABANCOURT C. "Apprendre à PROGRAMMER – Algorithmes et conception objet", Eyrolles, 2005;

SUPPORT DE COURS

----------------

DAVID J.-M. - Cours et TDs « Informatique 1A – S1 » sur ‘arche’, ESSTIN, 2009-2010;

CHEVRIER V. – Cours et TDs « Informatique 1A – S2 » sur ‘arche’, ESSTIN, 2009-2010;

NGUYEN-PHU H. - Cours et TDs « Structures de Données & Algorithmique en Java », 2A – S3, ESSTIN, 2009-2010;

GODART C. – Cours et TDs « Informatique 3A – S5 (UML & SGBD) » sur ‘arche’, ESSTIN, 2009-2010.