Algorithme

Organigrammes sont souvent utilis??s pour repr??senter graphiquement algorithmes.

En math??matiques , informatique, la linguistique et des disciplines connexes, un algorithme est un type de m??thode dans laquelle une liste d??finitive d'instructions bien d??finies pour remplir une t??che, quand donn?? un ??tat initial, sera trait?? par une s??rie bien d??finie d'??tats successifs, ??ventuellement terminant dans un ??tat final. La transition d'un ??tat ?? l'autre ne est pas n??cessairement d??terministe; certains algorithmes, appel??s algorithmes probabilistes, int??grent al??atoire.

Le concept d'un algorithme ?? l'origine un moyen de proc??dures pour r??soudre des probl??mes math??matiques tels que trouver le bon enregistrement diviseur de deux nombres ou la multiplication de deux nombres; ces algorithmes ??taient utilis??s par les Babyloniens d??s 1600 BC.

Une formalisation partielle du concept a commenc?? avec des tentatives pour r??soudre le Entscheidungsproblem (le ??probl??me de d??cision") que David Hilbert pos?? en 1928. formalisations ult??rieures ??taient con??ues comme des tentatives de d??finir " calculabilit?? effective "(Kleene 1943: 274) ou?? m??thode ??(Rosser 1939: 225); ces formalisations inclus l'G??del-Herbrand-Kleene fonctions r??cursives de 1930, 1934 et 1935, Eglise Alonzo lambda-calcul de 1936, "Formulation I" d'Emil Poster de 1936, et Alan Turing s ' Les machines de Turing de 1936-7 et 1939.

??tymologie

Al-Khwarizmi , Persique astronome et math??maticien , a ??crit un trait?? en arabe en 825 apr??s JC, sur le calcul des chiffres hindous. (Voir algorism). Il a ??t?? traduit en latin au 12e si??cle comme Algoritmi de numero Indorum (al-Daffa 1977), dont le titre ??tait susceptible entend "[R??server par] Algoritmus sur les num??ros des Indiens", o?? "Algoritmi" ??tait la restitution du traducteur du nom de l'auteur dans le cas g??nitif; mais les gens incompr??hension le titre Algoritmi trait??s comme un pluriel latine et ce qui a conduit au mot "algorithme" (de Algorismus latine) ?? venir pour signifier "m??thode de calcul". Le "e" intrusive est probablement d?? ?? un faux ami avec les grecs αριθμος (arithmos) signifie "nombre".

Pourquoi algorithmes sont n??cessaires: une d??finition informelle

Aucune d??finition formelle g??n??ralement accept?? de ??algorithme?? existe encore. Nous pouvons, cependant, tirer des indices sur les enjeux et un sens informel du mot de la citation suivante de Boolos & Jeffrey (1974, 1999) (gras ajout??):

Aucun ??tre humain ne peut ??crire assez vite ou assez longtemps ou assez petit pour lister tous les membres d'un ensemble enumerably infinie en ??crivant leurs noms, un apr??s l'autre, dans une notation. Mais les humains peuvent faire quelque chose d'aussi utile, dans le cas de certains ensembles infinis enumerably: Ils peuvent donner des instructions explicites pour d??terminer la ni??me membre de l'ensemble, pour arbitraire finie n. Ces instructions doivent ??tre donn??s de mani??re tr??s explicite, sous une forme dans laquelle ils pourraient ??tre suivies par une machine de calcul, ou par un humain qui est capable de ne effectuer que des op??rations tr??s ??l??mentaires sur les symboles (Boolos & Jeffrey 1974, 1999, p. 19 )

Les mots "enumerably infinie" signifient "en utilisant d??nombrable entiers se ??tendant peut-??tre ?? l'infini". Ainsi Boolos et Jeffrey disent qu'un algorithme implique des instructions pour un processus qui "cr??e" entiers de sortie ?? partir d'une "entr??e" entier arbitraire ou entiers qui, en th??orie, peut ??tre choisi parmi 0 ?? l'infini. Ainsi nous pourrions nous attendre un algorithme pour ??tre une ??quation alg??brique tels que y = m + n - deux ??variables d'entr??e" arbitraires m et n qui produisent une sortie y. Comme on le voit dans caract??risations de l'algorithme - le mot algorithme implique beaucoup plus que cela, quelque chose de l'ordre de (pour notre exemple de plus):

Des instructions pr??cises (en langue comprise par "l'ordinateur") pour une "efficace, bonne rapide," processus qui sp??cifie les "mouvements" de "l'ordinateur" (machine ou humain, ??quip?? avec les informations contenues interne et les capacit??s n??cessaires) pour trouver, d??coder, puis grignoter arbitraires entiers d'entr??e / symboles m et n, symboles + et = ... et (de mani??re fiable, correctement, ??efficacement??) de produire, dans un ??raisonnable?? le temps , sortie entier y en un lieu d??termin?? et dans un format sp??cifi??.

Le concept d'algorithme est ??galement utilis?? pour d??finir la notion de d??cidabilit?? (logique). Cette notion est centrale pour expliquer comment syst??mes formels naissent ?? partir d'un petit ensemble de axiomes et les r??gles. Dans la logique , le temps que n??cessite un algorithme pour compl??ter ne peut pas ??tre mesur??e, car il ne est apparemment pas li??e avec notre dimension physique coutumier. De telles incertitudes, qui caract??risent les travaux en cours, les tiges de l'indisponibilit?? d'une d??finition de l'algorithme qui convient ?? la fois concr??te (en quelque sorte) et l'utilisation abstraite du terme.

Pour une pr??sentation d??taill??e des diff??rents points de vue autour de la d??finition de "algorithme" voir caract??risations algorithme. Pour des exemples d'algorithmes simples d'addition sp??cifi??es de la mani??re d??crite dans l'd??taill??e caract??risations algorithme, consultez Exemples de algorithme.

Formalisation des algorithmes

Algorithmes sont essentiels ?? la fa??on dont les ordinateurs de traiter l'information, car un programme d'ordinateur est essentiellement un algorithme qui indique ?? l'ordinateur quelles mesures sp??cifiques ?? effectuer (dans quel ordre sp??cifique) afin d'effectuer une t??che pr??cise, comme le calcul de ch??ques de paie ou l'impression ??tudiants des employ??s les bulletins. Ainsi, un algorithme peut ??tre consid??r?? comme ne importe quelle s??quence d'op??rations qui peuvent ??tre effectu??es par un Turing-complet syst??me. Les auteurs qui affirment cette th??se comprennent Savage (1987) et Gurevich (2000):

... L'argument informel de Turing en faveur de sa th??se justifie une th??se forte: chaque algorithme peut ??tre simul?? par une machine de Turing (Gurevich 2000: 1) ... selon Savage [1987], un algorithme est un processus de calcul d??fini par une machine de Turing. (Gurevich 2000: 3)

Typiquement, quand un algorithme est associ?? au traitement d'informations, les donn??es sont lues ?? partir d'une source ou d'un dispositif d'entr??e, ??crites dans un ??vier ou un dispositif de sortie, et / ou stock??es pour un traitement ult??rieur. Les donn??es stock??es sont consid??r??s comme faisant partie de l'??tat interne de l'entit?? effectuant l'algorithme. Dans la pratique, l'??tat est stock?? dans un structure de donn??es, mais un algorithme n??cessite les donn??es internes seulement pour les jeux de fonctionnement sp??cifiques appel??s types de donn??es abstraits.

Pour tout ce processus de calcul, l'algorithme doit ??tre rigoureusement d??fini: sp??cifi?? dans la fa??on dont elle se applique en toutes circonstances possibles qui pourraient survenir. Ce est, toutes les mesures conditionnelles doivent ??tre syst??matiquement trait??es au cas par cas; les crit??res pour chaque cas doit ??tre clair (et calculable).

Parce que un algorithme est une liste pr??cise des ??tapes pr??cises, l'ordre de calcul sera presque toujours critique pour le fonctionnement de l'algorithme. Les instructions sont g??n??ralement suppos??s ??tre ??num??r??s explicitement, et sont d??crites comme de d??part "par le haut" et aller "vers le bas", une id??e qui est d??crit plus formellement par flux de contr??le.

Jusqu'?? pr??sent, cette discussion de la formalisation d'un algorithme a assum?? les locaux de la programmation imp??rative. Ce est la conception la plus courante, et il tente de d??crire une t??che dans discrets, des moyens ??m??caniques??. Unique ?? cette conception d'algorithmes formalis??s est le op??ration d'affectation, le r??glage de la valeur d'une variable. Elle d??coule de l'intuition de " m??moire "comme un bloc-notes. Il est un exemple ci-dessous d'une telle cession.

Pour certaines des conceptions diff??rentes de ce qui constitue une mer de l'algorithme programmation fonctionnelle et programmation logique.

R??siliation

Certains auteurs limitent la d??finition de l'algorithme ?? des proc??dures qui terminent finalement. Dans une telle cat??gorie Kleene place la "m??thode de proc??dure de d??cision ou de la d??cision ou de l'algorithme pour la question" (Kleene 1952: 136). D'autres, dont Kleene, incluent des proc??dures qui pourrait fonctionner pour toujours sans se arr??ter; une telle proc??dure a ??t?? appel?? une "m??thode de calcul" (Knuth 1997: 5) ou ??proc??dure de calcul ou d'un algorithme" (Kleene 1952: 137); toutefois, Kleene note qu'une telle m??thode doit finalement pr??senter "un objet" (Kleene 1952: 137).

Minsky fait l'observation pertinente, en ce qui concerne d??terminer si un algorithme finira fin (d'un ??tat de d??part particulier):

