Remerciez-le!

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

Algorithmique et Structures de Données I Sonia KEFI Année Universitaire : 2021-

Algorithmique et Structures de Données I Sonia KEFI Année Universitaire : 2021-2022 1ère année Cycle Préparatoire Plan du Cours • Introduction à l’algorithmique • Les concepts de base de l’algorithmique • Les structures répétitives • Les tableaux • Les fonctions et procédures • Les chaines de caractères • La récursivité • Le pointeur 2 Chapitre 1 Introduction à l’algorithmique Plan 1. Contexte scientifique 2. Démarche de programmation 3. Différences entre algorithme et programme 3 Informatique L’informatique est la science du traitement automatique de l’information. L’informatique traite deux aspects complémentaires : ◦les programmes immatériels (logiciel, software) qui décrivent un traitement à réaliser, ◦Les machines (matériel, hardware) qui exécutent ce traitement. Le matériel est donc l’ensemble des éléments physiques (microprocesseur, mémoire, écran, clavier, disques durs. . .) utilisés pour traiter les données. L’ordinateur est un terme générique qui désigne un équipement informatique permettant de traiter des informations selon des séquences d’instructions (les programmes) qui constituent le logiciel. 4 Programmation (1) Quelques définitions Un programme est un ensemble d’opérations ou d’instructions destinées pour accomplir un besoin ou résoudre un problème. Un programme est écrit par un langage de programmation. Le langage de programmation est un langage informatique, permettant à l’utilisateur d’écrire un code source qui sera analysé par un ordinateur. La Programmation est l’activité de rédaction du code source d’un programme. Exemple de programme : ◦Supposons qu’un enseignant dispose d’un ordinateur et d’un programme de calcul de la moyenne des étudiants. Pour s’exécuter, ce programme nécessite qu’on lui fournisse pour chaque étudiant, les notes de contrôle continu, de T.P et de l’examen final : ce sont les données. En retour, le programme va fournir la moyenne cherchée : c’est le résultat. 5 Programmation (2) Types de langages L’ordinateur ne sait exécuter qu’un nombre limité d’opérations élémentaires dictées par des instructions de programme et codées en binaire (langage machine). Avant, les premiers programmes étaient écrits en binaire. C’était une tâche difficile et exposée aux erreurs car il fallait aligner des séquences de bits dont la signification n’est pas évidente. Par la suite, pour faciliter le travail, les programmes ont été écrits en désignant les opérations par des codes faciles à retenir (ADD, DIV, SUB, MOVE, ...). Les adresses des instructions et les variables pouvaient aussi être données sous forme symbolique. Pour pouvoir utiliser effectivement tous ces symboles, il fallait trouver le moyen de les convertir en langage machine ; ce fut réalisé par un programme appelé assembleur. Le langage d’assemblage est toujours utilisé, car c’est le seul langage qui permet d’exploiter au maximum les ressources de la machine. L’écriture de programmes en langage d’assemblage reste une tâche fastidieuse. De plus, ces programmes présentent un problème de portabilité étant donné qu’ils restent dépendants de la machine sur laquelle ils ont été développés. L’apparition des langages évolués, tels que Fortran et Pascal, a apporté une solution à ces problèmes. Les programmes écrits en langage évolué doivent également être convertis en langage machine pour être exécutés. Cette conversion peut s’effectuer de deux façons : par compilation ou par interprétation. 6 Programmation (3) Récapitulation Langage machine (le langage binaire) : c’est le seule langage qui est compréhensible par la machine mais c’est difficile à utiliser et à le manipuler par l’homme. Langage de bas niveau (le langage d’assemblage) : c’est un langage alphanumérique. Il est plus lisible, mais il reste toujours difficile à utiliser. Langage de haut niveau : il est proche du langage humain. On utilise un compilateur ou un interpréteur pour traduire un programme en langage machine. 7 Programmation (4) Compilation et interprétation La compilation consiste à traduire la totalité du code source en une seule fois. Le compilateur lit toutes les lignes du programme source et produit une nouvelle suite de codes appelé programme objet (ou binaire). Ce code objet est exécuté indépendamment du compilateur et être conservé dans un fichier (« fichier exécutable») et peut être soumis au processeur pour le traitement. Les langages Ada, C, C++ et Fortran sont des exemples de langages compilés. 8 Suite L’interprétation consiste à traduire chaque ligne du programme source en des instructions du langage machine, qui sont ensuite directement exécutées au fur et à mesure. Aucun programme objet n’est généré. L’interpréteur doit être utilisé chaque fois que l’on veut faire fonctionner le programme. Les langages Lisp et Prolog sont des exemples de langages interprétés. 9 Suite Semi-compilation : Certains langages tentent de combiner les deux techniques afin de retirer le meilleur. C’est le cas des langages Python et Java. Ces langages commencent par compiler le code source pour produire un code intermédiaire, similaire à un langage machine (mais pour une machine virtuelle), que l’on appelle bytecode, lequel sera ensuite transmis à un interpréteur pour l’exécution finale. Pour l’ordinateur, le bytecode est très facile à interpréter en langage machine. Cette interprétation sera donc beaucoup plus rapide que celle d’un code source. 10 Récapitulation 11 Différents niveaux de langages de programmation Algorithmique (1) L'algorithmique, on la pratique tous les jours : ◦Cafetière Expresso ◦Laine Pull ◦Farine, œufs, …. Gâteau 12 instructions modèle recette Algorithmique (2) Quelques définitions • Un algorithme est un ensemble de tâches élémentaires ordonnées, qui indique la démarche à suivre pour résoudre un problème donné. • L’algorithmique est la science qui étudie l’application des algorithmes. Elle s’intéresse à l’art de construire des algorithmes ainsi qu’à caractériser leur validité, leur robustesse, leur utilisation, leur complexité ou leur efficacité. 13 1. Phase d’étude : consiste à comprendre le problème et déterminer les données (entrées) et les résultats (sorties) à produire. 2. Phase d’analyse : consiste à identifier la succession des étapes nécessaires pour résoudre le problème. 3. Phase d’écriture de l‘algorithme : traduire les phases précédentes en se basant sur les règles du langage algorithmique. 14 Entrées Sorties Analyse Entrées Sorties Le langage algorithmique est un langage proche du langage humain. Il s’agit d'un ensemble de convention et de notations, qui peuvent varier d’une personne à une autre, et qui sert à décrire un algorithme. Démarche de programmation 4. Phase de programmation : traduire l’algorithme dans un langage de programmation pour obtenir un programme qui peut ensuite être exécuté. 15 Démarche de réalisation d’un programme Démarche de programmation Récapitulation Analyse : Mode d'expression du problème, en un nombre fini d'étapes, indépendant du langage de programmation utilisé. Algorithmique : Analyse + Algorithme Programmation : Codification ou traduction dans un langage compréhensible par la machine. Programmatique : Analyse + Algorithme + Programmation 16 Exemple de problème (1) Problème : Division de deux nombres Enoncé du problème : Diviser deux nombres Questions : ◦Quel genre de division ? exemple euclidienne ◦Quel est le type des deux nombres ? exemple entiers strictement positifs ◦Quel est le résultat demandé ? exemple quotient, reste 17 Exemple de problème (2) 18 Exemple de problème (3) 1. Positionnement du problème : Connaissant la dividende x, le diviseur y, calculer le quotient entier q, puis le reste N définis par la relation mathématique x = yq+r avec 0 < r < y 2. Analyse du problème : ◦Etape 1 : Ordre de lecture du dividende x et du diviseur y. ◦Etape 2 : Calcul du quotient entier q, calcul du reste par la formule r = x – yq ◦Etape 3 : Edition des résultats 3. Algorithme : description systématique des étapes de l'analyse, sous forme d'une suite d 'actions convenablement enchaînées. 4. Programmation : traduire les actions (ou ensemble des étapes) dans un langage compréhensible par la machine. 19 Généralisation des étapes de résolution 20 Différences entre algorithme et programme L'algorithme est la méthode choisie pour résoudre un problème. Un programme traduit un algorithme dans un langage de programmation particulier, par la suite, il peut être exécuté par un ordinateur. À la programmation, on s’occupe de certaines difficultés techniques (système d’exploitation, gestion de la mémoire, interface graphique, ...) souvent ignorées au niveau algorithmique. 21 Chapitre 2 Les concepts de base de l’algorithmique 22 Algorithme Nom_algorithme Constantes Id_cst = Valeur Type <Définition d’un type déclaré par l’utilisateur> Variables Id_var1,Id_var2, … : type variable Début Instruction 1 (Action 1) Instruction 2 (Action 2) … … Instruction n (Action n) Fin 23 Structure générale d’un algorithme Partie 1 : Déclaration des objets qui seront manipuler dans l’algorithme. Partie 2 : Corps de l’algorithme. L’ensemble des instructions permettant d’aboutir aux résultats escomptés. Partie 1 Partie 2 Notion d’objet (1) Définition d’objet ◦Un objet correspond à un emplacement dans la mémoire (une ou plusieurs cases mémoires selon la grandeur), caractérisé par un identificateur, une taille et un type, pouvant contenir une valeur et subir des actions spécifiques. Identificateur d’objet ◦L’identificateur d’un objet est son nom. Un nom correct commence impérativement par une lettre, comporte des lettres et des chiffres, mais qui exclut la plupart des signes de ponctuation, en particulier les espaces (un espace peut être remplacé par le caractère « uploads/Science et Technologie/ cours1-introduction-algorithmique.pdf