Fondements de l'algorithmique et programmation

Ce document présente une initiation à l'algorithmique et à ses principes fondamentaux, indépendamment d'un langage de programmation spécifique. L'objectif est d'acquérir les compétences nécessaires pour analyser, spécifier, modéliser et résoudre des problèmes de manière rigoureuse.

Qu'est-ce que l'Algorithmique ?

Histoire de l'Algorithme

Le terme "algorithme" tire son origine du mathématicien persan du 8ème siècle, Al-Khawarizmi. Son travail visait à rendre les méthodes mathématiques compréhensibles et applicables sans ambiguïté. Bien que le nom soit ancien, la notion d'algorithme est encore plus lointaine, présente chez les Babyloniens 1800 ans avant J.-C.

Définition d'un Algorithme

Un algorithme est un ensemble de règles opératoires claires et non ambiguës, organisées de manière séquentielle, permettant de résoudre un problème donné ou d'accomplir une tâche spécifique à partir de données de départ pour aboutir à un résultat final.

Un algorithme est une suite d'instructions qui, exécutée correctement et dans un ordre précis, conduit à un résultat donné, solution à un problème posé.

Cette notion dépasse largement le cadre de l'informatique, comme illustré par une recette de cuisine (comme celle de l'attiéké Garba), un mode d'emploi, ou des indications de chemin à un touriste.

L'Algorithmique

L'algorithmique est la logique derrière l'écriture des algorithmes. Elle implique la connaissance de la résolution manuelle du problème, des capacités élémentaires d'un ordinateur et de la logique d'exécution des instructions. L'algorithmique est indépendante des langages de programmation et se veut universelle, se concentrant sur les méthodes de résolution d'un problème sans égard aux particularités d'un langage donné.

La Spécification de l'Algorithme

Spécifier un problème consiste à expliciter les informations pertinentes pour une modélisation algorithmique. Cela inclut la définition des données d'entrée, de la sortie (le résultat attendu), et la formalisation des relations qui les lient (le traitement).

Plusieurs méthodes de spécification existent :

• Le langage naturel.
• Le Langage de Description Algorithmique (LDA), privilégié dans ce cours.
• La forme de graphe (arbres binaires, etc.).

Caractéristiques et Propriétés d'un Algorithme

Les caractéristiques d'un algorithme

• La validité : Aptitude à accomplir précisément la tâche pour laquelle il a été conçu.
• La robustesse : Capacité à bien réagir face à des conditions d'utilisation anormales.
• La réutilisabilité : Possibilité d'être adapté pour des tâches équivalentes.
• La complexité : Mesure le nombre d'instructions élémentaires nécessaires à son exécution.
• L'efficacité : Capacité à utiliser de manière optimale les ressources matérielles (temps, mémoire).

Les propriétés d'un algorithme

Un algorithme doit être :

• D'un nombre fini d'étapes.
• Doit fournir un résultat.
• Avoir un comportement déterministe (toujours le même résultat pour les mêmes entrées).
• Chaque opération doit être :
  • Définie rigoureusement et sans ambiguïté.
  • Effective, c'est-à-dire réalisable par la machine.

Le Langage de Description des Algorithmes (LDA)

Le LDA est un pseudo-langage proche du langage humain, conçu pour faciliter l'élaboration et la compréhension des algorithmes. Son avantage principal est sa facilité de transcription vers des langages de programmation réels (Pascal, C, Python, etc.).

Principes du LDA

• Utilise des mots-clés et des structures pour décrire clairement les opérations.
• Permet d'écrire des algorithmes sans connaissance préalable d'un langage de programmation.
• N'a pas de normes universelles ou de syntaxe standardisée, mais les principes logiques sont identiques.
• Certains éléments des langages de programmation peuvent nécessiter des définitions spécifiques en LDA.

Le LDA, bien que non indispensable pour un programme informatique, est crucial pour la structuration et la compréhension de la solution avant la phase de programmation.

Analyse du Problème

Avant de résoudre un problème, une analyse précise est essentielle. Cette réflexion passe par plusieurs étapes incontournables.

1. Définition du problème

Il est primordial de définir clairement les fonctionnalités du programme. Cette étape, qui implique de lire et comprendre le problème plusieurs fois, est la plus importante, car une mauvaise compréhension mènerait à une solution non pertinente.

2. Identification des informations

Cette étape consiste à identifier les différentes catégories de données que l'algorithme manipulera :

• Les données ou entrées : Informations initiales fournies au problème.
• Les intermédiaires : Données temporaires ou de support utilisées pendant le traitement.
• Les sorties ou résultats : Informations finales que l'algorithme doit produire.

