Qu'est-ce qu'un algorithme exactement?

Je sais que cela peut sembler un peu hors de la boîte, en fait, je pensais toujours à l'intérieur de la boîte, mais récemment, j'ai pensé, peut-être parce que l'informatique offre un haut degré de liberté, sur les moyens de concevoir des programmes autres que ceux enseignés à l'université.

Considérez la fonction factorielle. En règle générale, nous définissons cette fonction comme

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

J'appellerais cela un algorithme et je n'ai aucun doute que c'est la bonne façon de le faire. Ensuite, je me suis demandé "est-ce que je peux faire ça en temps constant?", Ce qui a laissé l'idée suivante: que se passerait-il si j'avais un tableau d'entiers où tableau [n] abrite la factorielle de n? Une fois ce tableau rempli, je pourrais simplement définir le fait comme:

 int fact(int n) 
 { 
 return array[n]; 
 } 

Je n'arrive toujours pas à appeler cet algorithme, même s'il fournit le résultat correct et fonctionne en temps constant O (1). Peut-on appeler cela un algorithme? Sinon, pourquoi pas? Je pourrais affirmer que le remplissage du tableau nécessiterait qu'un algorithme ait fonctionné à un moment donné, même s'il était dans notre cerveau pour que nous remplissions le tableau, mais cela pourrait-il être le critère? Comment ces aspects sont-ils traités officiellement?

Notez que ce concept pourrait être étendu à toute fonction fonctionnant sur des entiers indépendamment de son nombre d'arguments, je n'aurais qu'à utiliser une matrice si la fonction avait 2 arguments, ou 3 si la fonction avait 3 arguments, et ainsi de suite. De plus, ces solutions ne sont-elles pas utilisées simplement en raison de la consommation de mémoire?

En outre, non que les fonctions puissent également englober n'importe quel programme avec sortie, car je pourrais trouver un moyen d'indexer chaque sortie possible qu'un programme pourrait fournir.

Comme autre exemple, considérons l'utilisation courante d'un tableau: j'alloue un tableau initialement de taille N, puis j'ajoute des éléments au tableau en stockant la valeur à l'index n et en augmentant n d'une unité. Ensuite, si je veux chercher un élémento, je ne peux pas m'empêcher d'effectuer une recherche linéaire sur le tableau. Si à la place, je créais un tableau de taille, par exemple, Integer.MAXVALUE, pour stocker des entiers, initialisés avec des zéros, je pourrais stocker un entier en plaçant 1 à son index. Ensuite, je pourrais rechercher son existence dans le tableau en temps O (1). Et si je voulais pouvoir placer plusieurs unités du même numéro? Pas de problème, je voudrais simplement augmenter la valeur stockée à l'index de l'entier.

Le tri serait un peu plus compliqué, mais la recherche et l'ajout pourraient néanmoins être effectués en temps O (1).

La définition informelle d'un algorithme dans un manuel populaire ressemble à ceci:

Un algorithme est (1) une procédure de calcul bien définie (2) qui prend une certaine entrée et (3) produit une sortie (4) pour un problème de calcul bien défini.

Dans votre premier cas, vous avez codé un algorithme où: Le problème est de trouver la factorielle (partie 4 de la définition), donnée int n en entrée (partie 2 de la définition), le code décrit le calcul à effectuer (partie 1 de la définition) ), la sortie est la factorielle (partie 3 de la définition).

Dans votre deuxième cas: le problème est de trouver l'élément de tableau en position n (partie 4 de la définition), donné n en entrée (partie 3 de la définition), le code décrit le calcul à effectuer (partie 2 de la définition), le sortie est l'élément à la position n (partie 1 de la définition).

Vous y avez stocké des factoriels, ce qui vous donne des factoriels. Si vous y aviez stocké des carrés ou des cubes, vous obtiendriez des carrés ou des cubes, donc on ne peut pas dire que le deuxième extrait de code en lui-même est un algorithme pour calculer les factorielles.

Et si vous dites qu'un tableau chercher avec un tableau ayant f (n) à la position n est un algorithme pour calculer f (n) alors vous êtes allé si profondément qu'il n'y a plus de calcul ci-dessous. Une procédure de calcul bien définie devrait être une information finie. Si un tableau infini de factorielles fait partie de la procédure de calcul, cela ne tient pas. Ce ne serait donc pas un algorithme pour calculer les factorielles.

