au sommaire
Bien que parfois nous ne nous en rendions pas compte, nous utilisons des algorithmes dans notre vie quotidienne.
Qu’est-ce qu’un l’algorithme ?
L'algorithme est simplement une « recette » pour exécuter une tâche ou résoudre un problème. L'informatique utilise beaucoup cet outil, dans le domaine de la programmation notamment.
Un aspect très important des algorithmes est l'efficacité. Pour de nombreux problèmes, il est assez facile de trouver une procédure qui finit par donner la bonne réponse, mais la véritable difficulté réside dans la recherche d'un algorithme qui trouve la réponse de manière efficace.
Exemple d’algorithme
Alice et Charles jouent à un jeu : Alice pense à un nombre entre 1 et 100 et Charles essaie de le deviner. Charles peut demander un nombre particulier, et Alice répond si ce nombre est celui auquel elle pense ou si le nombre est plus grand ou plus petit qu'elle ne le pense.
Charles peut simplement demander 1, puis 2, puis 3, et ainsi de suite jusqu'à ce qu'Alice réponde qu'il a raison. Cet algorithme est très simple et fonctionne toujours. Mais comparons-le à cet autre algorithme : Charles commence par proposer le nombre 50. S'il réussit, le jeu est terminé. En revanche, si Alice répond que le nombre est plus élevé, Charles va continuer et proposer 75. Ou bien, si Alice répond que le nombre est plus petit, le prochain nombre que Charles suggère est 25. Charles répète cette stratégie plusieurs fois, en réduisant à chaque fois de moitié la plage de numéros possibles, jusqu'à ce qu'il atteigne sans équivoque le nombre choisi par Alice.
Ce deuxième algorithme trouve également la réponse à chaque fois, mais il est beaucoup plus efficace. Ainsi, avec le premier algorithme, Charles peut avoir à poser jusqu'à 100 questions alors qu'avec le second algorithme, quel que soit le nombre choisi par Alice, Charles posera 6 questions au maximum. Cette idée de « réduction de moitié » est très courante dans le domaine de l'algorithmique.
Pour résumer, l'algorithmique comprend l'étude de la résolutionrésolution de problèmes par la mise en œuvre de suites d'opérations élémentaires selon un processus défini aboutissant à une solution.
