Aide-mémoire Ada

UV Algorithmique 2
INSA première année

Structures de données

N OM : ................................... P RÉNOM ...................................

G ROUPE : ...................................

Campagne 2009–2010 Didier L E B OTLAN

Second semestre contact.lebotlan@insa-toulouse.fr
 Introduction
Alors que l’UV1 couvre la base de la programmation, il manque les outils de passage
à l’échelle : comment écrire un programme qui gère un génome de 3 milliards de
paire de bases, ou un réseau routier comprenant des millions de segments ?

L’UV2 se focalise sur la représentation des informations et sur la décomposition

d’un problème complexe en tâches simples.

Notations
◦ La notation ` e ∈ τ , où τ est un type, signifie que l’expression e a le type τ .
◦ De même ` B ∈ bloc signifie que B est un bloc de code
◦ Enfin, ` D ∈ definition signifie que D est une définition, et doit donc être
placée avant le begin.

Table des matières

P RÉAMBULE
Règles de qualité 2

D ÉFINIR DES INTERVALLES

Sous-types 3
Types énumérés 4
Bloc CASE 5

E NSEMBLES DE VARIABLES
Tableaux 6
Parcours de tableaux 7
Matrices 8
Parcours de matrices 9

M ODIFIER UN ARGUMENT DE PROCÉDURE

Mode de passage IN OUT 10
Procédures avec arguments IN OUT 11

I NSÉRER DES DÉFINITIONS AU MILIEU D ’ UN BLOC

Bloc DECLARE 12

1
 Règles de qualité
Afin d’améliorer la robustesse des programmes, il convient de respecter cer-
taines normes de qualité (issues pour la plupart de la norme CNES pour Ada).

Règles de nommage
◦ Un identificateur est aussi informatif que possible, sans être trop long.
◦ Un nom de type commence par Un_, Une_, ou Des_.
◦ Un nom de procédure commence en général par un verbe.

Règles esthétiques
◦ Le code est indenté (décalage judicieux des blocs, automatique dans emacs).
◦ Le code est aéré, mais sans excès.
◦ Des commentaires perspicaces aident à la lecture du code.

Règles de conception
◦ Définir des constantes si besoin : à part dans les tests, il ne doit pas y
avoir de nombres après le begin (sauf éventuellement 0 ou 1).
◦ Utiliser une boucle for chaque fois que c’est possible, plutôt qu’une
boucle while.
◦ Le return d’une fonction se situe à la fin de la fonction.
◦ Chaque fonction ou procédure majeure doit être testée avec une
procédure associée : la fonction Foo est testée avec la procédure
TEST_Foo.

Exemples d’identificateurs
Nombre_Mots procedure Trouver_Min type Un_Gnome
Largeur procedure Afficher_Ensemble type Des_No_Telephone

N procedure Message type Gnome

ZKLFS procedure Trop_Grand type Tom_Cruise

◦ X et Y sont des noms acceptables pour des coordonnées.

◦ Lorsque le rôle d’une procédure est clair, son nom n’est pas forcément un verbe.
Par exemple Pause(10).

2
 Sous-types
Un sous-type représente un intervalle dans un type existant.

Définition de sous-types
subtype Un_Foo is un_type_existant range intervalle ;
∈ definition
Le sous-type peut ensuite être utilisé comme un type normal. Par exemple, pour
déclarer une variable : Compteur : Un_Foo ;

Exemples de sous-types

D ÉFINITION DU SOUS -TYPE ( ∈ definition ) I NTERVALLE REPRÉSENTÉ

subtype Un_Foo is Integer range -50 .. 2000 ; [−50 ; 2000]
subtype Un_Bar is Float range 0.0 .. 1.0 ; [0.0 ; 1.0]
subtype Un_Moo is Character range ’A’ .. ’D’ ; ’A’, ’B’, ’C’, ’D’
subtype Un_Bla is Integer range Integer’First .. -40 ; [−∞ ; −40]
subtype Des_Foo is Integer range 0 .. Integer’Last ; [0 ; +∞]

Noter qu’en Ada ∞ n’existe pas. Le plus grand entier vaut environ 2.109
Même remarque pour les réels (Float) : le plus grand réel vaut 3.438

Les sous-types Natural ([0 ; +∞]) et Positive ([1 ; +∞]) sont prédéfinis en Ada.

Notes personnelles

3
 Types énumérés
Un type énuméré représente un ensemble fini de valeurs.

Définition d’un type énuméré

type Un_Jour_Semaine is (Lun, Mar, Mer, Jeu, Ven, Sam, Dim) ;
∈ definition
Un type énuméré s’utilise comme tout type ou sous-type :
Demain : Un_Jour_Semaine ;

Le compilateur détecte automatiquement les incohérences :

Demain := Mer ; Correct
Demain := Mercredi ; Erreur de compilation ( Mercredi est inconnu)

R ÈGLE ` « Type énuméré »

