Cours Algorithme (Codage,Analyse)

Sommaire :

CHAPITRE  I   :    CODAGE DE L’INFORMATION

1- Introduction 

 2- Capacité Mémoire 

 3- Langage et Traducteurs 

 4- Phase de la programmation 

CHAPITRE  II : ANALYSE SEQUENTIELLE

1-  Introduction 

2-  Exemple d’analyse séquentielle :

3- Variable et type de variable 

4- Instructions algorithmique

5- Règles de priorité et d’affectation

6- Algorithme

7- Exercices

CHAPITRE  I : CODAGE DE L’INFORMATION

 1- Introduction :

Passage de base 2 à base 10

          Exemple : (1101) = ( .. )₁₀

1   1   0   1

         *

2³   2²  2¹  2⁰

^{-----------------------------}

8 + 4 +0 + 1 = 13          Donc ( 1101 ) ₂   =  ( 13 ) ₁₀

Pour convertir un nombre de la base 2 à la base 10, on multiplie à partir de la droite chacun de ces chiffres par une puissance de 2 successives à partir de 0. Le résultat recherché est obtenu en effectuant la somme des produits précédents.

          Application :

(10110101) = (181)₁₀

2- Capacité Mémoire :

           

2.1- Notion de la table ASCII :

L’information est stockée au niveau de la mémoire caractère par caractère. Or, l’ordinateur étant une machine binaire, chaque caractère doit être stocké sous forme de 0 ou de 1. Pour cela, on a répertorié une liste de 256 caractères. A chaque caractère on a attribué un code décimal, par conséquent, un code binaire. Cette table est appelée Table ASCII et elle a la forme suivante :

1 bit   = 1 ou 0

8 bits  = 1 Octet

D’après la table précédente, chaque caractère est donc représenté par un ensemble de 8 bits 1 ( 1 bit = 0 ou 0 ). Cet ensemble de 8 bits est appelé un Octet ( byte).

L’unité de mesure de la capacité est par conséquent l’Octet.

            2.2- Autres unités de mésures :

1 Kilooctet  = 1 Ko = 1024 octets » 10³ octets

1 Migaoctet = 1 Mo = 1024 Ko  » 10⁶ octets

1 Gigaoctet = 1 Go = 1024 Mo  » 10⁹ octets

               Exemple de Capacité Mémoire :

Disquette HD             : 1.44 Mo

CD                              : 650 Mo

Disque Dure               : 10 Go

Mémoire Centrale       : 64 Mo

            2.3- Mode de Stockage d’un caractère :

Une disquette contient un disque plastifié dont la surface est recouverte couche magnétique. Chaque point de la disquette peut être magnétisé ou non, ce qui permet de représenter une valeur binaire ( 1 ou 2 ).

Pour stocker un caractère représenté par 8 bits, l’ordinateur considère 8 petits segments sur la disquette qu’il magnétise ou non selon la valeurs du bit dont l’octet représentant le caractère.

Exemple :Stockage de la lettre « A » sur disquette :

A → 65 → 01000001

                              

Application :

                        Stockez le mot «  ISTA »

3- Langage et Traducteurs :

3.1-  Les langages Informatiques :

On distingue 2 catégories de langages.

a - Langage Machine :

Ce sont des langages utilisant des mots formés uniquement de 0 et de 1. Ces langages ont l’avantage d’être compréhensible par la machine et le fonctionnement interne de la machine.

Ils sont néanmoins, utilisés par des programmes nécessitant des exécutions rapides.

b - Langage Evolué :

Dans le but de faciliter l’accès de l’Informatique à un plus grand nombre de personne, on a été amené à créer des langages dont les mots sont proches d’une langue parlée (Souvent Anglais).

 Ces langages présentent l’avantage d’être universels dans la mesure ou ils ne dépendent pas de la machine qui les utilise. Ces langages évolués ont été généralement crée en fonction d’une orientation donnée.

Exemple :

Gestion : Cobol, Access, Dbase, Foxpro …

Calcul Scientifique : Fortron, Algol, Pascal …

Général : Visualbasic, C, …

Enseignement : Qbasic, Pascal, …

Intenet : Html, Java, Asp …

3.2-  Traducteurs :

Tout programme écrit en langage évolué doit être traduit en langage machine afin de pouvoir être exécuté.

On distingue 2 catégories de traducteurs ( programme spécial qui permet le passage du langage évolué vers le langage machine ).

a - Traducteurs : 

Les Interprèteurs permettent de traduire et d’exécuter chaque ligne du programme source, les Interprèteurs sont souvent utilisés dans la mise au point d’un programme.

a - Compilateurs : 

Le programme source est traduit entièrement en langage machine ce qui permet d’obtenir un programme Objet, quant celui-ci est dépourvu d’erreurs, il est alors exécuté.

4- Phase de la programmation :

4.1-  Schéma descriptif : 

