Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

1 Chapitre 2 Introduction à l’algorithmique 1 Notions d’algorithme et de progra

1 Chapitre 2 Introduction à l’algorithmique 1 Notions d’algorithme et de programme 1.1 Définitions □ Un algorithme représente l'enchaînement des actions (instructions) nécessaires pour résoudre un problème donné. Un algorithme s'écrit le plus souvent en pseudo-langage de programmation (appelé langage algorithmique). □ Un algorithme n'est donc pas exécutable directement par aucune machine. Mais il a l'avantage d'être traduit facilement dans tous les langages de programmation. □ Un programme est un assemblage et un enchaînement d’instructions élémentaires écrit dans un langage de programmation, et exécuté par un ordinateur afin de traiter les données d’un problème et renvoyer un ou plusieurs résultats. □ Trouver une solution informatique à un problème revient à trouver un ensemble d’actions permettant d’aboutir aux résultats demandés (objectifs). Du problème à la solution automatisée (programme informatique), on passe généralement par les étapes suivantes et qui peuvent être réparties en deux phases : Phase I : Analyse et proposition de solution au problème 1 ère étape : Analyse du problème Il s’agit ici de comprendre le problème et ce qui est demandé. En particulier, il s’agit de déterminer les données en entrée et les résultats demandés. De plus, il faudra trouver les traitements nécessaires permettant de manipuler les données en entrée pour obtenir les résultats souhaités. 2 ème étape : Elaboration de l’algorithme Durant cette étape, la solution au problème est exprimée sous forme d’un algorithme. En utilisant un langage algorithmique formel, un algorithme est une succession logique d’instructions (actions) pour passer des données aux résultats (objectifs). Une forme graphique est notamment utilisée qu’on appelle organigramme. 3 ème étape : Tests à la main (sans machine) Il s’agit ici de dérouler manuellement l’algorithme afin de le vérifier. C'est-à-dire suivre les étapes de l’algorithme pour vérifier s’il répond (aboutit) aux besoins exprimés en utilisant un jeu de tests. Phase II : Implémentation (mise en œuvre) 1 ère étape : programmation Une fois l’algorithme mis au point, il faut le traduire dans un langage de programmation donné. Exemples : pascal, fortran, C, basic, c++, java, caml, python, … En effet, le même algorithme peut être traduit dans plusieurs langages de programmation. A la fin de cette étape, on obtient un programme source qui correspond à l’algorithme établi lors de la phase précédente. 2 ème étape : compilation Cette étape est automatique et est réalisée grâce à un compilateur. Celui-ci est un programme qui traduit un programme source en un programme exécutable par la machine. 3 ème étape : tests sur machine Une fois le programme exécutable généré après la compilation, il faudra comparer les résultats rendus par ce programme par rapport aux résultats obtenus manuellement (durant la 3 ème étape de la phase I). Ceci permet de constater des erreurs et des incohérences dans les résultats obtenus qui pourraient être dues aux erreurs d’analyse ou de programmation. Dans ce cas, il faudra faire des corrections jusqu’à ce que les résultats soient satisfaisants. Ce qu’il faut signaler, c’est que l’automatisation d’un traitement est un processus itératif (répétitif) car il y aura 2 souvent des erreurs de programmation ou d’analyse du problème qu’il faudra corriger dans l’une des étapes précédentes. Par exemple, un résultat final incohérent pourrait être causé par une erreur de programmation même si l’algorithme est entièrement correct ou alors une erreur de conception de la solution. 4 ème étape : Rédaction d’une documentation pour l’utilisateur La documentation servira comme mode d’emploi du programme final (testé et validé). Elle est nécessaire quand le programme est difficile à manipuler (quand il offre beaucoup de fonctionnalités). 1.2 Propriétés d’un algorithme Un algorithme doit être : a/ Clair : pour éviter toute ambiguïté dans les exécutions d’opérations. b/ Fini : l’algorithme doit être fini c'est-à-dire toutes les actions doivent être exécutées en un temps fini. c/ Efficace: l’algorithme doit assurer (mener) le bon résultat (objectif) en utilisant le minimum de ressources (exp : minimum de variables pour un espace mémoire occupé minimal). d/ Général : l’algorithme ne doit pas être valable uniquement pour un cas particulier, il doit répondre à tous les cas qui peuvent se présenter pour un type de problème donné. 2 Syntaxe générale de l’algorithme Algorithme <nom algo> ; {en-tête de l’algorithme} < partie déclarations> ; Debut <partie instructions> ; Fin. Remarque : notion d’identificateur Un identificateur est un nom qu’on donne à un objet pour le désigner (référencer). Il doit être composé d’une suite de lettres et de chiffres et il doit toujours commencer par une lettre alphabétique. Les caractères spéciaux ne sont pas autorisés excepté le caractère « souligné ». Certains mots sont prédéfinis dans le langage algorithmique (mots réservés) et ils ne peuvent être redéfinis par l’utilisateur. Exemples d’identificateurs non permis : moy g , (car il contient un espace , moyg : juste) 1note ( faux car il commence par un chiffre , donc note1 , n1ote : justes) Algorithme, debut, fin sont quelques uns des mots réservés du langage, ils ne peuvent être des identificateurs. 2.1 En-tête d’un algorithme Est composé du mot réservé algorithme suivi du nom de l’algorithme qui doit être un identificateur. 2.2 Partie déclarations : A/ Déclaration des constantes : Une constante est une donnée dont on décide de garder la valeur inchangée tout le long d’un algorithme. La partie déclaration des constantes commence par le mot clé const. Syntaxe : const <identificateur constante > = <valeur constante> ; Exemples : const pi = 3,14 ; g = 9,80 ; Remarque : Les types standards 3 En algorithmique, on distingue 5 types standards de donnée principaux : □ Entier représente les entiers (les nombres sans virgule) ; □ Reel représente les réels (les nombres à virgule et sans virgule) ; □ Booleen représente les booléens (qui n'ont que deux valeurs possibles: soit VRAI, soit FAUX). □ caractere représente les caractères (lettres, chiffres, ponctuation, code des opérations, espace, retour chariot, et plus généralement toutes les touches que l'on peut trouver sur un clavier) □ chaine représente les chaînes de caractères (suites de caractères) ; B/ Déclaration des variables : Une variable peut être représentée par une case mémoire, qui contient la valeur d'une donnée. Chaque variable possède un nom unique appelé identificateur par lequel on peut accéder à son contenu. La valeur d'une variable peut varier au cours du programme. L'ancienne valeur est tout simplement écrasée et remplacée par la nouvelle. La partie déclaration des variables commence par le mot clé var. Syntaxe : var <identificateur variable > : <type variable> ; Exemples : Var neco, nalgo , nalgebr : reel ; Moy : reel ; Admis : booleen ; Remarque 1 : Il est possible de rassembler plusieurs variables d’un même type à condition de les séparer par des virgules. Remarque 2 : Si la partie déclarations contient des constantes, des types non standard et des variables, l’algorithme doit les déclarer selon cet ordre. 2.3 Les instructions élémentaires Les instructions élémentaires les plus courantes sont : □ L'affectation : donner une nouvelle valeur à une variable ; □ La saisie à travers le clavier □ L'affichage sur l'écran ; A/ L’affectation L’affectation consiste à placer une valeur dans une variable (ce qui revient à changer le contenu de cette variable). Syntaxe : <Identificateur variable> ← <expression> (le symbole ← se lit « reçoit ») Où <expression> peut être : □ Soit une autre variable ou constante ; □ Soit une valeur littérale ; {exemple nalgo ← 15} □ Soit une combinaison de variables, de valeurs littérales et d'opérateurs Exemples : A ← 3 ; B ← A + 5 ; A ← B ; 4 B/ La saisie (lecture – entrée des données) L’instruction de saisie permet de communiquer des données au programme. Cette instruction assigne une valeur entrée au clavier dans une variable. Tant que l'utilisateur n'entre rien au clavier, le déroulement du programme est stoppé. Syntaxe lire(variable1 , variable2, …) ; Exemples : Lire (x); Cette instruction va lire la valeur saisie au clavier et l'affecte à la variable x. Lire(x,y); ou lire (x) ; lire (y) ; Cette instruction lit la première valeur saisie au clavier et l'affecte à x, puis lit la deuxième valeur saisie et l'affecte à y. Utilité de la saisie: Si on utilise une instruction de saisie, le choix de la valeur se fait en cours d’exécution du programme. On peut donc utiliser le programme autant de fois que l’on veut avec des données différentes sans avoir à modifier le programme. C/ L’affichage sur écran La plupart des programmes nécessitent de communiquer à l’utilisateur un certain nombre de résultats via l’écran. Pour cela, ils utilisent des instructions d'affichage. L’instruction d’écriture est couramment utilisée dans deux situations : - Affichage de messages : Avant la lecture des données et l’affichage des résultats. - Affichage des résultats Syntaxe ecrire(expression1, expression2, …) ; Où expression peut être un commentaire (message), une constante, une variable ou une combinaison de ces derniers. Un message est une chaîne de caractères qui est toujours délimitée par deux apostrophes. Exemples : Ecrire (‘Veuillez saisir la note d’’algo1’) ; {l’apostrophe est doublée si elle uploads/s3/local-media4883281308897273924.pdf