différence entre une fonction et un algorithme

Salut à tous,

récemment un ami m’a demandé ce qui différencie un algorithme d’une fonction. Et je dois avouer que j’ai essayé d’y réfléchir un peu, notamment en cherchant un algorithme qui ne peut être écrit sous forme de fonction, mais sans vraiment trouver.

Toutefois je trouve cette question assez pertinente et intéressante¹ c’est pourquoi je la poste ici, dans le but d’avoir au moins des éléments de réponse pour moi et pour mon ami.

Je vous remercie d’avance pour vos réponses.

Un algorithme est un procédé résolvant un problème. Il prend des données en entrée et resort un résultat.

C’est donc une relation. Si l’algorithme est déterministe alors à chaque donné d’entrée correspond un résultat de sortie. C’est donc une application (donc une fonction).

Si ton algorithme est bugé et que du coup il n’est pas défini pour certaines entrées, alors éventuellement, il peut n’’être qu’une fonction

Du coup, de manière générale, algorithme != fonction. Car un algorithme n’est pas forcément déterministe. Mais dans le cas où il l’est alors oui je pense qu’on peut assimiler les deux.

Tu poses la question dans un contexte mathématique ou informatique ? Ache t’a fait la réponse informatique.

En maths, une fonction $f : A \to B$, c’est un objet mathématique tel que si $a$ est un élément de $A$, alors $f(a)$ est un élément de $B$. La définition exacte va dépendre du contexte dans lequel on se place. Et un algorithme, c’est une "procédure pour calculer quelque chose". La différence c’est que pour une fonction, il faut seulement une définition de la valeur de sortie pour chaque entrée, alors que pour un algorithme, il faut un moyen de calculer la valeur de sortie pour chaque entrée.

un algorithme qui ne peut être écrit sous forme de fonction

Je n’ai pas compris ce que tu veux dire.

Je ne suis pas totalement d’accord avec la réponse de Ache.

Mais déjà, il faut définir le mot fonction. Le mot fonction est utilisé en mathématiques, et aussi en informatique. Je pense que tu parles de fonction au sens mathématique (Ache a interprété dans ce sens lui aussi). Mais ce n’est pas sûr.

Je vais juste prendre un exemple très courant, les algorithmes de tri. On a une série de valeurs, des nombres, et en résultat, on veut les mêmes valeurs, mais ordonnées de la plus petite à la plus grande. On veut donc une procédure (une fonction) qui fasse ce job. Ma fonction va s’appeller TRI(), elle est parfaitement décrite avec les 2 ou 3 lignes ci-dessus. Tant que je parle de fonction, je ne m’intéresse pas à la mécanique qu’il y a à l’intérieur de cette procédure appelée TRI().

Par contre, quand je me lance dans l’algorithmique, je vais voir qu’il y a plein de façons de trier des valeurs. Tri-bulle, Tri-fusion, tri par insertion, etc

Une seule fonction, mais plein de choix d’algorithmes.

Quand on parle de fonction, au sens mathématique du terme, on s’intéresse aux fonctionnalités, à l’objectif. Alors que quand on parle d’algorithme, on s’intéresse à la route suivie pour atteindre cet objectif.

PS : du coup, je suis parfaitement d’accord avec blo yhg

Je parlais d’un point de vue mathématique (cf. le tag), mais si le point de vue informatique est aussi intéressant je suis preneur. 

un algorithme qui ne peut être écrit sous forme de fonction

Je n’ai pas compris ce que tu veux dire.

C’est pas grave, je me suis rendu compte que cela n’a pas beaucoup de sens.

Sinon merci, je suis bien plus éclairé maintenant.

Arf, c’est une vaste question … Je suis d’accord avec mes VDD. Il faut définir le cadre ou au moins le mot fonction.

Si tu parles de fonction … Comme celle que l’on retrouve dans les langages de programmation(peu importe il me semble le paradigme), alors il n’y a aucune différence entre une fonction et un algorithme.

Si tu parles en informatique théorique, on peut tout à fait définir un algorithme qui résout le voyageur de commerce en temps polynomial. Et travailler avec sans avoir besoin de le décrire. C’est dans ce cadre là que s’inscrit mon premier message. Ici on est la frontière stricte entre Mathématique et Informatique.

Je ne suis pas un spécialiste, et les informaticiens plus chevronnés que moi me corrigeront si je dis une ânerie.

On attend d’un algorithme qu’il soit calculable (au sens de la théorie de la calculabilité), au sens où je lui donne des entrées, et il me renvoie un résultat, éventuellement aléatoire. Il y a une mécanique sous-jacente.

En mathématiques, une fonction ça peut être abominablement compliqué, et pas du tout calculable. Typiquement, on peut construire des fonctions dont la définition fait appel à l’axiome du choix, ce qui est une manière assez brutale de s’empêcher de la calculer. Et pourtant, une telle fonction peut très bien être totalement déterministe, par exemple du fonction de choix sur un ensemble infini est déterministe… et pourtant pas du tout calculable, précisément parce qu’elle repose sur l’axiome du choix.

Et même sans l’axiome du choix (et là, je parle sous le regard prudent de gens qui connaissent mieux que moi ce genre de questions), je vois encore une différence entre fonction mathématique et algorithme. Considérons la fonction exponentielle sur l’ensemble des réels. Elle est parfaitement définie, et pour autant, je ne connais pas d’algorithme qui calcule, étant donné un réel $x$, le réel $e^x$ — en tout cas, pas d’algorithme qui s’exécute en temps fini…

