Remerciez-le!

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

Informatique ECAM2 © L. Bidoire Mémento d’algorithmique en Python 3 1/39 Mément

Informatique ECAM2 © L. Bidoire Mémento d’algorithmique en Python 3 1/39 Mémento d’algorithmique en Python 3 I. Définitions et vocabulaire : Le terme informatique est un néologisme proposé en 1962 par Philippe Dreyfus pour caractériser le traitement automatique de l’information : il est construit sur la contraction de l’expression « information automatique ». Ce terme a été accepté par l’Académie française en avril 1966, et l’informatique devint alors officiellement la science du traitement automatique de l’information, où l’information est considérée comme le support des connaissances humaines et des communications dans les domaines techniques, économiques et sociaux. Le mot informatique n’a pas vraiment d’équivalent aux Etats-Unis où l’on parle de Computer Science, science du calculateur, ou Information Technology (IT), technologie de l’information ; alors que Informatics est admis par les Britanniques. Couverture du magazine Time, février 1978 Définition : L’informatique est la science du traitement automatique de l’information. Microprocesseur AMD Opteron quadri-cœur, 2007 L’informatique traite de deux aspects complémentaires : les programmes (logiciel, software) qui décrivent un traitement à réaliser et 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. Dans ce contexte, 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. Le terme ordinateur a été proposé par le philologue Jacques Perret en avril 1955 en réponse à une demande d’IBM France qui estimait le mot « calculateur » (computer) bien trop restrictif en regard des possibilités de ces machines. Définition : Un algorithme est une suite finie ordonnée d’instructions qui indique la démarche à suivre pour résoudre une série de problèmes équivalents. Informatique ECAM2 © L. Bidoire Mémento d’algorithmique en Python 3 2/39 Exemple : Extrait d’un dialogue entre un touriste égaré et un autochtone. – Pourriez-vous m’indiquer le chemin de la gare, s’il vous plaît ? – Oui bien sûr : vous allez tout droit jusqu’au prochain carrefour, vous prenez à gauche au carrefour et ensuite la troisième à droite, et vous verrez la gare juste en face de vous. – Merci. Dans ce dialogue, la réponse de l’autochtone est la description d’une suite finie ordonnée d’instructions (allez tout droit, prenez à gauche, prenez la troisième à droite) qui manipulent des données (carrefour, rues) pour réaliser la tâche désirée (aller à la gare). Chacun a déjà été confronté à ce genre de situation et donc, consciemment ou non, a déjà construit un algorithme dans sa tête (ie définir la suite d’instructions pour réaliser une tâche). Mais quand on définit un algorithme, celui-ci ne doit contenir que des instructions compréhensibles par celui qui devra l’exécuter (des humains dans les l’exemple précédent). Dans ce cours, nous allons apprendre à définir des algorithmes pour qu’ils soient compréhensibles — et donc exécutables — par un ordinateur. Le mot algorithme est l’altération, sous l’influence du grec arithmos, « nombre », d’algorisme, qui, par l’espagnol, remonte à l’arabe Al-Khwârizmî, surnom d’un mathématicien originaire de la région du Khwarezm (actuel Ouzbékistan). Al-Khwârizmî (~780 - ~850) Définition : L’algorithmique est la science des algorithmes. L’algorithmique s’intéresse à l’art de construire des algorithmes ainsi qu’à caractériser : Leur validité, leur robustesse, leur réutilisabilité, leur complexité et leur efficacité. Définition : La validité d’un algorithme est son aptitude à réaliser exactement la tâche pour laquelle il a été conçu. Dans l’algorithme de recherche du chemin de la gare, l’étude de sa validité consiste à s’assurer qu’on arrive effectivement à la gare en exécutant scrupuleusement les instructions dans l’ordre annoncé. Définition : La robustesse d’un algorithme est son aptitude à se protéger de conditions anormales d’utilisation. Dans l’exemple, la question de la robustesse de l’algorithme se pose par exemple si le chemin proposé a été pensé pour un piéton, alors que le « touriste égaré » est en voiture et que la « troisième à droite » est en sens interdit. Définition : La réutilisabilité d’un algorithme est son aptitude à être réutilisé pour résoudre des tâches équivalentes à celle pour laquelle il a été conçu. L’algorithme de recherche du chemin de la gare est-il réutilisable tel quel pour se rendre à la mairie ? A priori non, sauf si la mairie est juste à côté de la gare. Définition : La complexité d’un algorithme est le nombre d’instructions élémentaires à exécuter pour réaliser la tâche pour laquelle il a été conçu. Si le « touriste égaré » est un piéton, la complexité de l’algorithme de recherche de chemin peut se compter en nombre de pas pour arriver à la gare. Informatique ECAM2 © L. Bidoire Mémento d’algorithmique en Python 3 3/39 Définition : L’efficacité d’un algorithme est son aptitude à utiliser de manière optimale les ressources du matériel qui l’exécute. N’existerait-il pas un raccourci piétonnier pour arriver plus vite à la gare ? L’algorithmique permet ainsi de passer d’un problème à résoudre à un algorithme qui décrit la démarche de résolution du problème. La programmation a alors pour rôle de traduire cet algorithme dans un langage « compréhensible » par l’ordinateur afin qu’il puisse exécuter l’algorithme automatiquement. Un algorithme exprime la structure logique d’un programme informatique et de ce fait est indépendant du langage de programmation utilisé. Par contre, la traduction de l’algorithme dans un langage particulier dépend du langage choisi et sa mise en œuvre dépend également de la plateforme d’exécution. La programmation d’un ordinateur consiste à lui « expliquer » en détail ce qu’il doit faire, en sachant qu’il ne « comprend » pas le langage humain, mais qu’il peut seulement effectuer un traitement automatique sur des séquences de 0 et de 1. Un programme n’est rien d’autre qu’une suite d’instructions, encodées en respectant de manière très stricte un ensemble de conventions fixées à l’avance par un langage informatique. La machine décode alors ces instructions en associant à chaque « mot » du langage informatique une action précise. Le programme que nous écrivons dans le langage informatique à l’aide d’un éditeur (une sorte de traitement de texte spécialisé) est appelé programme source (ou code source). Du problème au code source Pour « parler » à un ordinateur, il nous faudra donc utiliser des systèmes de traduction automatiques, capables de convertir en nombres binaires des suites de caractères formant des mots-clés (anglais en général) qui seront plus significatifs pour nous. Le système de traduction proprement dit s’appellera interpréteur ou bien compilateur, suivant la méthode utilisée pour effectuer la traduction. Définition : Un compilateur est un programme informatique qui traduit un langage, le langage source, en un autre, appelé le langage cible. Définition : Un interpréteur est un outil informatique (logiciel ou matériel) ayant pour tâche d’analyser et d’exécuter un programme écrit dans un langage source. Du code source à son exécution On appellera langage de programmation un ensemble de mots-clés (choisis arbitrairement) associé à un ensemble de règles très précises indiquant comment on peut assembler ces mots pour former des « phrases » que l’interpréteur ou le compilateur puisse traduire en langage machine (binaire). Définition : Un langage de programmation est un langage informatique, permettant à un humain d’écrire un code source qui sera analysé par un ordinateur. Le code source subit ensuite une transformation ou une évaluation dans une forme exploitable par la machine, ce qui permet d’obtenir un programme. Les langages permettent souvent de faire abstraction des mécanismes bas niveaux de la machine, de sorte que le code source représentant une solution puisse être rédigé et compris par un humain. Informatique ECAM2 © L. Bidoire Mémento d’algorithmique en Python 3 4/39 Définition : La programmation est l’activité de rédaction du code source d’un programme. Compilation : La compilation consiste à traduire la totalité du code source en une fois. Le compilateur lit toutes les lignes du programme source et produit une nouvelle suite de codes appelé programme objet (ou code objet). Celui-ci peut désormais être exécuté indépendamment du compilateur et être conservé tel quel dans un fichier (« fichier exécutable»). Les langages Ada, C, C++ et Fortran sont des exemples de langages compilés. Interprétation : L’interprétation consiste à traduire chaque ligne du programme source en quelques instructions du langage machine, qui sont ensuite directement exécutées au fur et à mesure (« au fil de l’eau »). 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. Ada Lovelace (1815 – 1852), première programmeuse de l’histoire, donne son prénom au langage Ada (1980) L’interprétation est idéale lorsque l’on est en phase d’apprentissage du langage, ou en cours d’expérimentation sur un projet. Avec cette technique, on peut en effet tester immédiatement toute modification apportée au programme source, sans passer par une phase de compilation qui demande toujours du temps. Mais lorsqu’un projet comporte des fonctionnalités complexes qui doivent s’exécuter rapidement, la compilation est préférable. Semi-compilation : Certains langages tentent de combiner les deux techniques afin de retirer le meilleur de chacune. C’est uploads/Science et Technologie/ memento-dalgorithmique-ecam2-python-3.pdf