Livre à fractionnerlink={{{link}}}

Il a été suggéré de fractionner ce livre en plusieurs sous-pages afin d'améliorer sa lisibilité.

Le but de ce cours est d'étudier comment on peut résoudre un problème en utilisant le Langage de Description des Algorithmes suivant l'approche Bertini et Tallineau. Il va donc falloir étudier les principes fondamentaux de la programmation, base valable quel que soit le langage utilisé.

Pour pouvoir résoudre un problème et transposer la solution sur ordinateur, il est nécessaire de passer par différentes étapes. Dans un premier temps, il va falloir effectuer une analyse du problème. Lorsque cette analyse est terminée, il faut l'adapter à l'ordinateur en traduisant l'analyse en une suite d'actions plus ou moins élémentaires.

L'algorithme

modifier

Un algorithme est un ensemble de règles opératoires propres à un calcul ou l'enchaînement des actions nécessaires à l'accomplissement d'une tâche. Un algorithme est un procédé reprenant un ensemble de suites élémentaires d'actions à exécuter afin de résoudre un problème à partir des données de départ et d'arriver à un résultat final déterminé. L'algorithme est indépendant des langages de programmation : si vous prenez une méthode de tri d'un tableau, par exemple le tri bulle, vous pouvez l'écrire dans la plupart des langages de programmation usuels. L'algorithmique va donc s'attacher à l'étude de différentes méthodes permettant de résoudre un problème donné sans tenir compte des particularités de tel ou tel langage de programmation. À ce titre l'algorithmique se veut universelle.
Le schéma usuel de résolution d'un problème sera donc :
Problème à résoudre (Données à traiter) --> Algorithme --> Implémentation dans un langage de programmation ->Résultat final
Il est possible de décrire un algorithme de différente manière :

  • Représentation grâce aux arbres programmatiques.
  • LDA : Langage descriptif des algorithmes.

Il n'existe pas hélas de langages de description des algorithmes universellement reconnus. Nous proposerons ici une syntaxe particulière, qui ressemble aux langages algorithmiques usuellement utilisés.

Analyse du problème

modifier

Avant de résoudre un problème, il faut l'analyser avec précision. Cette réflexion passe par certaines étapes incontournables :

  • Définition du problème :

On ne peut pas résoudre un problème si on ne l'a pas défini précisément ! Il faut donc fixer le plus clairement possible les différentes fonctionnalités du programme.

  • Spécification des résultats :

Il faut définir les différentes étapes de notre programme depuis la saisie des données jusqu'à l'affichage du résultat. On peut définir un prototype qui décrira point par point comment doit fonctionner notre programme.

  • Définition des données de base :

Avant de résoudre le problème, il faut définir la nature des différentes données que manipulera notre programme.

  • Analyses des données :

Il faut définir ici quelles sont les données au point de départ et quelles données doivent être sauvegardées.

  • Recherche d'une solution :

C'est la phase technique où il faut proposer une méthode pratique permettant de résoudre notre problème.

Les arbres programmatiques (AP)

modifier