Mais si la longueur de la proc??dure ne est pas connue ?? l'avance, puis 'essayer' il ne peut pas ??tre d??cisif, parce que si le processus ne va ??ternellement - puis ?? aucun moment nous ne jamais ??tre s??r de la r??ponse (Minsky 1967: 105) .

Comme il arrive, aucune autre m??thode ne peut faire mieux, comme l'a montr?? par Alan Turing avec son c??l??bre r??sultat sur l'ind??cidabilit?? de la soi-disant probl??me de l'arr??t. Il ne existe aucune proc??dure algorithmique pour d??terminer des algorithmes arbitraires ou non ils se terminent par les Etats de d??part donn??. L'analyse d'algorithmes pour leur probabilit?? de r??siliation est appel?? analyse de r??siliation.

Voir les exemples de (im -) soustraction "bon" au fonction partielle pour plus sur ce qui peut arriver quand un algorithme ??choue pour certains de ses num??ros d'entr??e - par exemple, (i) non-terminaison, (ii) la production de "junk" (sortie dans le mauvais format ?? ??tre consid??r?? comme un num??ro) ou pas Num??ro (s) du tout (arr??t termine le calcul sans sortie), (iii) un mauvais num??ro (s), ou (iv) une combinaison de ces. Kleene propos?? que la production de "junk" ou d??faut de produire un certain nombre est r??solu en ayant l'algorithme d??tecter ces cas et de produire par exemple, un message d'erreur (il a sugg??r?? ??0??), ou de pr??f??rence, forcer l'algorithme dans une boucle sans fin ( Kleene 1952: 322). Davis fait cela ?? son algorithme de soustraction - il fixe son algorithme dans un deuxi??me exemple de telle sorte que ce est une bonne soustraction (Davis 1958: 12-15). Avec les r??sultats logiques ??vrai?? et ??faux?? Kleene propose ??galement l'utilisation d'un troisi??me symbole logique "u" - ind??cis (Kleene 1952: 326) - donc un algorithme sera toujours produire quelque chose face ?? une ??proposition??. Le probl??me des mauvaises r??ponses doit ??tre r??solu avec une "preuve" ind??pendante de l'algorithme par exemple, en utilisant l'induction:

