Cours Algo Smahi [PDF]

Zitiervorschau

Introduction à l’algorithmique

1ère année ST1 2019/2020, Semestre 2

SMAHI Zakaria [email protected]

Maitre de Conférence Dépt de Génie Physique Faculté de Physique USTOMB

SMAHI Zakaria (2020)

1

Introduction à l’algorithmique 1. Définition d’un Algorithme Un

algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, en un nombre fini d‘étapes, à un certain résultat, et cela indépendamment des données.

SMAHI Zakaria (2020)

2

1.1. Son origine: 

Le mot algorithme provient du nom d'un célèbre mathématicien musulman de la première moitié du IXe siècle: Muhammad ibn Musa al Khawarizmi (Khiva (Xiva en ouzbek est une ville d'Ouzbekistan), son ancien nom, Khwarezm ou Khorezm).

SMAHI Zakaria (2020)

3

1.2. Son Rôle: Le rôle de l'algorithme est fondamental. En effet, sans algorithme, il n'y aurait pas de programme (qui n'est jamais que sa traduction dans un langage compréhensible par l'ordinateur). De

plus, les algorithmes sont fondamentaux en un autre sens: ils sont indépendants à la fois de l'ordinateur et des langages de programmation dans lesquels ils sont énoncés et traduits. SMAHI Zakaria (2020)

4



« Ecrire un algorithme », c’est : 

Analyser et comprendre le problème : étudier les données fournies et les résultats attendus



Résoudre le problème, c’est trouver les structures de données adaptées ainsi que l’enchaînement des actions à réaliser pour passer des données aux résultats

 Comment exécuter un algorithme sur un ordinateur ? 

Il faut traduire cet algorithme à l’aide d’un langage de programmation connu par l’ordinateur.

SMAHI Zakaria (2020)

5

En Résumé : 

Un Algorithme consiste à retranscrire un processus logique à l’aide d’un langage naturel.



Un Algorithme est la description d’un traitement qui consiste à transformer des données, appelées « entrées » , afin de produire d’autres données appelées « sorties ». Les entrées et les sorties représentent les variables manipulées par l’algorithme.





Processus de Principe : Entrées -> Traitement -> Sorties

SMAHI Zakaria (2020)

6

2.Représentation d’un algorithme Historiquement, trois façons pour représenter un algorithme:

2.1. Le langage Naturel (Exp : Français). Exemple : comment formuler l’algorithme qui calcule la surface d’un disque ? Réponse : Pour calculer la surface d’un disque, on prend d’abord connaissance de son rayon. La surface est égale au produit de la constante π par le carré du rayon. SMAHI Zakaria (2020)

7

2. Représentation d’un algorithme

2. 2. L’Organigramme: Représentation graphique avec des symboles (carrés, losanges, etc.)



Avantage : offre une vue d’ensemble de l’algorithme



Inconvénient : représentation quasiment abandonnée aujourd’hui

SMAHI Zakaria (2020)

8

Représentation graphique d’un Organigramme Symboles

Signification L’ellipse : indique le début de l’algorithme Le parallélogramme : représente une opération de Lecture ou Ecriture Le rectangle : représente le contenu de chaque étape de traitement, il définit l’opération à exécuter. La flèche : sert à indiquer l’ordre d’exécution des différentes taches. L’Hexagone : sert à indiquer l’initialisation de certains paramètres. Le losange : il représente l’existence d’un choix logique : la proposition logique est indiquée à l’intérieur du losange. Le cercle : indique la poursuite d’une étape précédente. Le triangle renversé : symbolise la fin de l’algorithme. SMAHI Zakaria (2020)

9

Exemple : Calcul de surface d’un disque

Pi=3.141592 Entrée: Clavier

Rayon Sur  Pi* Rayon²  Sur

SMAHI Zakaria (2020)

Sortie: Ecran

10

2. 3. Le pseudo-code ou Langage de Description d’Algorithme (LDA):

C’est une représentation textuelle avec une série de conventions ressemblant à un langage de programmation (sans les problèmes de syntaxe)  plus

pratique pour écrire un algorithme  représentation largement utilisée

SMAHI Zakaria (2020)

11

Exemple précédent devient: Algorithme surf_Disq ; CONST Pi = 3.141592 : Réel ; VAR Sur, Rayon: Réel ; DEBUT LIRE(Rayon) ; Sur Pi* Rayon**2 ; Ecrire(Sur) ; FIN SMAHI Zakaria (2020)

12

3. Structure générale d’un Algorithme : En générale, l’algorithme comprend les étapes suivantes : 3.1. En tête : Algo Nom de l’algorithme; 3. 2. Déclaration : (Constante, Variable, Structure)

3. 2.1. Type de variable Une variable correspond à un type de variable. Les principaux types sont : Byte