Cette méthode permet de représenter en arbre structuré les différents algorithmes du programme. Le programme (racine de l'arbre) peut se décomposer en sous-programmes (sous niveaux) toujours organisés en deux parties:

  • Les Déclarations (variables et constantes - DONNEES)
  • Les Instructions (traitements sur les données - OPERATIONS)

Les AP structurent le programme qui comprend :

  • Variables
  • Tests
  • Répétitives

Le test fait l'objet d'un nœud en fonction d'une condition booléenne (True/False).

  • La structure permet de distribuer le travail.
Struct=#Noeud+#Racine
  • Le traitement comprends les instructions.
Traitements=#Feuilles

D- : Début // F- : Fin // T : Traitement // I : Instruction intermédiaire

Au niveau 0, le programme (prg) est ici initialisé de droite à gauche entre les blocs de début (D-Prog) et de fin (F-Prog) et se hiérarchise en sous prg et itérations en descendant dans les niveaux (couches). AP définit la structure logique du programme et l'ordre d’exécution des traitements. On instruit les feuilles de haut en bas (Niveau 0 -> ...) et de droite à gauche.

On a donc :

  • STRUCTURE
Prog
T1
T4
T5
T7
  • TRAITEMENT:
D-T1
D-T5
D-T7
T9
F-T7
T8
F-T5
F-T1
T2
I1
T3
D-T4
T6
F-T4
F-Prog

LES DECLARATIONS

modifier

Tout algorithme comprend deux parties :

  • une partie déclaration
  • une partie instruction
Bloc
 - declaration
 - instruction
FBloc

Un algorithme va utiliser des variables. Une variable peut être vue comme une zone mémoire réservée permettant de stocker une valeur. Toute variable utilisé dans la partie « instruction » de l'algorithme doit faire l'objet d'une déclaration préalable. La phase de déclaration doit s'accompagner d'une réflexion sur les données manipulées par notre algorithme. Quelle sera leur nature précise ? Leur valeur sera-t-elle variable ? Loin d'être une contrainte, la phase de déclaration est une aide pour guider le programmeur dans sa réflexion.

Les constantes

modifier

Une constante permet d'attribuer un nom à une valeur ou une expression fixe relativement complexe à retranscrire ou relativement longue. Elle permet également une meilleure lisibilité du code.

La déclaration d'une constante permet une modification simplifiée d'une valeur reprise à maintes reprises au sein du code. L'utilisation des constantes permettra d'améliorer la lisibilité de notre algorithme et sa généralisation.


Déclaration des constantes

modifier

Pour déclarer une constante on utilise le mot réservé CONST. La syntaxe générale de cette déclaration se présente sous la forme :

CONST identificateur = valeur
CONST pi = 3.14
CONST ttl = "Message à afficher régulièrement"
CONST oui=Vrai
CONST résu=pi*2+5*(15+4)

Pour des raisons de facilté il est préférable d'utiliser des noms de constantes plus ou moins courts et représentatifs de leur contenu.

Il est possible d'utiliser des déclarations multiples.

CONST pi=3.14
      ttl="Message à afficher"
      oui=Vrai
      résu=pi*2+5*(5+4)

Les variables

modifier

Une variable est une zone réservée de la mémoire permettant de stocker une valeur. Pour atteindre cette zone mémoire on lui attribue un nom. La valeur ainsi stockée par la variable pourra être modifiée au cours de l’exécution du code. Pour pouvoir réserver la place nécessaire à la valeur, il va falloir déclarer le type du contenu et éventuellement sa taille.

Déclaration

modifier

Pour déclarer une variable on utilise le mot réservé de VAR. La syntaxe générale de cette déclaration se présente sous la forme.

VAR identificateur : type

Identificateur représente le nom que l'on attribue à la variable.

Type permet de spécifier l'ensemble des valeurs dans lequel la valeur de la variable pourra varier. Il permet également de déterminer la dimension de la zone mémoire à réserver et le type d'opérations que pourra supporter la valeur.

On peut classer les différents types en catégories. Ainsi on parle de type primitif, il s'agit d'un type qui existe de fait avec le langage de programmation, il est défini en même temps que le langage. On parle également de type scalaire, il s'agit d'un type qui possède un précédent (hormis la première valeur qui est la plus petite et un suivant hormis la dernière valeur qui est la plus grande) et est représentée ou codée par un entier dans la machine.

Ascii (à chaque char correspond une valeur numérique)
 A=65
 B=66
 ...
 a=97
 b=98
 13->Numérique (1 bit) 
 13->Alphanumérique (2 bits) |1|3| = 49 & 51
 2^16=65536 -> 2 bytes = word
 4 byte=2^32+-4.10^9 -> double word
 8 bytes=2^64
 variable=zone mémoire allouée

Les types de variables

modifier

On dispose de quatre types primitifs, tous ordonnés mais dont 3 sont scalaires et 1 non.

  • Scalaire : on trouve suivant ou précédant (ex. : 5, 6, 7...)
  • Primitif : on trouve le plus petit ou le plus grand (ex. : 5,78 < 19,72)
  • ENTIER (scalaire - primitif) // Var Max : Entier
  • REEL (non scalaire - primitif) // Var Point : Reel
  • CARACTERE (scalaire - primitif) // Var Initiale : Caractère
  • BOOLEEN (scalaire - primitif) // Var Reussi : Booléen
  • ALPHANUMERIQUE (chaine de ¢) // Var Message : Alphanumérique

Premières notions

modifier
  • La lecture

La lecture d'une variable permet à l'utilisateur de saisir une valeur et de la stocker dans une variable.

Var Age : Entier
Entrer Age

Dans cet exemple, l'utilisateur tapera sur le clavier la valeur d'un entier et cette valeur sera stockée dans la variable Age.

  • L'écriture

L'écriture permet d'afficher un message à l'écran à destination de l'utilisateur de l'algorithme.

Ecrire "Texte à afficher"
Ecrire Nom," ",Prenom," ",Age
  • L'affectation

L'affectation permet d'effectuer un calcul et de stocker le résultat de ce calcul dans une variable.

Syntaxe :

identificateur <- expression 

Sémantique :
On commence par évaluer l'expression et on stocke le résultat dans la variable.

Exemple :

Var Valeur : Entier
Valeur<-15
Valeur<-19
Valeur<-Valeur*3
Valeur=19*3
Ecrire Valeur

Exécution de l'algorithme :
Notre programme affiche :
57

  • La concaténation
Voyelle<-'a'
Phrase<-"Voici une voyelle:"
Phrase<-Phrase+Voyelle
Ecrire Phrase
>Voici une voyelle:a
  • Les commentaires

Les commentaires sont des explications destinées à un programmeur qui lit l'algorithme et lui permettent de mieux le comprendre. Un commentaire n’est pas exécuté au cours de l'exécution d’un algorithme.

!Texte du commentaire!

OPERATEURS

modifier
  • Mathématiques
^ puissance
* multiplication
/ division entière
mod modulo
  • Relationnels (booléens)
= < > <= >= <>
  • Logiques
non et ou

exercices

modifier

? Calculez le prix à payer en fonction de la quantité et du prix unitaire sachant que le taux de TVA est de 19 %

? Calculer surface et volume d'une sphère dont le rayon est introduit par l'utilisateur

? Calculer le laps de temps en seconde écoulé entre deux horaires exprimés en heure, en minute et en seconde

? Introduire deux nombres et les permuter

? Introduire 3 nombres et afficher la somme, la différence et le produit

? Introduire une somme en franc belge et la convertir en euro

? Calculer le déterminant d'une équation du second degré

? Introduire une valeur représentant des secondes et les convertir en heure, minutes, secondes

? On désire établir un prg permettant de calculer le nombre de rouleaux de papier peint nécessaire pour tapisser une pièce. Les dimensions d'un rouleau sont de 10m sur 95cm, sachant qu'une porte mesure 2m5 sur 80cm et qu'une fenêtre mesure 1m40 sur 1m. Sachant qu'on estime à 5% les chutes non réutilisables. Etablissez le programme permettant à l'utilisateur d'introduire les dimensions ainsi que le nombre de portes et fenêtres

LES STRUCTURES DE CONTROLE

modifier

Séquence = suite ordonnée d'instructions (nœud ou feuille)


Alternative

modifier
Si condition Alors
 -sequence
Sinon
 -sequence
Fsi
  • Plusieurs branches
Selon que
 condition 1 Faire
  -sequence
 condition 2 Faire
  -sequence
 consition 3 Faire
  -sequence
 autrement Faire
  -sequence
FSelon

On test le contenu d'une variable et en fonction de ses valeurs, dès qu'une condition est réalisée on quitte l'alternative.

exercices

modifier

? Introduire 2 nombres et les afficher dans l'ordre croissant

? Introduire deux horaires en H/M/S et afficher dans l'ordre croissant

? Introduire la date de naissance d'une personne et date actuelle et sortir son age

? En fonction d'un resultat introduit afficher la mention obtenue</>

? On demande d'introduire 2 nombres entiers ainsi qu'un opérateur (+,-,*,/,^,m). Afficher le résultat

Répétitive

modifier
  • Tant que : tant que condition est vrai on entre dans la boucle
≡}Séquence D-TantQue
TantQue [Cond vraie] Faire
 ≡}traitement