Nous exigeons normalement preuves auxiliaire pour ce (que l'algorithme d??finit correctement une mu fonction r??cursive), par exemple, sous la forme d'une preuve inductive que, pour chaque valeur de l'argument, le calcul se termine avec une valeur unique (Minsky 1967: 186).

Exprimant algorithmes

Les algorithmes peuvent ??tre exprim??s dans de nombreux types de notation, y compris langues naturelles, pseudo, organigrammes, et les langages de programmation . Expressions en langage naturel d'algorithmes ont tendance ?? ??tre verbeux et ambigu??, et sont rarement utilis??s pour les algorithmes complexes ou techniques. Pseudocode et organigrammes sont des moyens structur??s pour exprimer des algorithmes qui permettent d'??viter la plupart des ambigu??t??s communs dans les ??tats du langage naturel, tout en restant ind??pendant d'un langage de mise en ??uvre particuli??re. Les langages de programmation sont principalement destin??s ?? exprimer des algorithmes sous une forme qui peut ??tre ex??cut?? par un ordinateur , mais sont souvent utilis??s comme un moyen de d??finir ou algorithmes de documents.

Il ya une grande vari??t?? de repr??sentations possible et on peut exprimer une donn??e Turing programme de la machine comme une s??quence de tables de machine (voir plus ?? machine ?? ??tats finis et transition d'??tat de table), comme des organigrammes (voir plus ?? diagramme d'??tat), ou comme une forme de rudimentaires code machine ou code assembleur appel?? "ensembles de quadruples" (voir plus au Machine de Turing).

Parfois, il est utile dans la description d'un algorithme pour compl??ter petits "organigrammes" (diagrammes ??tat) en langage naturel et / ou expressions arithm??tiques ??crites ?? l'int??rieur " diagrammes "Pour r??sumer ce que les?? organigrammes ??accomplissent.

Repr??sentations algorithmes sont g??n??ralement class??s en trois niveaux accept??s de description de machine de Turing (Sipser 2006: 157):

• Description 1 de haut niveau:

"... La prose pour d??crire un algorithme, en ignorant les d??tails de mise en ??uvre. A ce niveau, nous ne avons pas besoin de mentionner comment la machine g??re sa cassette ou la t??te"

• Description 2 de mise en ??uvre:

"... La prose utilis??e pour d??finir la fa??on dont la machine de Turing utilise sa t??te et la fa??on dont il stocke les donn??es sur sa bande. A ce niveau, nous ne donnons pas de d??tails des Etats ou de la fonction de transition"

• 3 Description formelle:

Plus d??taill??, "plus bas niveau", donne "la table d'??tat" de la machine de Turing.

Ex??cution

La plupart des algorithmes sont destin??s ?? ??tre mis en oeuvre en tant que programmes informatiques. Cependant, les algorithmes sont ??galement mis en ??uvre par d'autres moyens, par exemple dans un biologique r??seau de neurones (par exemple, la cerveau humain ex??cution arithm??tique ou un insecte ?? la recherche de nourriture), dans une circuit ??lectrique, ou dans un dispositif m??canique.

Exemple

Un des algorithmes les plus simples est de trouver le plus grand nombre dans une liste (non tri??s) de nombres. La solution n??cessairement faut examiner ?? chaque num??ro de la liste, mais seulement une fois ?? chaque. De l?? d??coule un algorithme simple, qui peut ??tre indiqu?? dans une description de haut niveau English prose, que:

Description de haut niveau:

1. Supposons que le premier ??l??ment est le plus grand.
2. Regardez chacun des ??l??ments restants de la liste et se il est plus grand que le plus gros poste jusqu'?? pr??sent, faire une note.
3. Le dernier ??l??ment not?? est le plus grand dans la liste lorsque le processus est termin??.

(Quasi) description formelle: ??crit en prose, mais beaucoup plus proche du langage de haut niveau d'un programme informatique, ce qui suit est le codage plus formelle de l'algorithme pseudo ou Code pidgin:

 Algorithme LargestNumber
   Entr??e: Une liste non vide de chiffres L.
   Sortie: Le plus grand nombre dans la liste L.

   Le plus grand L ← 0
   pour chaque ??l??ment de la liste L ≥1, faire
     si l'article> plus grand, puis
       Le plus grand ← l'??l??ment
   revenir plus grand

Pour un exemple plus complexe d'un algorithme, consultez L'algorithme d'Euclide pour le plus grand commun diviseur , un des premiers algorithmes connus.

Algorithme d'analyse

Comme il arrive, il est important de savoir combien d'une ressource particuli??re (comme le temps ou le stockage) est n??cessaire pour un algorithme donn??. Des m??thodes ont ??t?? d??velopp??es pour la analyse des algorithmes pour obtenir ces r??ponses quantitatives; par exemple, l'algorithme ci-dessus a une exigence de temps en O (n), en utilisant la notation O grande avec n que la longueur de la liste. En tout temps l'algorithme ne doit se rappeler deux valeurs: le plus grand nombre trouv?? jusqu'ici, et sa position actuelle dans la liste d'entr??e. Par cons??quent, il est dit d'avoir un encombrement de O (1), si l'espace n??cessaire pour stocker les num??ros d'entr??e ne est pas compt??, ou O (log n) si elle est compt??e.

Diff??rents algorithmes peuvent remplir la m??me t??che avec un ensemble diff??rent d'instructions en moins ou de plus de temps, l'espace, ou d'effort que d'autres. Par exemple, compte tenu de deux recettes diff??rentes pour faire la salade de pommes de terre, on peut avoir peler la pomme de terre avant de faire bouillir la pomme de terre tandis que l'autre pr??sente les ??tapes dans l'ordre inverse, mais ils ont tous deux appel ?? ces mesures pour ??tre r??p??t??e pour toutes les pommes de terre et fin lorsque le salade de pomme de terre est pr??t ?? ??tre mang??.

Le l'analyse et l'??tude des algorithmes est une discipline de l'informatique , et est souvent pratiqu??e abstraitement, sans l'utilisation d'un sp??cifique langage de programmation ou de mise en ??uvre. En ce sens, l'analyse de l'algorithme ressemble ?? d'autres disciplines math??matiques en ce qu'elle met l'accent sur les propri??t??s sous-jacentes de l'algorithme et non sur les d??tails de toute mise en ??uvre particuli??re. Habituellement pseudo-code est utilis?? pour l'analyse comme ce est la repr??sentation la plus simple et le plus g??n??ral.

Classes

Il existe diff??rentes fa??ons de classer les algorithmes, chacun avec ses propres m??rites.

Classification par la mise en ??uvre

Une fa??on de classer les algorithmes est par des moyens de mise en ??uvre.

• R??cursivit?? ou it??ration: A algorithme r??cursif est celui qui invoque (fait r??f??rence ??) jusqu'?? ce que lui-m??me un certains matchs de condition, qui est une m??thode commune ?? programmation fonctionnelle. Algorithmes it??ratifs utilisent constructions r??p??titives comme les boucles et les structures de donn??es suppl??mentaires comme parfois piles pour r??soudre les probl??mes donn??s. Certains probl??mes sont naturellement adapt??s pour une mise en ??uvre ou de l'autre. Par exemple, tours de Hanoi est bien compris dans la mise en ??uvre r??cursive. Chaque Version r??cursive a un ??quivalent (mais peut-??tre plus ou moins complexe) version it??rative, et vice versa.

• Logique: Un algorithme peut ??tre consid??r??e comme contr??l??e d??duction logique. Cette notion peut ??tre exprim??e comme suit: Algorithme = + logique de contr??le (Kowalski 1979). Le composant logique exprime les axiomes qui peuvent ??tre utilis??s dans le calcul et le composant de commande d??termine la mani??re dont la d??duction est appliqu??e aux axiomes. Ce est la base de la paradigme de programmation logique. Dans les langages de programmation de la logique pure du composant de commande est fixe et algorithmes sont sp??cifi??s en fournissant uniquement le composant logique. L'int??r??t de cette approche est l'??l??gant s??mantique: un changement dans les axiomes a un changement bien d??fini dans l'algorithme.

• S??rie ou parall??le ou distribu??: Algorithmes sont habituellement discut??s avec l'hypoth??se que les ordinateurs ex??cutent une instruction d'un algorithme ?? la fois. Ces ordinateurs sont parfois appel??s ordinateurs s??rie. Un algorithme con??u pour un tel environnement est appel?? un algorithme en s??rie, par opposition ?? algorithmes parall??les ou algorithmes distribu??s. Algorithmes parall??les profitent des architectures informatiques o?? plusieurs processeurs peuvent travailler sur un probl??me en m??me temps, alors que les algorithmes distribu??s utilisent plusieurs machines connect??es avec un r??seau. Algorithmes parall??les ou distribu??s divisent le probl??me en sous plus sym??triques ou asym??triques et de recueillir les r??sultats de retour ensemble. La consommation de ressources dans ces algorithmes ne sont pas seulement des cycles de processeur de chaque processeur, mais aussi le co??t de communication entre les processeurs. Algorithmes de tri peuvent ??tre parall??lis??s efficacement, mais leurs frais g??n??raux de communication est cher. Algorithmes it??ratifs sont g??n??ralement parall??lisables. Certains probl??mes ne ont pas algorithmes parall??les, et sont appel??s intrins??quement probl??mes s??rie.

• D??terministe ou non-d??terministe: Algorithmes d??terministes de r??soudre le probl??me ?? la d??cision exacte ?? chaque ??tape de l'algorithme alors algorithme non d??terministe via r??soudre les probl??mes typiques deviner bien que des suppositions sont faites plus pr??cise par l'utilisation de heuristiques.

• Exacte ou approximative: Alors que de nombreux algorithmes atteignent une solution exacte, algorithmes d'approximation cherchent une approximation qui est proche de la vraie solution. Rapprochement peut utiliser soit un d??terministe ou une strat??gie al??atoire. Ces algorithmes ont une valeur pratique pour de nombreux probl??mes difficiles.

Classement par paradigme de conception

Une autre fa??on de classer les algorithmes est par leur m??thodologie de conception ou d'un paradigme. Il existe un certain nombre de paradigmes, chacune diff??rente de l'autre. En outre, chacune de ces cat??gories comprendra beaucoup de diff??rents types d'algorithmes. Des paradigmes couramment trouv??s sont les suivants:

• Diviser et conqu??rir. Un diviser et conqu??rir algorithme r??duit ?? plusieurs reprises une instance d'un probl??me ?? un ou plusieurs petits instances du m??me probl??me (g??n??ralement r??cursive), jusqu'?? ce que les cas sont assez petit pour r??soudre facilement. Un exemple de diviser pour r??gner est fusionner tri. Tri peut ??tre fait sur chaque segment de donn??es apr??s diviser les donn??es en segments et de tri des donn??es enti??res peuvent ??tre obtenus en phase de conqu??te en les fusionnant. Une variante plus simple de diviser pour r??gner est appel?? diminution et conqu??rir algorithme, qui r??sout un sous-probl??me identiques et utilise la solution de ce sous-probl??me ?? r??soudre le plus grand probl??me. Diviser pour r??gner divise le probl??me en plusieurs sous-probl??mes et ainsi de conqu??rir ??tape sera plus complexe que la diminution et conqu??rir algorithmes. Un exemple de diminution r??gner algorithme est Dichotomie.
• La programmation dynamique. Quand un probl??me montre sous-structure optimale, ce qui signifie la solution optimale ?? un probl??me peut ??tre construit ?? partir de solutions optimales pour sous-probl??mes, et sous-probl??mes qui se chevauchent, ce qui signifie les m??mes sous-probl??mes sont utilis??es pour r??soudre de nombreux cas de probl??mes diff??rents, une approche plus rapide appel?? programmation dynamique ??vite les solutions de recalculer qui ont d??j?? ??t?? calcul??es. Par exemple, le chemin le plus court pour un objectif d'un sommet en un pond??r?? graphique peut ??tre trouv??e en utilisant le chemin le plus court ?? l'objectif de tous les sommets adjacents. La programmation dynamique et memoization aller ensemble. La principale diff??rence entre la programmation dynamique et diviser pour r??gner, ce est que sous-probl??mes sont plus ou moins ind??pendante sur diviser pour r??gner, alors sous-probl??mes se chevauchent dans la programmation dynamique. La diff??rence entre la programmation dynamique et la r??cursivit?? directe est mise en cache ou memoization d'appels r??cursifs. Lorsque sous-probl??mes sont ind??pendants et il n'y a pas de r??p??tition, memoization ne aide pas; donc programmation dynamique ne est pas une solution ?? tous les probl??mes complexes. En utilisant memoization ou le maintien d'un table des sous-probl??mes d??j?? r??solu, programmation dynamique r??duit la nature exponentielle de nombreux probl??mes ?? la complexit?? polynomiale.
• La m??thode gourmande. Un algorithme glouton est similaire ?? un algorithme de programmation dynamique, mais la diff??rence est que les solutions aux sous-probl??mes ne ont pas ?? ??tre connu ?? chaque ??tape; au lieu d'un choix "gourmande" peut ??tre faite de ce qui semble le mieux pour le moment. La m??thode gourmande ??tend la solution avec la meilleure d??cision possible (pas toutes les d??cisions possibles) ?? un stade algorithmique bas??e sur le courant optimum local et la meilleure d??cision (pas toutes les d??cisions possibles) fait dans l'??tape pr??c??dente. Il ne est pas exhaustive, et ne donne pas de r??ponse pr??cise ?? de nombreux probl??mes. Mais quand ??a marche, ce sera la m??thode la plus rapide. L'algorithme glouton plus populaire est de trouver l'arbre couvrant minimal donn?? par Kruskal.
• La programmation lin??aire. Lorsque la r??solution d'un probl??me ?? l'aide programmation lin??aire, sp??cifique in??galit??s impliquant les entr??es se trouvent, puis une tentative est faite pour maximiser (ou minimiser) une fonction lin??aire des entr??es. De nombreux probl??mes (par exemple, la d??bit maximal pour dirig?? graphiques) peut ??tre indiqu?? d'une mani??re de programmation lin??aire, puis ??tre r??solu par un algorithme ??g??n??rique?? comme le algorithme simplex. Une variante plus complexe de la programmation lin??aire est appel?? programmation en nombres entiers, o?? l'espace de solution est limit??e aux nombres entiers .
• R??duction. Cette technique consiste ?? r??soudre un probl??me difficile en le transformant en un probl??me mieux connu pour laquelle nous avons (nous l'esp??rons) algorithmes asymptotiquement optimale. Le but est de trouver un algorithme dont la r??duction la complexit?? ne est pas domin?? par l'algorithme de r??duction r??sultant. Par exemple, une algorithme de s??lection pour trouver la m??diane dans une liste non tri??s consiste ?? trier d'abord la liste (la partie cher) et puis en tirant l'??l??ment central dans la liste tri??e (la partie pas cher). Cette technique est ??galement connu que de transformer et de conqu??rir.
• Recherche et d??nombrement. Beaucoup de probl??mes (comme le jeu d'??checs ) peuvent ??tre mod??lis??s comme des probl??mes sur graphiques. Un graphe algorithme d'exploration sp??cifie les r??gles pour se d??placer un graphique et est utile pour de tels probl??mes. Cette cat??gorie comprend ??galement algorithmes de recherche, branche et le d??nombrement li?? et retour en arri??re.
• Le paradigme probabiliste et heuristique. Algorithmes appartenant ?? cette classe correspondent ?? la d??finition d'un algorithme plus l??che.

1. Algorithmes probabilistes sont ceux qui font des choix au hasard (ou pseudo-al??atoire); pour certains probl??mes, il peut en effet ??tre prouv?? que les solutions les plus rapides doivent impliquer une certaine al??atoire.
2. Les algorithmes g??n??tiques tentent de trouver des solutions aux probl??mes en imitant biologiques ??volutives processus, avec un cycle de mutations al??atoires produisant des g??n??rations successives de ??solutions??. Ainsi, ils ??mulent reproduction et "la survie du plus apte??. En programmation g??n??tique, cette d??marche se ??tend ?? des algorithmes, en consid??rant l'algorithme lui-m??me comme une ??solution?? ?? un probl??me.
3. Algorithmes heuristiques, dont la mission g??n??rale est de ne pas trouver une solution optimale, mais une solution approximative o?? le temps ou les ressources sont limit??es. Ils ne sont pas pratiques pour trouver des solutions parfaites. Un exemple de ceci serait recherche locale, recherche tabou, ou algorithmes de recuit simul??, une classe d'algorithmes probabilistes heuristiques qui varient la solution d'un probl??me par une quantit?? al??atoire. Le nom " recuit simul?? ??fait allusion ?? l'expression m??tallurgique qui signifie que le chauffage et le refroidissement de m??tal pour atteindre la libert?? de d??fauts. Le but de la variance al??atoire est de trouver pr??s de globalement solutions optimales plut??t que ceux simplement localement optimales, l'id??e ??tant que l'??l??ment al??atoire sera ??tre diminu?? par l'algorithme se ??tablit ?? une solution.

Classification par domaine d'??tudes

Chaque domaine de la science a ses propres probl??mes et des besoins des algorithmes efficaces. Les probl??mes li??s ?? un champ sont souvent ??tudi??s ensemble. Certaines classes exemples sont algorithmes de recherche, algorithmes de tri, fusionner algorithmes, algorithmes num??riques, algorithmes de graphe, algorithmes de cha??ne, algorithmes g??om??triques de calcul, des algorithmes combinatoires , l'apprentissage machine, la cryptographie , les algorithmes de compression de donn??es et techniques de l'analyse.

Les champs tendent ?? se chevaucher les uns avec les autres, et les progr??s de l'algorithme dans un domaine peuvent am??liorer ceux des autres, parfois sans aucun rapport, les champs. Par exemple, la programmation dynamique a ??t?? invent?? pour l'optimisation de la consommation des ressources dans l'industrie, mais est maintenant utilis?? pour r??soudre un large ??ventail de probl??mes dans de nombreux domaines.

Classification par la complexit??

Les algorithmes peuvent ??tre class??s par la quantit?? de temps n??cessaire pour compl??ter rapport ?? leur taille d'entr??e. Il ya une grande vari??t??: certains algorithmes complets en temps lin??aire par rapport ?? la taille d'entr??e, certains le font dans une quantit?? exponentielle du temps, ou pire encore, et certains ne ont jamais se arr??ter. En outre, certains probl??mes peuvent avoir de multiples algorithmes de complexit?? diff??rente, tandis que d'autres probl??mes pourraient avoir aucun algorithmes ou aucun des algorithmes efficaces connus. Il existe ??galement des probl??mes de mappages d'autres probl??mes. De ce fait, il se est r??v??l?? ??tre plus appropri?? pour classer les probl??mes eux-m??mes au lieu des algorithmes en classes d'??quivalence en fonction de la complexit?? des meilleurs algorithmes possibles pour eux.

Classification par la puissance de calcul

Une autre fa??on de classer les algorithmes est par la puissance de calcul. Cela se fait habituellement en consid??rant une certaine collection (classe) d'algorithmes. Une classe d'algorithmes r??cursif est celui qui comprend des algorithmes pour toutes les fonctions calculables Turing. En regardant classes d'algorithmes permet la possibilit?? de restreindre les ressources informatiques disponibles (temps et m??moire) utilis??es dans un calcul. Une classe subrecursive d'algorithmes est celui dans lequel pas toutes les fonctions calculables Turing peuvent ??tre obtenus. Par exemple, les algorithmes qui se ex??cutent dans polynomiale suffit pour de nombreux types importants de calcul, mais ne ??puisent pas toutes les fonctions calculables de Turing. Les algorithmes de classe mises en ??uvre par fonctions r??cursives primitives est une autre classe subrecursive.

Burgin (2005, p. 24) utilise une d??finition g??n??ralis??e des algorithmes qui d??tend l'exigence commune que la sortie de l'algorithme qui calcule une fonction doit ??tre d??termin??e apr??s un nombre fini d'??tapes. Il d??finit aa classe d'algorithmes super-r??cursif "une classe d'algorithmes dans lesquels il est possible de calculer les fonctions non calculables par une machine de Turing" (Burgin 2005, p. 107). Ceci est ??troitement li?? ?? l'??tude de m??thodes de Hypercalcul.

Questions juridiques

Algorithmes, par eux-m??mes, ne sont g??n??ralement pas brevetables. Dans le ??tats-Unis , une r??clamation compos?? uniquement de simples manipulations de concepts abstraits, des chiffres ou des signaux ne constituent pas des "processus" (USPTO 2006) et donc algorithmes ne sont pas brevetables (comme dans Gottschalk v. Benson). Cependant, les applications pratiques des algorithmes sont parfois brevetable. Par exemple, dans Diamond c. Diehr, l'application d'un simple, r??troaction algorithme pour aider ?? la cuisson de de caoutchouc synth??tique a ??t?? jug??e brevetable. Le brevetabilit?? des logiciels est tr??s controvers??e, et il ya des brevets tr??s critiqu??e impliquant des algorithmes, en particulier les algorithmes de compression de donn??es, tels que Unisys ' Brevet LZW.

En outre, certains algorithmes cryptographiques ont des restrictions ?? l'exportation (voir l'exportation de la cryptographie).

Histoire: le d??veloppement de la notion de "algorithme"

Origine du mot

L'algorithme de mot vient du nom de la 9??me si??cle Math??maticien persan Abu Abdullah Muhammad ibn Musa al-Khwarizmi dont les ??uvres introduites chiffres indiens et concepts alg??briques. Il a travaill?? dans Bagdad ?? l'??poque o?? il ??tait le centre d'??tudes et des ??changes scientifiques. Le mot algorism origine ne visait que les r??gles de l'ex??cution arithm??tique utilisant Chiffres arabes, mais ??volu?? via la traduction latine europ??enne du nom de al-Khwarizmi dans algorithme par le 18??me si??cle. Le mot a ??volu?? pour inclure toutes les proc??dures d??finies pour r??soudre des probl??mes ou l'ex??cution de t??ches.

Symboles discrets et distinguables

Tally-marques: Pour garder une trace de leurs troupeaux, leurs sacs de grain et leur argent les anciens utilis??s d??compte: accumuler des pierres ou des marques ray??s sur des b??tons, ou de faire des symboles discrets dans l'argile. Gr??ce ?? l'utilisation babylonienne et ??gyptienne de marques et symboles, ??ventuellement chiffres romains et le boulier ??volu?? (Dilson, p.16-41). Tally marques apparaissent en bonne place dans unaire arithm??tique du syst??me de num??ration utilis?? dans Machine de Turing et Post-machine de Turing calculs.

Manipulation de symboles comme ??fictifs?? pour les num??ros: alg??bre

Le travail des anciens g??om??tres grecs, math??maticien perse Al-Khwarizmi (souvent consid??r?? comme le "p??re de l'alg??bre ??), et les math??maticiens d'Europe occidentale ont abouti ?? Leibniz notion de l 'de la calcul ratiocinator (ca 1680):

"Un bon si??cle et demi d'avance sur son temps, Leibniz propos?? une alg??bre de la logique, une alg??bre qui pr??cise les r??gles pour manipuler des concepts logiques de la mani??re que l'alg??bre ordinaire pr??cise les r??gles de manipulation de chiffres?? (Davis, 2000: 1)

Artifices m??caniques avec des ??tats discrets

L'horloge: Bolter attribue l'invention de la ?? poids horloge comme ??L'invention touche [de l'Europe au Moyen Age]", en particulier la ??chappement ?? verge <(Bolter 1984: 24) qui nous fournit avec le tic et le tac d'une horloge m??canique. "La machine automatique pr??cise" (Bolter 1984: 26) a conduit imm??diatement au ??m??canique automates "?? partir du XIIIe si??cle et enfin aux?? machines de calcul "- la Moteur de diff??rence et moteurs d'analyse de Charles Babbage et la comtesse Ada Lovelace (Bolter p.33-34, p.204-206).

m??tier ?? tisser Jacquard, cartes perfor??es Hollerith, t??l??graphie et la t??l??phonie - le relais ??lectrom??canique: Bell et Newell (1971) indiquent que la m??tier Jacquard (1801), pr??curseur de Cartes Hollerith (cartes perfor??es, 1887), et ??technologies de commutation t??l??phonique?? ??taient les racines d'un arbre menant ?? l'??laboration des premiers ordinateurs (Bell et Newell sch??ma p. 39, cf Davis 2000). Vers le milieu des ann??es 1800, le t??l??graphe, le pr??curseur du t??l??phone, ??tait en usage dans le monde entier, son codage discr??te et distingu??e de lettres comme ??points et de traits" un son commun. ?? la fin des ann??es 1800, le t??l??scripteur (des ann??es 1870 de CA) a ??t?? utilis??, comme ce ??tait l'usage de Cartes Hollerith dans le recensement am??ricain de 1890. Puis vint le T??l??scripteur (ca 1910) avec son usage de papier perfor?? Code Baudot sur bande.

T??l??phone-r??seaux de commutation ??lectrom??canique relais (invent?? 1835) ??tait derri??re le travail de George Stibitz (1937), l'inventeur du dispositif d'addition num??rique. Comme il a travaill?? dans les laboratoires Bell, il a observ?? l'utilisation "lourde" de calculatrices m??caniques avec des engrenages. "Il est all?? un soir en 1937 l'intention de tester son id??e .... Lorsque le bricolage ??tait termin??e, Stibitz avait construit un dispositif d'addition binaire". (Valley Nouvelles, p. 13).

Davis (2000) observe l'importance particulière du relais électromécanique (avec ses deux «états binaires"ouvertesetfermées):

Ce fut seulement avec le développement, en commençant dans les années 1930, des calculatrices électromécaniques utilisant des relais électriques, que les machines ont été construites ayant la portée Babbage avait imaginé. »(Davis, p. 14).

Mathématiques pendant les années 1800 jusqu'au milieu des années 1900

Symboles et règles : Dans une succession rapide les mathématiques de George Boole (1847, 1854), Gottlob Frege (1879), et Giuseppe Peano (1888-1889) a réduit l'arithmétique à une séquence de symboles manipulés par des règles. De Peano Les principes de l'arithmétique, présentés par une nouvelle méthode (1888) était "la première tentative d'axiomatisation des mathématiques dans un langage symbolique" (van Heijenoort: 81ff).

Mais Heijenoort donne Frege (1879) cette félicitations: Frege est «peut-être le travail le plus important jamais écrit dans la logique ... dans laquelle nous voyons un.» «Langue de formule», qui est uncharacterica lingua, une langue écrite avec des symboles spéciaux , "pour la pensée pure», qui est, sans fioritures rhétoriques ... construit à partir de symboles spécifiques qui sont manipulés conformément aux règles définies "(van Heijenoort: 1). Le travail de Frege était encore simplifiée et amplifiée parAlfred North Whitehead etBertrand Russelldans leurPrincipia Mathematica (1910-1913).

Les paradoxes : Dans le même temps un certain nombre de paradoxes troublants apparu dans la littérature, en particulier le paradoxe Burali-Forti (1897), le paradoxe Russell (1902-1903), et de la Richard Paradox (Dixon 1906, cf Kleene 1952: 36 -40). Les considérations qui en résultent ont conduit à l'article de Kurt Gödel (1931) - il cite spécifiquement le paradoxe du menteur - qui réduit complètement les règles de la récursivité pour les numéros.

Calculabilité effective : Dans un effort pour résoudre le Entscheidungsproblem défini précisément par Hilbert en 1928, les mathématiciens première série sur le point de définir ce que l'on entend par «méthode» ou «calcul efficace» ou «calculabilité effective" (ie, un calcul qui réussirait ). Dans une succession rapide qui suit est apparu: Alonzo Church, Stephen Kleene et de JB Rosser ??-calcul, (note cf dans Alonzo Church 1936a: 90, 1936b: 110) une définition finement aiguisé de «récursivité générale" du travail de Gödel agissant sur suggestions de Jacques Herbrand (les conférences de cf de Gödel Princeton de 1934) et des simplifications ultérieures par Kleene (1935-6: 237ff, 1943: 255ff). La preuve de l'église (1936: 88ff) que le Entscheidungsproblem était insoluble, la définition de Emil Poster de calculabilité effective en tant que travailleur stupidement suivant une liste d'instructions pour aller à gauche ou à droite à travers une séquence de pièces et bien qu'il soit la marque ou effacer un papier ou d'observer la papier et faire un oui-non décision au sujet de la prochaine instruction (cf "Formulation I", Poster 1936: 289-290). Alan Turing preuve s 'des que le Entscheidungsproblem était insoluble par l'utilisation de son "a- [matiquement] la machine "(Turing 1936-7: 116ff) - en effet presque identique à Postes" formulation ", J. La définition de Barkley Rosser de «méthode efficace" en termes de "une machine" (Rosser 1939: 226). La proposition de SC Kleene d'un précurseur de la " thèse de l'Eglise "qu'il a appelé" Thèse I "(Kleene 1943: 273-274), et quelques années plus tard Kleene de renommer sa thèse "la thèse de Church" (Kleene 1952: 300, 317) et de proposer des "Thèse de Turing" (Kleene 1952: 376).

Emil Post (1936) et Alan Turing (1936-7, 1939)

Voici une remarquable coïncidence des deux hommes ne sachant pas l'autre, mais un processus décrivant des hommes-comme-ordinateurs travaillant sur ??????des calculs - et ils céder définitions pratiquement identiques.

Emil Post (1936) décrit les actions d'un "ordinateur" (l'être humain) comme suit:

«... Deux concepts sont impliqués: celui d'unespace de symbolesdans lequel le travail menant de problème pour répondre doit être effectuée, et un inaltérable fixeensemble de directions.

Son espace de symbole serait

"Une à deux voies suite infinie des espaces ou des boîtes ... Le solveur de problème ou d'un travailleur est de se déplacer et de travailler dans cet espace de symbole, étant capable d'être dans, et opérant dans une boîte, mais à un moment .... une boîte est pour admettre, mais deux conditions possibles, à savoir, étant vide ou non marqué, et ayant une seule marque en elle, dire d'un trait vertical.

"Une boîte est d'être choisi et appelé le point de départ. ... Un problème spécifique doit être donnée sous forme symbolique par un nombre fini de boîtes [c.-à-INPUT] est marqué d'un trait. De même la réponse [c.-à- SORTIE] doit être donnée sous forme symbolique par une telle configuration des cases marquées ....

"Un ensemble de directives applicables à un problème général met en place un processus déterministe lorsqu'il est appliqué à chaque problème spécifique. Ce processus prendra fin que quand il vient à la direction de type (C) [ie, STOP]." (U p. 289-290) Voir plus à la machine de Turing Post-

Alan Turing travail de l '(1936, 1939: 160) a précédé celui de Stibitz (1937); on ignore si Stibitz connaissait le travail de Turing. Le biographe de Turing croit que l'utilisation de Turing d'un modèle de machine à écrire comme dérivé d'un intérêt de jeunesse: "Alan avait rêvé d'inventer des machines à écrire comme un garçon; Mme Turing avait une machine à écrire; et il pourrait bien avoir commencé par se demander ce que l'on entend par l'appel d'une machine à écrire «mécanique» (Hodges, p. 96). Compte tenu de la prévalence de morse et la télégraphie, machines de téléscripteur, et télétypes nous pourrions supposer que tous étaient influences .

Turing - son modèle de calcul est maintenant appelé une machine de Turing - commence, comme l'a fait Post, avec une analyse d'un ordinateur humaine qu'il rogne à une simple série de mouvements de base et des "états d'âme". Mais il continue un peu plus loin et crée une machine comme un modèle de calcul de nombres (Turing 1936-7: 116).

"Computing est normalement fait en écrivant certains symboles sur papier. Nous pouvons supposer ce document est divisé en carrés comme le livre de l'arithmétique d'un enfant .... Je suppose alors que le calcul est effectué sur papier à une dimension, à savoir, sur une bande divisée en carrés. Je vais aussi supposer que le nombre de symboles qui peuvent être imprimés est finie ....

"Le comportement de l'ordinateur à tout moment est déterminé par les symboles dont il est l'observation, et son" état ??????d'esprit "à ce moment. On peut supposer qu'il ya un B lié au nombre de symboles ou des carrés que l'ordinateur peut observer à un moment. Si il veut observer de plus, il doit utiliser observations successives. Nous allons également supposer que le nombre d'états d'esprit qui doivent être pris en compte est finie ...

"Imaginons que les opérations effectuées par l'ordinateur pour être divisés en« opérations simples »qui sont tellement élémentaire qu'il est pas facile de les imaginer outre divisé" (Turing 1936-7: 136).

La réduction de Turing donne le résultat suivant:

"Les opérations simples doivent donc comprendre:

"(A) Modifications du symbole sur une des places observés

"(B) Modifications de l'une des places observés à un autre carré dans L carrés de l'une des places observés précédemment.

"Il se peut que certains de ces changements invoquent nécessairement un changement d'état d'esprit La seule opération la plus générale doit donc être pris pour être l'un des suivants.:

"(A) Un changement possible (a) du symbole avec un éventuel changement de l'état d'esprit.

"(B) Un changement possible (b) de carrés observés, avec un éventuel changement de l'état d'esprit"

"Nous pouvons maintenant construire une machine pour faire le travail de cet ordinateur." (Turing 1936-7: 136)

Quelques années plus tard, Turing a élargi son analyse (thèse, définition) avec cette expression énergique de celui-ci:

"Une fonction est dite" effectivey calculable "si ses valeurs peuvent être trouvées par quelque procédé purement mécanique. Bien qu'il soit assez facile d'obtenir une compréhension intuitive de cette idée, il est souhaitable d'avoir neverthessless certains, la définition exprimable mathématique plus précis ... [il parle de l'histoire de la définition à peu près tel que présenté ci-dessus par rapport à Gödel, Herbrand, Kleene, Église, Turing et Post]... Nous pouvons prendre cette déclaration littéralement, la compréhension par un procédé purement mécanique qui pourrait être effectuée par une machine. Il est possible de donner une description mathématique, dans une certaine forme normale, des structures de ces machines. Le développement de ces idées conduit à la définition de l'auteur d'une fonction calculable, et à une identification de la calculabilité ??? avec calculabilité effective....

"??? Nous allons utiliser l'expression« fonction calculable »pour signifier une fonction calculable par une machine, et nous laisser" efficacement calculabile (Turing 1939: 160) "se réfèrent à l'idée intuitive sans identification particulière à l'une quelconque de ces définitions."

JB Rosser (1939) et SC Kleene (1943)

J. Barkley Rosserdéfini hardiment une «méthode [mathématique] efficace» de la manière suivante (en gras dans le texte):

«Méthode efficace» est utilisé ici dans le sens assez particulier d'une méthode chaque étape de ce qui est précisément déterminée, et qui est certain pour produire la réponse en un nombre fini d'étapes. Avec cette signification spéciale, trois définitions précises différents ont été donnés à ce jour [sa note n ° 5; voir la discussion immédiatement ci-dessous]. Le plus simple d'entre eux à l'état (en raison de la Poste et de Turing) dit essentiellement que. une méthode efficace de résolution de certains ensembles de problèmes existe si l'on peut construire une machine qui sera ensuite résoudre tout problème de l'ensemble sans aucune intervention humaine au-delà de l'insertion de la question et (plus tard) la lecture de la réponse . Tous les trois définitions sont équivalentes, de sorte qu'il n'a pas d'importance lequel est utilisé. En outre, le fait que tous les trois sont équivalentes est un argument très fort pour la justesse de l'une quelconque ". (Rosser 1939: 225-6)

La note N ° Rosser 5 références du travail de (1) Église et Kleene et leur définition de ??-définissabilité, dans l'utilisation de Eglise particulière de celui-ci dans son un problème insoluble du primaire Théorie des Nombres (1936); (2) Herbrand et Gödel et leur utilisation de la récursivité dans l'utilisation de Gödel notamment dans son fameux papier Sur Formellement indécidables Propositions de Principia Mathematica et des systèmes connexes I (1931); et (3) Post (1936) et Turing (1936-7) dans leur mécanisme modèles de calcul.

Stephen C. Kleene définie comme sa désormais célèbre "Thèse I" connu comme "la thèse de Church-Turing ". Mais il l'a fait dans le cadre ci-dessous (en caractères gras dans l'original):

"12.théories algorithmiques... En mettant en place une théorie algorithmique complète, ce que nous faisons est de décrire une procédure, exécutable pour chaque ensemble de valeurs des variables indépendantes, la procédure qui se termine nécessairement et de manière telle que le résultat que nous pouvons lu une réponse définitive, «oui» ou «non» à la question, "est la valeur de prédicat vrai?" "(Kleene 1943: 273)

Histoire après 1950

Un certain nombre d'efforts ont été dirigés vers affinement de la définition de «algorithme», et l'activité est en cours en raison de problèmes environnantes, en particulier, fondements des mathématiques (en particulier la Thèse de Church-Turing) et la philosophie de l'esprit (en particulier les arguments autour de l'intelligence artificielle). Pour plus, voir caractérisations algorithme.