Une information est une connaissance supplémentaire sur une donnée (Ex: 'Mfoutou a 20 ans' fait référence à l'âge). Une donnée est la représentation conventionnelle d'une information pour le traitement automatique (Ex: 20). Une donnée est souvent caractérisée par un nom et un type (Ex: âge = 20 de type entier).

3. Spécification des résultats

Il faut définir les étapes du programme, de la saisie des données à l'affichage du résultat. Un prototype peut être établi pour décrire le fonctionnement attendu.

4. Analyse des données

Définir la nature et le type des données, ainsi que celles à sauvegarder, est crucial. Un tableau récapitulatif est souvent utile.

5. Le corps de l'algorithme (Le traitement)

C'est la phase technique où une méthode pratique est proposée pour résoudre le problème.

6. La validation de l'algorithme

Après l'écriture, il est fortement recommandé de tester l'algorithme manuellement ("trace à la main") :

• Dessiner les cases mémoires des variables.
• Exécuter l'algorithme instruction par instruction, modifiant le contenu des variables.
• Vérifier que le résultat final correspond à la solution attendue.

Déclarations

Les Arbres Programmatiques (AP)

Les AP permettent de représenter les algorithmes de manière structurée. Un programme (racine) se décompose en sous-programmes, chacun ayant deux parties :

• Les Déclarations (variables et constantes : Données).
• Les Instructions (traitements sur les données : Opération).

Déclaration
DEBUT
    - instruction(s)
FIN
    

Toute variable utilisée dans les instructions doit être déclarée au préalable, en réfléchissant à sa nature, sa variabilité et son type. Cette phase guide le programmeur.

Les Constantes

Une constante associe un nom à une valeur fixe. Elle améliore la lisibilité et la maintenance du code, permettant de modifier une valeur fréquemment utilisée à un seul endroit.

Syntaxe de déclaration : CONST Nom_de_la_constante ← valeur : Type

Exemples :

• CONST pi ← 3.14 : REEL
• CONST ttl ← 'Message à afficher régulièrement' : CHAINE
• CONST Oui ← VRAI : BOOLEEN
• CONST Resu ← pi*2+5*(15+4) : REEL

Il est conseillé d'utiliser des noms de constantes courts et représentatifs.

Les Variables

Une variable est une zone de mémoire (RAM) identifiée par un nom, servant à stocker une valeur. Cette valeur peut être modifiée durant l'exécution de l'algorithme. La déclaration d'une variable inclut son type pour réserver l'espace mémoire nécessaire et déterminer les opérations possibles.

Syntaxe de déclaration : VAR Nom_de_la_variable : Type

Exemples :

VAR
    Nom_de_la_variable1 : Type1
    Nom_de_la_variable2 : Type2
    Nom_de_la_variable3, Nom_de_la_variable4 : Type3
    

Le Type spécifie l'éventail des valeurs possibles pour la variable, la dimension de la mémoire à réserver et les opérations compatibles.

Les Types

Les types peuvent être classés en plusieurs catégories :

• Types Primitifs : Types de base intégrés au langage de programmation (définis avec le langage).
• Types Scalaires : Types dont les valeurs ont un prédécesseur et un successeur (sauf la première et la dernière) et qui peuvent être représentés par un entier en machine.

Quatre types primitifs sont couramment utilisés, dont trois sont scalaires et un non :

• ENTIER (scalaire - primitif) : Ex: Var Max : Entier
• REEL (non scalaire - primitif) : Ex: Var Point : Reel
• CARACTERE (scalaire - primitif) : Représente un seul caractère. Ex: Var Initiale : Caractere
• BOOLEEN (scalaire - primitif) : Représente deux états (Vrai ou Faux, 0 ou 1). Ex: Var Reussite : Booleen
• ALPHANUMERIQUE (chaîne de caractères) : Ex: Var Message : Alphanumerique

Voici un tableau des types numériques courants et leurs plages :

Les types construits (non primitifs) incluent : les complexes, les piles, les files, les listes, et les tableaux à plusieurs dimensions.

Quelques règles du LDA sur les variables

• Le nom d'une variable ne doit pas contenir :
  • D'espace (ex: MonNom ou mon_nom au lieu de Mon Nom).
  • De caractères spéciaux ou de chiffres au début (ex: age au lieu de 6Toto, {age, l'age).
• Le nom d'une variable doit être significatif (ex: AgeEtudiant ou age_etudiant sont préférables à X).

Notions de base

La Lecture

La lecture permet à l'utilisateur de saisir une valeur qui sera stockée dans une variable. L'ordinateur "lit" la valeur entrée par l'utilisateur.

En LDA, on utilise l'instruction LIRE(variable1, variable2,...).

Exemple :

Var Age : Entier
...
LIRE(Age)
    

L'utilisateur saisira un entier qui sera stocké dans la variable Age.

L'Écriture

L'écriture permet d'afficher un message ou le contenu d'une variable à l'écran pour l'utilisateur. L'ordinateur "écrit" ou "affiche" le résultat.

En LDA, on utilise l'instruction ECRIRE(expression1 ou var1, expression2 ou var2,...).

Exemples :

1. ECRIRE("Texte à afficher")
2. ECRIRE(Nom, " ", Prenom, " ", Age)

La ligne 1 affichera la chaîne de caractères. La ligne 2 affichera les valeurs des variables Nom, Prenom, Age séparées par des espaces.

L'Affectation

L'affectation permet de calculer une expression ou de prendre une donnée et de stocker son résultat dans une variable.

Syntaxe : Nom_variable ← expression

Sémantique : L'expression est évaluée, puis son résultat est stocké dans la variable cible.

Exemple :

Var Valeur : Entier
Valeur ← 15
Valeur ← 19
Valeur ← Valeur*3
Valeur ← 19*3
Ecrire(Valeur) # affichera 57
    

Les Commentaires

Les commentaires sont des explications destinées au programmeur qui lit l'algorithme. Ils ne sont pas exécutés. En LDA, la syntaxe pour les commentaires est :

# Ceci est un commentaire sur une seule ligne
!Ici un commentaire!
/*un autre manière de faire un commentaire*/
/*un commentaire
Un autre sur une autre ligne
Un dernier commentaire */
    

Les Opérateurs

En LDA, plusieurs opérateurs permettent d'effectuer des calculs et des comparaisons :

Exemple d'algorithme de calcul de prix avec TVA :

ALGORITHME Calcul_TVA # Le nom de l'algorithme
CONST
    TauxTVA ← 0.2 : REEL
VAR
    Qt, Pu, Prix_de_revient : REEL
DEBUT
    ECRIRE("Entrer la quantité : ")
    LIRE(Qt)
    ECRIRE("Entrer le prix unitaire : ")
    LIRE(Pu)
    Prix_de_revient ← Pu * Qt * (1 + TauxTVA)
    ECRIRE("Le prix est : ", Prix_de_revient)
FIN # Fin du traitement
    

Les Tests ou les Structures Conditionnelles

Les Algorigrammes

Un algorigramme est une représentation graphique d'un algorithme utilisant des symboles normalisés. C'est un diagramme de directives (actions et décisions) exécutées dans un ordre strict pour accomplir une tâche.

Les Tests

Un test vérifie une condition logique. Le résultat est booléen (Vrai ou Faux).

Exemples :

• (4 < 2) ⇒ Faux
• (8 == 4*2) ⇒ Vrai
• (5 > 6) ET (8 < 12) ⇒ Faux

Tables de vérité pour les opérateurs logiques :

Les Structures Conditionnelles Simples

Cette structure exécute un bloc d'instructions uniquement si la condition est vraie. Si elle est fausse, le bloc est ignoré.

Syntaxe 1 :

SI (Test) ALORS
DEBUT
    Instructions # DEBUT et FIN si plusieurs instructions
FIN
    

Syntaxe 2 (plus compacte) :

SI (Test) ALORS
    Instructions # Omission de DEBUT et ajout de FINSI
FINSI
    

Syntaxe 3 (pour une seule instruction) :

SI (Test) ALORS
    Instruction # Omission de DEBUT et FIN
    

Exemple : Vérifier si un utilisateur est adulte (âge ≥ 18)

Algorithme Adulte
Var
    Age : Entier
Debut
    Ecrire("Saisissez votre âge SVP : ")
    Lire(Age)
    Si(Age >= 18) Alors
        Ecrire("Vous êtes bien un adulte ")
    FinSi
Fin
    

Les Structures Conditionnelles Alternatives

Permet d'exécuter un bloc d'instructions si la condition est vraie, ou un autre bloc si la condition est fausse. Un seul des deux blocs sera exécuté.

Syntaxe :

SI (Test) ALORS
    Instructions 1
SINON
    Instructions 2
FINSI
    

Exemple : Déterminer si un nombre est positif ou négatif :

Algorithme SigneNombre
Var
    a : Reel
Debut
    Ecrire("Entrer le nombre svp ")
    Lire(a)
    Si (a < 0) Alors
        Ecrire("Le nombre est négatif")
    Sinon
        Ecrire("Le nombre est positif ou nul")
    FinSi
Fin
    

Les Structures Conditionnelles Imbriquées

C'est l'emboîtement de plusieurs structures conditionnelles alternatives pour gérer plus de deux possibilités. Cela permet d'optimiser l'exécution en évitant de tester des conditions redondantes.

Syntaxe :

SI Test 1 ALORS
    Instructions
SINON
    SI (Test 2) Alors
        Instructions
    FINSI
FINSI
    

Exemple : Déterminer l'état de l'eau en fonction de la température :

Algorithme TemperatureEau
Var
    Temp : Reel
Debut
    Ecrire("Entrer la température svp : ")
    Lire(Temp)
    Si(Temp <= 0)Alors
        Ecrire("L'eau est à l'état solide")
    SiNon # Si Temp > 0
        Si(Temp < 100)Alors
            Ecrire("L'eau est à l'état liquide")
        SiNon # Si Temp >= 100
            Ecrire("L'eau est à l'état gazeux")
        FinSi
    FinSi
Fin
    

Cette version est plus performante car elle évite de tester des conditions qui sont forcément fausses si une condition précédente est avérée.

Les Boucles ou Structures Itératives

Les structures itératives permettent d'exécuter une séquence d'instructions plusieurs fois jusqu'à ce qu'une condition d'arrêt soit atteinte.

La Boucle Pour...Faire...FinPour

Cette boucle exécute un bloc d'instructions un nombre fini de fois, connu à l'avance. On connaît le nombre d'itérations déjà effectuées et le nombre d'itérations restantes.

Syntaxe :

Pour (variable) allant de (début) A (fin) par (pas) Faire
    Instructions
FinPour
    

Ou :

Pour variable ← debut A fin, pas Faire
    Bloc d'instructions
FinPour
    

Si le pas n'est pas spécifié, il vaut 1.

Exemple : Table de multiplication de 8 :

Algorithme Multiplication_8
Var
    i : Entier
Debut
    Pour i ← 1 A 10 Faire
        Ecrire(i, "x 8 = ", i*8)
    FinPour
Fin
    

La Boucle TantQue...Faire...FinTantQue

Cette boucle exécute des instructions tant qu'une condition est vraie. Le nombre d'itérations n'est pas connu à l'avance. La boucle s'arrête dès que la condition devient fausse. Elle peut s'exécuter 0 fois si la condition est fausse dès le début.

Attention : Il faut s'assurer que les instructions à l'intérieur de la boucle modifient la condition de sortie, sinon on risque une boucle infinie.

Syntaxe :

TANTQUE (Test) FAIRE
    instruction1
    ...
    InstructionN
FINTANTQUE
    

Ou :

TantQue (conditions) Faire
Debut
    instruction1
    ...
    InstructionN
Fin
    

Exemple : Division entière (algorithme de soustractions successives)

Algorithme DivisionEntiere
Var a,b : Entier
Debut
    Lire(a,b)
    TantQue (a < b) faire
        b ← b-a
        Si (a >= b) Alors
            Ecrire("La division entière est :",b)
        FinSi
    FinTantQue
Fin
    

La Boucle Répéter...Jusqu'à

Cette boucle exécute des instructions au moins une fois, puis continue de répéter tant que la condition spécifiée n'est pas vraie. La répétition se fait jusqu'à ce qu'une ou plusieurs conditions soient satisfaites.

Syntaxe :

REPETER
    Instruction 1
    ...
    Instruction N
JUSQUA(condition(s) vrai)
    

Exemple : Algorithme pour déterminer si un nombre est premier :

Algorithme NombrePremier
Var
    a,i : Entier
    Test : Boolean
Debut
    Test ← Vrai #C1 : Initialise 'Test' à Vrai, présumant 'a' est premier.
    Lire(a)
    i ← 2 #C2 : Initialise le diviseur potentiel à 2 (plus petit premier).
    Repeter
        Si(a % i == 0)Alors #C3 : Teste si 'i' divise 'a' (modulo 0).
            Ecrire("Le nombre ",a, "n'est pas premier")
            Test ← Faux #C4 : Si divisible, 'a' n'est pas premier, met 'Test' à Faux.
        SiNon
            i ← i+1 #C5 : Si non divisible, incrémente 'i' pour tester le prochain nombre.
        FinSi
    JusquA(i==a OU Test==Faux) #C6 : La boucle continue tant que 'i' n'atteint pas 'a' ET que 'a' est toujours considéré premier.
    Si(i==a)Alors #C7 : Si la boucle s'est terminée parce que 'i' a atteint 'a' (sans trouver de diviseur), alors 'a' est premier.
        Ecrire("Le nombre ",a,"est premier")
    FinSi
Fin
    

Cet algorithme teste si un nombre est premier. Il y a des cas limites, comme le nombre 2, qui est premier mais que cet algorithme pourrait ne pas traiter de manière optimale.

Les Sous-Procédures (Procédures et Fonctions)

Pour éviter la répétition de code et améliorer la lisibilité et la maintenance, on décompose les problèmes complexes en sous-problèmes, représentés par des sous-procédures.

Définition

Une sous-procédure (que ce soit une procédure ou une fonction) est un algorithme en soi, conçue pour accomplir une tâche spécifique et être réutilisée.

Les Procédures

Une procédure est un bloc d'instructions qui accomplit une tâche spécifique et peut être appelée plusieurs fois dans un programme.

Syntaxe 1 (sans paramètres) :

Procedure NomProcedure()
Const
    #Déclaration des constantes
Var
    #déclaration des variables
Debut
    #Suites d'instructions
FinProcedure
    

Exemple : Procédure SaisieNom()

Procedure SaisieNom()
Var
    Nom : Chaine
Debut
    Ecrire("Veuillez entrer votre nom SVP :")
    Lire(Nom)
FinProcedure
    

Note : Les parenthèses vides () sont obligatoires même sans paramètres.

Syntaxe 2 (avec paramètres) :

Procedure NomProcedureParametre(para1 :Type1, para2, para3 :Type2,...)
Const
    #Déclaration des constantes
Var
    #déclaration des variables
Debut
    #Suites d'instructions
FinProcedure
    

Un paramètre est une variable déclarée entre les parenthèses de la procédure, accessible à l'intérieur de celle-ci.

Appel d'une procédure : Simplement en utilisant son nom suivi des parenthèses dans la procédure principale (ou une autre sous-procédure) :

Debut
    SaisieNom()
Fin
    

Les Fonctions

Une fonction est une sous-procédure qui renvoie obligatoirement une valeur unique à son appelant. Elle est généralement utilisée avec des paramètres.

Les Fonctions Prédéfinies

Certaines fonctions sont déjà implémentées dans les langages de programmation (ex: Sin(), Cos(), Abs(), Tan(), Exp(), Log(), Sqrt()). On les utilise selon une syntaxe spécifique :

a ← Sin(1.2)
b ← Tan(cos(6.25))
c ← Log(45)/Sqrt(20)
    

Les Fonctions Personnalisées

On peut créer ses propres fonctions. Elles retournent une valeur d'un type spécifié.

Syntaxe :

Fonction NomFonctions(para1 :Type, para2, para3 :Type,...) Type renvoyé
Const
    #Déclaration des constantes
Var
    #déclaration des variables
Debut
    #Traitements
    Retourner Résultat
Fin
    

La valeur retournée par Retourner Résultat doit être du type spécifié comme Type renvoyé.

Exemple : Fonction Squart() pour calculer le carré d'un nombre réel :

Fonction Squart(a :Reel):Reel
Var
    Carre : Reel
Debut
    Carre ← a*a
    Retourner Carre
Fin
    

Ou plus succinctement :

Fonction Squart(a :Reel):Reel
Debut
    Retourner a*a
Fin
    

Appel d'une fonction : La valeur retournée est souvent stockée dans une variable.

a ← Squart(4) # 'a' vaut 16
    

La Procédure Principale

La procédure principale (ALGORITHME) est la composition des sous-procédures et fonctions. Les sous-procédures peuvent être déclarées soit en début après les déclarations de variables, soit à la fin de l'algorithme avant le mot Fin.

Structure recommandée :

Algorithme NomAlgo
Const # déclaration des constantes
Var # déclaration des variables
# déclaration des sous-procédures ou fonctions
Debut
    Traitements
Fin
    

Ou :

Algorithme NomAlgo
Const # déclaration des constantes
Var # déclaration des variables
Debut
    Traitements
# déclaration des sous-procédures ou fonctions
Fin
    

La Portée des Variables (Variables Locales et Globales)

• Variables globales : Déclarées dans la procédure principale, elles sont visibles et modifiables par toutes les sous-procédures de cette procédure principale.
• Variables locales : Déclarées au sein d'une sous-procédure, elles ne sont visibles que par cette sous-procédure et sont détruites après son exécution. Elles ne sont pas accessibles par la procédure principale ni par d'autres sous-procédures.

Le Mode de Passage des Variables (Passage par Valeur ou par Référence)

Lorsqu'une variable est passée en paramètre à une sous-procédure, il existe deux modes de passage :

Passage par Valeur

La sous-procédure crée une copie de la variable et travaille sur cette copie. La variable originale reste intacte et sa valeur n'est pas modifiée par la sous-procédure.

• Utilisation en Entrée : OUI
• Utilisation en Sortie : NON

Ce mode assure une sécurité : un bug dans la sous-procédure ne modifiera pas la variable du programme principal.

Passage par Référence

La sous-procédure utilise directement l'emplacement mémoire de la variable originale. Toute modification de la variable dans la sous-procédure affecte la variable correspondante dans la procédure appelante.

• Utilisation en Entrée : OUI
• Utilisation en Sortie : OUI

C'est un mode puissant mais qui exige de la prudence, car des modifications involontaires peuvent introduire des bugs. Dans ce cours, le passage par référence est adopté (comme c'est souvent le cas en Python pour certains types).

La Récursivité

La récursivité est un mécanisme où une fonction ou une procédure s'appelle elle-même. Elle repose sur des principes similaires à la récurrence en mathématiques (suites numériques).

Exemple classique : La suite de Fibonacci où `$f(n) = f(n-1) + f(n-2)$` avec `$f(0) = 0$` et `$f(1) = 1$`. Pour calculer `$f(n)$`, on fait appel à des termes précédents de la même suite.

Avantages et Inconvénients

• Avantages :
  • Très économique en termes de lignes de code pour certains problèmes.
  • Permet une écriture claire et élégante de solutions.
• Inconvénients :
  • Très gourmande en ressources machine (mémoire) en raison de la création de multiples variables temporaires (pile d'appels).

Note : Tout problème formulé en termes récursifs peut aussi être formulé en termes itératifs (avec des boucles). La récursivité n'est jamais indispensable mais est un outil puissant pour le programmeur.

Exemples de Récursivité

Fonction Pgcd() (Plus Grand Commun Diviseur)

Pour calculer le PGCD de deux entiers positifs a et b :

• Si a > b, alors Pgcd(a,b) = Pgcd(a-b, b)
• Si b > a, alors Pgcd(a,b) = Pgcd(a, b-a)
• Condition d'arrêt : Pgcd(a,a) = a ou Pgcd(a,0) = a (dans le cas de l'algorithme d'Euclide par soustractions).

Implémentation récursive du PGCD :

Fonction Pgcd(a,b :Entier) :Entier
Debut
    Si(a == b)Alors
        Retourner a # Condition d'arrêt !
    SiNon
        Si(a > b)Alors
            Retourner Pgcd(a-b,b) # Appel récursif
        SiNon
            Retourner Pgcd(a,b-a) # Appel récursif
        FinSi
    FinSi
Fin
    

Fonction Fibonacci(n)

Implémentation récursive de la suite de Fibonacci :

Fonction Fibo(n :Entier) :Entier
Debut
    Si(n == 0)Alors
        Retourner 0
    SiNon
        Si(n == 1)Alors
            Retourner 1
        SiNon
            Retourner Fibo(n-1) + Fibo(n-2) # Appels récursifs
        FinSi
    FinSi
Fin
    

Cette fonction est élégante mais très inefficace pour de grandes valeurs de n en raison des calculs répétés de mêmes sous-problèmes.

Fonction Somme(n) (Somme des entiers de 1 à n)

Fonction récursive pour calculer la somme des nombres de 1 à n si `$n > 0$` et 0 sinon :

Fonction Somme(n :Entier) :Entier
Debut
    Si(n > 0)Alors
        Retourner (Somme(n-1) + n) # Appel récursif
    SiNon
        Retourner 0
    FinSi
Fin
    

Exemple de trace pour Somme(5) :

• `Somme(5) = Somme(4) + 5`
• `Somme(4) = Somme(3) + 4`
• `Somme(3) = Somme(2) + 3`
• `Somme(2) = Somme(1) + 2`
• `Somme(1) = Somme(0) + 1`
• `Somme(0) = 0` (condition d'arrêt)
• Puis remontée : `Somme(1)=0+1=1`, `Somme(2)=1+2=3`, `Somme(3)=3+3=6`, `Somme(4)=6+4=10`, `Somme(5)=10+5=15`.

Les Tableaux

Définition

Un tableau est un ensemble de valeurs de même type (entiers, réels, chaînes, caractères, etc.), stockées sous un même nom de variable et repérées par un indice.

Exemple de tableau Tab :

Pour accéder à un élément, on utilise le nom du tableau suivi de son indice entre crochets, ex: Tab[5] vaut 2 (le 6ème élément si l'indice commence à 0).

Les indices des tableaux commencent souvent à 0 (comme en C ou Python) mais peuvent parfois commencer à 1 selon le langage.

Déclaration

Les tableaux traités ici sont à une dimension et statiques (leur taille est connue d'avance). Ils ne peuvent contenir que des éléments de même type. Pour des cas de types différents, on utilise d'autres structures comme les enregistrements.

Syntaxe : NomDuTableau : Tableau[taille] De Type des valeurs

Exemple : Tab : Tableau[11] De Entier (un tableau de 11 entiers).

Les Tableaux Dynamiques

Quand la taille d'un tableau n'est pas connue à l'avance, on peut le déclarer dynamiquement. La taille est fixée au cours du programme via une instruction de redimensionnement (par exemple, Redim).

Syntaxe :

NomDuTableau : Tableau[] De Type des valeurs
Lire(n)
Redim NomDuTableau[n-1] # n étant le nombre d'éléments, si indices de 0 à n-1
    

Un tableau non dimensionné est inutilisable.

Les Opérations sur les Tableaux

Remplir un tableau

Consiste à stocker des valeurs dans le tableau, souvent via une boucle.

Exemple : Remplir un tableau avec les 20 premiers termes de la suite de Fibonacci :

Procedure RemplirTabFibo(Tab :Tableau[19] De Entier)
Var
    i : Entier
Debut
    Tab[0] ← 0
    Tab[1] ← 1 # Correction de l'erreur dans la source qui utilise F1 non défini
    Pour i ← 2 A 19 Faire
        Tab[i] ← Tab[i-1] + Tab[i-2] # Stockage du terme Fibonacci
    FinPour
Fin
    

Affichage des éléments d'un tableau

Parcourir le tableau et afficher chaque valeur. La boucle Pour est idéale pour cela.

Exemple :

Procedure AfficheTab(Tab :Tableau[N] De Entier)
Var
    i : Entier
Debut
    Ecrire("Les éléments du tableau sont : ")
    Pour i ← 0 A N-1 Faire
        Ecrire(Tab[i]) # On affiche l'élément à l'indice 'i'
    FinPour
Fin
    

Maximum et minimum d'un tableau

Deux approches :

1. Parcours direct : Comparer chaque élément à un maximum/minimum courant.
2. Tri préalable : Trier le tableau, puis récupérer le premier et le dernier élément.

Exemple (parcours direct) :

Procedure MaxMinTab(Tab :Tableau[N] De Entier)
Var
    Max, Min, i : Entier
Debut
    Max ← Tab[0]
    Min ← Tab[0]
    Pour i ← 0 A N-1 Faire
        Si(Tab[i] < Min)Alors
            Min ← Tab[i]
        FinSi
        Si(Tab[i] > Max)Alors # Correction: comparaison avec Tab[i], pas Tab[0]
            Max ← Tab[i]
        FinSi
    FinPour
    Ecrire("Le maximum est : ", Max, " Et le minimum est : ", Min)
Fin
    

Trier un tableau (Exemple : Tri à Bulle)

Le Tri à Bulle est un algorithme qui parcourt un tableau, compare des paires d'éléments successifs et les échange s'ils sont dans le mauvais ordre. Il répète ce processus jusqu'à ce qu'aucun échange n'ait lieu, signifiant que le tableau est trié.

Procedure TriBulle() # La taille 'n' du tableau doit être passée ou définie
Var
    i, Temp : Entier
    Tab: Tableau[n] : De Entier # 'n' doit être une variable ou une constante connue
    Changement : Booleen
Debut
    Changement ← Vrai
    TantQue (Changement == Vrai) Faire
        Changement ← Faux
        Pour i ← 0 A n - 2 Faire # 'n-2' car on compare Tab[i] et Tab[i+1]
            Si(Tab[i] > Tab[i + 1])Alors
                Temp ← Tab[i]
                Tab[i] ← Tab[i + 1]
                Tab[i + 1] ← Temp
                Changement ← Vrai
            FinSi
        FinPour
    FinTantQue
Fin
    

Il existe de nombreux autres algorithmes de tri (tri par insertion, tri rapide, tri fusion, etc.), chacun ayant des avantages en fonction des caractéristiques du tableau à trier.

Les Chaînes de Caractères

Définition

Une chaîne de caractères est une séquence de caractères (ASCII). Elle représente des mots, des assemblages de lettres et de chiffres.

• Les caractères sont stockés sous forme numérique (code ASCII).

Déclaration

Les chaînes peuvent être déclarées sans taille fixe ou avec une taille maximale :

Machaine : Chaine # Peut prendre n'importe quelle longueur
Ou
Machaine[10]: Chaine # Limitée à 10 caractères
    

Exemple d'affectation : Machaine ← 'Bonjour'

Les Opérations sur les Chaînes

Les chaînes se manipulent de manière similaire aux tableaux.

• Accès aux caractères par indexation :

  Ecrire(Machaine[0]) # Affiche 'B'
  Ecrire(Machaine[6]) # Affiche 'r' (pour 'Bonjour')
              

• Extraction de sous-chaînes :
  • Un caractère : Machaine[i]
  • Plusieurs caractères (de l'indice i à j) : Machaine[i:j]
  • Du début au j-ème caractère : Machaine[:j]
  • Du i-ème caractère à la fin : Machaine[i:]
• Concaténation : Combinaison de chaînes.

  Machaine[i] + ' Tout le monde !' # Donne 'Bonjour Tout le monde !'
  Machaine3 ← Machaine1 + Machaine2
              

• Taille : Fonction pour obtenir la longueur d'une chaîne.

  len(Machaine) # Renvoie la taille de la chaîne (ex: 7 pour 'Bonjour')
              

Les Enregistrements

Définition

Contrairement aux tableaux (éléments de même type), les enregistrements sont des structures de données dont les éléments (champs) peuvent être de types différents mais se rapportent à une même entité sémantique. On les appelle parfois structures (comme en C) ou objets (en POO).

Déclaration d'un type structuré

Avant de déclarer une variable d'enregistrement, il faut définir son type, c'est-à-dire le nom et le type de ses champs.

Les types structurés sont déclarés dans une section Type, qui précède la section Var.

Syntaxe :

Type
    Structure NomType
        NomChamp1: TypeChamp1
        ...
        NomChampN: TypeChampN
    FinStruct
    

Exemple :

Type
    Structure Personne
        Nom : Chaine
        Prenoms : Chaine
        Age : Entier
    FinStruct
    

Déclaration d'un enregistrement à partir d'un type structuré

Une fois le type structuré défini, on peut déclarer des variables de ce type comme n'importe quelle variable primitive.

Syntaxe : Var NomVariable:TypeEnregistrer

Exemple :

Var Pers1, Pers2, Pers3 : Personne
    

Les enregistrements sont des zones de données composées de champs.

Manipulation d'un enregistrement

La manipulation se fait champ par champ. On peut affecter un enregistrement à un autre du même type. Pour accéder à un champ, on utilise l'opérateur point « . » :

Syntaxe : NomEnregistrement.NomChamp

Exemple : Pour accéder à l'âge de Pers1 :

SonAge ← Pers1.Age # SonAge vaut 12
    

Attention : Le nom du champ est toujours précédé du nom de l'enregistrement. On ne peut pas manipuler un champ seul.

Un enregistrement comme champ d'une structure

Un type structuré peut être utilisé comme type pour un champ d'une autre structure. Par exemple, une date de naissance peut être un enregistrement à part entière, intégrée dans une structure Personne.

TYPE
    Structure LaDate
        Jour: Entier
        Mois: Chaîne
        Annee: Entier
    FinStruct
    Structure Personne
        Nom : chaîne
        DtNaissance : LaDate # Un enregistrement DtNaissance de type LaDate
    FinStruct
    

Pour accéder à un champ imbriqué, on utilise l'opérateur point de manière successive :

Var
    Pers1 : Personne
    Annee_de_Naissance ← Pers1.DtNaissance.Annee
    

Les tableaux d'enregistrements (ou tables)

Pour gérer plusieurs enregistrements de type similaire (ex: un groupe d'étudiants), on utilise un tableau d'enregistrements, souvent appelé "table".

Type
    Structure Etudiant
        Nom : Chaîne
        Prenoms : Chaîne
        Sexe : Caractere # (M ou F)
        Age : Entier
    FinStruct
    Tab : Tableau[N] : De Etudiant
    

Représentation d'une table :

Pour accéder au nom du quatrième étudiant : Tab[3].Nom.

Points Clés et Réflexions Finales

• L'algorithmique est le fondement de la programmation, axé sur la logique de résolution de problèmes plutôt que sur un langage spécifique.
• Un algorithme est une suite finie et non ambiguë d'instructions pour accomplir une tâche.
• Le LDA (Langage de Description Algorithmique) est un outil essentiel pour concevoir et communiquer des algorithmes de manière claire.
• L'analyse d'un problème (définition, identification des données, spécification des résultats) est cruciale avant toute implémentation.
• Les déclarations (constantes, variables, types) structurent et facilitent la compréhension du code.
• Les structures de contrôle (conditionnelles et itératives) sont les piliers pour diriger le flux d'exécution de l'algorithme.
• Les sous-procédures (fonctions et procédures) permettent la modularité, la réutilisabilité et la maintenance du code.
• La récursivité est une technique puissante mais à utiliser avec discernement en raison de son coût en ressources.
• Les tableaux et les enregistrements sont des structures de données fondamentales pour organiser des collections d'informations, qu'elles soient de même type ou hétérogènes.

Notion d'Algorithme

L'algorithme est un concept fondamental en informatique et au-delà. Il s'agit d'une suite d'instructions précises et non ambiguës, organisées de manière logique, qui visent à résoudre un problème donné ou à accomplir une tâche spécifique.

Capacités attendues à l'issue du cours

1. Analyser, spécifier et modéliser rigoureusement une situation ou un problème, indépendamment d'un langage de programmation.

2. Expliquer le fonctionnement d'un algorithme.

3. Déterminer la trace d'un algorithme.

4. Justifier qu'une itération (ou boucle) produit l'effet attendu au moyen d'un invariant.

5. Démontrer qu'une boucle se termine effectivement et modifier un algorithme existant pour obtenir un résultat différent.

6. Décomposer un problème complexe en sous-problèmes plus simples.

Qualités requises pour la maîtrise de l'algorithmique

• Intuition: Nécessaire pour concevoir les instructions permettant d'atteindre le résultat souhaité. Elle s'acquiert par l'expérience répétée, transformant un raisonnement ardu en réflexe spontané.

• Méthode et Rigueur: Indispensables pour vérifier l'exactitude des instructions. Il faut se mettre mentalement à la place de la machine, crayon et papier en main, pour s'assurer que le résultat obtenu est celui escompté.

Il est fortement recommandé de s'exercer régulièrement, par exemple en écrivant deux algorithmes chaque soir. Une pratique assidue permet de "déceler le mythe des algorithmes" et d'aborder tout algorithme, quelle que soit sa complexité.

Histoire de l'Algorithme

La notion d'algorithme tire son nom d'Al-Khawarizmi, un mathématicien Perse du VIII^e siècle. Son travail visait à rendre les méthodes mathématiques compréhensibles et applicables sans ambiguïté à un large public. Bien que le terme soit ancien, la notion d'algorithme est encore plus ancienne, présente chez les Babyloniens 1800 ans avant J.-C.

Définition d'un Algorithme

Un algorithme est un ensemble de règles opérationnelles propres à un calcul ou l'enchaînement des actions nécessaires à l'accomplissement d'une tâche.

Un algorithme, c'est une suite d'instructions qui, une fois exécutée correctement dans un ordre bien précis, conduit à un résultat donné, solution à un problème posé.

La notion d'algorithme dépasse largement l'informatique. Sa création exige un vocabulaire partagé, des opérations de base maîtrisées par tous et de la précision.

L'Algorithmique

L'algorithmique est la logique d'écrire des algorithmes. Elle nécessite de connaître la résolution manuelle du problème, les capacités de l'ordinateur en termes d'actions élémentaires et la logique d'exécution des instructions.

L'algorithmique est indépendante des langages de programmation. Un algorithme de tri, par exemple, peut être implémenté dans la plupart des langages. L'algorithmique s'attache à l'étude des méthodes de résolution de problèmes sans prendre en compte les particularités d'un langage, la rendant ainsi universelle.

Schéma usuel de résolution d'un problème

Le processus de résolution d'un problème est structuré :

1. Définition du problème

2. Analyse de la solution

3. Conception de l'algorithme

4. Codage du programme

5. Test et validation

Spécification de l'Algorithme

Spécifier un problème consiste à expliciter les informations pertinentes pour une modélisation algorithmique, incluant les données d'entrée, les sorties (résultats) et les relations qui caractérisent leur traitement.

Plusieurs méthodes de spécification existent :

• Le langage naturel.

• Le Langage de Description Algorithmique (LDA), privilégié dans ce cours.

• Les formes graphiques (arbres binaires, etc.).

NB: Une information est une connaissance supplémentaire sur une donnée (ex: "Mfoutu a 20 ans" réfère à l'âge). Une donnée est la représentation conventionnelle d'une information permettant son traitement automatique (ex: 20). Une donnée est souvent désignée par un nom et son type (ex: âge = 20 de type entier naturel positif).

Caractéristiques et Propriétés d'un Algorithme

Caractéristiques d'un algorithme

• Validité: Aptitude à réaliser exactement la tâche pour laquelle il a été conçu.

• Robustesse: Aptitude à se protéger des conditions anormales d'utilisation.

• Réutilisabilité: Aptitude à être réutilisé pour des tâches équivalentes.

• Complexité: Nombre d'instructions élémentaires nécessaires à l'exécution.

• Efficacité: Aptitude à utiliser de manière optimale les ressources matérielles.

Propriétés d'un algorithme

• Doit comporter un nombre fini d'étapes.

• Doit fournir un résultat.

• Doit avoir un comportement déterministe.

• Chaque opération doit être définie rigoureusement et sans ambiguïté.

• Chaque opération doit être effective, c'est-à-dire réalisable par la machine.

Le Langage de Description Algorithmique (LDA)

Le LDA est un pseudo-langage proche du langage humain, facile à comprendre et permettant d'élaborer un algorithme. Il offre une vue générale de la logique et du fonctionnement des langages de programmation et est facilement transposable dans des langages comme Pascal, C, ou Python.

• Le LDA utilise des mots-clés et des structures pour décrire les opérations sur les données.

• Il n'existe pas de normes ou de syntaxes universelles pour le LDA ; la réalisation peut varier d'un individu à l'autre, mais la logique reste la même.

• Tous les éléments d'un langage de programmation ne sont pas nécessairement présents dans le LDA ; il peut être nécessaire de définir des expressions pour les représenter.

Bien que non indispensable, le LDA est très important pour une meilleure structuration et compréhension de la solution avant la programmation.

Analyse du problème

Avant de résoudre un problème, une analyse précise est nécessaire. Elle comprend les étapes suivantes :

Définition du problème

Il faut définir clairement les fonctionnalités du programme en lisant attentivement le problème pour bien le cerner et détecter les routines. C'est l'étape la plus importante : une mauvaise compréhension du problème mène à une solution invalide.

Identification des informations

Il s'agit de déterminer les données de départ, les données à sauvegarder, et les données intermédiaires.

• Données d'entrée: Informations initiales fournies par le problème.

• Données intermédiaires: Informations temporaires utilisées pour stocker des valeurs ou des résultats, ou pour parcourir des variables.

• Sorties ou résultats: Informations que l'algorithme doit retourner à l'utilisateur, constituant la solution du problème.

Spécification des résultats

Définir les étapes du programme, de la saisie des données à l'affichage du résultat. Un prototype peut être établi pour décrire le fonctionnement du programme.

Analyse des données

Définir la nature des différentes données et celles qui doivent être sauvegardées. Il est conseillé d'utiliser un tableau pour résumer ces informations.

Corps de l'algorithme (Le traitement)

C'est la phase technique où l'on propose une méthode pratique pour résoudre le problème.

Validation de l'algorithme

Après écriture, l'algorithme doit être testé manuellement ("brouillon de calcul").

1. Dessiner les cases mémoires de toutes les variables.

2. Exécuter l'algorithme en modifiant le contenu de chaque variable pour chaque instruction.

3. Vérifier si le résultat final correspond à la solution attendue.

Les déclarations

Un algorithme est structuré en deux parties principales :

• Les Déclarations (variables et constantes : Données).

• Les Instructions (traitements sur les données : Opération).

Déclaration
DEBUT
    - instruction(s)
FIN

Toute variable utilisée dans la partie "instruction" doit être déclarée au préalable. La phase de déclaration doit inclure une réflexion sur la nature, la variabilité et l'utilité des données, servant de guide au programmeur.

Les constantes

Une constante associe un nom à une valeur ou une expression fixe. Elle améliore la lisibilité du code et simplifie les modifications d'une valeur répétée plusieurs fois.

La déclaration utilise le mot réservé CONST (ou "Const").

CONST Nom_de_la_constante ← valeur : Type

Exemples :

CONST pi ← 3.14 : REEL
CONST ttl ← 'Message à afficher régulièrement' : CHAINE
CONST Oui ← VRAI : BOOLEEN
CONST Resu ← pi*2+5*(15+4) : REEL

Il est préférable d'utiliser des noms courts et représentatifs pour les constantes.

Les variables

Une variable est une zone mémoire réservée (RAM) pour stocker une valeur. Elle est identifiée par un nom et sa valeur peut être modifiée durant l'exécution. La déclaration d'une variable requiert le type de son contenu pour réserver la taille mémoire nécessaire.

La déclaration utilise le mot réservé VAR (ou "Var").

VAR Nom_de_la_variable : Type

Exemples :

VAR
    Nom_de_la_variable1 : Type1
    Nom_de_la_variable2 : Type2
    Nom_de_la_variable3, Nom_de_la_variable4 : Type3

• Nom_de_la_variable: Le nom attribué à la variable.

• Type: Spécifie l'ensemble des valeurs possibles pour la variable, la dimension de la zone mémoire et les opérations supportées.

Les types

Types primitifs et scalaires

Les types peuvent être classés en catégories. Un type primitif est un type intégré au langage de programmation. Un type scalaire est un type dont chaque valeur (sauf la première et la dernière) a un prédécesseur et un successeur, et est représenté par un entier en machine.

Plages de valeurs des types numériques

Les types construits: Complexes, Piles, Files, Listes, Tableaux à plusieurs dimensions.

Quelques règles du LDA sur les variables

• Le nom d'une variable ne doit jamais contenir d'espace (ex: MonNom ou mon_nom, pas Mon Nom).

• Ne doit pas contenir de caractères spéciaux ni de chiffres au début (ex: Toto6, pas 6Toto).

• Le nom d'une variable doit être significatif (ex: AgeEtudiant ou age_etudiant, pas X).

Notions de base

La lecture

La lecture permet à l'utilisateur de saisir une valeur qui sera stockée dans une variable. L'ordinateur "lit" la valeur saisie par l'utilisateur.

En LDA, l'instruction utilisée est LIRE(variable1, variable2,...).

Exemple :

VAR Age : Entier
...
LIRE(Age)

L'utilisateur saisira une valeur entière qui sera stockée dans la variable Age.

L'écriture

L'écriture permet d'afficher un message ou le contenu d'une variable à l'écran pour l'utilisateur. L'ordinateur "écrit" (affiche) le résultat.

En LDA, l'instruction utilisée est ECRIRE(expression1 ou var1, expression2 ou var2,...).

Exemples :

1. ECRIRE("Texte à afficher")

2. ECRIRE(Nom, " ", Prenom, " ", Age)

La ligne 1 affichera la chaîne de caractères. La ligne 2 affichera les contenus des variables Nom, Prenom, Age séparés par des espaces.

L'affectation

L'affectation permet de stocker le résultat d'un calcul ou une donnée dans une variable.

Syntaxe :

Nom_variable ← expression

Sémantique : L'expression est d'abord évaluée, puis son résultat est stocké dans la variable.

Exemple :

VAR Valeur : Entier
Valeur ← 15    # Valeur contient maintenant 15
Valeur ← 19    # Valeur contient maintenant 19 (l'ancienne valeur est écrasée)
Valeur ← Valeur*3 # Valeur est 19*3 = 57
Valeur ← 19*3   # Valeur est 57
ECRIRE(Valeur)   # affichera 57

Les commentaires

Les commentaires sont des explications ajoutées à l'algorithme pour faciliter sa compréhension par un programmeur. Ils ne sont pas exécutés par la machine.

Syntaxes :

# Ceci est un commentaire sur une seule ligne.

Une autre syntaxe acceptée (mais moins utilisée dans ce cours) :

/*une autre manière de faire un commentaire*/
/*un commentaire
Un autre sur une autre ligne
Un dernier commentaire */
!Ici un commentaire!

Les opérateurs

Le LDA utilise des opérateurs pour effectuer des calculs et des comparaisons.

Logique OU Inclusif a OU b ET Juxtaposition a ET b NON Négation NON a Opération arithmétique + Addition a + b - Soustraction a - b * Multiplication a * b / Division euclidienne a / b % Reste de la division a % b ^ Exponentielle a ^ b Opération d'affectation ← Attribuer une donnée ou un calcul à une variable a ← b

Les tests ou les structures conditionnelles

Les tests permettent de vérifier une condition logique qui est soit Vrai, soit Faux (booléen).

Algorigrammes

Un algorigramme est une représentation graphique d'un algorithme utilisant des symboles normalisés. Il représente le fonctionnement des automatismes séquentiels.

Les tests

Un test évalue une condition à Vrai ou Faux.

• (4 < 2) → Faux

• (8 == 4*2) → Vrai

• (5 > 6) ET (8 < 12) → Faux

Tables de vérité

Les structures conditionnelles simples

Permettent d'exécuter un bloc d'instructions si une condition est Vraie. Si elle est Fausse, le bloc est ignoré.

Syntaxe 1 (plusieurs instructions) :

SI (Test) ALORS
DEBUT
    Instructions
FIN

Syntaxe 2 (plusieurs instructions, syntaxe privilégiée) :

SI (Test) ALORS
    Instructions
FINSI

Syntaxe 3 (une seule instruction, facultatif) :

SI (Test) ALORS
    Instruction

Exemple : Vérifier si un utilisateur est adulte

Algorithme Adulte
VAR Age : Entier
DEBUT
    ECRIRE("Saisissez votre âge SVP : ")
    LIRE(Age)
    SI (Age >= 18) ALORS
        ECRIRE("Vous êtes bien un adulte ")
    FINSI
FIN

Les structures conditionnelles alternatives

Permettent d'exécuter un bloc d'instructions si le test est Vrai, ou un autre bloc si le test est Faux. Un seul des deux blocs sera exécuté.

Syntaxe :

SI (Test) ALORS
    Instructions 1
SINON
    Instructions 2
FINSI

Remarque : Si la condition du SI est Vraie, le bloc SINON est automatiquement ignoré. Un seul branchement est choisi à l'exécution.

Exemple : Déterminer le signe d'un nombre

Algorithme SigneNombre
VAR a : Reel
DEBUT
    ECRIRE("Entrer le nombre svp ")
    LIRE(a)
    SI (a < 0) ALORS
        ECRIRE("Le nombre est négatif")
    SINON # <- il fera l'opération opposée si le test est faux
        ECRIRE("Le nombre est positif ou nul")
    FINSI
FIN

Les structures conditionnelles imbriquées

Ces structures consistent à emboîter plusieurs conditions alternatives, permettant plus de deux possibilités.

Syntaxe :

SI Test 1 ALORS
    Instructions
SINON
    SI Test 2 ALORS
        Instructions
    FINSI
FINSI

L'imbrication permet de réduire les tests et d'optimiser le temps d'exécution. Si une condition est vraie, les conditions suivantes dans la même branche SINON ne sont pas évaluées, ce qui rend l'algorithme plus performant.

Exemple : État de l'eau en fonction de la température

Algorithme TemperatureEauOptimise
VAR Temp : Reel
DEBUT
    ECRIRE("Entrer la température svp : ")
    LIRE(Temp)
    SI (Temp <= 0) ALORS
        ECRIRE("L'eau est à l'état solide")
    SINON
        SI (Temp < 100) ALORS
            ECRIRE("L'eau est à l'état liquide")
        SINON
            ECRIRE("L'eau est à l'état gazeux")
        FINSI
    FINSI
FIN

Cette version est plus efficace que trois SI indépendants car elle évite d'évaluer des conditions qui seraient forcément fausses.

Les boucles ou structures itératives

Les structures itératives permettent d'exécuter une séquence d'instructions plusieurs fois jusqu'à ce qu'une condition d'arrêt soit atteinte.

La boucle Pour... Faire... FinPour

Cette boucle exécute un bloc d'instructions un nombre fini de fois, connu à l'avance. On connaît le nombre d'itérations déjà effectuées et celles restantes.

Syntaxe :

Pour (variable) allant de (début) À (fin) par (pas) Faire
    Instructions
FinPour

Ou :

Pour variable ← debut À fin, pas Faire
    Bloc d'instructions
FinPour

Si le pas n'est pas spécifié, il vaut 1 par défaut.

Exemple : Table de multiplication de 8

Algorithme Multiplication_8
VAR i : Entier
DEBUT
    Pour i ← 1 À 10 Faire # Lorsque le pas n'est pas spécifié, il vaut 1
        ECRIRE(i, " x 8 = ", i*8)
    FinPour
FIN

La boucle TantQue... Faire... FinTantQue

Cette boucle exécute des itérations tant qu'une certaine condition est vérifiée. Le nombre d'itérations n'est pas connu à l'avance. À chaque itération, la condition est vérifiée. La boucle s'arrête dès que la condition devient Fausse. Le nombre minimum d'exécutions est 0 (la condition peut être fausse dès le début).

Attention : Il faut s'assurer que les itérations modifient la valeur de la condition de boucle, sinon on risque une "boucle infinie".

Syntaxe :

TANTQUE (Test) FAIRE
    instruction1
    ...
    InstructionN
FINTANTQUE

Ou avec DEBUT/FIN pour plusieurs instructions :

TantQue (conditions) Faire
DEBUT
    instruction1
    ...
    InstructionN
FIN

Exemple : Division entière (trace pour a=3, b=14)

Algorithme DivisionEntiere
VAR a, b : Entier
DEBUT
    LIRE(a,b) # a=3, b=14
    TantQue (a < b) faire # 3 < 14 est Vrai
        b ← b - a # b ← 14 - 3 = 11
        # La boucle continue...
        # 3 < 11 est Vrai → b ← 11 - 3 = 8
        # 3 < 8 est Vrai → b ← 8 - 3 = 5
        # 3 < 5 est Vrai → b ← 5 - 3 = 2
        # 3 < 2 est Faux, la boucle se termine.
    FinTantQue
    SI (a >= b) Alors # 3 >= 2 est Vrai
        ECRIRE("La division entière est :", b) # Affichera "La division entière est : 2"
    FINSI
FIN

La boucle Répéter... Jusqu'à

Cette boucle exécute un bloc d'instructions jusqu'à ce qu'une ou plusieurs conditions soient satisfaites. La particularité est qu'elle s'exécute au minimum une fois, car le test est effectué en fin de boucle.

Syntaxe :

REPETER
    Instruction 1
    ...
    Instruction N
JUSQUA (condition(s) vrai)

Exemple : Déterminer si un nombre est premier

Un nombre est premier s'il n'admet pas de diviseurs (en dehors de 1 et lui-même) parmi les nombres positifs inférieurs à lui.

Algorithme NombrePremier
VAR a, i : Entier
    Test : Booleen
DEBUT
    Test ← Vrai # C1 : Initialisation du flag de test
    LIRE(a)
    i ← 2 # C2 : Initialisation du diviseur potentiel
    REPETER
        SI (a % i == 0) ALORS # C3 : Si 'a' est divisible par 'i'
            ECRIRE("Le nombre ", a, " n'est pas premier")
            Test ← Faux # C4 : Le nombre n'est pas premier
        SINON
            i ← i + 1 # C5 : Incrémenter le diviseur potentiel
        FINSI
    JUSQUA (i == a OU Test == Faux) # C6 : Arrêt si 'i' atteint 'a' ou si 'a' n'est pas premier
    SI (i == a) ALORS # C7 : Si la boucle s'est terminée car 'i' a atteint 'a' (sans trouver de diviseur)
        ECRIRE("Le nombre ", a, " est premier")
    FINSI
FIN

Les sous-procédures et fonctions

Pour éviter la répétition de code et améliorer la maintenabilité, on décompose un programme en modules séparés appelés sous-procédures (ou procédures) et fonctions.

Un sous-algorithme (procédure ou fonction) est un algorithme à part entière, avec sa propre structure.

Contexte de l'utilisation des sous-procédures

Quand un code source est long et que des traitements similaires doivent être exécutés plusieurs fois (ex: contrôle de saisie), répéter le code est une mauvaise pratique car :

• Cela rend le programme lourd et illisible.

• Cela complexifie la maintenance : toute modification doit être appliquée à chaque occurrence, augmentant les risques de bugs.

La solution est de regrouper ces instructions dans un module séparé et de l'appeler chaque fois que nécessaire. Cela assure la lisibilité, la modularité et facilite la maintenance en centralisant les modifications.

Le corps du programme s'appelle la procédure principale, et les groupes d'instructions réutilisables sont les fonctions et les sous-procédures.

Définition des sous-procédures

Une sous-procédure (ou procédure) est un algorithme qui accomplit une tâche spécifique et est conçue pour être réutilisée plusieurs fois au sein d'une procédure principale.

Syntaxe :

Procedure NomProcedure(paramètres facultatifs)
    Const
        # Déclaration des constantes
    Var
        # Déclaration des variables
    Debut
        # Suites d'instructions
    FinProcedure

Exemple : Procédure de saisie de nom

Procedure SaisieNom()
    Var
        Nom : Chaine
    Debut
        ECRIRE("Veuillez entrer votre nom SVP :")
        LIRE(Nom)
    FinProcedure

Attention : Ne pas oublier les parenthèses ouvrante et fermante après le nom de la procédure. Cette procédure est dite "sans paramètre".

Syntaxe avec paramètres :

Procedure NomProcedureParametre(para1 :Type1, para2, para3 :Type2,...)
    Const
        # Déclaration des constantes
    Var
        # Déclaration des variables
    Debut
        # Suites d'instructions
    FinProcedure

Un paramètre est une variable déclarée entre les parenthèses de la procédure et utilisable à l'intérieur de celle-ci.

Appel d'une procédure :

Pour utiliser une procédure, il suffit de la "référencer" par son nom dans le corps du programme principal.

Debut
    SaisieNom() # Appel de la procédure SaisieNom
Fin

Les fonctions

Une fonction est une sous-procédure qui renvoie obligatoirement une valeur unique à son utilisateur. Elle s'utilise toujours avec des paramètres.

Fonctions prédéfinies

Ce sont des fonctions déjà connues et programmées. Il suffit de les connaître et de les appeler. Exemples : Sin(), Cos(), Abs(), Tan(), Exp(), Log(), Sqrt().

Utilisation en LDA :

a ← Sin(1.2)
b ← Tan(Cos(6.25))
c ← Log(45)/Sqrt(20)

Fonctions personnalisées

Pour créer ses propres fonctions. La fonction doit renvoyer une valeur unique.

Syntaxe :

Fonction NomFonctions(para1 :Type, para2, para3 :Type,...) Type_renvoyé
    Const
        # Déclaration des constantes
    Var
        # Déclaration des variables
    Debut
        # Traitements
        Retourner Résultat

Le type du résultat renvoyé par la fonction doit correspondre à Type renvoyé. Une fonction utilise l'instruction Retourner au lieu de FinFonction.

Exemple : Fonction pour calculer le carré d'un nombre réel

Fonction Carre(a :Reel):Reel
    Var
        ResCarre : Reel
    Debut
        ResCarre ← a*a
        Retourner ResCarre

Ou de manière plus concise :

Fonction Carre(a :Reel):Reel
    Retourner a*a

Appel d'une fonction :

Comme une fonction renvoie une valeur, il est courant de stocker cette valeur dans une variable.

Exemple :

x ← Carre(4) # x vaut 16

La procédure principale

La procédure appelée Algorithme au début du cours est la procédure principale. Elle est la composition de sous-procédures et fonctions.

Les sous-procédures et fonctions doivent être déclarées au sein de la procédure principale : soit en début (après la déclaration des variables), soit à la fin (avant le mot Fin).

Syntaxe 1 :

Algorithme NomAlgo
    Const # Déclaration des constantes
    Var   # Déclaration des variables
    # Déclaration des sous-procédures ou fonctions
    Debut
        Traitements
    Fin

Syntaxe 2 :

Algorithme NomAlgo
    Const # Déclaration des constantes
    Var   # Déclaration des variables
    Debut
        Traitements
    # Déclaration des sous-procédures ou fonctions
    Fin

La portée des variables

Lorsqu'il y a plusieurs déclarations de variables (dans la procédure principale et dans les sous-procédures) :

• Les variables déclarées dans la procédure principale sont des variables globales. Elles sont visibles et modifiables par toutes les sous-procédures de la procédure principale.

• Les variables déclarées au sein d'une sous-procédure sont des variables locales. Elles ne sont visibles que par cette sous-procédure. En dehors (dans la procédure principale ou d'autres sous-procédures), elles ne sont pas reconnues et sont détruites après l'exécution de la sous-procédure.

Le mode de passage des variables (arguments)

Lorsqu'une variable est passée en paramètre à une sous-procédure ou fonction, elle est appelée argument. Il existe deux modes de passage : par valeur ou par référence.

• Passage par valeur:

  • La sous-procédure crée une copie de l'argument et travaille uniquement sur cette copie.

  • La variable originale reste intacte et inchangée.

  • C'est une sécurité : si un bug survient dans la sous-procédure, il n'altère pas la valeur de la variable dans le programme appelant.

  • Un argument passé par valeur ne peut être utilisé qu'en entrée (lecture) par la sous-procédure.

• Passage par référence:

  • La sous-procédure manipule directement la variable originale (une "référence" à l'emplacement mémoire de la variable).

  • Toute modification de la valeur de l'argument dans la sous-procédure affecte directement la variable correspondante dans la procédure appelante.

  • Permet l'utilisation de l'argument à la fois en entrée (lecture) et en sortie (écriture).

  • Présente un risque : un bug dans la sous-procédure peut altérer de manière inattendue la variable du programme principal.

Récapitulatif des modes de passage :

Dans ce cours, le passage par référence sera adopté.

La récursivité

La récursivité est un concept où une fonction (ou procédure) s'appelle elle-même durant son exécution.

En mathématiques, on retrouve un concept similaire avec la récurrence dans les suites numériques, comme la suite de Fibonacci : avec , et . Pour calculer , il faut faire appel à et , créant une pile de calculs en attente.

Avantages et Inconvénients de la Récursivité

• Avantages :

  • Très économique pour le programmeur pour certains problèmes, permettant d'écrire des solutions élégantes avec peu d'instructions.

• Inconvénients :

  • Peut être très gourmande en ressources machine (mémoire et temps d'exécution), car elle doit créer des variables temporaires pour chaque appel récursif en attente.

Tout problème formulé en termes récursifs peut également être formulé en termes itératifs (avec des boucles). La récursivité n'est donc jamais indispensable, mais c'est une technique essentielle à connaître pour un informaticien.

Exemple : Calcul du PGCD (Plus Grand Commun Diviseur)

En utilisant les formules mathématiques : si , alors , et . L'appel répétitif de Pgcd est une illustration de récursivité, avec une condition d'arrêt (ex: ).

Approche itérative pour le PGCD :

Algorithme PgcdIteratif
VAR a, b : Entier
DEBUT
    ECRIRE("Entrez deux nombres entiers svp ! ")
    LIRE(a,b)
    TantQue (b <> a) Faire
        SI (a > b) ALORS
            a ← a - b
        SINON
            b ← b - a
        FINSI
    FinTantQue
    ECRIRE("Pgcd =", b)
FIN

Approche récursive pour le PGCD :

Fonction PgcdRecursif(a,b :Entier) :Entier
DEBUT
    SI (a == b) ALORS

Retourner a # Condition d'arrêt SINON SI (a > b) ALORS Retourner PgcdRecursif(a-b,b) # Appel récursif SINON Retourner PgcdRecursif(a,b-a) FINSI FINSI FIN

Exemple de trace pour Pgcd(42, 25) :

2. \mathrm{Pgcd}(17,25) \rightarrow a</p></li><li><p style="text-align: left;"><span data-latex="\mathrm{Pgcd}(17,8) \rightarrow a&gt;b \rightarrow \mathrm{Pgcd}(17-8, 8) = \mathrm{Pgcd}(9,8)" data-type="inline-math"></span></p></li><li><p style="text-align: left;"><span data-latex="\mathrm{Pgcd}(9,8) \rightarrow a&gt;b \rightarrow \mathrm{Pgcd}(9-8, 8) = \mathrm{Pgcd}(1,8)" data-type="inline-math"></span></p></li><li><p style="text-align: left;"><strong>\mathrm{Pgcd}(1,8) \rightarrow a

3. ...

4. $\mathrm{Pgcd}(1,2) \rightarrow a

5. (condition d'arrêt)

Exemple : Suite de Fibonacci

Approche itérative pour Fibonacci :

Algorithme FibonacciIteratif
VAR F1, F2, F3, n, i : Entier
DEBUT
    F1 ← 0
    F2 ← 1
    ECRIRE("Entrer la valeur de n : ")
    LIRE(n)
    Pour i ← 2 À n Faire
        F3 ← F2 + F1
        F1 ← F2 # On garde les valeurs précédentes
        F2 ← F3 # On garde les valeurs précédentes
    FinPour
    ECRIRE("Le ", n, "ième terme de la suite de Fibo est : ", F3)
FIN

Approche récursive pour Fibonacci :

Fonction FiboRecursif(n :Entier) :Entier
DEBUT
    SI (n == 0) ALORS
        Retourner 0
    SINON
        SI (n == 1) ALORS
            Retourner 1
        SINON
            Retourner FiboRecursif(n-1) + FiboRecursif(n-2)
        FINSI
    FINSI
FIN

Exemple : Somme de nombres de 1 à n

Fonction SommeRecursif(n :Entier) :Entier
DEBUT
    SI (n > 0) ALORS
        Retourner (SommeRecursif(n-1) + n)
    SINON
        Retourner 0
    FINSI
FIN

Exemple de trace pour Somme(5) :

• Somme(5) = Somme(4) + 5

• Somme(5) = (Somme(3) + 4) + 5

• Somme(5) = ((Somme(2) + 3) + 4) + 5

• Somme(5) = (((Somme(1) + 2) + 3) + 4) + 5

• Somme(5) = ((((Somme(0) + 1) + 2) + 3) + 4) + 5

• Somme(5) = (((((0) + 1) + 2) + 3) + 4) + 5

• Somme(5) = 1 + 2 + 3 + 4 + 5 = 15

Les tableaux

Un tableau est un ensemble de valeurs du même type, portant le même nom de variable et repérées par un indice.

Exemple de tableau (Tab) :

L'indice est le nombre qui permet de repérer chaque valeur dans le tableau. Pour accéder à un élément, on utilise NomDuTableau[indice]. Par exemple, Tab[5] vaut 2 (le 6ème élément si l'indexation commence à 0).

Les indices d'un tableau commencent par 0 dans ce cours (comme Python et C), mais peuvent commencer par 1 dans d'autres langages.

Déclaration d'un tableau

Un tableau est déclaré pour contenir des valeurs de même type (entier, réel, chaîne, caractère...).

La syntaxe est : NomDuTableau : Tableau[taille] De Type_des_valeurs.

Exemple :

Tab : Tableau[11] De Entier # Tableau de 11 entiers

Pour accéder à un élément d'un tableau, il suffit de connaître son indice. Ex: Tab[5] pour le 6ème élément.

Les tableaux dynamiques

Lorsque le nombre d'éléments d'un tableau n'est pas connu à l'avance, on peut utiliser des tableaux dynamiques pour

éviter le gaspillage de mémoire.

On déclare le tableau sans taille fixe, puis on utilise une instruction de redimensionnement (ex: Redim) pour lui attribuer une taille pendant l'exécution.

Syntaxe :

NomDuTableau : Tableau[] De Type_des_valeurs
LIRE(n)
Redim NomDuTableau[n-1] # n-1 pour une indexation à partir de 0

Important : Un tableau n'est utilisable qu'après avoir précisé son nombre d'éléments, par déclaration statique ou redimensionnement dynamique.

Les opérations sur les tableaux

Remplir un tableau

Consiste à stocker des valeurs dans un tableau. On peut par exemple le remplir avec les 20 premiers termes de la suite de Fibonacci.

Procedure RemplirTabFibo(Tab :Tableau[19] De Entier)
VAR i : Entier
DEBUT
    Tab[0] ← 0
    Tab[1] ← 1 # Correction : F1 devrait être Fibo(1) qui est 1. La source utilise 'F1' alors que F1 n'est pas déclaré comme ça.
    Pour i ← 2 À 19 Faire
        Tab[i] ← Tab[i-1] + Tab[i-2] # Stockage de F3 dans le tableau Tab
    FinPour
FIN

Affichage des éléments d'un tableau

Parcourir le tableau et afficher chaque valeur. La boucle Pour est souvent utilisée car le nombre d'opérations est fini.

Procedure AfficheTab(Tab :Tableau[N] De Entier)
VAR i : Entier
DEBUT
    ECRIRE("Les éléments du tableau sont : ")
    Pour i ← 0 À N-1 Faire
        ECRIRE(Tab[i]) # On affiche l'élément i
    FinPour
FIN

Maximum et minimum d'un tableau

Trouver les valeurs maximale et minimale dans un tableau.

Première approche : Parcours et comparaison

Procedure MaxMinTab(Tab :Tableau[N] De Entier)
VAR Max, Min, i : Entier
DEBUT
    Max ← Tab[0]
    Min ← Tab[0]
    Pour i ← 1 À N-1 Faire # Commencer par 1 car Tab[0] est déjà utilisé pour l'initialisation
        SI (Tab[i] < Min) ALORS
            Min ← Tab[i]
        FINSI
        SI (Tab[i] > Max) ALORS # Correction : le test était Tab[0]>Max au lieu de Tab[i]>Max
            Max ← Tab[i]
        FINSI
    FinPour
    ECRIRE("Le maximum est : ", Max, " Et le minimum est : ", Min)
FIN

La seconde approche consiste à trier le tableau d'abord, puis à récupérer les extrémums aux début et fin du tableau.

Trier un tableau

Il existe plusieurs algorithmes de tri. L'un des plus simples est le tri à bulles.

Le tri à Bulle

Il parcourt le tableau, compare les éléments successifs et les échange s'ils ne sont pas dans le bon ordre. Cette opération est répétée jusqu'à ce qu'aucun échange n'ait lieu durant un parcours complet, indiquant que le tableau est trié.

Procedure TriBulle(Tab :Tableau[n] De Entier)
VAR i, Temp : Entier
    Changement : Booleen
DEBUT
    Changement ← Vrai
    TantQue (Changement == Vrai) Faire
        Changement ← Faux
        Pour i ← 0 À n - 2 Faire # jusqu'à n-2 car on compare Tab[i] et Tab[i+1]
            SI (Tab[i] > Tab[i + 1]) ALORS
                Temp ← Tab[i]
                Tab[i] ← Tab[i + 1]
                Tab[i + 1] ← Temp
                Changement ← Vrai
            FINSI
        FinPour
    FinTantQue
FIN

Autres algorithmes de tri : tri stupide, tri de Shell, tri par tas, tri introso, tri à peigne, tri rapide, tri par insertion, tri par sélection, tri par fusion, tri cocktail, tri pair-impair.

Les chaînes de caractères

Une chaîne de caractères est une séquence de caractères ASCII. Les ordinateurs stockent tous les caractères sous forme numérique (code ASCII).

Définition

Les chaînes de caractères sont des assemblages de lettres et de chiffres.

Déclaration

Elles peuvent être déclarées avec ou sans taille fixe.

MaChaine : Chaine # MaChaine peut contenir une taille quelconque de caractères
Ou
MaChaine[10]: Chaine # MaChaine peut contenir 10 caractères maximum

Exemple d'affectation :

MaChaine ← 'Bonjour'

Accès aux caractères : comme pour les tableaux, avec des indices.

ECRIRE(MaChaine[0]) # Affiche 'B'
ECRIRE(MaChaine[6]) # Affiche 'r'

Les opérations sur les chaînes

• Extraction :

  • Un caractère à la position i : MaChaine[i]

  • Plusieurs caractères (sous-chaîne) :

    • Du caractère i au caractère j (exclus) : MaChaine[i:j]

    • Du premier au j^ème caractère : MaChaine[:j]

    • À partir du i^ème caractère jusqu'à la fin : MaChaine[i:]

• Concaténation :

  • Combiner des chaînes avec l'opérateur +.

    • MaChaine + ' Tout le monde !' → 'Bonjour Tout le monde !'

    • MaChaine3 ← MaChaine1 + MaChaine2

• Taille :

  • La fonction len() renvoie la longueur de la chaîne.

    • len(MaChaine) # Renvoie 7 pour 'Bonjour'

Les enregistrements

Contrairement aux tableaux (éléments de même type), les enregistrements sont des structures de données dont les éléments (champs) peuvent être de types différents mais se rapportent à la même entité sémantique (ex: une personne avec Nom, Prénoms, Âge).

Déclaration d'un type structuré

Avant de déclarer une variable d'enregistrement, il faut définir son type, c'est-à-dire le nom et le type de ses champs. Ce type est appelé type structuré (ou parfois "structure" ou "objet").

Les types structurés sont définis dans une section Type, qui précède la section Var.

Syntaxe :

Type
    Structure NomType
        NomChamp1: TypeChamp1
        ...
        NomChampN: TypeChampN
    FinStruct

Exemple :

Type
    Structure Personne
        Nom    : Chaine
        Prenoms: Chaine
        Age    : Entier
    FinStruct

Déclaration d'un enregistrement à partir d'un type structuré

Une fois le type structuré défini, on déclare des variables d'enregistrement comme n'importe quelle autre variable.

Syntaxe :

Var NomVariable:TypeStructuré

Exemple :

Var Pers1, Pers2, Pers3 : Personne

Représentation d'une variable d'enregistrement (ex: Pers1) :

Manipulation d'un enregistrement

Un enregistrement est manipulé via ses champs. On ne peut pas manipuler un enregistrement globalement, sauf pour l'affecter à un autre enregistrement de même type ou le passer en paramètre. Pour afficher un enregistrement, il faut afficher ses champs un par un.

Accès aux champs d'enregistrement :

Les champs sont accessibles par leur nom, en utilisant l'opérateur point (.).

NomEnregistrement.NomChamp

Exemple :

SonAge ← Pers1.Age # SonAge vaut 12

La lecture se fait de droite à gauche : l'âge de la personne 1. Attention : le nom d'un champ est toujours précédé du nom de l'enregistrement auquel il appartient.

Exemple : Enregistrement d'étudiants

Algorithme EnregistrementEtudiant
# Déclaration de la structure
Type
    Structure Etudiant
        Nom     : Chaine
        Prenoms : Chaine
        Sexe    : Caractere # (M ou F)
        Age     : Entier
    FinStruct
Var
    Tab  : Tableau[] : De Etudiant
    Etud : Etudiant
    i, N : Entier
Debut
    ECRIRE("Entrez le nombre d'étudiants SVP : ")
    LIRE(N)
    Redim Tab[N]
    Pour i ← 0 À N-1 Faire
        ECRIRE("Entrez l'étudiant N°", i+1, " Svp : ")
        ECRIRE("Nom : ")
        LIRE(Etud.Nom) # Enregistrement du champ Nom
        ECRIRE("Prénoms : ")
        LIRE(Etud.Prenoms) # Enregistrement du champ Prenoms
        ECRIRE("Age : ")
        LIRE(Etud.Age) # Enregistrement du champ Age
        ECRIRE("Sexe(M ou F) : ")
        LIRE(Etud.Sexe) # Enregistrement du champ Sexe
        Tab[i] ← Etud
    FinPour
FIN # Fin de l'algorithme, pas FinProcedure

Un enregistrement comme champ d'une structure

Un type structuré peut être utilisé comme type pour des champs d'un autre type structuré (imbrication de structures).

Exemple : Date de naissance dans une structure Personne

Type
    Structure LaDate
        Jour  : Entier
        Mois  : Chaîne
        Annee : Entier
    FinStruct

Structure Personne
    Nom       : Chaine
    DtNaissance : LaDate # La structure LaDate est un champ ici
FinStruct

Pour accéder à un champ d'une structure imbriquée, on utilise l'opérateur point plusieurs fois.

Var
    Pers1 : Personne
    Annee_de_Naissance ← Pers1.DtNaissance.Annee

Lecture : l'année de la date de naissance de la personne 1.

Les tableaux d'enregistrements (ou tables)

Pour traiter un groupe de plusieurs enregistrements (ex: un groupe d'étudiants), on utilise un tableau d'enregistrements, aussi appelé "table".

Type
    Structure Etudiant
        Nom     : Chaine
        Prenoms : Chaine
        Sexe    : Caractere # (M ou F)
        Age     : Entier
    FinStruct

Tab : Tableau[N] : De Etudiant # Tableau d'enregistrements de type Etudiant

Représentation d'un tableau d'enregistrements :

Pour accéder au nom du quatrième étudiant dans ce tableau, on écrira : Tab[3].Nom.

Récapitulatif des boucles :