4.2-  Les étapes :

Programmer consiste à considérer l’ensemble des étapes suivants :

Etapes d’Analyse : cette étape consiste à élaborer une solution écrite du problème posé. Cette solution doit être décrite sous forme d’instructions exécutables par un ordinateur et disposés dans un ordre logique.

Cette solution est appelée : ALGORITHME.

Cette étape est délicate dont la mesure ou il fait appel à plusieurs éléments à la fois : le raisonnement logique, la connaissance du domaine traité, les règles et les méthodes algorithmiques, l’expérience et également une part d’intuition.

Etape de Traduction : cette étape consiste à réécrire l’algorithme à l’aide d’un langage informatique. Le résultat de cette traduction est appelé un PROGRAMME.

Cette étape ne présente pas généralement beaucoup de difficultés, elle nécessite toutefois une maîtrise du langage informatique choisis.

 

Etape d’Exécution : cette étape consiste à introduire le programme dans la mémoire de l’ordinateur afin qu’il y soit exécuté.

4.3-  Définitions :

On appelle Algorithme un procédé de résolution d’un problème informatique écrit sous forme d’une suite d’instructions disposés dans un ordre logique et exécutables par un ordinateur.

On appelle Programme la traduction d’un algorithme moyennant un langage informatique.

CHAPITRE II : ANALYSE SEQUENTIELLE

 1-  Introduction :

On distingue en informatique 3 types d’analyses :    

v  Analyse séquentielle : dans ce type d’analyse, la solution est décrite sous forme d’une suite d’instructions disposés dans un ordre logique.

v  Analyse répétitive : dans ce type d’analyse, on élabore la répétition d’une même série d’instructions.

v  Analyse conditionnelle : dans ce type d’analyse, la solution comporte une condition qui entraîne 2 possibilités. 

Un algorithme combine le plus souvent les 3 formes d’analyses.

2-  Exemple d’analyse séquentielle :

2.1-  Enoncé :

Calculer et afficher le salaire net d’un employé ayant travaillé NH heures au tarif brut THB sachant que le taux de réduction entre le brut et le net est de 17%.

2.2-  Analyse du problème :

v  Recherche des données de sortie :

SN : salaire net de l’employé

v  Recherche des données d’entrée :

NH : nombre d’heures de travail

THB : tarif horaire brut

TR : taux de réduction

v  Recherche des données de traitement :

SB : salaire brut

SB = NH * THB

MR = SB * 17% ( montant de réduction)

SN = SB – MR

2.3-  Définitions:

     a – On appelle donnée d’entrée une donnée hypothèse de travail fournit toujours par          l’énoncé.Par définition, une donnée d’entrée est une donnée qu’on ne peut pas                  calculer  Une donnée d’entrée peut être chiffrée ou non, dans ce dernier cas, elle est          évaluée au moment de l’exécution du programme par l’ordinateur.

    b - On appelle donnée de sortie une donnée qui est nécessaire de calculer comme             objectif du problème posé.

    c - On appelle donnée de traitement, une donnée calculable à partir des données               d’entrées ou d’autres données de traitement.

    Une donnée de traitement est toujours calculée dans l’objectif d’aboutir à la donnée de       sortie.

2.4-  Approche d’une solution: 

Une solution comporte obligatoirement 3 phases :

       a-    Phase d’entrée : dans cette phase il s’agit de communiquer à l’ordinateur les                 valeurs des données d’entrée.

      b-   Phase de traitement : dans cette phase il s’agit d’élaborer la suite des calculs                 nécessaires à partir des données d’entrées pour aboutir vers les données de                         sorties.L’ordre de calcul doit respecter la règle suivante :« Toute donnée de traitement         à calculer ne peut l’être qu’à partir de données d’entrées ou de données de traitement           préalablement calculées.

      c-    Phase de sortie : dans cette phase, il s’agit d’afficher des données de sorties sur un       périphérique de sortie.

3- Variable et type de variable :

3.1 Notion de variable :

On appelle variable un emplacement en mémoire centrale auquel le programmeur attribue un nom et qui est destiné à contenir une valeur .

Remarques :

v Le programmeur choisi librement le nom de la variable en respectant la règle suivante : « le nom de la variable doit commencer par une lettre alphabétique qui peut être suivie par d’autres lettres ou des chiffres .

v Une variable ne peut contenir qu’une et une seule valeur à un instant donné mais ce contenu peut varier au cours du temps.

3.2 Type de variable

a- Définition

On appelle type de variable un ensemble de valeurs que peut contenir une variable ainsi que l’ensemble des opérations que l’on peut réaliser sur ces valeurs.

b- Type standard de variable

On distingue en programmation quatre types standard de variable

4- Instructions algorithmique

4.1 : La lecture

La syntaxe est la suivante :  lire <variable>

