Remerciez-le!

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

Prof. A.SABOUR Algorithmique introduction générale et terminologie 2 Syllabus d

Prof. A.SABOUR Algorithmique introduction générale et terminologie 2 Syllabus du cours ... Objectif : L’acquisition des notions fondamentales de l’algorithmique. Apprendre les principes de l'algorithmique ; Se familiariser avec les méthodes de résolution de problèmes avec l'outil informatique ; résoudre des problèmes «comme» une machine savoir expliciter son raisonnement savoir formaliser son raisonnement concevoir (et écrire) des algorithmes : Apprendre comment Spécifier, Concevoir, Coder, Mettre au point et Documenter des programmes performants, en utilisant un langage de haut niveau. 2 3 Introduction à l'algorithmique Une autre définition Un algorithme est un moyen pour un humain de présenter la résolution par calcul d'un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En effet, un algorithme est un énoncé dans un langage bien défini d'une suite d'opérations permettant de résoudre par calcul un problème. 3 4 Qu'est ce qu'un algorithme ? Définition informelle Un algorithme est une procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de valeurs, et qui donne en sortie une valeur, ou un ensemble de valeurs. Un algorithme est donc une séquence d’étapes de calcul qui transforment l'entrée en sortie. Un algorithme est un moyen pour un humain de présenter la résolution par calcul d'un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En effet, un algorithme est un énoncé dans un langage bien défini d'une suite d'opérations permettant de résoudre par calcul un problème. 4 5 Définition Algorithmique: Définition 1: désigne l'ensemble des règles et des techniques qui sont impliquées dans la définition et la conception des algorithmes. Définition 2: l'algorithmique c'est de savoir comment lire, écrire, évaluer et optimiser des algorithmes. 5 6 Définition Définition : Un algorithme est un ensemble d'opérations de calcul élémentaires, organisé selon des règles précises dans le but de résoudre un problème donné. Pour chaque donnée du problème, l'algorithme retourne une réponse après un nombre fini d'opérations (+, -,/,<,>,... ). Un algorithme est une procédure systématique permettant de résoudre une classe de problèmes. À partir d'une entrée (représentant une instance du problème), un algorithme suit un ensemble déterminé de règles et, en un nombre fini d'étapes, produit une sortie (représentant une réponse à l'instance donnée). L'algorithmique est donc l'étude des algorithmes, de leur conception et de leurs propriétés. 6 7 Définition Qu’est-ce qu’un programme? Un programme est donc une suite d'instructions exécutées par la machine. La machine a son propre langage appelé langage machine. Un programme est l’expression d’un algorithme par une machine donnée dans un langage de programmation donné en utilisant le répertoire d’actions(opérations, instructions) et les règles de composition propres à cette machine et à ce langage donnés. 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. 7 8 Introduction a l'algorithmique Pour être bon en algorithmique ... Faut-il être matheux pour être bon en algorithmique? Non, pas du tout ! La maîtrise de l'algorithmique requiert trois qualités : 1. Il faut être méthodique. Avant d‘écrire les instructions d'un algorithme, il faut analyser le problème à résoudre. Il faut ensuite définir les entrées et les sorties de l'algorithme. 8 9 Aucune recette ne permet de savoir à priori quelles instructions permettront d'obtenir le résultat voulu. Les réflexes du raisonnement algorithmique deviennent spontanés avec l'expérience. Introduction a l'algorithmique Pour être bon en algorithmique ... Faut-il être matheux pour être bon en algorithmique? Non, pas du tout ! La maîtrise de l'algorithmique requiert trois qualités : 1. Il faut être méthodique. 2. Il faut avoir de l'intuition. 9 10 Introduction a l'algorithmique Pour être bon en algorithmique ... Faut-il être matheux pour être bon en algorithmique? Non, pas du tout ! La maîtrise de l'algorithmique requiert trois qualités : 1. Il faut être méthodique. 2. Il faut avoir de l'intuition. 3. Il faut être rigoureux. Chaque fois qu'on écrit une série d'instructions, il faut systématiquement se mettre mentalement à la place de la machine qui va les exécuter. Si nécessaire, il faut avoir recours à une simulation sur papier. 10 11 Méthodologie Pour résoudre un problème, il est vivement conseillé de réfléchir d'abord à l'algorithme avant de programmer. La résolution d’un problème est caractérisé par 4 étapes: Comprendre la nature du problème posé Préciser les données fournies (Entrées) Préciser les résultats que l’on désire obtenir (Sorties) Déterminer le processus de transformation des données en résultats. 11 12 Méthodologie Comment on programme? On utilise un pseudo-langage, comportant toutes les structures de base d'un langage de programmation On traduit notre "pseudo" en langage évolué en fonction des possibilités de ce langage Ce langage sera ensuite traduit en langage machine Niveaux de développement 1. Analyse : niveau conceptuel ; 2. Algorithmique : niveau logique ; 3. Programmation : niveau physique. 12 13 L'algorithmique et la programmation ... Quelle est la différence entre l'algorithmique et la programmation ? Réponse L’écriture d'un programme dans un langage de programmation n'est que l‘étape finale d'un développement qui se déroule en trois phases : l'analyse, l'algorithmique et la programmation. En d'autre terme : Un algorithme est un maillon de la chaîne de développement d'un programme. Il est le lien indispensable entre l'analyse et la programmation. 13 14 Environnement algorithmique Niveau logique du développement Apprendre l'algorithmique, c'est apprendre à manier la structure logique d'un programme informatique. L'algorithmique exprime les instructions résolvant un problème donné indépendamment des particularités de tel ou tel langage. Lorsqu'on programme dans un langage (en C, en Visual Basic, etc.) on doit, en plus de la structure logique, prendre en considération les problèmes de syntaxe et les types d'instructions propres a ce langage. 14 15 Environnement algorithmique Représentation d'un algorithme Historiquement, plusieurs types de notations ont été utilises pour représenter des algorithmes : Descriptions littéraires Organigrammes Pseudo-codes Définition informelle Un pseudo-code est une série de conventions qui ressemble à un langage de programmation authentique dont on aurait évacue la plupart des problèmes de syntaxe. Important Un pseudo-code est susceptible de varier d'une référence à une autre. En effet, un pseudo-code est purement conventionnel. Aucune machine n'est censée le reconnaître. 15 16 les algorithmes sont rédigés dans un langage à mi- chemin entre le français et les langages de programmation, dit pseudo-code . plus pratique pour écrire un algorithme représentation largement utilisée pseudo-code 16 problème du tri Entrée: une séquence de n nombres (a1, : : : ,an) Sortie: une permutation (a1’; : : : ;an’) de la séquence d’entrée: a1’<a2’<….<an’ Exemple : (31;41;59;26;41;58)  (26;31;41;41;58;59) Exemple 17 Les instructions fondamentales Les ordinateurs ne comprennent que quatre catégories d'instructions : 1. l'affectation de variables ; 2. la lecture/écriture ; 3. les tests (les structures conditionnelles) ; 4. les boucles (les structures itératives). Important Un algorithme informatique se ramène toujours à la combinaison de ces quatre types d'instruction. Il peut y en avoir quelques unes, quelques dizaines, et jusqu‘à plusieurs centaines de milliers. 17 18 Caractéristiques d'un algorithme Un algorithme est l'énoncé dans un langage bien défini d'une suite d'opérations permettant de répondre au problème. Un algorithme doit donc être : lisible: l'algorithme doit être compréhensible même par un non-informaticien de haut niveau: l'algorithme doit pouvoir être traduit en n'importe quel langage de programmation, il ne doit donc pas faire appel à des notions techniques relatives à un programme particulier ou bien à un système d'exploitation donné précis: chaque élément de l'algorithme ne doit pas porter à confusion, il est donc important de lever toute ambiguïté concis: un algorithme ne doit pas dépasser une page. Si c'est le cas, il faut décomposer le problème en plusieurs sous-problèmes structuré: un algorithme doit être composé de différentes parties facilement identifiables 18 II- Les instructions de base pour commencer : un exemple - ensuite : • les variables • saisir et afficher des données • simuler un algorithme • faire des tests • répéter des traitements - pour terminer : les principales erreurs a éviter 20 Un premier algorithme Algorithme EleveAuCarre {Cet algorithme calcule le carré du nombre que lui fournit l'utilisateur} variables unNombre, sonCarre: entiers début {saisie d’un nombre} afficher("Quel nombre voulez-vous elever au carre?") saisir(unNombre) {calcul du carré du nombre saisi} sonCarre ← unNombre Χ unNombre {affichage du résultat} afficher("Le carre de ", unNombre) afficher("c'est ", sonCarre) fin 20 21 Un premier algorithme Algorithme EleveAuCarre {Cet algorithme calcule le carré du nombre que lui fournit l'utilisateur} variables unNombre, sonCarre: entiers début {saisie d’un nombre} afficher("Quel nombre voulez-vous elever au carre?") saisir(unNombre) {calcul du carré du nombre saisi} sonCarre ←unNombre Χ unNombre {affichage du résultat} afficher("Le carre de ", unNombre) afficher("c'est ", sonCarre) fin 21 22 Un premier algorithme Algorithme EleveAuCarre variables unNombre, sonCarre: entiers début afficher("Quel nombre voulez-vous elever au carre?") saisir(unNombre) sonCarre ←unNombre Χ unNombre afficher("Le carre de ", unNombre) afficher("c'est ", sonCarre) fin Bloc de Déclaration Bloc de Traitement Ou Bloc actions 22 23Syntaxe Syntaxe général de l’algorithme  Exemple Exemple: :Algorithme Algorithmetoto toto {les constantes: il est obligatoire de leur donner une valeur dès leur déclaration } uploads/Philosophie/ 1-algorithmique-pdf.pdf