Cours Algorithme Et Programmation PDF [PDF]

Zitiervorschau

Algorithme et Programmation Première Année

Carlos AGOSSOU DOCTEUR EN SCIENCES DE L’INGENIEUR

Algorithme et Programmation

Cours d’Algorithme et Programmation Objectif :  

Apprendre les concepts de base de l'algorithmique et de la programmation Être capable de mettre en œuvre ces concepts pour analyser des problèmes simples et écrire les programmes correspondants

Points généraux :       

introduction à l’algorithmique et à la programmation Généralités sur l’algorithmique et les langages de programmation Notion de variable, affectation, lecture et écriture Instructions conditionnels et instructions itératives Les Tableaux, les fonctions et procédures, la récursivité Introduction à la complexité des algorithmes Données structurées

Initiation au Langage C (Travaux pratiques)

1 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation

Table des matières 1.1.

Qu’est-ce qu’un algorithme ?........................................................................... 3

1.2.

Qu’est-ce qu’un programme ? .......................................................................... 4

1.3.

Variable, Affectation ....................................................................................... 4

1.4.

Types de base des variables ............................................................................ 5

1.5.

Lecture et écriture de variables ...................................................................... 8

1.6.

Langage algorithmique ................................................................................... 8

1.7.

Phase d’analyse ............................................................................................... 9

2 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation

Chapitre 1 : Introduction à l’algorithme et la programmation 1.1. Qu’est-ce qu’un algorithme ? Définition : Un algorithme est une suite finie d’opérations élémentaires, à appliquer dans un ordre déterminé, à des données. Sa réalisation permet de résoudre un problème donné. Exemples : suivre une recette de cuisine, suivre un plan, faire une division euclidienne à la main sont des exemples d’algorithme.

Remarques : 1. Un algorithme doit être lisible de tous. Son intérêt, c’est d’être codé dans un langage informatique afin qu’une machine (ordinateur, calculatrice, etc.) puisse l’exécuter rapidement et efficacement. 3 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation 2. Les trois phases d’un algorithme sont, dans l’ordre : (a) l’entrée des données (b) le traitement des données (c) la sortie des résultats Autrement dit, un algorithme est une procédure de calcul bien définie qui prend en entrée un ensemble de données, exprime un traitement particulier et qui délivre en sortie un ensemble de résultats. Exemple : Problème : Trier une suite de nombres entiers dans l'ordre croissant. Entrée : Suite de n nombres entiers (a1, a2, ...an) Sortie : Une permutation de la suite donnée en entrée (a'1, a'2, ...a'n) telle que a'1≤a'2≤, ...≤a'n. A partir de la suite (6,9,2,4), un algorithme de tri fournira le résultat (2,4,6,9).

1.2. Qu’est-ce qu’un programme ? Un programme est une série d’instructions pouvant s’exécuter en séquence, ou en parallèle qui réalise (implémente) un algorithme. L’écriture algorithmique est un travail de programmation à visée universelle :  

un algorithme ne dépend pas du langage dans lequel il est implanté, ni de la machine qui exécutera le programme correspondant.

1.3. Variable, Affectation Définition : Lors de l’exécution d’un algorithme, on va avoir besoin de stocker des données, voire des résultats. Pour cela, on utilise des variables. On attribue un nom à chaque variable. Remarques : 1. Une variable est comme une boîte, repérée par un nom, qui va contenir une information. Pour utiliser le contenu de cette boîte, il suffit de l’appeler par son nom. 2. Dans l’écriture d’un algorithme, on prendra l’habitude de préciser dès le départ le nom des variables utilisées en indiquant leur type (nombre, chaîne de caractère, liste, etc.). Cette étape est appelée déclaration des variables. 3. Le choix du nom d’une variable est soumis à quelques règles qui varient selon le langage, mais en général: 4. • Un nom doit commencer par une lettre alphabétique. 4 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Exemple : E1 (1E n’est pas valide)  doit être constitué uniquement de lettres, de chiffres et du soulignement (« _ ») (Éviter les caractères de ponctuation et les espaces) Exemples : SMI2008, SMI_2008 (SMP 2008, SMP-2008, SMP;2008 : sont non valides)  doit être différent des mots réservés du langage 5. Pour la lisibilité du code choisir des noms significatifs qui décrivent les données manipulées Exemples: NoteEtudiant, Prix_TTC, Prix_HT En langage algorithmique, on va respecter les règles citées, même si on est libre dans la syntaxe

