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 STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 1 Dr BACH

ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 1 Dr BACHI Katia CHAPITRE 1 : INTRODUCTION ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 2 Plan du chapitre 1 - Bref historique sur l’informatique …………………………………... - Introduction à l’algorithmique…………………………………………. I. Bref historique sur l’informatique I.1 Définitions 1) Le terme informatique a été créé en 1962 par Philippe Dreyfus à partir des mots «information» et «automatique». Il désigne littéralement l'automatisation du traitement de l'information par ordinateur. Il s'agit en fait des sciences et techniques de l'information. Par extension, il désigne aussi bien le matériel informatique que la conception et l'administration de la partie immatérielle d'un ordinateur. L'informatique est inséparable à la programmation, mais aussi aux machines, ordinateurs, terminaux. 2) Le terme système informatique est un ensemble de moyens matériel et logiciels permettant de satisfaire les besoins des utilisateurs. - Le Matériel informatique: Il s’agit des ressources matérielles qui sont exploitées pour exécuter les différents logiciels destinés à satisfaire les besoins des utilisateurs : micro- ordinateurs, imprimantes, scanners, etc. - Les Logiciels: Un logiciel est un ensemble de programmes qui répond aux besoins fréquents de l’utilisateur dans un domaine d’activités bien déterminé. On distingue plusieurs types de logiciels tels que les logiciels de base comme le système d'exploitation ou les programmes d'application (Traitement de texte, comptabilité ...). 3) Le terme utilisateur : un utilisateur est une personne initié à l’informatique et autorisé à exploiter et à manipuler les ressources du système informatique 4) Un ordinateur est un ensemble de circuits électroniques qui traite l'information grâce à un programme qu'il mémorise, communique et archive des informations. Le traitement de l'information se fait automatiquement et vise à résoudre un problème bien défini. La structure de base d’un ordinateur comprend les éléments fondamentaux suivants :  La mémoire centrale  L’unité centrale ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 3  Les périphériques  Le système de bus i) La mémoire centrale contient les programmes systèmes nécessaires au bon fonctionnement de l'ordinateur, et les programmes utilisateurs répondant à un besoin particulier et résolvant un problème rencontré par l’utilisateur. Ces programmes auront besoin d'un ensemble de données afin d'être exécutés et fournir les résultats escomptés, ces données existent également dans la mémoire centrale. ii) L'unité centrale va s'occuper de l'exécution des programmes logés dans la mémoire centrale. Elle est constituée de: - l'unité arithmétique et logique (UAL) qui s'occupe de toutes les opérations arithmétiques et logiques (addition, soustraction, multiplication, division, comparaison, etc.) - l'unité de commande (UC) est chargée de commander et de gérer tous les différents constituants de l’ordinateur (contrôler les échanges, gérer l’enchaînement des différentes instructions, etc). iii) Les périphériques sont les unités qui assurent la relation de l'ordinateur avec le monde extérieur. Ils se répartissent en 3 types: - les périphériques d'entrée assurant l'entrée des données à partir de l'utilisateur (exemples: clavier, souris, microphone, etc.) - les périphériques de sortie assurant la sortie des données vers l'utilisateur (exemples: imprimante, écran, haut-parleurs, etc.) - Les périphériques d'entrée et de sortie assurant l'entrée et la sortie des données à partir et vers l'utilisateur (exemples: disque dur, bande magnétique, disquette, cd-rom groupés sous le nom mémoire auxiliaire ou mémoire de masse ou mémoire secondaire, modem, etc.) iv) Le système bus permet de véhiculer l’information entre l’unité centrale et les autres unités. La figure ci-dessous illustre la structure globale d'un ordinateur. ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 4 L’utilisation d’un ordinateur pour la résolution d’un problème nécessite tout un travail de préparation. N’ayant aucune capacité d’invention, l’ordinateur ne peut en effet qu’exécuter les ordres qui lui sont fournis par l’intermédiaire d’un programme. Ce dernier doit donc être établi de manière à envisager toutes les éventualités d’un traitement. I. 2 Résolution d’un problème en informatique Plusieurs étapes sont nécessaires pour résoudre un problème en informatique  Etape 1 : Définition du problème. Il s’agit de déterminer toutes les informations disponibles et la forme des résultats désirés.  Etape 2 : Analyse du problème. Elle consiste à trouver le moyen de passer des données aux résultats. Dans certains cas on peut être amené à faire une étude théorique. Le résultat de l’étape d’analyse est un algorithme. Une première définition d’un algorithme peut être la suivante : "On appelle algorithme une suite finie d’instructions indiquant de façon unique l’ordre dans lequel doit être effectué un ensemble d’opérations pour résoudre tous les problèmes d’un type donné."  Etape 3 : Ecriture d’un algorithme avec un langage de description algorithmique. ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 5 Une fois qu’on trouve le moyen de passer des données aux résultats, il faut être capable de rédiger une solution claire et non ambiguë. Comme il est impossible de le faire en langage naturel, l’existence d’un langage algorithmique s’impose.  Etape 4 : Traduction de l’algorithme dans un langage de programmation. Les étapes 1, 2 et 3 se font sans le recours à la machine. Si on veut rendre l’algorithme concret ou pratique, il faudrait le traduire dans un langage de programmation. Nous dirons alors qu’un programme est un algorithme exprimé dans un langage de programmation.  Etape 5 : Mise au point du programme. Quand on soumet le programme à la machine, cette dernière le traite en deux étapes 1. La machine corrige l’orthographe, c’est ce qu’on appelle syntaxe dans le jargon de la programmation. 2. La machine traduit le sens exprimé par le programme. Si les résultats obtenus sont ceux attendus, la mise au point du programme se termine. Si nous n’obtenons pas de résultats, on dira qu’il y a existence des erreurs de logique. Le programme soit ne donne aucun résultat, soit des résultats inattendus soit des résultats partiels. Dans ce cas, il faut revoir en priorité si l’algorithme a été bien traduit, ou encore est-ce qu’il y a eu une bonne analyse. II. Introduction à l’algorithmique II.1 Définitions  Algorithme : On peut définir un algorithme comme suit : Résultat d’une démarche logique de résolution d’un problème. C’est le résultat de l’analyse. Ou encore : Une suite finie d'instructions indiquant de façon précise l'ordre dans lequel doit être effectué un ensemble d'opérations pour obtenir la solution d’un problème.  Programme On peut définir un programme comme suit : Un algorithme codé dans un langage compréhensible par ordinateur à l’aide d’un compilateur (traducteur). Ou encore : Une liste d’instructions qu’il faut exécuter pour atteindre un objectif donné. ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 6 Selon les définitions précédentes, on voit qu’il existe une grande similitude entre les termes « programme » et « algorithme ». Les deux désignent une méthode pour résoudre un problème donné. On emploie le terme « algorithme » lorsque la séquence d’instructions est écrite en langage algorithmique et fait abstraction d’un ensemble de détail. On emploie le terme « programme » lorsque la séquence d’instructions est écrite dans un langage compréhensible par la machine.  Notion d’algorithmique C’est la logique d’écrire des algorithmes. Pour pouvoir écrire des algorithmes, il faut connaître la résolution manuelle du problème, connaître les capacités de l’ordinateur en terme d’actions élémentaires qu’il peut assurer et la logique d’exécution des instructions.  Langage de programmation Un langage de programmation est un code de communication, permettant à un être humain de dialoguer avec une machine en lui soumettant des instructions et en analysant les données matérielles fournies par le système, généralement un ordinateur. L'activité de rédaction du code source d'un programme est nommée programmation. Elle consiste en la mise en œuvre de techniques d'écriture et de résolution d'algorithmes informatiques, lesquelles sont fondées sur les mathématiques. Pour résoudre un problème, il est vivement conseillé de réfléchir d'abord à l'algorithme avant de programmer proprement dit, c'est à dire d'écrire le programme en langage de programmation. II.2 Les caractéristiques d’un algorithme a. Claire: l’algorithme ne doit pas présenter des ambiguïtés (instruction interprétable de plusieurs manières) et facile à lire et à comprendre. ALGORITHMIQUE ET STRUCTURE DE DONNEES 1 Année universitaire 2020/2021 7 b. Correct: Il faut que l’algorithme exécute correctement les tâches pour lesquelles il a été conçu. c. Complet: Il faut que l’algorithme considère tous les cas possibles et donne un résultat dans chaque cas. d. Fini : l’algorithme doit se terminer quelle que soit la machine ainsi que le temps et la date d’exécution. e. Efficacité : l’algorithme doit effectuer le travail demandé avec l’utilisation du minimum de ressources. II. 3 Etapes de construction d’un algorithme Un algorithme comprend trois étapes : - Une phase d'initialisation : C'est la préparation du traitement. On repère les données nécessaires à la résolution. - Une phase de traitement du problème : On détermine les étapes du traitement et donc les instructions à donner pour une exécution automatique. - Une phase de sortie des résultats : Les résultats obtenus peuvent être affichés à l'écran, imprimés ou encore sauvegardés dans un fichier. Les sorties peuvent éventuellement être des graphiques, des images... Exemple : calculer la somme de deux nombres  Récupérer les valeurs des deux nombres  Calculer la uploads/Industriel/chapitre-1 18 .pdf