Plus largement, un algorithme est une série d'étapes pour résoudre un problème .

Dans CS, les éléments suivants sont généralement compris / supposés lors de l'utilisation du terme algorithme:

• L'algorithme a une description finie et une procédure bien définie pour effectuer ses étapes compte tenu de toute instance de problème. (Plus ci-dessous.)
• Une instance de problème donnée sous forme de chaîne finie (séquence de symboles d'entrée) et la sortie de l'algorithme peuvent être codées sous forme de chaîne finie.
• Un problème est une collection d'instances de problème avec des sorties "correctes" possibles pour chaque instance. "Résoudre" signifie produire une sortie correcte.
• (Habituellement) les instances de problème peuvent être arbitrairement grandes (il existe un nombre infini d'instances possibles que votre algorithme fini doit résoudre).

Avant la fondation de CS, les mathématiciens avaient les mêmes types de préoccupations que vous soulevez et ont introduit des définitions formelles du calcul pour répondre à ces préoccupations. Ainsi, de nos jours, nous pouvons formaliser toutes les hypothèses ci-dessus en disant simplement "qu'un algorithme est une procédure qui peut être implémentée sur une machine de Turing" . C'est probablement la meilleure réponse officielle à votre question.

Notez que la thèse de Church-Turing dit que nous pensons qu'il n'y a pas de formalisation "plus puissante" des algorithmes que la machine de Turing.

L'exemple factoriel entre dans un modèle de calcul différent, appelé calcul non uniforme. Une machine de Turing est un exemple de modèle de calcul uniforme : elle a une description unique et finie et fonctionne pour des entrées de taille arbitrairement grande. En d'autres termes, il existe une MT qui résout le problème pour toutes les tailles d'entrée.

Maintenant, nous pourrions plutôt considérer le calcul comme suit: Pour chaque taille d'entrée, il existe une MT (ou un autre dispositif de calcul) qui résout le problème. C'est une question très différente. Notez qu'une seule MT ne peut pas stocker la factorielle de chaque entier, car la TM a une description finie. Cependant, nous pouvons créer une MT (ou un programme en C) qui stocke les factorielles de tous les nombres inférieurs à 1000. Ensuite, nous pouvons créer un programme qui stocke les factorielles de tous les nombres entre 1000 et 10000. Et ainsi de suite.

Ces types de calcul non uniformes sont généralement modélisés dans des CS théoriques par des circuits. Vous envisagez une construction de circuit différente pour chaque taille d'entrée possible.

Les modèles de calcul non uniformes ne sont généralement pas considérés comme des algorithmes , même s'ils peuvent correspondre à ma première phrase. La raison en est qu'ils ne correspondent pas à nos hypothèses clés: ils n'ont pas de description finie qui peut être implémentée pour résoudre le problème «entier» pour n'importe quelle taille d'entrée. Au contraire, ils ont besoin d'une description de plus en plus grande à mesure que le problème s'aggrave (comme avoir besoin d'une table de recherche plus grande). Cependant, ce sont encore des modèles de calcul intéressants.

Un algorithme est un programme écrit en C qui devrait fonctionner pour n'importe quelle longueur d'entrées (en supposant une mémoire infinie et des entiers illimités). Dans vos exemples, si nous voulions que le programme fonctionne pour toutes les longueurs d'entrées, le tableau dans lequel les résultats sont stockés serait infiniment grand; les programmes en C sont toujours finis, donc cette approche ne peut pas être utilisée.

$n!$$n!$) peut y être calculé beaucoup plus efficacement que C.

Lorsque nous nous inquiétons des durées de fonctionnement réelles sur un ordinateur réel, nous devons être encore plus prudents, mais cela dépasse généralement les limites de l'informatique théorique, malheureusement.

$n$$n!$

Quelle notion d'algorithme utiliser? Une suggestion, décrite ci-dessus, est d'utiliser des programmes C. On peut appeler cette notion C-calcul. Turing-calcul est ce que vous obtenez lorsque vous utilisez des machines Turing. Il s'avère qu'une fonction est calculable en C si et seulement si elle est calculable en Turing. C'est en ce sens que ces deux modèles de calcul sont équivalents. En effet, de nombreux autres modèles sont équivalents, par exemple tous les langages de programmation d'usage courant (en supposant une mémoire infinie et des variables illimitées).