Après une définition type Un_Foo is (Nom1 , Nom2 , . . ., Nomk ) ;

les k jugements ` Nomi ∈ Un_Foo sont valides pour 1 6 i 6 k.

+ Ainsi, on a ` Dim ∈ Un_Jour_Semaine (à comparer avec ` ”Dim” ∈ String).

Pour tester une variable d’un type énuméré, on utilise très souvent un bloc case.

Notes personnelles

4
 Bloc CASE
Le bloc case permet de tester un type énuméré.

Définition du bloc CASE

Syntaxe : case e is ` Bi ∈ bloc

when Nom1 => B1 ;
.. ` e ∈ τ , où τ est un type énuméré.
.
when Nomk => Bk ; ` Nomk ∈ τ
end case ;
Exécution du bloc CASE :
1 – L’ expression e est calculée et donne une valeur Nomj .
2 – Le bloc Bj correspondant est exécuté, puis le bloc case se termine.

+ Il est possible de factoriser plusieurs cas en écrivant when Nom1 | Nom2

R ÈGLE ` « Bloc CASE »

Un bloc CASE est un bloc :
Si ` e ∈ τ ` Nomi ∈ τ et ` Bi ∈ bloc,
case e is
when Nomi => Bi
alors ` ∈ bloc
...
end case ;
Exemple d’utilisation
1 Cette procédure affiche son argument de type Un_Jour_Semaine (voir page de gauche).
2 On suppose que l’acteur Txt est défini.
4 procedure Afficher_Jour (Jour : Un_Jour_Semaine) is
5 begin
6 case Jour is
7 when Lun => Txt . Put ( "Lundi, jour difficile" ) ;
8 when Mar | Mer | Jeu => Txt . Put ( "Milieu de la semaine" ) ;
9 when Ven => Txt . Put ( "Vendredi" ) ;
10 when Sam | Dim => Txt . Put ( "Week end" ) ;
11 end case ;
∈ bloc
12 end Afficher_Jour ;
∈ definition
+ L’ expression e testée par le bloc case est l’argument Jour (ligne 6).

Jour : Un_Jour_Semaine Afficher_Jour

5
 Tableaux
Un tableau (array) représente un ensemble fini de variables du même type
repérées par un indice : v1 , v2 , . . ., vk .
Définition d’un type tableau
type Des_Foo is array (Integer range <>) of Float ;
∈ definition
Ce type Des_Foo permet de définir des ensembles de variables réelles :
Bar est une famille de 5 variables réelles, numérotées de 1 à 5
Bar : Des_Foo (1..5) ;
Moo est une famille de 3 variables réelles, numérotées de 10 à 12
et initialisées à 0.0
Moo : Des_Foo (10..12) := (others => 0.0) ; ∈ definition

Accès aux variables du tableau

L’expression Bar( i ) , où i est un entier, renvoie la ieme variable du tableau.
Pour modifier sa valeur, il suffit d’écrire : Bar( i ) := valeur ;

Bar 1 2 3 4 5

Moo 10 11 12

R ÈGLE ` « Tableau »
Après la définition type Des_Foo is array (Integer range <>) of τ où τ est un
type quelconque,

◦ Si ` e1 , e2 ∈ Integer alors ` Bar : Des_Foo (e1 .. e2 ) ∈ definition

◦ Si ` e ∈ Des_Foo et ` e0 ∈ Integer alors ` e(e0 ) ∈ τ
◦ Si ` e ∈ Des_Foo et ` e0 ∈ Integer et ` e00 ∈ τ alors ` e(e0 ) := e00 ∈ bloc

6
 Parcours de tableaux
Pour parcourir toutes les variables du tableau, on utilise une boucle for.
Les indices de début et de fin du tableau sont obtenus avec les attributs ‘FIRST
et ‘LAST.
Parcours d’un tableau
L’intervalle peut s’écrire
for Index in Bar ’ First . . Bar ’ Last loop
Ici on ajoute 1.0 à toutes les variables
de manière équivalente
Bar(Index) := Bar(Index) + 1.0 ; Bar’Range
end loop ;

R ÈGLE ` « Attributs d’un tableau »

Après la définition type Des_Foo is array (Integer range <>) of τ où τ est un
type quelconque,

Si ` e : Des_Foo alors ` e’First ∈ Integer et ` e’Last ∈ Integer

Notes personnelles

7
 Matrices
En Ada, une matrice de n lignes et m colonnes se représente par un tableau
(array) à deux dimensions.
Définition d’un tableau à 2 dimensions
type Une_Matrice is array (Integer range <>, Integer range <>) of Float ;
∈ definition

Bar est une matrice de 2 lignes et 4 colonnes

Bar : Une_Matrice(1..2 , 1..4) ;
Moo est une matrice de 3 lignes et 3 colonnes initialisée à 0
Moo : Une_Matrice(5..7 , 0..2) := (others => (others => 0.0)) ; ∈ definition

Accès aux variables de la matrice

L’expression Bar( i, j) , où i et j sont des entiers, renvoie la variable si-
tuée ligne i, colonne j.
Pour modifier sa valeur, il suffit d’écrire : Bar( i, j) := valeur ;

0 1 2
1 2 3 4
5
Bar : 1 Moo :
6
2
7

R ÈGLE ` « Matrice »
Après la définition type Une_Mat is array (Integer range <>, Integer range <>) of τ
où τ est un type quelconque,

◦ Si ` e1 , e2 , e3 , e4 ∈ Integer alors ` Bar : Une_Mat (e1 .. e2 , e3 .. e4 ) ∈ definition

◦ Si ` e ∈ Une_Mat et ` e1 , e2 ∈ Integer alors ` e(e1 , e2 ) ∈ τ
◦ Si ` e ∈ Une_Mat , ` e1 , e2 ∈ Integer et ` e0 ∈ τ alors ` e(e1 , e2 ) := e0 ∈ bloc

8
 Parcours de matrices
Pour parcourir toute la matrice ligne par ligne, il suffit d’imbriquer deux boucles
for (comparer avec le parcours de tableaux, page précédente).
Les indices des lignes ou des colonnes sont obtenus avec les attributs
‘RANGE(1) et ‘RANGE(2), respectivement.

Parcours d’une matrice

Les deux intervalles
for Ligne in Bar ’ First ( 1 ) . . Bar ’ Last(1) loop peuvent s’écrire de
for Colonne in Bar ’ First ( 2 ) . . Bar ’ Last(2) loop
manière équivalente
On met toutes les variables à 0
Bar’Range(1) et
Bar(Ligne , Colonne) := 0.0
end loop ; Bar’Range(2) .
end loop ;

R ÈGLE ` « Attributs d’une matrice »

Après la définition type Une_Mat is array (Integer range <>, Integer range <>) of τ
Si ` e : Une_Mat alors ` e’First(1) ∈ Integer et ` e’Last(1) ∈ Integer
De même pour e’First(2) et e’Last(2)

Notes personnelles

9
 Mode de passage IN OUT
Par défaut, il est interdit de modifier les arguments des procédures et fonctions.
On dit que les arguments sont en mode IN, c.-à-d. en entrée seulement.

Mode IN Dest : Character Rouler_Vers

Il est possible de définir des procédures qui modifient leur(s) argument(s), en

particulier lorsque ce sont des tableaux ou des matrices.
Un argument modifié est en mode IN OUT.

Mode IN OUT Arg : Une_Matrice Ajouter_Constante

Lors de l’exécution de la procédure, la matrice passée en argument est modifiée.

Notes personnelles

10
 Procédures avec arguments IN OUT
Une procédure peut modifier ses arguments qui sont en mode IN OUT.
(en général des tableaux ou des matrices)

Définition de procédure avec argument IN OUT

procedure Foo (Bar1 : in Float ; Bar2 : in out Une_Matrice) is
begin
Corps de la procédure Ce in est facultatif
end Foo ;
∈ definition

Exemple de procédure avec argument IN OUT

Cette procédure ajoute une constante à chaque variable de la matrice
procedure Ajouter_Constante (Const : in Float ; Mat : in out Une_Matrice ) is
begin
for Ligne in Mat’Range(1) loop L’argument Mat est
for Col in Mat’Range(2) loop en mode IN OUT.
Mat(Ligne , Col) := Mat(Ligne , Col) + Const ; Il est modifiable
end loop ;
end loop ;
end Ajouter_Constante ;
∈ definition

Const : Float Ajouter_Constante

Mat : Une_Matrice

+ UNE PROCÉDURE AVEC ARGUMENTS IN OUT N’EST PAS UNE FONCTION !

(Elle ne renvoie rien)

11
 Bloc DECLARE
Un bloc declare permet d’insérer des définitions dans un bloc quelconque.

R ÈGLE ` « Bloc DECLARE »

Si ` Dj ∈ definition, et ` B ∈ bloc,
Les définitions Dj sont évaluées
declare
Dj ;
alors ` begin ∈ bloc puis le bloc B est exécuté.
B;
end ;

Exemple de bloc declare

with GAda. Text_IO, GAda. Integer_Text_IO ;
procedure Mission is
package Txt renames GAda. Text_IO ;
package ITxt renames GAda. Integer_Text_IO ;
type Des_Entiers is array( Integer range <>) of Integer ;
Nb_Termes : Integer ;
begin
Txt . Put( "Combien de termes a entrer ? " ) ;
Nb_Termes := ITxt .FGet ;
declare
ZeTab : Des_Entiers ( 1 . .Nb_Termes) ; ∈ definition
begin
for Indice in ZeTab’Range loop
Txt . Put( "Entrer le terme numero " & Integer ’Image( Indice ) & " : " ) ;
ZeTab( Indice ) := ITxt .FGet ;
end loop ;
end ; ∈ bloc
end Mission ;

12
 Vade mecum
SOUS-TYPE (p. 3)
subtype Un_Foo is un_type_existant range intervalle
ex : subtype Natural is Integer range 0 .. Integer’Last

TYPE ÉNUMÉRÉ (p. 4) BLOC CASE (p. 5)

type Un_Signal is (Rouge, Orange, Vert ) ; case Foobar is
Déclaration d’une variable when Rouge => B1 ;
Foobar : Un_Signal ; ∈ definition when Orange => B2 ;
when Vert => B3 ;
Affectation de la variable end case ; ∈ bloc
Foobar := Orange ; ∈ bloc

TABLEAUX (p. 6) PARCOURS DE TABLEAUX (p. 7)

Définition d’un type tableau for Num in Bar ’Range loop
type Des_Foo is array ( Integer range <>) of Float ; Bar(Num) := Bar(Num) + 1.0 ;
Déclaration d’une famille de 5 variables end loop ;
Bar : Des_Foo (1..5) ;
Affectation des variables du tableau
Bar(1) := 12.0 ;
Bar(2) := Bar(1) ∗ 3.0 ;

MATRICES (p. 8) PARCOURS DE MATRICE (p. 9)

Définition d’un type matrice for Ligne in Moo’Range(1) loop
type Une_Mat is array ( Integer range <>, for Col in Moo’Range(2) loop
Integer range <>) of Float ; Moo(Ligne , Col) := 5.0 ;
Déclaration d’une matrice 2x3 end loop ;
Moo : Une_Mat (1..2 , 1..3) ; end loop ;
Affectation des variables de la matrice
Moo(1 ,1) := 0.0 ; Ligne 1, colonne 1
Moo(2 ,1) := 100.0 ; Ligne 2, colonne 1

BLOC DECLARE (p. 12) PROCÉDURE AVEC ARGUMENT IN OUT (p. 11)
declare procedure Foo (Bar1 : in Float ; Bar2 : in out Une_Mat) is
Dj ; ∈ definition begin
begin Corps de la procédure
B ; ∈ bloc end Foo ;
end ;

13
Document compilé le 14 janvier 2010.