Remerciez-le!

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

Cours pour apprendre les bases de l'algorithmique Par M. Delest Date de publica

Cours pour apprendre les bases de l'algorithmique Par M. Delest Date de publication : 3 novembre 2016 Un algorithme est une procédure de calcul bien définie qui prend en entrée un ensemble de valeurs et qui délivre en sortie un ensemble de valeurs. Le but de ce cours est de vous apprendre les bases de l'algorithmique. Commentez Cours pour apprendre les bases de l'algorithmique par M. Delest I - Introduction..............................................................................................................................................................5 I-A - Notion d'algorithme........................................................................................................................................ 5 I-B - Notion de complexité..................................................................................................................................... 6 I-C - Langage de description d'algorithmes...........................................................................................................6 II - Codage et structures de contrôle.......................................................................................................................... 6 II-A - Définitions......................................................................................................................................................6 II-B - Types de base.............................................................................................................................................. 7 II-B-1 - Booléens...............................................................................................................................................7 II-B-2 - Entiers...................................................................................................................................................8 II-B-3 - Réels.....................................................................................................................................................8 II-B-4 - Caractères............................................................................................................................................ 8 II-B-5 - Attention................................................................................................................................................8 II-B-6 - Comparaison.........................................................................................................................................8 II-C - Structures de contrôle...................................................................................................................................8 II-D - Fonctions.......................................................................................................................................................9 II-D-1 - Syntaxe...............................................................................................................................................10 II-D-2 - Utilisation............................................................................................................................................ 10 II-D-3 - Exemple..............................................................................................................................................10 III - Description d'algorithme - Langage EXALGO.................................................................................................... 11 III-A - Généralités................................................................................................................................................. 11 III-B - Type............................................................................................................................................................11 III-C - Variables.....................................................................................................................................................11 III-D - Expressions................................................................................................................................................11 III-E - Instructions simples....................................................................................................................................11 III-F - Structure de contrôle..................................................................................................................................11 III-G - Fonctions....................................................................................................................................................12 III-H - Types..........................................................................................................................................................12 III-H-1 - Type structuré....................................................................................................................................12 III-H-2 - Type pointeur.....................................................................................................................................13 IV - Structures de données....................................................................................................................................... 13 IV-A - Définition.................................................................................................................................................... 13 IV-B - Structure.....................................................................................................................................................14 IV-C - Table d'association à clé unique............................................................................................................... 15 V - Complexité........................................................................................................................................................... 15 V-A - Définitions................................................................................................................................................... 15 V-B - Structures de contrôle................................................................................................................................ 16 V-C - Exemples.................................................................................................................................................... 17 V-C-1 - Somme des N premiers entiers.........................................................................................................17 V-C-2 - Apparition d'une pile dans une suite de n lancers d'une pièce......................................................... 17 V-D - Les courbes « étalon »...............................................................................................................................19 V-D-1 - n, log(n), nlog(n)................................................................................................................................ 19 V-D-2 - nlog(n), n2, n3................................................................................................................................... 19 V-D-3 - n2, 1.5n ,2n........................................................................................................................................20 V-D-4 - 2n, nn n !............................................................................................................................................20 V-E - Formule de Stirling..................................................................................................................................... 21 VI - Tableaux..............................................................................................................................................................21 VI-A - Définition.................................................................................................................................................... 21 VI-B - Primitives....................................................................................................................................................22 VI-B-1 - Initialisation d'un tableau...................................................................................................................22 VI-B-2 - Taille d'un tableau............................................................................................................................. 22 VI-B-3 - Échange d'éléments..........................................................................................................................22 VI-B-4 - Copie de tableau...............................................................................................................................23 VI-C - Quelques exemples d'algorithmes............................................................................................................ 24 VI-C-1 - Somme des éléments d'un tableau d'entiers....................................................................................24 VI-C-2 - Recherche d'un élément...................................................................................................................24 VI-C-3 - Recherche de l'indice du premier élément minimum........................................................................25 VI-D - Matrices..................................................................................................................................................... 25 VI-D-1 - Déclaration........................................................................................................................................ 25 - 2 - Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 M. Delest. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://algo.developpez.com/tutoriels/initiation/ Cours pour apprendre les bases de l'algorithmique par M. Delest VI-D-2 - Initialisation........................................................................................................................................25 VI-D-3 - Somme de deux matrices réelles.....................................................................................................26 VII - Tri non récursif...................................................................................................................................................26 VII-A - Tri sélection...............................................................................................................................................26 VII-B - Tri insertion et tri à bulle.......................................................................................................................... 27 VII-B-1 - Tri insertion.......................................................................................................................................27 VII-B-2 - Tri à bulle......................................................................................................................................... 27 VII-C - Fusion de tableaux triés...........................................................................................................................28 VII-D - Tri par dénombrement..............................................................................................................................28 VII-E - Algorithme de fusion de deux tableaux....................................................................................................29 VII-E-1 - Aide.................................................................................................................................................. 29 VII-E-2 - Algorithme de fusion........................................................................................................................ 29 VII-E-3 - Algorithme de fusion pour des morceaux de tableaux.................................................................... 30 VIII - Retour sur les fonctions, récursivité.................................................................................................................30 VIII-A - Visibilité.................................................................................................................................................... 30 VIII-A-1 - Visibilité d'une variable....................................................................................................................30 VIII-A-2 - Exemple...........................................................................................................................................31 VIII-A-3 - Visibilité d'une fonction....................................................................................................................31 VIII-A-3-a - Exemple..................................................................................................................................31 VIII-B - Récursivité............................................................................................................................................... 32 VIII-C - Complexité...............................................................................................................................................34 VIII-D - Exemples................................................................................................................................................. 35 VIII-D-1 - Recherche d'un élément dans un tableau d'entiers....................................................................... 35 VIII-D-2 - Minimum dans un tableau d'entiers................................................................................................35 IX - Diviser pour régner.............................................................................................................................................36 IX-A - Dichotomie................................................................................................................................................. 36 IX-B - Exemples................................................................................................................................................... 36 IX-B-1 - Recherche du zéro d'une fonction croissante...................................................................................36 IX-B-2 - Trouver un élément dans un tableau ordonné..................................................................................36 IX-B-3 - Remarque..........................................................................................................................................37 IX-C - Complexité.................................................................................................................................................38 X - Tris récursifs........................................................................................................................................................ 39 X-A - Tri fusion..................................................................................................................................................... 39 X-B - Tri rapide.....................................................................................................................................................40 XI - Une implémentation des polynômes.................................................................................................................. 41 XI-A - Énoncé.......................................................................................................................................................41 XI-B - Structure et primitives................................................................................................................................41 XI-B-1 - Structure............................................................................................................................................41 XI-B-2 - Addition..............................................................................................................................................41 XI-B-3 - Multiplication......................................................................................................................................42 XI-B-4 - Polynôme opposé............................................................................................................................. 42 XI-B-5 - Multiplication par xn.......................................................................................................................... 42 XI-B-6 - Dérivée.............................................................................................................................................. 43 XI-B-7 - Valeur en un point.............................................................................................................................43 XI-B-8 - Intégrale définie.................................................................................................................................44 XI-C - Amélioration de la complexité................................................................................................................... 44 XI-C-1 - Valeur en un point............................................................................................................................ 44 XI-D - Multiplication.............................................................................................................................................. 44 XII - Listes..................................................................................................................................................................47 XII-A - Définition................................................................................................................................................... 47 XII-B - Liste simplement chainée.........................................................................................................................47 XII-B-1 - Test de fin de liste........................................................................................................................... 48 XII-B-2 - Chercher un élément dans une liste................................................................................................48 XII-B-3 - Trouver le dernier élément...............................................................................................................49 XII-C - Liste doublement chaînée........................................................................................................................ 49 XII-C-1 - Supprimer un élément..................................................................................................................... 49 XII-D - Quelques algorithmes...............................................................................................................................50 XII-D-1 - Taille................................................................................................................................................. 50 - 3 - Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 M. Delest. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://algo.developpez.com/tutoriels/initiation/ Cours pour apprendre les bases de l'algorithmique par M. Delest XII-D-2 - Insérer dans une liste triée..............................................................................................................50 XIII - Une implémentation de liste simplement chaînée de caractères.....................................................................50 XIII-A - Qu'est-ce qu'implémenter........................................................................................................................ 50 XIII-B - Choix de la structure............................................................................................................................... 51 XIII-C - Primitives d'accès....................................................................................................................................51 XIII-D - Gestion de l'espace de stockage............................................................................................................51 XIII-E - Primitives de modifications......................................................................................................................52 XIV - Remerciements.................................................................................................................................................53 - 4 - Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 M. Delest. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://algo.developpez.com/tutoriels/initiation/ Cours pour apprendre les bases de l'algorithmique par M. Delest I - Introduction I-A - Notion d'algorithme Définition 1.1. Un algorithme est une procédure de calcul bien définie qui prend en entrée un ensemble de valeurs et qui délivre en sortie un ensemble de valeurs. Exemple 1.1 Problème : trier une suite de nombres entiers dans l'ordre croissant. Entrée : suite de n nombres entiers ( ) Sortie : une permutation de la suite donnée en entrée ( ) telle que . À partir de la suite (6,9,2,4), un algorithme de tri fournira le résultat (2,4,6,9). Définition 1.2. Une valeur particulière de l'ensemble des valeurs données en entrée est appelée instance du problème. Exemple 1.1 (suite) La valeur (6,9,2,4) est une instance du problème. Définition 1.3. Un algorithme est correct, si pour toute instance du problème il se termine et produit une sortie correcte. Les algorithmes peuvent être spécifiés en langage humain ou tout langage informatique. Dans ce qui suit, nous utiliserons un langage proche du langage naturel. Nous donnerons une implémentation en Python (voir cours MISMI MIS 102). Définition 1.4. Une heuristique est une procédure de calcul correcte pour certaines instances du problème (c'est- à-dire se termine ou produit une sortie correcte). Ce cours n'aborde pas les heuristiques. Pour qu'un algorithme puisse être décrit et s'effectue, les données d'entrées doivent être organisées. Définition 1.5. Une structure de données est un moyen de stocker et d'organiser des données pour faciliter leur stockage, leur utilisation et leur modification. De nombreux problèmes nécessitent des algorithmes : • bio-informatique ; • moteur de recherche sur Internet ; • commerce électronique ; • affectation de tâches. Définition 1.6. L'efficacité d'un algorithme est mesurée par son coût (complexité) en temps et en mémoire. Un problème NP-complet est un problème pour lequel on ne connaît pas d'algorithme correct efficace, c'est-à-dire réalisable en temps et en mémoire. Le problème le plus célèbre est le problème du voyageur de commerce. L'ensemble des problèmes NP-complets ont les propriétés suivantes : • si on trouve un algorithme efficace pour un problème NP complet alors il existe des algorithmes efficaces pour tous ; • personne n'a jamais trouvé un algorithme efficace pour un problème NP-complet ; - 5 - Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2016 M. Delest. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://algo.developpez.com/tutoriels/initiation/ Cours pour apprendre les bases de l'algorithmique par M. Delest • personne n'a jamais prouvé qu'il ne peut pas exister d'algorithme efficace pour un problème NP-complet particulier. I-B - Notion de complexité L'efficacité d'un algorithme est fondamentale pour résoudre effectivement des problèmes. Exemple1.2. Supposons que l'on dispose de deux ordinateurs. L'ordinateur A est capable d'effectuer 109 instructions par seconde. L'ordinateur uploads/S4/ initiation-algorithme.pdf