Les Algorithmes
I/ notion générale
Phase d’élaboration d’un programme
Pour trouver une solution informatique qui a un problème pose le concepteur élabore cette solution en passant par les phases suivantes :
phase d’analyse
phase de spécification
phase de traduction
phase d’exécution
Phase d’analyse
Un problème est donné ou posé par son énoncé sous d’écrit ou de parole. Donc il est exprimé dans un langage évolué (humain) non précis. La phase d’analyse consiste à élaborer un model conceptuel d’analyse a partir de l’énoncé du problème sous forme d’une suite d’action et d’étapes. Deux méthodes se présentent pour obtenir le model d’analyse.
méthode ascendante : le concepteur compose la solution du problème a partir d’une boite a outils (algorithme élémentaire), il maîtrise la solution a partir de son expérience et de l’utilisation fréquente de l’outil.
SP = sous problème
PROBLEME POSE
SP1, 2
SP3
SP1
Méthode descendante : elle consiste a subdiviser le problème posé en sous problème. La subdivision se continue jusqu'à avoir des sous problème a solution facile ou connue. On obtient un arbre hiérarchisé en niveau de difficulté
Problème poser
SP
SP
SP
sp
sp
sp
sp
sp
sp
Feuilles de l’arbre
EXEMPLE 1 : Elaborer un modèle d’analyse pour la préparation d’une omelette
Exercice 2 : Un étudiant passe un examen de 3 matières a coefficient unitaire. Elaborer un model conceptuel d’analyse permettant le calcul de la moyenne de l’examen ?
Exercice d’application :
Exos 1 :
Elaborer un model d’analyse permettant la transformation d’un temps exprimé en heure, minutes et secondes en un temps total de seconde.
Exos 2 :
Elaborer le model d’analyse réalisant le travail inverse de l’exos 1.
Exos 3 :
UN employé est rémunère en fonction du nombre de jours travaillés avec une indemnité journalière. Il perçoit en plus 0.5% du bénéfice mensuel de l’entreprise. Elaborer le model d’analyse pour calculer le salaire mensuel.
Exos 4 :
Je dispose chez moi d’une connection a 512kbits/s. Elaborer le model d’analyse permettant le calcul du temps (exprimé en heure, min, sec) de téléchargement exprimé en méga octets.
Phase de spécification
Le model d’analyse décrit la solution avec des termes non informatique (non précis). Il approche la solution avec un niveau sémantique vague. Et donc ne pas être considère comme outil de programmation machine. La phase de spécification permet la description du model d’analyse avec des termes informatique liés au formalise algorithme facilitant le passage au programmes utilisables sur machine. L écriture d’un algorithme suit une syntaxe bien définie pour permettre la communication entre les concepteurs de programmes.
Langage humain
Analyse + spécification
Langage algorithmique
Traduction
Langage évolué (C, pascal, VB…)
Exécution
Langage machine binaire.
la phase de traduction
l’exploitation d’un algorithme une fois écrit sur machine nécessite sa traduction (ou codage) dans un langage évolué compréhensible par la machine (exemple : langage C, VB, C++, Java …)
Algorithme
Traduction
Programme
Librairie du langage
Algorithme
Traduction
Programme
Librairie du langage
Exemple
Algorithme | Langage C | Langage Pascal
Afficher (« votre prix ») | Printf (« votre prix ») | writeln (« votre prix »)
Lire (« votre prix ») | scanf (%d, « &prix ») | readln (prix)
phase d’execuction
l’exécution d’un programme passe par les étapes suivantes
Programme sur papier
Edition de texte
Fichier source
compilation
Erreur
Correction erreur
Editions des liens
Fichiers objets
Exécutions
Résultat
Librairie langage
Programme sur papier
Edition de texte
Fichier source
compilation
Erreur
Correction erreur
Editions des liens
Fichiers objets
Exécutions
Résultat
Librairie langage
édition de texte : c’est la saisie du programme dans un éditeur de texte. le fichier est sauvegarder avec une extension du langage de programmation : .c ; .cpp ; .pas.
éditions compilation : c'est la recherche des éventuelles erreurs syntaxiques ou sémantique commise dans le programme source ne respectant pas le formalise du langage utilisé.
Exemple : oublie de point virgule, non déclaration de variable, utlisation frauduleuse de type…
éditions de liens : l’écriture d’un programme nécessite l’utilisation d’une série de fonction prédéfinie dans un langage de programmation. l’éditions de lien permet d’insérer les codes des ces fonctions dans le programme source.
Exécution : l’éditions de lien donne un fichier exécutable qui lui fournissant des données nécessaires, gênera des résultats attendus (EXE)
Syntaxe générale
Un algorithme est écrit par un nom, une partie déclaration, et un corps. La partie déclaration sert à définir les objets de données de l’algorithme. Le corps de l’algorithme rassemble les instructions qui doivent être exécutés sur les objets.
Syntaxe
Algo : Nom_algorithme
Decalartion
Objet de données
Début
Instructions
Fin nom_algorithme
Algo : Nom_algorithme
Decalartion
Objet de données
Début
Instructions
Fin nom_algorithme
Nom de l’algorithme : c’est un identifiant, composé d’une suite de lettre, chiffre et le caractère «_ »
Exemple : calcul_moyenne
Tous les mots clés du langage algorithmique doivent être souligné : algo, declaration, si, alors …
Les commentaires : pour documenter l’algorithme ou explicité le rôle des variables ou des étapes de traitement on insérera des commentaires. Le commentaire est insère entre deux accolades et peut se tenir sur plusieurs lignes
Exemple : {ce ci est un commentaire}
objet de donnée et type
un objet de donnée est défini par son nom, son type, son utilisation et sa nature.
nom : c’est un identificateur (suite de lettre, chiffre et « _ ». il ne faut pas utiliser des blancs ou des symboles (« » ; {}, -)
exemple : prix_ht ; prix_2004
le type : définie l’ensemble des valeurs que prend l’objet. Type entier, réel, caractères, chaîne et booléen.
Un caractère est une lettre, un chiffre, ou un symbole.
Une chaîne est une suite finie de caractères.
Booléen: deux valeurs (vrai ou faux)
L’utilisation : un objet peut être utilisé sous forme de :
donnée ou entrée : reçu par l’algorithme pour réaliser le traitement.
Sortie ou résultat : fourni par l’algorithme à son environnement (utilisateur).
Intermédiaire : objet servant pour les calculs intermédiaire non visible à l’utilisateur.
Algorithme
entrée
intermédiaire
Sortie
Algorithme
entrée
intermédiaire
Sortie
la nature : un objet qui change de contenue est appelé variable, sa déclaration suit la syntaxe suivante :
nom_variable : type
exemple : i : entier
prix : réel
nom : chaîne
trouve : booléen
un objet qui ne change pas de contenu est appelé une constante :
constante nom_variable : valeur
exemple : constante TVA = 19.6
max = 15
nom_usine = « Perrier »
Entrée / Sortie
entrée : pour saisir une donnée et affecter à une variable on utilise l’une des fonctions prédéfinie lire ou saisir.
Syntaxe :
Lire (nom_variable)
Saisir (nom_variable)
Lire (nom_variable_1, nom_variable_2,…)
sortie : pour afficher à l’écran un texte, message ou le contenue d’une variable on utilise les fonctions prédéfinie écrire ou afficher.
Syntaxe :
Afficher (« texte »)
Ecrire (« nom_variable »)
Afficher (nom_variable, « texte »,…)
exemples
Nb : l’écriture des algos a été testée avec le logiciel alg exec
Ecrire un algorithme qui permet de saisir un temps exprimer en heure, minute, seconde et fourni un total en seconde
Ecrire l’algo inverse du précèdent
Calcul salaire :
D’après le cours pour changer un peu !
Algo : calcul_salaire
4572009842500Déclaration
Nbre_jours, ind_j, benf, salaire : réel
Début
4572002286000 Afficher (« nombre de jours ? »)
Lire (Nbre_jours)
Afficher (« indemnité »)
Lire (ind_j)
Afficher (« quel est le bénéfice »)
Lire (benf)
Salairenbre_jours, * ind_j + 0.005 * benf
Afficher (« le salaire mensuel est de : », salaire)
Fin calcul_salaire
Téléchargement
Algo : temps_telechargement
Déclaration
Taille_fichier, débit, conv, temps, heure, reste, min, sec : entier
Début
Afficher (« taille du fichier en Mo : »)
Lire (taille_fichier)
Afficher (« débit »)
Lire (débit)
Conver taille_fichier * 1024 * 8
Temps conv /débit
Heure temps /3600
Restetemps – heure * 3600
Min reste /60
Sec reste - min * 60
Afficher (« temps de téléchargement : », heure, min, sec)
fin temps_telechargement
L’affectation
Pour affecter une valeur à une variable on utilise le signe « »
Ex : nom_variable expression
L’ancien contenu de la variable est écrasé avec la nouvelle valeur.
A différencie écriture informatique et les écritures mathématique.
Informatique | Mathématique
x x + 5 | x = x +5 (impossible)
A différencier entre affectation et = test d’égalité
x y | x = y
x va recevoir la valeur y si x est égale a y ?
Dans les langages évolués
Langage C
Pascal
Algorithme
Affectation
=
: =
Test d’égalité
= =
=
=
Il ne faut pas utiliser le signe « » pour l’affectation
(Ne pas faire) 5 y | (faire) y 5
Les opérations :
les opérations arithmétiques :
Opérateurs
Désignations
Exemples
+
Plus unitaire
+ x
-
Moins unitaire
- x
+
Addition
x + y
-
Soustraction
x – y
*
Multiplication
x * y
/
Divisions sans reste
x /y
%div
Division avec reste
x div y x%y
% mod
Reste de la division
x mod y x%y
Exemple :
5/3 = 1.666…. division sans reste
5 div 3 = 1
5 mod 3 = 2
Opérateur de test
Opérateurs
Désignations
Exemples
=
Test d’égalité
x = y
Différent de
x = y
>
Supérieur à
x > y
>=
Supérieur ou égale
x >= y
<
Inférieur à
x < y
<=
Inférieur ou égale
x <= y
Opérateur logique
Opérateurs
Désignation
Exemple
Non
Négation
Non(x)
Et
Et logique
x Et y
Ou
Ou logique inclusif
X ou y
X et Y sont des variables booléens.
Table de vérité
X et y sont des variables booléens : vrai ou faux
Non : négation
X
Non(x)
Vrai
Faux
Faux
vrai
Et logique : il est vrai si les variables sont vrai
X
Y
X et Y
Faux
Faux
Faux
Faux
Vrai
Faux
Vrai
Faux
Faux
Vrai
Vrai
Vrai
Ou inclusif : il est vrai que si l’une au moins des variables est vrai
X
Y
X Ou Y
Faux
Faux
Faut
Faux
Vrai
Vrai
Vrai
Faux
Vrai
Vrai
Vrai
vrai
Séries d’exos :
Exercices 1 : un employé surveille le fonctionnement d’un moteur en relevant des temps exprimés en heure, minutes et secondes. Ecrire un algorithme lui permettant de faire sommer deux temps.
Algo : somme_temps
Declaration:
H1, h2, h, m1, m2, m, s1, s2, s: entier
Debut:
Afficher (“temps1”)
Lire (h1, m1, s1)
Afficher (« temps2 »)
Lire (h2, m2, s2)
S (s1+s2) % 60
M m1 + m2 + (s1+s2/div60) %60
H h1 + h2 + (m1 + m2 + (s1+s2/div60) div60
Afficher (“la somme des temps est :”h, m, s)
Fin : somme_temps
Exos 2 : écrire un algorithme qui permet un nombre de jour et une date exprimée en jour, année et siècle et réalise leur somme.
Alglo : temps
Déclaration
Siècle, jour, année, nbr_j : entier
Siecle_result, année_result, jour_result : entier
Début :
Afficher (« donner la date »)
Lire (siècle, année, jour)
Afficher (« le nombre de Jour »)
Lire (nbr_j)
J jour + nbr_j mod 365
A année + (jour +nbr_j div 365) mod 100
S siècle + (année + (jour + nbr_ j)/365) div 100
Afficher (« le résultat : »s « ; » a « ; » j)
Fin : temps
II) les structures de contrôle
l’alternative simple
Syntaxe : Si condition
Alors instruction
Fin Si
L’alternative simple permet d’exécuter une instruction (ou plusieurs) instruction si une condition est vérifié. L’instruction (ou bloc d’instructions) simplement sauté si la condition n’est pas vérifiée.
La condition est une expression booléenne simple ou composée avec des opérateurs logiques (Et, Ou, Non)
Représentation en organigramme
285750063500Faux /non
Condition
Oui / vrai
Instructions
Faux /non
Condition
Oui / vrai
Instructions
Exemple :
Condition simple
Si prix < 100
Alors afficher (« prix raisonnable »)
Fin Si
Condition composée
Si moyenne < 0 ou moyenne > 20
Alors afficher (« moyenne erronée »)
Fin Si
l’alternative double
Syntaxe : Si condition
Alors instruction 1
Sinon instruction 2
Fin Si
La première instruction (ou bloc) est exécutée si la condition est vrai (vérifiée). Dans le cas contraires les c’est la 2eme instruction qui est exécutée. L’exécution est exécutive, l’une des instructions qui est exécutée a la fin.
Représentation organigramme :
Instruction 2
Instruction 1
Condition
Faux/non
Oui/non
Instruction 2
Instruction 1
Condition
Faux/non
Oui/non
Remarque : le « sinon » exprime la négociation de la condition, il n’y a pas lieu de rester le cas contraire.
Exemple :
Si moyenne>=10
Alors afficher (« élève admit »)
Sinon afficher (« élève recalé »)
Fin Si
Si prix>0
Alors prix_ttc prix *1.196
Afficher (« prix TTC est : », prix_ttc)
Sinon afficher (« erreur de saisie »)
Fin Si
Imbrication d’alternative
Dans certains cas de résolution de problème on peu être amenée a imbriqué des alternatives simple ou doubles. Il faut veiller à respecter la syntaxe.
a chaque si un alors et fin si sont obligatoire.
Un sinon ne peut être entame que si un Si est ouvert au préalable
Deux schémas qui se pressentent :
Si condition1
Alors si condition 2
Alors si condition 3
Alors….
Sinon instruction
Fin si
Sinon instruction
Fin si
Fin si
Si condition 1
Alors instruction 1
Sinon si condition 2
Alors instruction
Sinon si …
Fin si
Fin si
Fin si
Exemple : teste deux nombre a, b
Si a>b
Alors Afficher (a, « est plus grand », b)
Sinon Si a