FTant
≡}Séquence F-TantQue

ex:

Entrer b
Tantque b=0 Faire
 Ecrire "erreur"
 Entrer b
Ftant
  • Jusque : jusque condition est vrai on entre dans la boucle
≡}Séquence D-Jusque
Jusque [Cond vraie] Faire
 ≡}traitement
FTant
≡}Séquence F-Jusque

ex:

Entrer b
Jusque b=0 Faire
 Ecrire "erreur"
 Entrer b
FJusque
  • Pour : De valeur initiale à valeur finale on entre dans la boucle
Pour [Var] De [val. init] A [val. fin] Pas [val] Faire
 ≡}traitement
FPour

Pas : 1 par défaut, est la valeur d’incrémentation - ex.: de 1 en 1 / de 5 en 5 - ex:

Pour x De 8 A 20 Pas 1 Faire
 Ecrire x
FPour

exercices

modifier

? Afficher table de multiplication de 8

? Calcul de somme, moyenne, min, max d'une série de nombres introduits au clavier. Valeur 0 indiquant la fin de la serie.

? Etablir un tableau reprenant la liste des nombres entre 1 et 20, leur exposant 2 et 3.

LES STRUCTURES COMPOSEES

modifier

Structures consecutives

modifier

 

  • En LDA:
 !Double alternative!
 ≡} D-Trait
 Si c1 Alors
  ≡} T1
 Sinon
  ≡} T2
 FSi
 ≡}I-Trait !(Fin de 1er Si) et (Debut de 2e Si)!
 Si c2 Alors
  ≡} T3
 Sinon
  ≡} T4
 FSi
 ≡} F-Trait
 !Double repetitive!
 ≡} D-Trait
 Tantque c1 Faire
  ≡} T1
 FTant
 ≡} I-Trait
 Jusque c2 Faire
  ≡} T2
 FJusque
 ≡} F-Trait
 !Alternative suivant repetitive!
 ≡} D-Trait
 Jusque c1 Faire
  ≡} T1
 FJusque
 ≡}I-Trait
 Si c2 Alors
  ≡} T2
 Sinon
  ≡} T1
 FSi
 ≡} F-Trait