Nous disons qu'un langage de programmation P est Turing-complet est une fonction est P-calculable si et seulement s'il est Turing-calculable. L'hypothèse Church-Turing est une déclaration informelle selon laquelle tous les modèles de calcul raisonnables ayant une description finie et prenant un temps fini sont Turing-complets. Votre modèle a une description finie mais ne prend pas de temps fini.

La partie importante de la définition commune d'un algorithme qui vous manque est que la spécification doit être finie et que la taille de la spécification ne doit pas varier avec la taille de l'entrée.

La mémoire peut être arbitrairement grande, tout comme les entrées, mais pour être une définition utile d'un algorithme, l'espace de code doit être fini. Sinon, vous obtenez le problème que vous venez d'identifier.

$O(\log A)$$A$$O(\log n)$$O(\log n!)$$O(n (\log n)^2)$$s$$n = O(2^s)$$O(2^s~s^2)$$O(1)$

Quelques observations qui pourraient être utiles:

Les problèmes sont des déclarations sur les entrées autorisées et les sorties correspondantes. C'est ce que nous voulons résoudre. Les algorithmes sont des procédures de calcul. Nous pouvons dire qu'un algorithme est correct par rapport à un problème s'il accepte des entrées qui sont autorisées par rapport au problème et produit des sorties selon la description du problème.

Vos deux exemples sont des algorithmes, car ils sont tous deux clairement des procédures de calcul. Que les algorithmes soient corrects ou non dépend de la façon dont vous définissez le problème et de la façon dont vous interprétez la représentation de l'algorithme. Quelques déclarations de problèmes:

1. $n$$n!$
2. $n > 0$$n! <$ INT_MAX$n!$

Quelques interprétations de votre premier extrait de code:

1. C'est un pseudocode qui ressemble à C / C ++ sauf dans les détails. intsignifie vraiment "n'importe quel entier", par exemple.
2. Cela doit être interprété comme s'il s'agissait d'un vrai programme C / C ++.

L'interprétation 1 est correcte pour l'énoncé de problème 1, tant que la factorielle prend la valeur 1 pour les nombres négatifs (sinon, nous pourrions modifier l'énoncé du problème pour restreindre le domaine ou l'algorithme pour tenir compte du comportement souhaité). L'interprétation 2 est correcte pour l'énoncé de problème 2, avec la même mise en garde.

arrayarray$n$$n > 0$$n! <$ INT_MAX$n!$$n < 0$

$n$$n! \geq 2^{32}$$n! \geq 2^{64}$

$k$$k$$n$$kn$$k+n$

Un algorithme est un programme écrit dans un langage complet de Turing qui s'arrête de manière prouvée sur toutes les entrées valides. Tous les langages de programmation standard sont complets de Turing. Le mot provient d'une traduction européenne du nom al-Khwārizmī, un mathématicien, astronome et géographe persan, dont les travaux s'appuient sur ceux du mathématicien indien Brahmagupta du 7e siècle, qui a introduit le système numérique indien dans le monde occidental.

La question semble être essentiellement de savoir si les tables de recherche font partie des algorithmes. Absolument! Dans les machines Turing (TM), les tables peuvent être encodées dans la table d'état de la TM. Le TM peut initialiser la bande sur la base d'une quantité finie de données stockées dans la table de transition. Cependant, les "algorithmes" qui ne fonctionnent pas sur des entrées infinies, seulement des entrées finies, sont des machines à états finis (FSM) "trivialement" .

En bref : un algorithme est la partie constructive d'une preuve constructive qu'un problème donné a une solution. La motivation de cette définition est l'isomorphisme de Curry-Howard entre les programmes et la preuve, considérant qu'un programme n'a d'intérêt que s'il résout un problème, mais de manière prouvée. Cette définition permet plus d'abstraction et laisse certaines portes ouvertes concernant le type de domaines qui peuvent être concernés, par exemple concernant les propriétés de finitude.

