Extrait du cours écriture et comparaison des algorithmes, tris

Première partie: Écriture et comparaison des algorithmes, tris
Chapitre 1: Introduction
1.1 La notion d’algorithme
Un algorithme est un procédé permettant l’accomplissement mécanique d’une tâche assez générale.
Cette tâche peut être par exemple la résolution d’un problème mathématique ou, en informatique, un problème d’organisation, de structuration ou de création de données. Un algorithme est décrit par une suite d’opérations simples à effectuer pour accomplir cette tâche. Cette description est finie et destinée à des humains. Elle ne doit pas produire de boucles infinies : étant donné une situation initiale (une instance du problème, une donnée particulière), elle doit permettre d’accomplir la tâche en un nombre fini d’opérations.
Quelques exemples de problèmes pour lesquels on utilise des algorithmes : rechercher un élément dans un liste, trouver le plus grand commun diviseur de deux nombres entiers, calculer une expression algébrique, compresser des données, factoriser un nombre entier en nombres premiers, trier un tableau, trouver l’enveloppe convexe d’un ensemble de points, créer une grille de sudoku, etc.
Le problème résolu ou la tâche accomplie doivent être assez généraux. Par exemple, un algorithme de tri doit être capable de remettre dans l’ordre n’importe quelle liste d’éléments deux à deux comparables (algorithme généraliste) ou être conçu pour fonctionner sur un certain type d’élément correpondant à des données usuelles (le type int du C, par exemple). Contre-exemple : le tri chanceux. Cet algorithme rend la liste passée en argument si celle-ci est déjà triée et il ne rend rien sinon. Autre contre-exemple : si on se restreint au cas où la liste à trier sera toujours la liste des entiers de 0 à n − 1 dans le désordre (une permutation de {0,… ,n − 1}) alors nul besoin de trier, il suffit de lire la taille n de la liste donnée en entrée et de rendre la liste 0, . . . , n− 1 sans plus considérer l’entrée. Il serait incorrect de dire de ce procédé qu’il est un algorithme de tri.
Un algorithme doit toujours terminer en un temps fini, c’est à dire en un nombre fini d’étapes, toutes de temps fini. Contre-exemple : tri bogo (encore dénommé tri stupide). Ce tri revient, sur un jeu de cartes, à les jeter en l’air, à les ramasser dans un ordre quelconque puis à vérifier si les cartes sont dans le bon ordre, et si ça n’est pas le cas, à recommencer. Cet algorithme termine en un temps fini avec une probabilité 1 mais il est toujours possible qu’il ne termine jamais.
En général, un algorithme est déterministe : son exécution ne dépend que des entrées (ce n’est pas le cas du tri bogo).
En particulier, un algorithme déterministe réalise une fonction (au sens mathématique) : il prend une entrée et produit une sortie qui ne dépend que de l’entrée.
Toutefois, pour une même fonction mathématique il peut y avoir plusieurs algorithmes, parfois très différents. Il y a par exemple plusieurs algorithmes de tri, qui réalisent tous la fonction « ordonner les éléments d’un tableau ».
Nous verrons également des algorithmes randomisés qui ne sont pas déterministes. Toutefois  la seul part de hasard dans l’exécution se ramènera à une modification de l’entrée sans conséquence sur la justesse du résultat. Par exemple, un algorithme de tri randomisé désordonne la liste d’éléments qu’on lui donne à trier avant de se lancer dans le tri.

……..

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Cours écriture et comparaison des algorithmes, tris (1.3 Mo)  (Cours PDF)