Cette instruction permet à l’ordinateur au moment de l’exécution d’aller saisir une valeur à partir d’un périphérique d’entrée et de la placer dans une variable.

Remarques :

v  Les crochets signifient que le programmeur peut choisir librement la variable.

v  Le type de la valeur lue doit être identique au type de la variable.

v  L’Instruction de lecture intervient le plus souvent  dans la phase d’entrée d’entrée d’un algorithme.

Exemple :

Dés que la valeur lue validée elle est affectée dans la variable NH.

 4.2 : L’Affectation :

Cette instruction permet à l’exécution de calculer le résultat  d’une expression et de l’affecter dans une variable.

Remarques :

      v  L’expression peut être une constante, une variable ou une formule.

v  Le type du résultat de l’expression doit être identique au type de la variable.

v  Le plus souvent , une instruction d’affectation intervient dans la phase du traitement  mais il est également possible de la placer dans une phase d’entrée .(lorsque la donnée d’entrée est chiffrée).

Exemple :

Soient 2 variables X et Y de type entier :

Remarque :

Une variable peut être affectée de deux façons seulement : soit par lecture soit par affectation directe.

4.3 : L’Ecriture :

La syntaxe est la suivante :     écrire    <liste d’expression>

Remarques :

v  L’expression peut être :

Ø  Une constante : c’est la constante qui est affichée

Ø  Une variable : c’est le contenu de la variable qui est affiché

Ø  Une fonction : c’est le résultat de l’opération qui est affiché

v  Dans le cas d’une liste d’expression , 2 expressions sont séparés par une virgule.

v  Une instruction d’écriture intervient le plus souvent dans une phase de sortie.

v  Il est préférable de faire précéder une instruction de lecture par une instruction d’écriture d’un message explicatif relatif à la donnée à lire.

5- Règles de priorité et d’affectation

5.1 : Priorité des opérateurs arithmétiques

a : Dans les Réels

Pour calculer une expression arithmétique dont le type réel, l’ordinateur obéit à l’échelle des priorités suivantes :

b : Dans le type Entier

5.2 : Les règles d’affectation

a : Notion de Table d’Exécution

            On appelle Table d’exécution un tableau qui permet de suivre l’exécution d’une suite d’instructions.

Ce tableau est constitué d’autant de colonnes que de variables.

            A chaque ligne du tableau, correspond une instruction pour laquelle il s’agit d’évaluer le contenu de chaque variable.

Remarque :

Une table d’exécution permet de vérifier des résultats obtenus par l’ordinateur à la suite de l’exécution d’un programme.

           

b : Exemples

          d : Règles d’affectation

                 Remarque 1 :

           Une variable peut être affectée de 2 façons soit par lecture soit par affectation.

                Remarque 2 : 

           Le contenu d’une variable reste inconnu jusqu’à ce que la variable soit affectée.

                Remarque 3 :

           Une variable mémorise son contenu jusqu’à nouvelle affectation.

                Remarque 4 :

           A un instant donné, une variable ne contient qu’une et une seule valeur.

               Remarque 5 : 

           A chaque nouvelle affectation, le nouvelle valeur écrase la précédente.

               Remarque 6 :

          Toute variable appartient à une expression d’affectation doit être préalablement                affectée.

   6- Algorithme

          6.1 : Définition

On appelle Algorithme un procédé de résolution d’un problème informatique constitué d’une suite d’instruction exécutable par un ordinateur.

          6.2 : Forme générale

La forme générale d’un algorithme est la suivante :

L’Algorithme commence toujours par le mot Début et se termine par le mot Fin.

La partie des déclarations permet de déclarer les éléments nécessaires à la partie des instructions. Parmi ces éléments  on trouve :

Les variables, les tableaux, les fonctions, les procédures, les fichiers, de nouveaux types…etc.

Pour déclarer une ou plusieurs variables de même type, la syntaxe est la suivante :

                         Var < liste des variables > : < Type >

                Exemples :

Soit à déclarer les variables I ,J et K de type Entier ; X1 et X2 de type Réel ; C1 et C2  de type Chaîne et B1,B2 et B3 de type Booléen.

Var      I, J, K : Entier

  X1,X2 : Réel

  C1, C2 , C3 : Chaîne

  B1, B2 , B3 : Booléen

       Déclarer une variable, consiste à réserver la place mémoire nécessaire pour le contenu de cette variable.

      La partie des instructions constitue la solution effective du problème .Elle ne doit contenir que les seules instructions algorithmiques .Elle se divise en 3 parties

   q  La phase d’entrée : dans cette phase , il s’agit de communiquer à la mémoire centrale de l’ordinateur les données d’entrées du problème.

   q  La phase de traitement :dans cette phase il s’agit de calculer les données intermédiaires de traitement permettant d’aboutir aux données de sorties .

        q  La phase de sortie : dans cette phase , il s’agit de classer les données sur les périphériques de sortie.

6.3 : Exemple