Meilleure réponse
Il ny a pas de réponse à cela.
Trouvons la réponse à cet énoncé de problème:
Q. Comment trouver un algorithme qui fonctionne mieux?
A. Moyens les plus courants de comparer des algorithmes:
1) Complexité temporelle
2) Complexité spatiale
3) Qualité de la solution (peut ne pas applicable s’il propose de résoudre exactement un problème). Celui-ci peut être un facteur énorme si nous « parlons dalgorithmes dapproximation.
4) Facilité dimplémentation / adaptation dalgorithme. Certains algorithmes peuvent avoir beaucoup de frais généraux à implémenter correctement. Il existe parfois des algorithmes plus appropriés pour votre application. Par exemple, dans le calcul parallèle, la plupart trouveront Bellman-Ford plus utile que lalgorithme de Dijkstra en raison de la façon dont fonctionne Bellman-Ford.
Cependant, le temps et la complexité ne sont pas * toujours * la fonctionnalité souhaitable à maximiser; Je vais donner deux exemples.
Lun est la « stabilité numérique » , une caractéristique des algorithmes à la fois en algèbre linéaire et dans les équations différentielles. Nous consacrerons à la fois plus de temps algorithmique et plus de complexité algorithmique à des algorithmes plus stables numériquement. En algèbre linéaire, linstabilité est généralement causée lorsquun algorithme rencontre des nombres trop proches de zéro ou de linfini ou des deux, en raison de la représentation finie des nombres, la résolution peut être perdue. En général, cela provoque des nombres très légèrement différents, juste quelques epsilon différents les uns des autres (où epsilon est le plus petit nombre qui peut être ajouté à un, sur une machine, et obtenir un résultat! = 1), pour produire de grandes différences dans la réponse. Ainsi, par exemple, nous dépensons beaucoup de complexité en temps et en espace en « pivotant » dans la factorisation LU afin dobtenir un algorithme stable; sans pivotement LU nest pas stable. De même, nous avons des algorithmes qui ne font que « conditionner » les matrices afin déviter linstabilité.
Un deuxième exemple est « robustness » dans son sens statistique technique. La robustesse signifie une mesure ou un algorithme qui nest * pas * sensible aux valeurs aberrantes. Ainsi, par exemple, lorsque jadapte une ligne des moindres carrés à un ensemble de points, la ligne peut être fortement biaisée par une seule valeur extrêmement grande. Même si jai 99 paires de nombres qui forment une ligne parfaite à 45 degrés, si jajoute une seule paire aberrante pour laquelle la valeur Y est cent fois ce quelle «devrait» être pour tomber sur la même ligne, la ligne ajustée sera sévèrement déformé de la ligne de 45 degrés. Lalgorithme «abandonnera» lajustement parfait pour 99 points afin de mieux représenter le point aberrant. Ce nest * pas * robuste.
Une approche robuste des moindres carrés consiste, au lieu de trouver la ligne qui minimise la somme des erreurs quadratiques créées en utilisant cette ligne, à trouver la ligne qui minimise la * médiane * de les erreurs au carré créées en utilisant cette ligne. Dans lexemple, cette ligne est la ligne de 45 degrés, et la médiane des erreurs au carré est zéro, et le point aberrant (et en fait jusquà 98 autres valeurs aberrantes plus folles) serait complètement ignoré. On trouverait la ligne à 45 degrés.
Des algorithmes robustes similaires existent pour ajuster les courbes statistiques, trouver des formes, etc. Cependant, ils sont coûteux en temps, parfois sévèrement. Mais le coût en temps en vaut la peine, car les statistiques robustes sont effectivement insensibles au «bruit» dans les signaux, ce qui nest pas le cas des approches de lerreur des moindres carrés. Le monde réel regorge à la fois de bruits et de valeurs aberrantes, dont certaines sont causées par une erreur humaine ou machine, en particulier dans les images pixélisées ou le son échantillonné. Dans de telles circonstances, un algorithme robuste plus coûteux en temps peut trouver des signaux dans un environnement bruyant où des algorithmes plus rapides produisent des réponses tellement corrompues par le bruit quelles sont inutiles, voire dangereuses si elles sont acceptées.
Dans certains cas, le temps et la complexité spatiale ne sont pas aussi importantes que de trouver la réponse la plus susceptible de modéliser le signal réel malgré le bruit et la dégradation du signal.
Réponse
Les algorithmes issus des mathématiques sont des «recettes» pour effectuer des calculs basés sur des fonctions, qui peuvent être suivis mécaniquement. Dans la vision du monde mathématique basée sur les fonctions, toutes les entrées doivent être spécifiées au début du calcul, qui se déroule en boîte fermée. La notion d’algorithme est intrinsèquement informelle, car une description algorithmique ne se limite pas à un seul langage ou formalisme.
L’exemple le plus ancien est peut-être l’algorithme d’Euclide pour trouver des diviseurs communs. Les algorithmes capturent ce que signifie pour un calcul dêtre « efficace ». Comme les formules mathématiques, les algorithmes nous disent comment calculer une valeur; contrairement à eux, les algorithmes peuvent impliquer ce que nous appelons maintenant des boucles ou des branches.
Rôle de lalgorithme: étant donné une valeur dentrée finie x, un algorithme décrit les étapes pour la transformer efficacement en une valeur de sortie y, où y est f (x) pour une fonction récursive f.
Les algorithmes ont été adoptés par les premiers informaticiens dans les années 1950, qui ont fait le lien entre les algorithmes et les machines de Turing (TM, un modèle formel de calcul datant de 1936), assimilant leur expressivité.
Le célèbre et influent manuel de Knuth, « The Art of Computer Programming, Vol. 1 », à la fin des années 1960, a popularisé la centralité des algorithmes en informatique. Dans sa définition des algorithmes, Knuth était cohérent avec les fondements basés sur les fonctions mathématiques de la théorie du calcul. «Il existe de nombreuses autres façons essentiellement équivalentes de formuler le concept dune méthode de calcul efficace (par exemple, en utilisant des MT).»
Knuth a explicitement spécifié que les algorithmes sont fermés; aucune nouvelle entrée nest acceptée une fois le calcul commencé: «Un algorithme a zéro ou plusieurs entrées, cest-à-dire des quantités qui lui sont données initialement avant le début de lalgorithme. Il a distingué les algorithmes du calcul arbitraire pouvant impliquer des E / S. Un exemple quil a donné dun problème qui nest pas algorithmique est linstruction suivante tirée dune recette: « mélanger légèrement jusquà ce que le mélange soit friable. » Ce problème nest pas algorithmique car il est impossible pour un ordinateur de savoir combien de temps mélanger; cela peut dépendre de conditions externes qui changent dynamiquement, telles que lhumidité, qui ne peuvent être prédites avec certitude à lavance.
Bien quil ny ait pas daccord sur la notion exacte dalgorithmes, la discussion de Knuth sur les algorithmes reste définitive.
Le premier langage de programmation de haut niveau développé expressément pour spécifier des algorithmes était ALGOL (ALGOrithmic Language). Introduit à la fin des années 50 et affiné dans les années 60, il a servi de norme pour la publication d’algorithmes. Fidèle à la conceptualisation basée sur la fonction des algorithmes, ALGOL na fourni aucune construction pour lentrée et la sortie, considérant ces opérations en dehors du domaine des algorithmes. (Sans surprise, cette absence a entravé l’adoption d’ALGOL par l’industrie à des fins commerciales.)
Les années 60 ont vu une prolifération de programmes d’informatique (CS) de premier cycle. Selon lAssociation for Computing Machinery (ACM), le nombre de programmes CS aux États-Unis est passé de 11 en 1964 à 92 en 1968. Cette augmentation sest accompagnée dune intense activité visant à asseoir la légitimité de cette nouvelle discipline aux yeux des universitaires. communauté. ACM a joué un rôle central dans cette activité. En 1965, il a énoncé la justification et la description de la CS en tant que discipline, qui a servi de base à ses recommandations de 1968 pour les programmes de premier cycle de CS
La description de lACM de la CS identifiait la transformation efficace de linformation comme une préoccupation centrale: » Linformatique sintéresse à linformation au même sens que la physique se préoccupe de lénergie … Linformaticien sintéresse à la découverte des moyens pragmatiques par lesquels linformation peut être transformée. Cette description place les algorithmes au centre de linformatique, car ce sont les «recettes» pour effectuer ces transformations efficaces dentrées en sorties. En fait, ACM a mis laccent sur les algorithmes explicitement dans la phrase suivante de son rapport:
«Cet intérêt conduit à rechercher des moyens efficaces de représenter linformation, des algorithmes efficaces pour transformer linformation, des langages efficaces avec lesquels exprimer des algorithmes … et des moyens efficaces pour y parvenir à un coût raisonnable. »
Le fait davoir une préoccupation algorithmique centrale, analogue à celle de lénergie en physique, a contribué à faire de la CS une discipline universitaire légitime à égalité avec la physique. Les algorithmes sont restés au cœur de linformatique à ce jour.
La coexistence des approches informelle (basée sur un algorithme) et formelle (basée sur la MT) pour définir les problèmes résolubles persiste à ce jour et peut être trouvée dans tous les manuels modernes sur les algorithmes ou la calculabilité. Cela sest avéré très pratique pour les informaticiens, en nous permettant de décrire le calcul algorithmique de manière informelle en utilisant le «pseudocode», sachant quune machine de Turing équivalente peut être construite.
– Un problème est résoluble sil peut lêtre. spécifié par un algorithme. – Un problème peut être résolu s’il existe une machine de Turing pour lui.
La décision des années 60 des théoriciens et des éducateurs de placer les algorithmes au centre de la CS était clairement reflétée dans les premiers manuels de premier cycle. Cependant, il ny avait pas de définition standard explicite dun algorithme et divers manuels ont choisi de définir ce terme différemment. Alors que certains manuels comme celui de Knuth ont pris soin de restreindre explicitement les algorithmes à ceux qui calculent des fonctions et sont donc équivalents aux machines de Turing, la plupart des livres de théorie ont laissé cette restriction implicite mais non énoncée.
Un des premiers exemples est un manuel de Hopcroft et Ullman de 1969, dont les éditions ultérieures sont utilisées à ce jour: «Une procédure est une séquence finie dinstructions qui peuvent être exécutées mécaniquement, comme un programme dordinateur …Une procédure qui se termine toujours est appelée un algorithme. »
Cette description dun algorithme nexclut pas explicitement les calculs non fonctionnels tels que la préparation daliments. Cependant, leurs exemples de divers problèmes montrent clairement quils nont considéré que le calcul basé sur les fonctions. En fait, ils ont utilisé ALGOL pour leurs exemples, qui noffrait même pas de constructions dentrée et de sortie.
Depuis la fin des années 60, les langages de programmation de haut niveau utilisés dans la pratique et enseignés dans les programmes CS nétaient plus lié par les contraintes algorithmiques du début dALGOL. Vous pouvez écrire des programmes qui interagissent avec leur environnement de manière continue tout au long du calcul, tels que des systèmes dexploitation, des interfaces utilisateur graphiques ou des véhicules automatiques et dautres robots.
En réponse, des manuels de programmation contemporains tels que Rice et Rice (1969) a explicitement élargi la notion dalgorithmes pour inclure les problèmes non fonctionnels. Cette approche, reflétant la centralité des algorithmes sans les restreindre au calcul de fonctions, est devenue typique des manuels non théoriques. Le sujet de ces manuels est la méthodologie de programmation plutôt que la théorie du calcul, et les principes mathématiques qui sous-tendent nos modèles de calcul ont été mis de côté pour des raisons pratiques.
À première vue, la définition dun algorithme dans Rice and Rice et dautres manuels similaires nest pas différent de Hopcroft et Ullman: «Un algorithme est une recette, un ensemble dinstructions ou les spécifications dun processus pour faire quelque chose. Ce quelque chose résout généralement un problème quelconque. » Cependant, leurs exemples de problèmes calculables ne sont plus basés sur des fonctions, admettant juste le type de calcul que Knuth avait rejeté. Deux exemples de ce type, qui peuvent être résolus par un algorithme, sont la fabrication de vodka de pomme de terre et le remplissage dun fossé avec du sable; Knuth les aurait rejetés tous les deux.
Ces manuels ne faisaient aucune déclaration déquivalence TM pour leurs «algorithmes». Cependant, les étudiants n’ont pas été informés que cette notion d’algorithme était différente de celle de Knuth et que l’ensemble des problèmes considérés comme calculables s’était ainsi élargi. En associant une conceptualisation plus large et plus pratique des algorithmes (et donc des problèmes calculables) avec des théories affirmant que des problèmes très calculables peuvent être calculés par des MT, le programme CS axé sur les algorithmes a laissé aux étudiants limpression erronée que cet ensemble plus large de problèmes pourrait être résolus par les MT.
Alors que les informaticiens pratiques ont depuis longtemps suivi lexemple de Rice et Rice et élargi le concept dalgorithmes au-delà du calcul des fonctions, linformatique théorique a conservé la vision mathématique du monde qui encadre calcul basé sur une fonction, et délimite notre notion de problème de calcul en conséquence. Cela est vrai au moins au niveau du premier cycle. Le résultat est une dichotomie, où la communauté informatique considère les algorithmes comme synonymes de la notion générale de calcul («ce que font les ordinateurs») mais en même temps comme équivalents aux machines de Turing.
Jai pensé Jai dû écrire cette longue réponse, pour sensibiliser les gens à cette dichotomie. Comme je lai dit au début, la notion dalgorithme est informelle. Nous pouvons le considérer comme équivalent au calcul de fonctions (ou aux machines de Turing) ou nous pouvons le considérer comme tout ce pour quoi vous pouvez écrire un programme, y compris des programmes interactifs en temps réel comme des systèmes dexploitation ou des voitures automatiques. Mais les deux définitions ne sont pas équivalentes, malgré la confusion commune du contraire.