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 l'apprenti programmeur Par bluestorm , Cygal et lastsseldon

Algorithmique pour l'apprenti programmeur Par bluestorm , Cygal et lastsseldon www.openclassrooms.com Licence Creative Commons 7 2.0 Dernière mise à jour le 10/08/2011 Sommaire 2 Sommaire ........................................................................................................................................... 2 Partager .............................................................................................................................................. 4 Algorithmique pour l'apprenti programmeur ....................................................................................... 4 But du tutoriel .................................................................................................................................................................... 4 Prérequis ........................................................................................................................................................................... 4 Historique .......................................................................................................................................................................... 5 Partie 1 : Présentation de la notion de complexité algorithmique ....................................................... 6 Qu'est-ce qu'un algorithme ? ............................................................................................................................................ 6 Omniprésence des algorithmes .................................................................................................................................................................................. 6 Rôle privilégié des ordinateurs .................................................................................................................................................................................... 6 Notion de structure de données .................................................................................................................................................................................. 7 Les grenouilles partent en vacances ................................................................................................................................ 8 Situation ...................................................................................................................................................................................................................... 8 Les deux possibilités ................................................................................................................................................................................................... 8 Tous les ans : choix personnalisé ............................................................................................................................................................................... 9 Cette année : choix de groupe .................................................................................................................................................................................... 9 Comparaison ............................................................................................................................................................................................................... 11 La notion de complexité ................................................................................................................................................... 11 Correction de l'algorithme .......................................................................................................................................................................................... 11 Complexité ................................................................................................................................................................................................................. 12 Mesure 'asymptotique' ............................................................................................................................................................................................... 12 Notation "grand O" .................................................................................................................................................................................................... 13 Complexité en temps, complexité mémoire .............................................................................................................................................................. 13 Complexité dans le pire des cas ............................................................................................................................................................................... 15 Un peu de pratique .......................................................................................................................................................... 15 Qu'est-ce qu'on attend de vous ? .............................................................................................................................................................................. 15 Chercher le plus grand / petit élément ...................................................................................................................................................................... 16 Trouver les éléments uniques ................................................................................................................................................................................... 16 Solution proposée ..................................................................................................................................................................................................... 17 Complexité ................................................................................................................................................................................................................ 18 Trouver les éléments uniques : autre solution ........................................................................................................................................................... 20 Partie 2 : Premiers exemples de structures de données et d'algorithmes courants .......................... 20 Notions de structures de données : tableaux et listes chaînées ..................................................................................... 20 Définition ................................................................................................................................................................................................................... 20 Tableaux .................................................................................................................................................................................................................... 21 Listes ......................................................................................................................................................................................................................... 22 Ajout / retrait, taille, accès à un élément ................................................................................................................................................................... 22 Ajout / Retrait ............................................................................................................................................................................................................. 24 Taille .......................................................................................................................................................................................................................... 24 Accès à un élément ................................................................................................................................................................................................... 25 Concaténation, filtrage .............................................................................................................................................................................................. 25 Concaténation ........................................................................................................................................................................................................... 27 Filtrage ...................................................................................................................................................................................................................... 28 Synthèse ................................................................................................................................................................................................................... 28 Opérations ................................................................................................................................................................................................................. 28 Conversions .............................................................................................................................................................................................................. 29 Attention aux langages de moches .......................................................................................................................................................................... 30 Une classe d'algorithme non naïfs : diviser pour régner ................................................................................................. 30 Gagner au jeu du 'Plus ou Moins' .............................................................................................................................................................................. 30 Dichotomie : Recherche dans un dictionnaire ........................................................................................................................................................... 31 Calcul de la complexité ............................................................................................................................................................................................. 32 Trouver un zéro d'une fonction .................................................................................................................................................................................. 35 Diviser pour régner : exponentiation rapide .............................................................................................................................................................. 37 Introduction au problème du tri ....................................................................................................................................... 37 Formuler le problème du tri ....................................................................................................................................................................................... 37 Question de la structure de donnée .......................................................................................................................................................................... 37 Tri par sélection ......................................................................................................................................................................................................... 38 Complexité ................................................................................................................................................................................................................ 39 Implémentation du tri par sélection ........................................................................................................................................................................... 39 Pour une liste ............................................................................................................................................................................................................ 40 Pour un tableau ......................................................................................................................................................................................................... 42 Comparaison ............................................................................................................................................................................................................. 42 Tri par insertion ......................................................................................................................................................................................................... 42 Le retour du "diviser pour régner" : Tri fusion ............................................................................................................................................................ 43 Algorithme ................................................................................................................................................................................................................. 44 Implémentation avec des listes ................................................................................................................................................................................. 48 Implémentation avec des tableaux ............................................................................................................................................................................ 49 Complexité ................................................................................................................................................................................................................ 50 Efficacité en pratique ................................................................................................................................................................................................. 52 Partie 3 : Quelques autres structures de données courantes ........................................................... 53 Piles et files ..................................................................................................................................................................... 53 Concept ..................................................................................................................................................................................................................... 2/70 www.openclassrooms.com 54 Mise en pratique ........................................................................................................................................................................................................ 54 Piles .......................................................................................................................................................................................................................... 55 Files ........................................................................................................................................................................................................................... 58 Arbres .............................................................................................................................................................................. 59 Définition ................................................................................................................................................................................................................... 62 Quelques algorithmes sur les arbres ........................................................................................................................................................................ 62 Taille .......................................................................................................................................................................................................................... 64 Hauteur ...................................................................................................................................................................................................................... 64 Liste des éléments .................................................................................................................................................................................................... 65 Parcours en profondeur ............................................................................................................................................................................................. 66 Parcours en largeur ................................................................................................................................................................................................... 66 En mettant des couches ............................................................................................................................................................................................ 67 Avec une file .............................................................................................................................................................................................................. 68 Comparaison des méthodes de parcours ................................................................................................................................................................. 68 Une symétrie assez surprenante ............................................................................................................................................................................... 68 Choix de l'implémentation ......................................................................................................................................................................................... 68 Analyse de complexité .............................................................................................................................................................................................. 69 Utilisation en pratique ................................................................................................................................................................................................ Sommaire 3/70 www.openclassrooms.com Algorithmique pour l'apprenti programmeur Par bluestorm et lastsseldon et Cygal Mise à jour : 10/08/2011 Difficulté : Facile V ous venez d'apprendre les bases d'un langage de programmation ? V ous vous êtes peut-être rendu compte que parfois, en modifiant un peu votre programme, vous pouvez obtenir le même résultat mais 2, 10 ou 1000 fois plus vite ? De telles améliorations ne sont pas le fruit du hasard, ni même dues à une augmentation de la mémoire vive ou à un changement de processeur : il y a plusieurs manières de programmer quelque chose et certaines sont incroyablement meilleures que d'autres. Avec un peu de réflexion, et des outils théoriques de base, vous serez vous aussi en mesure de faire de bons choix pour vos programmes. À la fin de ce tutoriel, vous serez de meilleurs développeurs, en mesure de comprendre, corriger et concevoir des programmes plus efficaces. But du tutoriel Les deux notions clés de ce tutoriel sont les suivantes : la complexité, et les structures de données. La complexité est une manière d'estimer les performances d'un algorithme. Les structures de données sont la manière dont vous organisez les informations dans votre programme. En choisissant une structure de données adaptée, vous serez capables de coder des opérations très performantes (de faible complexité). Chaque algorithme résout un problème donné. Pour chaque problème, il existe un ou plusieurs algorithmes intéressants (mais on en découvre de nouveaux tous les ans !). Nous vous présenterons, dans ce tutoriel, un petit panorama de problèmes "courants", dans le but de vous familiariser avec la complexité et les structures de données. V ous apprendrez par exemple à chercher un élément qui vous intéresse à l'intérieur d'un ensemble d'éléments, à trier un ensemble, ou même à trouver le plus court chemin d'un "endroit" à un autre. Prérequis Le but de ce tutoriel n'est pas de vous apprendre à programmer. Pour le lire, vous devez déjà savoir programmer. L'apprentissage de l'algorithmique n'utilise pas de concepts bas niveau (assembleur, etc.) ou de bibliothèques logicielles spécialisées (SDL, Qt...), mais vous devez être à l'aise avec les variables, conditions, boucles et fonctions. La connaissance du concept de 'récursivité' (si vous vous sentez en manque, il y a déjà un tuto à ce sujet sur le SDZ) est aussi un avantage. Le langage que vous utilisez n'est pas très important, car on tentera de formuler les algorithmes d'une manière qui en est indépendante. Nous donnerons aussi, pour les curieux, des exemples dans quelques langages de programmation. Si vous n'y voyez pas le vôtre, trouvez-en un suffisamment proche, et faites un petit effort. La complexité algorithmique est une mesure formelle de la complexité d'un algorithme. Elle s'exprime donc en langage mathématique. Le calcul de certains algorithmes avancés est très compliqué et demande des connaissances mathématiques poussées. Cependant, notre tutoriel se concentre sur des choses simples, et devrait être largement accessible : une connaissance des puissances et des racines (carrées) devrait suffire à être à l'aise. Un objet plus avancé, la fonction logarithme, sera présenté et expliqué avant son utilisation. Historique Ce tutoriel est en cours d'écriture. V ous l'avez déjà lu, et vous voulez savoir si quelque chose a été rajouté ? V oici un historique des modifications, les plus récentes en premier : 08 août 2011 : correction d'une bévue repérée par Arnolddu51, et clarification par Cygal de la recherche de racine par Sommaire 4/70 www.openclassrooms.com dichotomie, suite à une question de bouboudu21 15 juin 2010 : révision de l'implémentation C du tri par fusion sur les listes 13 juin 2010 : diverses reformulations suite aux commentaires des lecteurs (candide, Equinoxe, programLyrique) 12 juin 2010 : implémentation en C du tri par sélection sur les tableaux juillet 2009 : correction de quelques typos, clarification de certains passages 26 avril 2009 : ajout d'exemples de code pour le chapitre sur les arbres 25 avril 2009 : ajout d'icônes pour les chapitres existants 22 avril 2009 (partie 3) ajout du deuxième chapitre : arbres; les exemples de code sont à venir 20 avril 2009 (partie 3) ajout d'un premier chapitre, assez simple, sur les piles et les files 27 février 2009 (partie 1) reformulation et clarification de certains paragraphes 22 février 2009 : ajout de l'historique, présentation d'un site d'exercices en fin de deuxième partie 18 février 2009 (partie 2) ajout d'exemples de code C pour les listes chaînées 11 février 2009 (partie 2) chapitre "Introduction au problème du tri" janvier 2009 : zcorrection par ptipilou (rédaction arrêtée à cause d'un bug du SdZ) mi octobre 2008 (partie 2) chapitre "Notions de structures de données : tableaux et listes chaînées" début septembre 2008 (partie 2) chapitre "Une classe d'algorithme non naïfs : diviser pour régner", par lasts et Cygal mi août 2008 (partie 1) publication de la première partie Algorithmique pour l'apprenti programmeur 5/70 www.openclassrooms.com Partie 1 : Présentation de la notion de complexité algorithmique Qu'est-ce qu'un algorithme ? Un algorithme est la description précise, sous forme de concepts simples, de la manière dont on peut résoudre un problème. Dans la vie de tous les jours, nous avons souvent besoin de résoudre des problèmes. Surtout si on considère la notion de "problème" au sens large. Omniprésence des algorithmes Un exemple de problème qui nous concerne tous (oui, même vous) est celui de la cuisine : vous êtes dans une cuisine, vous trouvez du riz, comment le cuire ? V oici une marche à suivre simple : remplir une casserole d'eau ; y ajouter une pincée de sel ; la mettre sur le feu ; attendre l'ébullition de l'eau ; mettre le riz dans la casserole ; le laisser cuire 10 à 15 minutes ; égoutter le riz. J'ai décrit une solution au problème "il faut faire cuire du riz", sous forme de concepts simples. V ous remarquerez qu'il y a pourtant beaucoup de uploads/Ingenierie_Lourd/ algorithmique-pour-l-apprenti-programmeur.pdf