Algorithmique pour lapprenti programmeur. Algorithmique pour l'apprenti programmeur. Vous venez d'apprendre les bases d'un langage de programmation ? Vous 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. Chaque algorithme résout un problème donné. Prérequis. Les arbres de décisions. Les arbres binaires de recherche. Lorsque l'on parle d'arbres, bien des gens penseront de prime abord à la biologie, la botanique et donc aux arbres tels que vous pouvez sûrement les voir en jetant un coup d'œil par votre fenêtre.
Cependant, les arbres se retrouvent dans un ensemble de domaines tous plus variés les uns que les autres, et c'est sur l'algorithmique que nous allons nous pencher ici. Les arbres ont effectivement inspiré les algorithmiciens de la deuxième moitié du vingtième siècle, les amenant à créer une structure de données révolutionnaire : les arbres binaires de recherche. Qu'est-ce que c'est, à quoi ça sert, comment ça marche, comment les implémenter, comment les améliorer ; ce sont autant de questions qui seront abordées dans ce cours, qui va, je l'espère de tout cœur, vous brancher sans vous faire prendre racine ! Un mot sur les prérequis Dans la mesure où ce cours traite d'algorithmique, une connaissance basique dans ce domaine sera nécessaire pour ne pas se perdre dans les explications.
Définitions. Découverte des algorithmes de graphe. Ce tutoriel va vous expliquer ce qu'est un graphe, et à quoi il sert.
Il détaillera les algorithmes de graphe les plus courants, en indiquant leur complexité en temps et en mémoire, avec peut-être des schémas si vous êtes sages. Chaque algorithme sera accompagné d'un pseudo-code pour laisser au programmeur l'opportunité de le coder dans son langage favori. Le cours est ouvert aux contributions : vous pouvez m'envoyer une implémentation de l'algorithme dans le langage de votre choix et je l'y ajouterais. Il sera appuyé d'exemples concrets pour que l'intérêt de chaque algorithme apparaisse dans une situation courante. L'objectif est d'apprendre à reconnaître des problèmes de graphe, ou à modéliser un problème sous forme de graphe, pour le résoudre avec des outils éprouvés et efficaces.
Ce document n'a pas pour ambition de faire une démonstration formelle de la complexité ou de la validité des algorithmes. Le tri par sélection. Le tri par insertion. Comment peut-on évaluer la rapidité de cet algorithme ? On pourrait mesurer son temps d'exécution sur mon ordinateur, mais cela n'est pas fiable parce que si on change d'ordinateur, le temps d'exécution change aussi : il peut être très rapide chez mon voisin (qui a un super PC) et très lent chez moi.
Une mesure plus rigoureuse de la "rapidité" de l'algorithme serait de mesurer le "nombre d'opérations" qu'il effectue : que ce soit chez moi ou chez mon voisin, pour trier le même tableau, il va effectuer le même nombre d'opérations, mais pas à la même vitesse. La récursivité. Le backtracking par l'exemple : résoudre un sudoku.
Analyse et critique du code Le code ci-dessus est-il parfait ?
Non, car on pourrait lui reprocher plusieurs points : Pire des cas Même si le code que nous avons écrit fournira en général la solution assez rapidement (moins d'une demi seconde chez moi), les performances dépendent totalement de la grille passée en entrée. Certaines grilles spécialement conçues peuvent lui demander beaucoup plus de travail, ce qui montre bien que la complexité dans le pire des cas n'est pas si bonne que cela.
L'image ci-contre (source - Wikipédia) est un exemple d'une telle grille. Pour pallier à cet inconvénient, essayons de réfléchir si l'on peut améliorer l'exploration des possibilités de manière à ce que la bonne solution sorte au plus tôt. Optimisation Considérons quelques points : Il apparait que si nous effectuons le backtracking depuis les cases avec un minimum de solutions vers les cases avec un maximum de solutions, nous minimisons sensiblement l'exploration des possibilités. Voici un code possible :