Pour définir formellement la notion de complexité on passe par une forme de machine, par exemple les machines de Turing. Un algorithme a une complexité polynomiale si la machine de Turing qui l’implémente a un temps d’exécution borné par un polynome en fonction de la taille des données d’entrées ... finalement l’algo présenté sous cette forme n’est rien d’autre qu’un programme.
Mais la principale différence, à mon avis, entre un programme et un algo, c’est qu’un programme n’est pas forcément spécifié, un programme fait des trucs. Genre un programme de dessin créatif dessine des trucs, mais il ne résoud par forcément de problème bien spécifié. Alors qu’un algorithme est créé pour résoudre une certaine classe de problème : tous les algos de tris résolvent des problèmes de tri de liste, et on peut prouver qu’à la fin de l’exécution de l’algo on a bien résolu le problème.
Après si tu veux on doit pouvoir pousser la notion d’unicité en utilisant des transformations de programmes, deux programmes correspondent au même algorithme si il existe un moyen de les transformer réciproquement l’un en l’autre de manière équivalente. Ou alors si les états de la mémoire successifs ont une forme d’équivalence, on pourra dire qu’ils font la même chose dans le même ordre. Plutôt qu’une forme d’unicité ou de canonicité on parle plutôt d’isomorphisme et d’équivalence. Un algo serait une [[classe d’équivalence]] de programme pour lesquels en codant les données pour les différentes sortes de machines de manière appropriée on peut définir une suite d’états intermédiaires équivalents ?
Mais pour faire les choses formellement on aura du mal à se passer de la notion de machine. Si un algorithme définit une suite d’instruction on doit d’abord définir ce que sont les instructions basiques qu’il peut utiliser, quoi qu’il arrive.
Bêtement en prenant wp en français
Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes.
et pour un programme
Un programme informatique est un ensemble d'instructions et d’opérations destinées à être exécutées par un ordinateur.
La différence essentielle semble bien être, dans ces définitions « permettant de résoudre une classe de problèmes. » (autrement dit, les IAs, ou les algorithmes de recommandation, sont pas vraiment des algorithmes, définir mathématiquement quel problèmes résoud une IA générative est pas trivial :p si on avait déjà pas assez de troll en réserve)
[^] # Re: Broyé du Poitou
Posté par thoasm . En réponse à la dépêche Claire Mathieu et les algorithmes. Évalué à 4.
Pour définir formellement la notion de complexité on passe par une forme de machine, par exemple les machines de Turing. Un algorithme a une complexité polynomiale si la machine de Turing qui l’implémente a un temps d’exécution borné par un polynome en fonction de la taille des données d’entrées ... finalement l’algo présenté sous cette forme n’est rien d’autre qu’un programme.
Mais la principale différence, à mon avis, entre un programme et un algo, c’est qu’un programme n’est pas forcément spécifié, un programme fait des trucs. Genre un programme de dessin créatif dessine des trucs, mais il ne résoud par forcément de problème bien spécifié. Alors qu’un algorithme est créé pour résoudre une certaine classe de problème : tous les algos de tris résolvent des problèmes de tri de liste, et on peut prouver qu’à la fin de l’exécution de l’algo on a bien résolu le problème.
Après si tu veux on doit pouvoir pousser la notion d’unicité en utilisant des transformations de programmes, deux programmes correspondent au même algorithme si il existe un moyen de les transformer réciproquement l’un en l’autre de manière équivalente. Ou alors si les états de la mémoire successifs ont une forme d’équivalence, on pourra dire qu’ils font la même chose dans le même ordre. Plutôt qu’une forme d’unicité ou de canonicité on parle plutôt d’isomorphisme et d’équivalence. Un algo serait une [[classe d’équivalence]] de programme pour lesquels en codant les données pour les différentes sortes de machines de manière appropriée on peut définir une suite d’états intermédiaires équivalents ?
Mais pour faire les choses formellement on aura du mal à se passer de la notion de machine. Si un algorithme définit une suite d’instruction on doit d’abord définir ce que sont les instructions basiques qu’il peut utiliser, quoi qu’il arrive.
Bêtement en prenant wp en français
et pour un programme
La différence essentielle semble bien être, dans ces définitions « permettant de résoudre une classe de problèmes. » (autrement dit, les IAs, ou les algorithmes de recommandation, sont pas vraiment des algorithmes, définir mathématiquement quel problèmes résoud une IA générative est pas trivial :p si on avait déjà pas assez de troll en réserve)