Structures imbriquées

modifier

 

  • En LDA:
 ! Repetitive de repetitive !
 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Tantque c2 Faire
   ≡} T2
  FTant
  ≡} F-T1
 FTant
 ≡} F-Trait
 ! Repetitive d'alternative !
 ≡} D-Trait
 Si c1 Alors
  ≡} T1
 Sinon
  ≡} D-T2
  Tantque c2 Faire
   ≡} T3
  FTant
  ≡} F-T2
 FSi
 ≡} F-T
 ! Alternative de repetitive !
 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Si c2 Alors
   ≡} T2
  Sinon
   ≡} T3
  FSi
  ≡} F-T1
 FTant
 ≡} F-Trait

Structures multiples

modifier

 

  • En LDA:
 ≡} D-Trait
 Tantque c1 Faire
  ≡} D-T1
  Si c3 Alors
   ≡} D-T4
   Tantque c5 Faire
    ≡} T7
   FTant
   ≡} F-T4
  Sinon
   ≡} T5
  FSi
  ≡} F-T1
 FTant
 ≡} I1
 Si c2 Alors
  ≡} T2
 Sinon
  ≡} D-T3
  Tantque c4 Faire
   ≡} D-T6
  FTant
  ≡} F-T3
 FSi
 ≡} F-Trait

exercices

modifier

? Additionner tous les nombres pairs entre 2 nombres introduits par l'utilisateur

LES TABLEAUX

modifier

Ensemble de valeurs

Unidimensionnel

modifier

Dans un VECTEUR de X : Type

Multidimensionnel

modifier

Dans une MATRICE de X * X : Type

Programme permettant de permuter les valeurs d'une matrice carrée de 10 selon sa diagonale principale

LES SOUS-PROGRAMMES

modifier

Ensemble nommé d'instructions paramétrable et appelable.

Procédures

modifier

Sans sortie:

Proc nom1(param1 : Type, param2 : Type)
  ...
FProc

Fonctions

modifier

Avec sortie.

? faire une fonction qui retourne le carre d'un nombre

LA RECURSIVITE

modifier

La récursivité consiste en une procédure ou une fonction faisant appel à elle même.

exercices

modifier

? Ecrire une fonction récursive permettant de trouver la valeur d'un élément du triangle de pascal connaissant sa position

? Ecrire une procédure permettant de convertir une valeur décimale en une valeur binaire et une procédure convertissant une valeur décimale en une valeur hexadécimale

LES TRIS

modifier

Réorganisation de données

  • Par insertion
  • A bulle
  • Hybrides
  • Par selection
  • Par comptage

LES ENREGISTREMENTS

modifier

Un enregistrement permet de regrouper sous un identificateur commun des variables de types différents

? Faire une fiche personnelle

LES POINTEURS

modifier

Les pointeurs sont des directeurs de gestion d'allocations.

Les listes à simple chaînage

modifier

Structure de données linéaires unidirectionnelles

Les listes à double chaînage

modifier

Structure de données linéaires bidirectionnelles

Les arbres binaires

modifier

Structures de données non linéaires

? Compter le nombre de feuilles et sommets d'un AB

LES FICHIERS

modifier

Piles stockées

Sequentiels

modifier

Stockage de données

Acces Directs

modifier

Stockage d'enregistrements

Exercices

modifier

? Soit un FAD et un FS contenant des infos similaires on demande de créer un nouveau FAD fusionnant alternativement les enregistrements des 2 fichiers

Liens externes

modifier
http://www.ac-nancy-metz.fr/eco-gestion/eric_crepin/accueil.htm
http://www-id.imag.fr/Laboratoire/Membres/Legrand_Arnaud//Teaching/Algo-DEUG-02/Cours/node1.html