1.4. Types de base des variables Définitions : Un type abstrait est un triplet composé :   

d'un nom, d'un ensemble de valeurs, d'un ensemble d'opérations définies sur ces valeurs.

Les types abstrait de bases de l'algorithmique sont :    

Entier Caractères Booléen (Type logique) Réel

Une variable est un triplet composé :   

d'un type (déjà défini), d'un nom (a priori toute chaîne alphanumérique), d'une valeur.

Une variable constante donne une instruction permettant de réserver de l’espace mémoire pour stocker une constante dont la valeur ne varie pas. Toute variable utilisée dans un programme doit avoir fait l’objet d’une déclaration préalable Formalisme : Variable : type Constante : type ← valeur ou expression

5 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Exemples : Variables val, unNombre : entiers nom, prénom : chaînes de caractères Constante MAX : entier ← 10 DEUXFOISMAX : entier ← MAX * 2

Les Expressions sont constituées à l'aide de variables déjà déclarées, de valeurs, de parenthèses et d'opérateurs du (des)type(s) des variables concernées. L'affectation est l'instruction qui permet de stocker une valeur dans une variable. En langage algorithmique, l'affectation est notée par le signe ← 

Var ← e : attribue la valeur de e à la variable Var o e peut être une valeur, une autre variable ou une expression o Var et e doivent être de même type ou de types compatibles o l’affectation ne modifie que ce qui est à gauche de la flèche

Exemples : i ←1

j ← i k ← i+j

x ←10.3

ok ←FAUX

ch2 ←ch1

x ←4

ch1 ←"SMI" x ←j

(avec i, j, k : entier; x : réel; ok : booléen; ch1, ch2 : chaine de caractères) Exemples non valides: i ←10.3

ok ←"SMI"

j ←x

Remarque : Toute variable doit être déclarée et recevoir une valeur initiale.

Booléens Une variable de type booléen prend comme valeur VRAI ou FAUX. Les opérations usuelles sont OU, ET et NON qui sont données dans les tables qui suivent.

6 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Entiers Une variable de type entier peut prendre comme valeur l'ensemble des nombres entiers signés. Les opérations associées sont les opérations usuelles :      

Addition : + Soustraction : Produit : * Divisions : / Elévation à la puissance : ^ : Modulo : %

L’ordre de priorité des opérateurs est le suivant (du plus prioritaire au moins prioritaire) :

Réels Une variable de type réel peut prendre comme valeur l'ensemble des nombres réels. Les opérations associées sont les opérations usuelles +,-,*,/.

Caractères Une variable de type caractère peut prendre comme valeur l'ensemble des caractères imprimables. On notera les valeurs entre guillemets. On considère souvent que les caractères sont ordonnés dans l'ordre alphabétique.

Attention Les valeurs   

"1" qui est un caractère, 1 qui est un entier, 1.0 qui est un réel

sont différentes et ne seront pas codés de la même manière dans la mémoire de la machine.

7 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Comparaison Les opérateurs    

< ; > : est inférieur resp. supérieur = : est inférieur ou égal resp. supérieur ou égal == : est égal != : est différent

permettent de comparer les valeurs de type entier, réel et caractère. Le résultat de cette comparaison est une valeur booléenne.

1.5. Lecture et écriture de variables Définition : Les instructions de base sur des variables sont les suivantes :   

la saisie : on demande à l’utilisateur de l’algorithme de donner une valeur à la variable ; l’affectation : le concepteur de l’algorithme donne une valeur à la variable. Cette valeur peut-être le résultat d’un calcul ; l’affichage : on affiche la valeur de la variable.