On attend d’un algorithme qu’il soit calculable (au sens de la théorie de la calculabilité), au sens où je lui donne des entrées, et il me renvoie un résultat, éventuellement aléatoire. Il y a une mécanique sous-jacente.

C’est plutôt faux, même si c’est le cas en pratique. En fait le mot algorithme tout seul n’a pas vraiment de sens, et d’ailleurs il n’y a pas de définition formelle de ce qu’est un algorithme. C’est d’ailleurs pour ça qu’il est difficile de répondre à la question. Quand on pense à algorithme, on imagine un système calculatoire derrière et la plupart du temps, ce système peut-être implémenté par une machine de Turing.

Cependant, tu peux imaginer des algorithmes dans des systèmes de calculs qui ne peuvent pas être simulés par une machine de Turing.

Et même sans l’axiome du choix (et là, je parle sous le regard prudent de gens qui connaissent mieux que moi ce genre de questions), je vois encore une différence entre fonction mathématique et algorithme. Considérons la fonction exponentielle sur l’ensemble des réels. Elle est parfaitement définie, et pour autant, je ne connais pas d’algorithme qui calcule, étant donné un réel x , le réel ex — en tout cas, pas d’algorithme qui s’exécute en temps fini…

Alors qu’entends-tu par $e^x$, et par calculer $e^x$ ? Car en général, le développement décimal de $e^x$ est infini donc pas représentable sur une mémoire finie. Par contre, on connais des algorithmes qui permettent d’approximer $e^x$ à $\varepsilon$ près pour $\varepsilon > 0$

En résumant un peu les idées énoncées ici, on voit intervenir trois différents niveaux :

1. Le programme, qui est un truc qu’on imagine raisonnablement bien pouvoir définir. Une machine de Turing ? Une fonction récursive ? Un automate linéairement borné ?
2. La fonction, qui est la partie haut niveau : on associe une sortie à une entrée. La collection « minimale » de fonctions qu’on va considérer dépend du modèle de programme choisi. Exemple : ensemble des fonctions calculables de $\mathbf{N}^m$ dans $\mathbf{N}$. Typiquement, deux machines de Turing peuvent calculer la même fonction.
3. L’algorithme, quelque part entre les deux. Intuitivement deux programmes peuvent implémenter le même algorithme (renommer une variable, dérouler une boucle, etc.), et de même deux algorithmes peuvent représenter la même fonction (plusieurs algos de tris).

Le message, c’est que si on se fixe un modèle de programmes et une relation d’équivalence « correspondent au même algorithme » sur ceux-ci, on obtient en quotientant une définition convenable de ce qu’on appelle couramment un algorithme. Voir par exemple ici pour une possible formalisation de cette relation d’équivalence sur les fonctions récursives primitives.

Pour faire le lien avec la question initiale :

• En choisissant un modèle de programmes réaliste, les fonctions qu’on considère sont de domaine et de codomaine limités (exemple du calcul de $e^x$ de @c_pages).
• On peut associer une fonction à chaque algorithme (si on choisit une relation d’équivalence qui conserve bien cette propriété), et à chaque fonction on peut typiquement associer plusieurs algorithmes (exemple des algorithmes de tris de @elegance).

Ce que j’appelle $e^x$ (mais qui est en fait la définition), c’est la quantité $e^x = \sum_{k=}^{+\infty}\frac{x^k}{k!}$. Calculer $e^x$, c’est en donner une valeur exacte. Je ne connais pas d’algorithme qui donne une valeur exacte en un nombre fini d’étapes (ça se saurait, si ça existait. ), et ce même si $e^x$ est un nombre rationnel, voire entier.

J’ai donc une fonction mathématique bien définie, que je peux approcher à précision arbitraire (au moins théoriquement), mais je n’ai pas sous la main de d’algorithme qui la calcule (de manière exacte) en un nombre fini d’étapes.

Voici un algorithme qui te calcule $e^0$ en un temps fini d’étape :3

1
2

def exp_zero():
  return 1

@c_pages Pour avoir quelque chose qui est calculable ou non, il faut commencer par avoir une fonction. Il faut donc une convention sur comment représenter des réels informatiquement et ça peut par exemple être par un algorithme qui l’approche à $2^{-k}$ près quand on lui donne en entrée le nombre $k$ (les algorithmes sont bien représentables en mémoire). Il y a d’autres conventions non équivalentes pour ce qu’est une fonction numérique calculable, ça peut être une fonction telle qu’on lui donne une précision, elle demande une précision pour l’entrée, on la lui donne, et elle donne la sortie avec la précision demandée. Mais si on dit que ça n’est pas calculable presque "par définition"… bof.

(edit : correction de phrase incompréhensible)

Ensuite il n’y a pas un problème de dénombrabilité ?
Un algorithme est un ensemble fini de symboles (lettres, parenthèses, accolades, points virgules…) or les fonctions sont en nombre infini (et même plus que R). Il y a donc une infinité non dénombrable de fonctions impossibles a calculer par algorithme.

Oui, ça montre que presque tous les réels ne sont pas calculables. Chercher "computable analysis", "realizability".

edit

Je voudrais aussi réagir sur ça

Si on définit une fonction avec l’axiome du choix, alors en fait on n’a pas défini une fonction… on a seulement montré qu’il existe une fonction d’une certaine forme. Si la fonction de choix est déterministe, pas besoin de l’axiome du choix.

Pour un exemple de fonction non calculable, il y a le problème de l’arrêt. Un exemple un peu moins "autoréférent" (dans l’énoncé) est le problème de Post.