(codé sur 1 octet: de 0 à 255) Caractère (codé sur 1 octet: de 0 à 255) Chaîne de caractères (toute suite de caractères ) Entier (codé sur 2 octets: de -32768 à 32767) Réel (codé sur 4 octets: de 0 à 255) Booléen (vraie ou fausse 0 ou 1, codé sur 1 octet SMAHI Zakaria (2020)

13

3. 2.2. Déclaration d’une variable 



Rappel: toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable En pseudo-code, on va adopter la forme suivante pour la déclaration de variables

Var 

liste d'identificateurs : type;

Exemple: Var

i, j,k : Entier; x, y : Réel; OK: Booléen;

ch1, ch2 : Chaîne;

SMAHI Zakaria (2020)

14

3.3. Corps de l’Algo: Début Lecture de données; Initialisation des paramètres; Transformation des données en résultats; Ecriture des résultats; Fin.

SMAHI Zakaria (2020)

15

4. Les instructions Algorithmiques  4.1. L’instruction d’affectation 



Affecter une variable consiste à lui donner une valeur. Cette valeur peut être soit une constante, soit une valeur d’une autre variable, soit le résultat d’un calcul. L’affectation est représentée par une flèche orientée à gauche 

Exemple : Exemple Si A,B sont deux variables de type Byte (valeur comprise entre 0 et 255), alors on peut écrire : B  15, A  B+ 4, A  A + 1 1/ Le terme de droite (15) est affecté au terme de gauche (variable A) 2/ " " (valeur de la variable B + 4) affecté au terme gauche (variable A) 3/ " "" (valeur de A (avant instruction) + 1) affecté (variable A. Dans ce dernier cas la nouvelle valeur de A remplace l'ancienne. Si une variable est numérique A  0 Si une variable est chaîne de caractères A  "0", ou A  " Lettres " SMAHI Zakaria (2020)

16

4.1. L’instruction d’affectation Quelques remarques : Beaucoup de langages de programmation (C, Fortran, pascal, …) utilisent le signe égal = pour l’affectation ←. Attention aux confusions: l'affectation n'est pas commutative : A=B est différente de B=A  l'affectation est différente d'une équation mathématique : 

 

A=A+1 a un sens en langages de programmation A+1=2 n'est pas possible en langages de programmation et n'est pas équivalente à A=1

SMAHI Zakaria (2020)

17

4.2. L’entrée d’information 

La primitive d’entrée ou saisir (entrée clavier) et lire (lecture en provenant du disque dur). Le but de ces primitives est de permettre à l’ordinateur d’affecter une variable extérieure à une autre variable. Le nom de cette variable symbolise une adresse en mémoire centrale. A cette adresse se trouve la valeur, à un moment donné de la variable.



La primitive de sortie : écrire, afficher, imprimer. Le but est de permettre à l’ordinateur de sortir la valeur d’une variable vers les périphériques extérieurs (écran, imprimante, etc…) SMAHI Zakaria (2020)

18

4.2.1. Instructions d'entrées-sorties: (Lecture et Ecriture) Les instructions de lecture et d'écriture permettent à la machine de communiquer avec l'utilisateur

4.2.1.1. Entrées (Lecture) La lecture permet d'entrer des données à partir du clavier Synthaxe: Lire (A) la machine met la valeur entrée au clavier dans la zone mémoire nommée A 



Remarque: Le programme s'arrête lorsqu'il rencontre une instruction Lire et ne se poursuit qu'après la frappe d’une valeur au clavier et de la touche Entrée SMAHI Zakaria (2020)

19

4.2.1. Instructions d'entrées-sorties (Lecture et Ecriture) 4.2.2. Sorties (Ecriture) L'écriture permet d'afficher des résultats à l'écran (ou de les écrire dans un fichier) 

Synthaxe: Ecrire (A) la machine affiche le contenu de la zone mémoire A



Conseil: Avant de lire une variable, il est fortement conseillé d’écrire des messages à l’écran, afin de prévenir l’utilisateur de ce qu’il doit frapper 

SMAHI Zakaria (2020)

20

4.2.2. Méthode de construction d’un algorithme simple

Exemple : Écrire un algorithme qui consiste à calculer l’air S d’un cercle selon la formule S = Pi * R2 Rappel : Pi = 3.14159 et R le rayon du cercle

SMAHI Zakaria (2020)

21

4.2.2. Méthode de construction d’un algorithme simple

Méthodologie à suivre :  Constantes : Pi = 3.14159  Variables : Rayon, Surface  Types : Rayon, Surface : réel  Expressions et affectation : Surface N ); Moy := Total / N; writeln('La moyenne est : ',Moy) END. SMAHI Zakaria (2020)

76

FIN du cours

SMAHI Zakaria (2020)

77