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 pour le lycée – Éric Sopena N1MA0011 1 version du mercredi 9 janv

Algorithmique pour le lycée – Éric Sopena N1MA0011 1 version du mercredi 9 janvier 2013 Master Sciences, Technologies, Santé Mention Mathématiques, spécialité Enseignement des mathématiques N1MA0011 Algorithmique et graphes, thèmes du second degré ALGORITHMIQUE POUR LE LYCÉE Éric SOPENA Eric.Sopena@labri.fr SOMMAIRE Chapitre 1. Notions de base d’algorithmique........................................................................ 5 1.1. Qu’est-ce qu’un algorithme ?.................................................................................................... 5 1.2. Structure d’un algorithme.......................................................................................................... 6 1.3. La notion de variable, l’affectation ........................................................................................... 7 1.4. Opérations d’entrée-sortie......................................................................................................... 9 1.5. Initialisation de variables......................................................................................................... 10 1.6. Enchaînement séquentiel ........................................................................................................ 10 1.7. Structures conditionnelles ...................................................................................................... 10 1.7.1. Alternative simple ...............................................................................................................................11 1.7.2. Structure à choix multiple..................................................................................................................12 1.8. Structures répétitives............................................................................................................... 13 1.8.1. Tant que faire.......................................................................................................................................13 1.8.2. Répéter jusqu’à ...................................................................................................................................14 1.8.3. Boucle pour .........................................................................................................................................15 1.9. Exécution « manuelle » d’un algorithme................................................................................ 16 1.10. Les listes ................................................................................................................................... 17 1.11. Primitives graphiques.............................................................................................................. 19 1.12. Répertoire des types et opérations de base .......................................................................... 20 Chapitre 2. Corpus d’exercices généraux............................................................................ 21 2.1. Affectation et opérations d’entrée-sortie ............................................................................... 21 2.2. Structures conditionnelles ...................................................................................................... 21 2.3. Structures répétitives............................................................................................................... 22 2.4. Manipulations de listes............................................................................................................ 25 N1MA0011Algorithmique pour le lycée – Éric Sopena N1MA0011 2 version du mercredi 9 janvier 2013 Chapitre 3. Corpus d’exercices liés au programme de la classe de seconde.................. 27 3.1. Fonctions .................................................................................................................................. 27 3.1.1. Images, antécédents...........................................................................................................................27 3.1.2. Étude qualitative de fonctions...........................................................................................................27 3.1.3. Résolution d’équations ......................................................................................................................27 3.1.4. Fonctions de référence.......................................................................................................................28 3.1.5. Polynômes de degré 2........................................................................................................................28 3.1.6. Fonctions homographiques...............................................................................................................28 3.1.7. Inéquations..........................................................................................................................................28 3.1.8. Trigonométrie......................................................................................................................................28 3.2. Géométrie.................................................................................................................................. 28 3.2.1. Coordonnées d’un point du plan.......................................................................................................28 3.2.2. Configurations du plan.......................................................................................................................29 3.2.3. Droites..................................................................................................................................................29 3.2.4. Vecteurs...............................................................................................................................................30 3.2.5. Géométrie dans l’espace....................................................................................................................31 3.3. Statistiques et probabilités...................................................................................................... 31 3.4. Divers......................................................................................................................................... 32 3.4.1. Intervalles ............................................................................................................................................32 3.4.2. Approximations de Pi .........................................................................................................................32 Chapitre 4. Exécution d’algorithmes avec AlgoBox ........................................................... 34 4.1. Introduction............................................................................................................................... 34 4.2. Installation du logiciel.............................................................................................................. 35 4.3. Premiers pas............................................................................................................................. 35 4.4. Quelques compléments........................................................................................................... 37 4.4.1. Le type NOMBRE.................................................................................................................................37 4.4.2. Le type LISTE. .....................................................................................................................................37 4.4.3. Définir et utiliser une fonction numérique........................................................................................39 4.4.4. Dessin ..................................................................................................................................................39 4.5. Quelques exemples illustratifs................................................................................................ 40 4.5.1. Déterminer si un nombre est ou non premier ..................................................................................40 4.5.2. Dessin d’une étoile .............................................................................................................................41 Chapitre 5. Programmer en Python...................................................................................... 43 5.1. Introduction............................................................................................................................... 43 5.2. Éléments du langage................................................................................................................ 45 5.3. Types de données élémentaires ............................................................................................. 45 5.4. Affectation et opérations d’entrée-sortie ............................................................................... 46 5.5. Structures de contrôle ............................................................................................................. 47 5.5.1. Alternative simple ...............................................................................................................................47 5.5.2. Structure à choix multiple..................................................................................................................47 5.5.3. Boucle while ........................................................................................................................................47 5.5.4. Boucle for ............................................................................................................................................48 5.6. Quelques exemples de scripts Python................................................................................... 48 5.7. Traduction d’algorithmes en Python – Tableau de synthèse............................................... 49 5.8. Dessiner en Python.................................................................................................................. 50 Chapitre 6. Pour aller (un petit peu) plus loin en Python…................................................ 53 6.1. Nombres complexes ................................................................................................................ 53 6.2. Listes ......................................................................................................................................... 53 6.3. Fonctions .................................................................................................................................. 54 N1MA0011Algorithmique pour le lycée – Éric Sopena N1MA0011 3 version du mercredi 9 janvier 2013 6.4. Visibilité des variables............................................................................................................. 55 6.5. Modules..................................................................................................................................... 56 Chapitre 7. Algorithmes de tri............................................................................................... 57 7.1. Les méthodes de tri simples ................................................................................................... 57 7.1.1. Sélection ordinaire..............................................................................................................................58 7.1.2. Insertion séquentielle .........................................................................................................................58 7.1.3. Insertion dichotomique ......................................................................................................................59 7.1.4. Tri-bulle (ou bubble sort)....................................................................................................................59 7.2. Le tri rapide : Quicksort........................................................................................................... 60 7.3. Le tri par tas : Heapsort ........................................................................................................... 63 7.4. Les méthodes de tri externe (tri-fusion)................................................................................. 66 7.4.1. Tri balancé par monotonies de longueur 2n .....................................................................................66 7.4.2. Tri balancé par monotonies naturelles .............................................................................................67 7.5. Tri de « grands objets » ........................................................................................................... 68 Algorithmique pour le lycée – Éric Sopena N1MA0011 5 version du mercredi 9 janvier 2013 Chapitre 1. Notions de base d’algorithmique 1.1. Qu’est-ce qu’un algorithme ? De façon intuitive, un algorithme décrit un enchaînement d’opérations permettant, en un temps fini, de résoudre toutes les instances d'un problème donné. Partant d’une instance du problème (les données en entrée), il fournit un résultat correspondant à la solution du problème sur cette instance. La définition du Larousse est la suivante : « ensemble de règles opératoires dont l'application permet de résoudre un problème énoncé au moyen d'un nombre fini d'opérations. Un algorithme peut être traduit, grâce à un langage de programmation, en un programme exécutable par un ordinateur ». On se doit cependant d’y apporter les compléments suivants : • un algorithme décrit un traitement sur un nombre fini de données structurées (parfois aucune). Ces données peuvent avoir une structure élémentaire (nombres, caractères, etc.), ou une structure plus élaborée (liste de nombres, annuaire, etc.). • un algorithme est composé d'un nombre fini d'opérations1. Une opération doit être bien définie (rigoureuse, non ambiguë), effective, c’est-à-dire réalisable par un ordinateur (la division entière est par exemple une opération effective alors que la division réelle, avec un nombre éventuellement infini de décimales, ne l’est pas). • un algorithme doit toujours se terminer après exécution2 d’un nombre fini d'opérations et donner un résultat. Ainsi, l'expression d'un algorithme nécessite un langage clair (compréhension), structuré (décrire des enchaînements d'opérations), non ambigu (la programmation ne supporte pas l'ambiguïté !). Il doit de plus être « universel » : un (vrai) algorithme doit être indépendant du langage de programmation utilisé par la suite (e.g. l’algorithme Euclide !). En particulier, une recette de cuisine est un très mauvais exemple d’algorithme, du fait de l’imprécision notoire des instructions qui la composent (rajouter une « pincée de sel », verser un « verre de farine », faire mijoter « à feu doux », placer au four « 45 mn environ », …). 1 Nous utiliserons le terme d’opération en algorithmique, er réserverons le terme d’instruction pour désigner leur équivalent en programmation. 2 On s’autorisera fréquemment cet abus de langage. Il s’agit bien évidemment ici de l’exécution d’un programme implantant l’algorithme considéré. Algorithme est un terme dérivé du nom du mathématicien Muhammad ibn Musa al-Khwarizmi (Bagdad, 783-850) qui a notamment travaillé sur la théorie du système décimal (il est l’auteur d’un précis sur l'Al-Jabr qui, à l’époque, désignait la théorie du calcul, à destination des architectes, astronomes, etc.) et sur les techniques de résolution d'équations du 1er et 2ème degré (Abrégé du calcul par la restauration et la comparaison, publié en 825). La notion d'algorithme est cependant plus ancienne : Euclide (3e siècle av. JC, pgcd, division entière), Babyloniens (1800 av. JC, résolution de certaines équations). Lors de la conception d’un algorithme, on doit être attentif aux points suivants : N1MA0011Algorithmique pour le lycée – Éric Sopena N1MA0011 6 version du mercredi 9 janvier 2013 • Adopter une méthodologie de conception : l’analyse descendante consiste à bien penser l'architecture d'un algorithme. On décompose le problème, par affinements successifs, en sous- problèmes jusqu'à obtenir des problèmes simples à résoudre ou dont la solution est connue. On obtient ainsi un schéma général de découpage du problème. On résout les sous-problèmes et, en composant ces différentes solutions, on obtient une solution du problème général. • Utiliser la modularité : spécification claire des modules construits, réutilisation de modules existants, en évitant les modules trop spécifiques, afin de garantir un bon niveau de réutilisabilité (cet aspect se situe cependant au-delà du contenu du programme de la classe de seconde). • Être attentif à la lisibilité, la « compréhensibilité » : en soignant en particulier la mise en page, la qualité de la présentation, en plaçant des commentaires pertinents, et en choisissant des identificateurs parlants. • Se soucier du coût de l'algorithme : notion de complexité en temps (nombre d’opérations nécessaires à la résolution d’un problème de taille donnée), de complexité en espace (taille mémoire nécessaire à la résolution d’un problème de taille donnée). • Ne pas chercher à « réinventer la roue » : cela nécessite une bonne culture algorithmique (problèmes et solutions standards, techniques usuelles de résolution, etc.). Le schéma suivant permet de situer la place de l’algorithmique dans le cadre général du développement (traditionnel, maintenant dépassé) d’une application informatique : Lors de la conception d’un algorithme, on doit avoir à l’esprit trois préoccupations essentielles : • La correction de l’algorithme. Il s’agit ici de s’assurer (il est souvent possible d’en donner une « preuve mathématique ») que les résultats produits par l’algorithme sont corrects (l’algorithme réalise bien ce pour quoi il a été conçu) et ce, quelles que soient les (valeurs des) données de départ. • La terminaison de l’algorithme. Tout algorithme doit effectuer ce pour quoi il a été conçu en un temps fini. Il est donc nécessaire de s’assurer que l’algorithme termine toujours et, là encore, quelles que soient les données de départ. • La complexité de l’algorithme. La complexité en espace fait référence à l’espace mémoire nécessaire à l’exécution d’un algorithme (directement lié à l’espace mémoire nécessaire pour stocker les différentes données) et la complexité en temps au temps nécessaire à celle-ci. En réalité, la complexité permet de mesurer l’évolution, de l’espace ou du temps nécessaires, en fonction de l’évolution de la taille des données de départ. Ainsi, un algorithme linéaire en temps est un algorithme dont le temps d’exécution dépend linéairement de la taille des données (pour traiter 10 fois plus de données, il faut 10 fois plus de temps). On se doit de garder à l’esprit la distinction indispensable entre algorithme et programme. L’algorithme décrit une méthode de résolution d’un problème donné et possède un caractère universel, qui permet de l’implanter dans la plupart (sinon tous) des langages de programmation. Un programme n’est alors que la traduction de uploads/Ingenierie_Lourd/ algorithmique-pour-le-lycee-03.pdf