Attention . J'essaie de trouver une approche officielle appropriée pour répondre à la question. Je pense que cela est nécessaire, mais il semble qu'aucun des utilisateurs qui ont répondu jusqu'à présent (moi y compris, et certains étaient plus ou moins explicites à ce sujet dans d'autres articles) n'a pas le bon fond pour développer correctement les problèmes, qui sont liés à mathématiques constructives, théorie des preuves, théorie des types et des résultats tels que l' isomorphisme de Curry-Howard entre les preuves et les programmes. Je fais de mon mieux ici, avec les extraits de connaissances que je possède (je crois), et je ne suis que trop conscient des limites de cette réponse. J'espère seulement donner quelques indications sur ce à quoi je pense que la réponse devrait ressembler. Si vous voyez un point qui est clairement faux formellement (prouvablement), laissez-moi maintenant un commentaire - ou par e-mail.

Identifier certains problèmes

Une manière standard de considérer un algorithme est de déclarer qu'un algorithme est un programme arbitrairement spécifié de manière finie pour certains appareils informatiques , y compris ceux qui n'ont aucune limitation en mémoire. Le langage peut aussi être le langage machine informatique. En fait, il suffit de considérer tous les programmes pour un appareil informatique complet de Turing (ce qui implique de n'avoir aucune limitation de mémoire). Il peut ne pas vous donner toutes les présentations d'algorithmes, dans le sens où les algorithmes doivent être exprimés sous une forme qui dépend dans ses détails du contexte d'interprétation, même théorique, car tout est défini jusqu'à un certain encodage. Mais, puisqu'il calculera tout ce qu'il y a à calculer, il inclura en quelque sorte tous les algoritms, jusqu'au codage.

$\pi$

$\pi$, peut-être au sens mathématique de presque tous. Mais cela exigerait plus de précision dans les définitions.

La vraie question est donc de savoir quels sont les algorithmes significatifs. La réponse est que les algorithmes significatifs sont ceux qui résolvent un problème, calculant pas à pas la "solution", la "réponse" à ce problème. Un algorithme est intéressant s'il est associé à un problème qu'il résout.

Donc, étant donné un problème formel, comment obtenir un algorithme qui résout le problème. Que ce soit explicitement ou implicitement, les algorithmes sont associés à l'idée qu'il existe une solution au problème, qui peut être prouvée correcte. La précision de nos techniques de preuve est une autre affaire, mais nous essayons au moins de nous convaincre. Si vous vous limitez aux mathématiques constructives, ce qui est en fait ce que nous devons faire (et c'est une contrainte axiomatique très acceptable pour la plupart des mathématiques), le moyen de prouver l'existence d'une solution est de passer par des étapes de preuve qui présentent réellement une construction qui représente la solution, y compris éventuellement d'autres étapes qui établissent son exactitude.

Tous les programmeurs pensent quelque chose comme: si je joue avec les données de telle ou telle manière, alors j'obtiens ce widget qui a juste les bonnes propriétés en raison du théorème de Sesame, et en exécutant cette transformation préservant le foo, j'obtiens la réponse souhaitée . Mais la preuve est généralement informelle, et nous ne travaillons pas sur tous les détails, ce qui explique pourquoi un satellite a tenté d'orbiter Mars sous terre (entre autres). Nous faisons une grande partie de la réflexion, mais nous ne conservons en fait que la partie constructive qui construit la solution, et nous la décrivons dans un langage informatique pour être l'algorithme qui résout le problème.

Algorithmes (ou programmes) intéressants

Tout cela pour introduire les idées suivantes, qui font l'objet de nombreuses recherches actuelles (dont je ne suis pas spécialiste). La notion d '« algorithme intéressant » utilisée ici est la mienne, introduite comme un espace réservé informel pour des définitions plus précises.

Un algorithme intéressant est la partie constructive d'une preuve constructive qu'un problème donné a une solution . Cela signifie que la preuve doit réellement montrer la solution plutôt que simplement prouver son existence, par exemple par contradiction. Pour plus de détails, voir Logique intuitive et constructivisme en mathématiques.

C'est bien sûr une définition très restrictive, qui ne considère que ce que j'ai appelé des algorithmes intéressants. Il les ignore donc presque tous. Mais il en va de même pour tous nos manuels sur l'algorithme. Ils essaient d'enseigner seulement quelques-uns des plus intéressants.

Compte tenu de tous les paramètres du problème (données d'entrée), il vous indique comment obtenir un résultat spécifié étape par étape. Un exemple typique est la résolution des équations (l' algorithme du nom est en fait dérivé du nom d'un mathématicien persan, Muḥammad ibn Mūsā al-Khwārizmī , qui a étudié la résolution de certaines équations). Des parties de la preuve sont utilisées pour établir que certaines valeurs calculées dans l'algorithme ont certaines propriétés, mais ces parties n'ont pas besoin d'être conservées dans l'algorithme lui-même.

Bien sûr, cela doit avoir lieu dans un cadre logique formalisé qui établit quelles sont les données calculées, quelles sont les étapes de calcul élémentaires autorisées et quels sont les axiomes utilisés.

Pour revenir à votre exemple factoriel, il peut être interprété comme un algorithme, quoique trivial. La fonction factorielle normale correspond à une preuve que, étant donné un cadre arithmétique, et étant donné un entier n, il existe un nombre qui est le produit des n premiers entiers. C'est assez simple, tout comme le calcul factoriel. Cela pourrait être plus complexe pour d'autres fonctions.

Maintenant, si vous décidez de tabuler factorielle, en supposant que vous le pouvez, ce qui n'est pas vrai pour tous les entiers (mais pourrait être vrai pour un domaine fini de valeurs), tout ce que vous faites est d'inclure dans vos axiomes l'existence de factorielle en définissant avec un nouvel axiome sa valeur pour chaque entier, de sorte que vous n'avez plus besoin de prouver (donc de calculer) quoi que ce soit.

Mais un système d'axiomes est censé être fini (ou du moins défini de manière finie). Et il y a une infinité de valeurs pour factorielle, une par entier. Vous êtes donc en difficulté pour votre système fini d'axiomes si vous axiomatisez une fonction infinie, c'est-à-dire définie sur un domaine infini. Cela se traduit par le fait que votre recherche de table potentielle ne peut pas être implémentée pour tous les entiers. Cela tuerait l'exigence de finitude habituelle pour les algorithmes (mais doit-elle être aussi stricte que souvent présentée?).

Vous pouvez décider d'avoir un générateur d'axiomes défini de manière finie pour gérer tous les cas. Cela reviendrait, plus ou moins, à inclure le programme factoriel standard dans votre algorithme pour initialiser le tableau selon les besoins. Cela s'appelle la mémorisation par les programmeurs. C'est en fait le plus proche de l'équivalent d'une table précalculée. On peut comprendre qu'il a une table précalculée, à l'exception du fait que la table est réellement créée en mode d' évaluation paresseuse , chaque fois que cela est nécessaire. Cette discussion aurait probablement besoin d'un peu plus de soins formels.

Vous pouvez définir vos opérations primitives comme vous le souhaitez (en cohérence avec votre système formel) et leur affecter le coût que vous choisissez lorsqu'il est utilisé dans un algorithme, afin de faire une analyse de complexité ou de performance. Mais, si les systèmes concrets qui implémentent réellement votre algorithme (un ordinateur ou un cerveau par exemple) ne peuvent pas respecter ces spécifications de coût, votre analyse peut être intellectuellement intéressante, mais ne vaut rien pour une utilisation réelle dans le monde réel.

$2^{1000}$

Quels programmes sont intéressants

Cette discussion devrait être plus correctement liée à des résultats tels que l' isomorphisme de Curry-Howard entre les programmes et la preuve. Si un programme est en fait une preuve de quelque chose, tout programme peut être interprété comme un programme intéressant au sens de la définition ci-dessus.

Cependant, à ma compréhension (limitée), cet isomorphisme est limité aux programmes qui peuvent être bien typés dans un système de typage approprié, où les types correspondent aux propositions de la théorie axiomatique. Par conséquent, tous les programmes ne peuvent pas être considérés comme des programmes intéressants. Je suppose que c'est dans ce sens qu'un algorithme est censé résoudre un problème.

Cela exclut probablement la plupart des programmes "générés aléatoirement".

C'est aussi une définition quelque peu ouverte de ce qu'est un «algorithme intéressant». Tout programme qui peut être considéré comme intéressant l'est certainement, car il existe un système de type identifié qui le rend intéressant. Mais un programme qui n'était pas typable jusqu'à présent, pourrait devenir typable avec un système de type plus avancé, et devenir ainsi intéressant. Plus précisément, cela a toujours été intéressant, mais faute de connaître le bon système de typage, nous ne pouvions pas le savoir.

Cependant, il est connu que tous les programmes ne sont pas typables, car il est connu que certaines expressions lambda, telles que l'implémentation du combinateur Y , ne peuvent pas être typées dans un système de type sonore .

Cette vue s'applique uniquement aux formalismes de programmation qui peuvent être directement associés à un système de preuve axiomatique. Je ne sais pas comment il peut être étendu à des formalismes de calcul de bas niveau tels que la machine de Turing. Cependant, étant donné que l'algorithmique et la calculabilité sont souvent un jeu d'encodage de problèmes et de solutions (pensez aux arithmétiques encodées dans le calcul lambda ), on peut considérer que tout calcul défini formellement qui peut être montré comme étant l'encodage d'un algorithme est également un algorithme. De tels encodages n'utilisent probablement qu'une très petite partie de ce qui peut être exprimé dans un formalisme de bas niveau, tel que Turing Machines.

Un intérêt de cette approche est qu'elle donne une notion d'algorithme plus abstraite et indépendante des problèmes de codage réel, de "représentabilité physique" du domaine de calcul. Ainsi, on peut, par exemple, considérer des domaines avec des objets infinis tant qu'il existe une manière solide sur le plan informatique de les utiliser.

Il n'y a pas de bonne définition formelle d '"algorithme" au moment de la rédaction. Cependant, il y a des gens intelligents qui y travaillent.

Ce que nous savons, c'est que quel que soit un «algorithme», il se situe quelque part entre «fonction mathématique» et «programme informatique».

Une fonction mathématique est la notion formelle d'un mappage des entrées aux sorties. Ainsi, par exemple, "trier" est un mappage entre une séquence d'articles commandables et une séquence d'articles commandables du même type, qui mappe chaque séquence à sa séquence ordonnée. Cette fonction pourrait être implémentée en utilisant différents algorithmes (par exemple, tri par fusion, tri par tas). Chaque algorithme, à son tour, pourrait être implémenté en utilisant des programmes différents (même avec le même langage de programmation).

Ainsi, la meilleure façon dont nous disposons de ce qu'est un «algorithme» est qu'il s'agit d'une sorte de classe d'équivalence sur les programmes, où deux programmes sont équivalents s'ils font «essentiellement la même chose». Deux programmes qui implémentent le même algorithme doivent calculer la même fonction, mais l'inverse n'est pas vrai.

De même, il existe une classe d'équivalence entre les algorithmes, où deux algorithmes sont équivalents s'ils calculent la même fonction mathématique.

Le plus difficile dans tout cela est d'essayer de saisir ce que nous entendons par «essentiellement la même chose».

Il y a certaines choses évidentes que nous devrions inclure. Par exemple, deux programmes sont essentiellement identiques s'ils ne diffèrent que par des renommages variables. La plupart des modèles de langages de programmation ont des notions natives d '«équivalence» (par exemple, la réduction bêta et la conversion ETA dans le calcul lambda), nous devons donc les ajouter également.

Quelle que soit la relation d'équivalence que nous choisissons, cela nous donne une certaine structure. Les algorithmes forment une catégorie en raison du fait qu'ils sont la catégorie de quotient des programmes. Certaines relations équivalentes intéressantes sont connues pour donner lieu à des structures catégorielles intéressantes; par exemple, la catégorie des algorithmes récursifs primitifs est un objet universel dans la catégorie des catégories. Chaque fois que vous voyez une structure intéressante comme celle-ci, vous savez que cette piste d'enquête sera probablement utile.

Votre question et votre description n'ont pas grand-chose à voir. L'algorithme est théorique et ne concerne aucun langage de programmation. L'algorithme est un ensemble de règles ou d'étapes (procédure) pour résoudre un problème. Votre problème peut être résolu de plusieurs manières ou avec de nombreux algorithmes.

Votre deuxième solution consiste à calculer d'abord un large éventail de factorielles qui, dans un premier temps, prendra beaucoup de temps, puis à le stocker. Il consommera plus de stockage mais finalement il sera plus rapide tandis que le premier ne consomme pas de stockage mais consomme de la puissance de calcul, vous devrez donc choisir en fonction de votre environnement.