Formalisme : Saisir Afficher Les fonctions « Saisir » et « Afficher » sont des instructions permettant :  

de placer en mémoire les informations fournies par l'utilisateur. De visualiser des données placées en mémoire

Exemples : Saisir(unNombre) Afficher(‘‘le nom est ‘‘, nom, ‘‘ et le prénom est ‘‘ , prénom ) Saisir(val)

1.6. Langage algorithmique Algorithme NomAlgorithme {ceci est un commentaire} ou /* ceci est un commentaire */ Début ... Actions Fin Remarques : Tout programme en langage algorithmique doit respecter les points suivants : 8 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation     

Il faut avoir une écriture rigoureuse Il faut avoir une écriture soignée : respecter l’indentation Il est nécessaire de commenter les algorithmes Il existe plusieurs solutions algorithmiques à un problème posé Il faut rechercher l’efficacité de ce que l’on écrit

Par ailleurs :     

Les opérations d'un algorithme sont habituellement exécutées une à la suite de l'autre, en séquence (de haut en bas et de gauche à droite). L'ordre est important. On ne peut pas changer cette séquence de façon arbitraire. Par exemple, enfiler ses bas puis enfiler ses bottes n’est pas équivalent à enfiler ses bottes puis enfiler ses bas.

Exemple 1 : Algorithme Bonjour /* il dit juste bonjour mais … en anglais ! */ Début afficher('Hello world !!!') Fin Exemple 2:

1.7. Phase d’analyse Elle consiste à extraire de l’énoncé du problème des éléments de modélisation. La technique à utiliser est de distinguer en soulignant de différentes couleurs quelles sont :   

Quel est le but du programme (traitement à réaliser) Données en entrée du problème Où vont se situer les résultats en sortie 9

Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Application • On souhaite calculer et afficher, à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC • Le montant TTC dépend de :  

Du prix HT Du taux de TVA de 20,6

Traitement à réaliser Calculer et afficher , à partir d’un prix hors taxe saisi, la TVA ainsi que le prix TTC Données en entrée  

Le prix HT Le taux de TVA de 20,6

Données en sortie  

La TVA Le prix TTC

D’où l’algorithme TVA suivant : Algorithme CalculTVA /* Saisit un prix HT et affiche le prix TTC correspondant */ /* déclarations des variables */ Constantes (TVA : réel) ←20.6 (Titre : chaîne) ←"Résultat" Variables prixHT : réel Variable prixTTC, montantTVA : réels Début /* préparation du traitement */ Afficher("Donnez-moi le prix hors taxe :") Saisir(prixHT) /* Traitement et affectation */ prixTTC ← prixHT * (1+TVA/100) /* calcul du prix TTC */ montantTVA ← prixTTC- prixHT Afficher (Titre) {présentation du résultat} Afficher (prixHT, " euros H.T. + TVA ", TVA, " devient ", prixTTC, " eurosT.T.C.") Fin

10 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Exercice 1 Donnez les valeurs des variables A, B et C après exécution des instructions suivantes ? Variables A, B, C : Entier Début A←7 B ← 17 A←B B ← A+5 C←A+B C←B–A Fin Exercice 2 Donnez les valeurs des variables A, B et C après exécution des instructions suivantes ? Variables A, B, C : Entier Début A←6 B←2 A←B B←A Fin Les deux dernières instructions permettent-elles d’échanger les valeurs de A et B ? Exercice 3 Quelles sont les différentes valeurs des variables :

Exercice 4 Écrire un algorithme qui permet d’effectuer la saisie d’un nom, d’un prénom et affiche ensuite le nom complet 11 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur

Algorithme et Programmation Exercice 5 Ecrire en langage algorithmique un programme calcule l’image d’un réel x par la fonction f : x → 2x + 1.

12 Enseignant : Ing Carlos AGOSSOU, Docteur en Sciences de l’Ingénieur