Algorithme

Souvent, un mécanisme (ordinateur, tour, machine à coudre), mais la notion d'algorithme ne fait pas nécessairement référence à des programmes informatiques, par exemple, une recette clairement décrite pour préparer un plat est aussi un algorithme, auquel cas l'interprète est une personne.

Le concept d’algorithme fait référence aux concepts initiaux et fondamentaux des mathématiques. Les processus informatiques de nature algorithmique (opérations arithmétiques sur des nombres entiers, recherche du plus grand commun diviseur de deux nombres, etc.) sont connus de l'humanité depuis l'Antiquité. Cependant, le concept explicite d’algorithme n’a été formé qu’au début du 20e siècle.

La formalisation partielle du concept d'algorithme a commencé avec des tentatives pour résoudre le problème de résolution (allemand. Problème d'entscheidungs), formulée par David Hilbert en 1928. Les étapes de formalisation suivantes étaient nécessaires pour définir un calcul efficace ou « méthode efficace » ; ces formalisations incluent les fonctions récursives de Gödel-Herbrand-Kleene, le λ-calcul d'Alonzo Church, la Formule 1 d'Emil Post de 1936 et la machine de Turing. Dans la méthodologie, l'algorithme est un concept de base et reçoit un concept qualitativement nouveau d'optimalité à mesure qu'il se rapproche de l'absolu prédit. DANS monde moderne l'algorithme en expression formalisée constitue la base de l'éducation par l'exemple, par la similarité. Sur la base de la similitude des algorithmes dans divers domaines d'activité, le concept (théorie) de systèmes experts s'est formé.

Histoire du terme

La définition formelle moderne d'un algorithme a été donnée dans les années 30-50 du 20e siècle dans les travaux de Turing, Post, Church (thèse Church-Turing), N. Wiener, A. A. Markov.

Le mot « algorithme » lui-même vient du nom du scientifique du Khorezm Abu Abdullah Muhammad ibn Musa al-Khorezmi (algorithme - al-Khorezmi). Vers 825, il rédige un essai dans lequel il décrit pour la première fois la technique positionnelle inventée en Inde. système décimal Compte. Malheureusement, l’original persan du livre n’a pas survécu. Al-Khwarizmi a formulé les règles de calcul dans le nouveau système et fut probablement le premier à utiliser le chiffre 0 pour indiquer une position manquante dans la notation d'un nombre (son nom indien était traduit par les Arabes par as-sifr ou simplement sifr, d’où des mots tels que « chiffre » et « chiffre »). À peu près à la même époque, d’autres érudits arabes ont commencé à utiliser des chiffres indiens. Dans la première moitié du XIIe siècle, le livre d’al-Khwarizmi dans une traduction latine pénétra en Europe. Le traducteur, dont le nom ne nous est pas parvenu, lui a donné le nom Algorithme de numéro Indorum(« Algorithmes sur le comptage indien »). En arabe, le livre s'appelait Kitab al-jabr wal-muqabala(« Un livre sur l'addition et la soustraction »). Le mot Algèbre (algèbre - al-jabr - achèvement) vient du titre original du livre.

Ainsi, nous voyons que le nom latinisé du scientifique d'Asie centrale a été inclus dans le titre du livre, et on pense aujourd'hui que le mot « algorithme » est entré dans les langues européennes précisément grâce à ce travail. Cependant, la question de sa signification suscite depuis longtemps de vifs débats. Au cours des siècles, diverses explications ont été données sur l’origine du mot.

Certains ont apporté algorisme du grec algiros(malade) et arithmétique(nombre). Cette explication ne permet pas de comprendre très bien pourquoi les chiffres sont « malades ». Ou les linguistes considéraient-ils comme malades les gens qui avaient le malheur de faire des calculs ? Le dictionnaire encyclopédique de Brockhaus et Efron propose également son explication. En lui algorithme(d'ailleurs, avant la révolution, l'orthographe était utilisée algorithme, via fita) est dérivé « du mot arabe Al-Goretm, c'est-à-dire la racine ». Bien entendu, ces explications peuvent difficilement être considérées comme convaincantes.

La traduction mentionnée ci-dessus de l’œuvre d’Al-Khwarizmi fut le premier signe, et au cours des siècles suivants, de nombreux autres ouvrages parurent consacrés au même sujet : l’enseignement de l’art de compter à l’aide des nombres. Et ils avaient tous le mot dans le titre algorithme ou algorithmes.

Les auteurs ultérieurs ne savaient rien d'al-Khorezmi, mais comme la première traduction du livre commence par les mots : « Dixit algorizmi : … » (« Al-Khorezmi a dit : … »), ils associaient toujours ce mot au nom d'un particulier. personne. Une version très courante était l'origine grecque du livre. Dans un manuscrit anglo-normand du XIIIe siècle, écrit en vers, on lit :

L’algorithme est l’art de compter à l’aide de nombres, mais au début, le mot « chiffre » faisait référence uniquement à zéro. Le célèbre trouveur français Gautier de Coincy (1177-1236) a utilisé les mots chiffrement algorismus(ce qui signifiait le chiffre 0) comme métaphore pour caractériser une personne absolument sans valeur. Évidemment, la compréhension d’une telle image nécessitait une préparation appropriée des auditeurs, ce qui signifie que nouveau système le calcul leur était déjà bien connu.

Pendant de nombreux siècles, le boulier était pratiquement le seul moyen de calcul pratique ; il était utilisé par les marchands, les changeurs de monnaie et les scientifiques. Les mérites des calculs sur une planche à compter ont été expliqués dans ses écrits par un penseur aussi remarquable qu'Herbert d'Avrilak (938-1003), devenu pape en 999 sous le nom de Sylvestre II. La nouvelle a trouvé son chemin avec beaucoup de difficulté, et l'histoire des mathématiques comprenait une confrontation obstinée entre les camps des algorismes et des abacistes (parfois appelés herbeckistes), qui préconisaient l'utilisation d'un boulier au lieu de chiffres arabes pour les calculs. Il est intéressant de noter que le célèbre mathématicien français Nicolas Chuquet (1445-1488) a été inscrit au registre des contribuables de la ville de Lyon en tant qu'algoriste. Mais plus d'un siècle s'est écoulé avant nouvelle façon La comptabilité étant enfin instaurée, il a fallu tellement de temps pour élaborer des notations généralement admises, améliorer et adapter les méthodes de calcul à l'enregistrement sur papier. En Europe occidentale, les professeurs d'arithmétique ont continué à être appelés « maîtres du boulier » jusqu'au XVIIe siècle, comme le mathématicien Niccolò Tartaglia (1500-1557).

Ainsi, les ouvrages sur l'art de compter s'appelaient Algorithmes. Parmi les centaines, on peut en distinguer des plus inhabituels comme un traité écrit en vers Carmen de Algorisme(Latin Carmen et signifie poésie) d'Alexandre de Villa Dei (mort en 1240) ou le manuel de l'astronome et mathématicien viennois Georg Peurbach (1423-1461) Opus algorithmi jocundissimi(« L’essai le plus drôle sur un algorithme »).

Peu à peu, le sens du mot s'est élargi. Les scientifiques ont commencé à l’appliquer non seulement à des procédures purement informatiques, mais également à d’autres procédures mathématiques. Par exemple, vers 1360, le philosophe français Nicolas Oresme (1323/25-1382) écrivit un traité mathématique Algorisme proportionné(« Calcul des proportions »), dans lequel il a utilisé pour la première fois des puissances avec des exposants fractionnaires et s'est en fait rapproché de l'idée des logarithmes. Lorsque le boulier a été remplacé par ce qu'on appelle le comptage de lignes, de nombreux manuels à ce sujet ont commencé à être appelés Algorithme linéaire, c'est-à-dire les règles de comptage des lignes.

On peut noter que la forme originale algorithmes après un certain temps, la dernière lettre a été perdue et le mot a acquis une forme plus pratique pour la prononciation européenne algorisme. Plus tard, il a été à son tour sujet à une distorsion, très probablement associée au mot arithmétique.

Machine de Turing

L’idée de base d’une machine de Turing est très simple. Une machine de Turing est une machine abstraite (automate) qui fonctionne sur une bande cellules individuelles, dans lequel les caractères sont écrits. La machine dispose également d'une tête pour écrire et lire les caractères des cellules, qui peuvent se déplacer le long de la bande. À chaque étape, la machine lit un caractère dans la cellule pointée par la tête et, en fonction du caractère lu et de l'état interne, passe à l'étape suivante. En même temps, la machine peut changer d'état, écrire un autre caractère dans une cellule ou déplacer la tête d'une cellule vers la droite ou la gauche.

Sur la base de l'étude de ces machines, la thèse de Turing (l'hypothèse principale des algorithmes) a été avancée :

Cette thèse est un axiome, un postulat, et ne peut être prouvée méthodes mathématiques, puisqu'un algorithme n'est pas un concept mathématique exact.

Fonctions récursives

Chaque algorithme peut être associé à la fonction qu'il calcule. Cependant, la question se pose : est-il possible d'associer une fonction arbitraire à une machine de Turing, et sinon, pour quelles fonctions existe-t-il un algorithme ? Les recherches sur ces questions ont conduit à la création de la théorie des fonctions récursives dans les années 1930.

La classe des fonctions calculables a été écrite dans une image rappelant la construction d'une théorie axiomatique basée sur un système d'axiomes. Tout d'abord, les fonctions les plus simples ont été choisies, dont le calcul était évident. Ensuite, les règles (opérateurs) permettant de construire de nouvelles fonctions basées sur celles existantes ont été formulées. La classe de fonctions requise comprend toutes les fonctions pouvant être obtenues à partir des fonctions les plus simples à l'aide d'opérateurs.

Semblable à la thèse de Turing, une hypothèse a été avancée dans la théorie des fonctions informatiques appelée La thèse de Church:

Prouver que la classe des fonctions calculables coïncide avec les fonctions calculables de Turing se déroule en deux étapes : d'abord, ils prouvent le calcul des fonctions les plus simples sur une machine de Turing, puis le calcul des fonctions obtenues grâce à l'application d'opérateurs.

Ainsi, de manière informelle, un algorithme peut être défini comme un système précis d'instructions définissant un processus discret et déterministe qui mène d'une donnée initiale (entrée) à un résultat souhaité (sortie), s'il existe, en un nombre fini d'étapes ; si le résultat souhaité n’existe pas, l’algorithme ne se termine jamais ou atteint une impasse.

Algorithme de Markov normal

L'algorithme normal de Markov est un système demandes successives substitutions qui mettent en œuvre certaines procédures pour obtenir de nouveaux mots à partir de mots de base, construits à partir de caractères d'un certain alphabet. Comme la machine de Turing, algorithmes normaux n'effectuent pas eux-mêmes les calculs : ils effectuent uniquement la transformation des mots en remplaçant les lettres selon des règles données.

Normalement calculable est une fonction qui peut être implémentée par un algorithme normal. C'est-à-dire un algorithme qui transforme chaque mot de l'ensemble des données valides d'une fonction en ses valeurs d'origine.

Le créateur de la théorie des algorithmes normaux, A. A. Markov, a avancé une hypothèse appelée principe de normalisation de Markov :

Comme la thèse de Turing et Church, le principe de normalisation de Markov ne peut être prouvé mathématiquement.

Algorithmes stochastiques

Cependant, la définition formelle ci-dessus d’un algorithme peut être trop stricte dans certains cas. Il est parfois nécessaire d’utiliser des variables aléatoires. Un algorithme dont le fonctionnement est déterminé non seulement par les données initiales, mais également par les valeurs obtenues à partir d'un générateur de nombres aléatoires est appelé stochastique(ou randomisé, de l'anglais. algorithme randomisé) . Formellement, de tels algorithmes ne peuvent pas être appelés algorithmes, car il existe une probabilité (proche de zéro) qu'ils ne s'arrêtent pas. Cependant, les algorithmes stochastiques sont souvent plus efficaces que les algorithmes déterministes et, dans certains cas, ils constituent le seul moyen de résoudre un problème.

En pratique, au lieu d'un générateur nombres aléatoires utilisez un générateur de nombres pseudo-aléatoires.

Cependant, il convient de distinguer les algorithmes stochastiques des méthodes qui donnent le résultat correct avec une forte probabilité. Contrairement à la méthode, l'algorithme donne des résultats corrects même après un travail prolongé.

Certains chercheurs admettent la possibilité qu'un algorithme stochastique donne un résultat incorrect avec une probabilité connue. Les algorithmes stochastiques peuvent alors être divisés en deux types :

• algorithmes comme Las Vegas donnent toujours le résultat correct, mais leur durée de fonctionnement n'est pas définie.
• algorithmes Type Monte-Carlo, contrairement aux précédents, peut donner des résultats incorrects avec une probabilité connue (on les appelle souvent Méthodes de Monte Carlo).

Autres formalisations

Pour certains problèmes, les formalisations ci-dessus peuvent rendre difficile la recherche de solutions et la réalisation de recherches. Pour surmonter les obstacles, des modifications des schémas « classiques » et de nouveaux modèles d'algorithmes ont été créés. On peut notamment citer :

• machines de Turing multi-bandes et non déterministes ;
• registre et machine RAM - prototype ordinateurs modernes et machines virtuelles ;

et d'autres.

Propriétés formelles des algorithmes

Diverses définitions d'un algorithme, explicitement ou implicitement, contiennent la série d'exigences générales suivante :

Types d'algorithmes

Un rôle particulier est joué par les algorithmes appliqués conçus pour résoudre certains problèmes appliqués. Un algorithme est considéré comme correct s’il répond aux exigences du problème (par exemple s’il donne un résultat physiquement plausible). Un algorithme (programme) contient des erreurs si, pour certaines données initiales, il donne des résultats incorrects, des échecs, des échecs ou ne produit aucun résultat. La dernière thèse est utilisée dans les Olympiades de programmation algorithmique pour évaluer les programmes compilés par les participants.

Le cas où le résultat de l’évaluation d’une fonction est une expression logique « vrai » ou « faux » (ou l’ensemble (0, 1)) est appelé un problème, qui peut être résoluble ou insoluble selon la calculabilité de la fonction.

Il est important de spécifier précisément l’ensemble valide de données d’entrée, car un problème peut être résolu pour un ensemble et insoluble pour un autre.

L’un des premiers problèmes à s’avérer insoluble est celui de l’arrêt. Il est formulé ainsi :

Prouver l’insolvabilité du problème d’arrêt est important car d’autres problèmes peuvent y être réduits. Par exemple, problème simple l'arrêt peut être réduit au problème de l'arrêt sur la ligne vide (quand il faut déterminer pour une machine de Turing donnée si elle s'arrêtera si elle est exécutée sur la ligne vide), prouvant ainsi l'indécidabilité de cette dernière. .

Analyse d'algorithme

Parallèlement à la diffusion des technologies de l'information, le risque de pannes logicielles a augmenté. L’un des moyens d’éviter les erreurs dans les algorithmes et dans leur mise en œuvre est de prouver l’exactitude des systèmes à l’aide de moyens mathématiques.

L'utilisation d'appareils mathématiques pour analyser des algorithmes et leurs implémentations est appelée méthodes formelles. Les méthodes formelles impliquent l'utilisation de spécifications formelles et, généralement, d'un ensemble d'outils pour analyse et la preuve des propriétés des spécifications. L'abstraction des détails de mise en œuvre permet d'établir les propriétés d'un système indépendamment de sa mise en œuvre. De plus, la précision et l’absence d’ambiguïté des énoncés mathématiques évitent la polysémie et l’imprécision des langues naturelles.

Selon l'hypothèse de Richard Mace, « éviter les erreurs mieux que l'élimination erreurs." Selon l'hypothèse de Hoare, « la preuve des programmes résout le problème de l'exactitude, de la documentation et de la compatibilité ». Prouver l'exactitude des programmes nous permet d'identifier leurs propriétés par rapport à l'ensemble des données d'entrée. À cette fin, le concept d'exactitude a été divisé en deux types :

• Exactitude partielle- le programme donne le résultat correct dans les cas où il se termine.
• Exactitude totale- le programme se termine et produit le résultat correct pour tous les éléments de la plage d'entrée.

Lors de la vérification de l'exactitude, le texte du programme est comparé à la spécification de la relation entrée-sortie souhaitée. Pour les preuves de type Hoare, cette spécification prend la forme d’énoncés appelés préconditions et postconditions. Avec le programme lui-même, ils sont également appelés le triple de Hoare. Ces déclarations sont enregistrées

P.{Q} R.

Où P.- c'est une condition préalable qui doit être remplie avant le démarrage du programme Q, UN R.- une postcondition qui est valide une fois le programme terminé.

Les méthodes formelles ont été appliquées avec succès à un large éventail de problèmes, notamment : le développement circuits électroniques, intelligence artificielle, systèmes automatiques sur chemin de fer, vérification des microprocesseurs , spécification des normes et spécification et vérification des programmes .

Heures d'ouverture

Un critère courant pour évaluer les algorithmes est le temps de fonctionnement et l'ordre dans lequel le temps de fonctionnement augmente en fonction de la quantité de données d'entrée.

Pour chaque tâche spécifique constituent un certain nombre, appelé sa taille. Par exemple, la taille du problème du calcul du produit de matrices pourrait être plus grande taille matrices multiplicatrices, pour les problèmes sur les graphiques, la taille peut être le nombre d'arêtes du graphique.

Le temps passé par un algorithme en fonction de la taille du problème est appelé la complexité temporelle de cet algorithme. T(n). Le comportement asymptotique de cette fonction à mesure que la taille du problème augmente est appelé complexité temporelle asymptotique, et une notation spéciale est utilisée pour le désigner.

C’est la complexité asymptotique qui détermine la taille des problèmes que l’algorithme peut traiter. Par exemple, si un algorithme traite des données d'entrée de taille dans le temps CN², où c est une constante, alors ils disent que la complexité temporelle d'un tel algorithme Ô(n²).

Souvent, lors du développement d’un algorithme, des tentatives sont faites pour réduire la complexité temporelle asymptotique pour les pires cas. Dans la pratique, il existe des cas où un algorithme qui fonctionne « habituellement » rapidement suffit.

En gros, l'analyse de complexité temporelle asymptotique moyenne peut être divisée en deux types : analytique et statistique. Méthode analytique donne des résultats plus précis, mais est difficile à utiliser en pratique. Mais la méthode statistique permet une analyse plus rapide tâches complexes.

Le tableau suivant répertorie les difficultés asymptotiques courantes avec les commentaires.

Complexité	Un commentaire	Exemples
Ô(1)	Durée d'exécution cohérente indépendamment de la taille de la tâche	Temps de recherche attendu dans une table de hachage
Ô(journal journal n)	Temps de croissance très lent requis	Durée d'exécution prévue de la recherche par interpolation néléments
Ô(enregistrer n)	Croissance logarithmique : doubler la taille d'un problème augmente le temps d'exécution d'une quantité constante	Calcul X n; Recherche binaire dans un tableau de néléments
Ô(n)	Croissance linéaire : doubler la taille de la tâche doublera le temps requis	Ajouter/soustraire des nombres à n Nombres; Recherche linéaire dans un tableau de néléments
Ô(n enregistrer n)	Croissance rythmique linéaire : doubler la taille du problème fera légèrement plus que doubler le temps requis	Fusionner ou trier par tas néléments; limite inférieure du tri correspondant néléments
Ô(n²)	Croissance quadratique : doubler la taille d'un problème quadruple le temps requis	Algorithmes de tri élémentaires
Ô(n³)	Croissance cubique - doubler la taille d'un problème augmente le temps requis par huit	Multiplication matricielle normale
Ô(c n)	Croissance exponentielle - augmenter la taille du problème de 1 entraîne c- une augmentation multiple du temps requis ; doubler la taille d'un problème quadruple le temps requis	Quelques problèmes de voyageur de commerce, algorithmes de recherche par force brute

Disponibilité des données initiales et quelques résultats

L'algorithme est précis instruction spécifique, en l'appliquant séquentiellement aux données initiales, on peut obtenir une solution au problème. Pour chaque algorithme, il existe un certain ensemble d'objets acceptables comme données d'entrée. Par exemple, dans l'algorithme de division des nombres réels, le dividende peut être n'importe quoi, mais le diviseur ne peut pas être nul.

L'algorithme sert, en règle générale, à résoudre non pas un problème spécifique, mais une certaine classe de problèmes. Ainsi, l’algorithme d’addition est applicable à n’importe quelle paire de nombres naturels. Cela exprime son caractère de masse, c'est-à-dire la capacité d'utiliser de manière répétée le même algorithme pour n'importe quel problème de la même classe.

Utilisé pour développer des algorithmes et des programmes algorithmisation- le processus de compilation systématique d'algorithmes pour résoudre les problèmes appliqués assignés. L'algorithmisation est considérée comme une étape obligatoire dans le processus de développement de programmes et de résolution de problèmes sur un ordinateur. C'est pour les algorithmes et les programmes appliqués que le déterminisme, l'efficacité et la production de masse, ainsi que l'exactitude des résultats de la résolution des problèmes assignés, sont fondamentalement importants.

Un algorithme est une instruction claire et précise pour exécuter une séquence d’actions visant à atteindre un objectif.

Présentation des algorithmes

Formulaires d'enregistrement d'algorithmes :

• verbal ou verbal (linguistique, formule-verbale);
• pseudocode (langages algorithmiques formels) ;
• schématique:
  • diagrammes de structure (diagrammes de Nussi-Schneiderman) ;
  • graphique (schémas fonctionnels).

Habituellement, au début (au niveau de l'idée), l'algorithme est décrit avec des mots, mais à mesure qu'il approche de la mise en œuvre, il acquiert de plus en plus de contours formels et de formulation dans un langage compréhensible pour l'interprète (par exemple, le code machine).

Efficacité des algorithmes

Bien que la définition d’un algorithme ne nécessite qu’un nombre fini d’étapes pour obtenir un résultat, en pratique, même un milliard d’étapes est trop lent. Il existe également généralement d'autres restrictions (sur la taille du programme, sur les actions autorisées). À cet égard, des concepts tels que la complexité des algorithmes (temps, taille du programme, calcul, etc.) sont introduits.

Pour chaque tâche, il peut y avoir de nombreux algorithmes menant à l’objectif. Augmenter l’efficacité des algorithmes est l’une des tâches de l’informatique moderne. Dans les années 50 Au 20e siècle, même un domaine distinct est apparu : les algorithmes rapides. En particulier, dans le problème de la multiplication des nombres décimaux, connu de tous depuis l'enfance, un certain nombre d'algorithmes ont été découverts qui permettent d'accélérer considérablement (au sens asymptotique) la recherche du produit. Voir multiplication rapide

L'algorithme euclidien est une méthode efficace pour calculer le plus grand commun diviseur (PGCD). Nommé d'après le mathématicien grec Euclide ; l'un des algorithmes les plus anciens encore utilisés aujourd'hui.

Décrit dans les Éléments d'Euclide (environ 300 avant JC), notamment dans les livres VII et X. Le septième livre décrit un algorithme pour les nombres entiers et le dixième pour les longueurs des segments.

Il existe plusieurs variantes de l'algorithme ; ci-dessous une version récursive écrite en pseudocode :

fonction nœud (a, b) Si b = 0 retour un sinon retour nœud (b, un module b)

PGCD des nombres 1599 et 650 :

Étape 1	1599 = 650*2 + 299
Étape 2	650 = 299*2 + 52
Étape 3	299 = 52*5 + 39
Étape 4	52 = 39*1 + 13
Étape 5	39 = 13*3 + 0

voir également

Remarques

1. Kleene 1943 dans Davis 1965 : 274
2. Rosser 1939 dans Davis 1965 : 225
3. (Igoshin, p. 317)
4. Les bases : La Machine de Turing (avec un interprète ! . Bonnes mathématiques, mauvaises mathématiques(9 février 2007). Archivé de l'original le 2 février 2012.
5. (Igoshin, article 33)
6. Encyclopédie de la cybernétique, vol. 2 , ch. 90-91.
7. (Igoshin, article 34)
8. « Il ne faut pas confondre les algorithmes probabilistes avec les méthodes (que je refuse d’appeler algorithmes) qui produisent un résultat qui a une forte probabilité d’être correct. Il est essentiel qu’un algorithme produise des résultats corrects (en excluant les erreurs humaines ou informatiques), même si cela se produit après très longtemps. Henri Cohen Un cours de théorie algébrique computationnelle des nombres. - Springer-Verlag, 1996. - P. 2. - ISBN 3-540-55640-0
9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. -ISBN0-262-03293-7

Résoudre un problème à l'aide d'un ordinateur commence par l'élaboration d'un algorithme. Qu'est-ce qu'un algorithme ?

L'origine du terme « algorithme » est associée au nom du grand mathématicien Muhammad al-Khwarizmi (763-850), qui a développé les règles permettant d'effectuer quatre opérations arithmétiques.

Selon GOST 19781-74 :

Un algorithme est une prescription précise qui définit un processus informatique menant de données initiales variables au résultat souhaité.

C'est algorithme – il s’agit d’une instruction claire adressée à l’exécuteur de l’algorithme pour effectuer une certaine séquence d’actions pour résoudre la tâche et obtenir le résultat.

Développer un algorithme signifie décomposer un problème en une séquence spécifique d’étapes. Le développeur d’algorithmes doit connaître les caractéristiques et les règles de composition des algorithmes.

Principales caractéristiques des algorithmes :

Disponibilité saisir données source.

Disponibilité sortir le résultat de l'exécution de l'algorithme, puisque le but de l'exécution de l'algorithme est d'obtenir un résultat qui a une relation très spécifique avec les données d'origine.

L'algorithme doit avoir structure discrète , c'est à dire. l'algorithme est présenté comme une séquence d'étapes et l'exécution de chaque étape suivante commence après l'achèvement de la précédente.

Sans ambiguïté – chaque étape de l'algorithme doit être clairement définie et ne doit pas permettre une interprétation arbitraire de la part de l'interprète.

Membre – l'exécution de l'algorithme doit être réalisée en un nombre fini d'étapes.

Exactitude – l'algorithme doit spécifier la bonne solution au problème.

Caractère de masse (généralité) – un algorithme est développé pour résoudre une certaine classe de problèmes qui diffèrent par les données initiales.

Efficacité - l'algorithme doit s'exécuter dans un temps fini raisonnable. Dans ce cas, le moyen le plus simple et le plus court de résoudre le problème est sélectionné, sous réserve, bien entendu, de toutes les restrictions et exigences de l'algorithme.

Façons d'écrire des algorithmes

L’algorithme développé peut être présenté de plusieurs manières :

en langage naturel (enregistrement verbal de l’algorithme) ;

sous forme de schémas fonctionnels (forme graphique) ;

dans un langage de programmation.

Enregistrement verbal de l'algorithme. La forme verbale est généralement utilisée pour décrire des algorithmes conçus interprète - personne. Les commandes sont écrites en langage clair et exécutées dans l'ordre. Les commandes peuvent utiliser des formules et des notations spéciales, mais chaque commande doit être compréhensible pour l'interprète. L'ordre naturel des commandes peut être perturbé (si, par exemple, une transition vers la commande précédente est requise ou s'il est nécessaire de contourner la commande suivante sous certaines conditions), dans ce cas les commandes peuvent être numérotées et la commande à laquelle vous vouloir y aller est indiqué. Par exemple, passer à l'étape 3 ou répéter à partir de l'étape 4.

Forme graphique. Les algorithmes sont présentés sous forme de schémas fonctionnels. Il existe des normes spéciales pour la construction de diagrammes fonctionnels, dans lesquels des images graphiques de blocs sont définies. Les commandes d'algorithme sont écrites dans des blocs dans un langage ordinaire ou à l'aide de formules mathématiques. Les blocs sont connectés selon certaines règles par des lignes de communication qui indiquent l'ordre dans lequel les commandes sont exécutées.

Dans un langage de programmation. Si un algorithme est développé pour résoudre un problème sur un ordinateur, alors pour qu'il soit exécuté interprète - ordinateur, il doit être enregistré dans une langue compréhensible par cet artiste. A cet effet, de nombreux langages de programmation ont été développés pour résoudre des problèmes de différentes classes. L'écriture d'un algorithme dans un langage de programmation s'appelle programme.

Aujourd'hui, nous répondrons à la question de savoir ce qu'est un algorithme.

Un algorithme est souvent appelé un ensemble d'instructions qui décrivent actions nécessaires(ainsi que l'ordre de leur mise en œuvre) afin de résoudre la tâche. De nos jours, les algorithmes sont utilisés non seulement en ingénierie et en sciences, mais également dans d’autres domaines de la vie.

Ce qu'on appelle un algorithme

Le concept d'algorithme est assez ancien et appartient à l'un des principaux, ainsi qu'à concepts de base en mathématiques. Le terme vient de l'orthographe latine du nom du célèbre mathématicien oriental de 787-850 Muhammad al-Khwarizmi - Algorithmi. Ce scientifique fut le premier à formuler des règles précises pour écrire des nombres naturels, ainsi que des règles pour additionner les comptes dans une colonne. Assez fait intéressant C’est aussi le fait que, malgré ses racines anciennes, le concept lui-même n’a été formulé avec précision qu’au début du XXe siècle. De nos jours, l'algorithme est la composante principale de l'entreprise moderne, quelle qu'elle soit. processus éducatif ou de la recherche. C'est pourquoi tout le monde à l'homme moderne il vous suffit de savoir exactement ce que signifie l'algorithme.

Un algorithme est souvent constitué d'instructions formulées avec précision, d'une procédure pour certaines actions qui doivent garantir la réalisation d'un objectif fixé.

Quelles sont les propriétés des algorithmes

Mais il convient de rappeler que toutes les séquences d’actions ne peuvent pas être qualifiées d’algorithme. Une séquence n’est un algorithme que si elle possède certaines propriétés. Listons-les :

1. L'une des propriétés les plus importantes est la discrétion. Nous l'examinerons un peu plus bas.
2. La certitude est tout aussi importante. Selon cette propriété, chaque commande doit être sans ambiguïté et diriger l'interprète vers une action spécifique.
3. Il convient de rappeler que l'algorithme est compréhensible. L'algorithme doit utiliser uniquement les commandes nécessaires et pertinentes pour la tâche à accomplir.
4. Une propriété importante est l’efficacité (également souvent appelée finitude) de l’algorithme. La propriété « efficacité » indique que l'algorithme comporte un certain nombre d'étapes préalablement spécifié, dont la mise en œuvre conduira à l'achèvement de la tâche.
5. De plus, tout algorithme doit nécessairement avoir une propriété telle que la disponibilité massive. Si un algorithme assure l'exécution de toutes les tâches d'un certain type, il a alors la propriété d'une production de masse.

Qu'est-ce qu'un algorithme en informatique

Tous les scientifiques s’accordent sur le fait que le concept d’algorithme est fondamental dans l’informatique moderne. En créant logiciel La première étape consiste toujours à créer un algorithme.

Un algorithme écrit dans un langage formel est généralement appelé programme. Très souvent, le concept d'algorithme est étroitement associé au processus d'écriture dans un programme. C’est pourquoi les termes algorithme et programme sont souvent considérés comme synonymes.

Comment créer un algorithme

Afin de créer un algorithme efficace et de qualité, plusieurs règles doivent être respectées :

1. L'algorithme doit être écrit dans un langage formel et clair. L’ambiguïté ou la clarté des instructions est inacceptable.
2. Lors de la compilation d'un algorithme, il est nécessaire de prendre en compte pour qui il est compilé. L'interprète doit comprendre tous les points de l'algorithme et être capable de les mettre en œuvre.
3. Il est conseillé de garder l’algorithme concis, précis et clair.

Qu'est-ce que l'algorithme linéaire

Parmi tous les algorithmes, on distingue les algorithmes linéaires et non linéaires. Un algorithme est considéré comme linéaire s’il maintient un ordre constant d’actions tout au long du processus d’exécution.

En informatique, le langage de programmation avec lequel un algorithme est décrit est généralement appelé opérateur. Il existe des opérateurs simples et structurés. Des déclarations simples décrivent une seule action.

Exactement opérateurs simples le plus souvent utilisé dans les algorithmes linéaires.

La propriété de discrétion de l'algorithme et sa signification

Nous avons mentionné plus tôt que tout algorithme possède une propriété telle que la discrétion. Examinons maintenant plus en détail le concept de discrétion.

La discrétion est souvent remplacée par des termes tels que discontinuité et séparation de l'algorithme. Essentiellement, les trois termes signifient la même chose, à savoir l’exécution séquentielle (alternée) de toutes les commandes de l’algorithme. Si la discrétion est observée, chaque action n'est effectuée qu'après l'achèvement de la précédente, et la mise en œuvre de tous les points de consigne conduit au résultat final spécifié précédemment (à solution complète Tâches).

Nous avons maintenant examiné les termes et concepts de base liés à notre sujet d'aujourd'hui. Ce n’est sûrement plus un problème pour vous de répondre à la question de savoir ce qu’est un algorithme. Les connaissances acquises vous seront utiles plus d'une fois tant dans votre domaine professionnel que dans Vie courante. Comme toujours, vous pouvez clarifier les détails ou trouver la réponse à votre question en utilisant système pratique commentaires ci-dessous.

Salutations, amis ! Nous continuons à vous faire découvrir le monde de la cryptographie et des cryptomonnaies. Aujourd'hui, j'aimerais parler des protocoles de sécurité Preuve de travail Et Preuve de participation. Quelle est leur différence et comment le passage de l’un à l’autre peut affecter le monde minier. Comme toujours, avec des mots simples et intéressants. Aller!

Je propose de revenir sur les principales étapes qui caractérisent la blockchain et le minage en prenant comme exemple le réseau Bitcoin. ( , et ). Ainsi, toutes les transactions ayant lieu sur le réseau doivent être confirmées. Les transactions non confirmées sont placées dans un bloc. Pour confirmer les transactions, les mineurs doivent signer un bloc, qui est ensuite enregistré dans la blockchain.

Preuve de travail

Examinons maintenant l'algorithme de confirmation des transactions et de création de nouveaux blocs, appelé Proof of Work. Considérez toutes les transactions comme les pièces d’un puzzle cryptographique () qui s’assemblent pour créer un bloc. La résolution de ce puzzle (bloc) s’appelle l’exploitation minière.

Comment un mineur gagne-t-il de l’argent ?

Pour signer un bloc avec des transactions non confirmées, les mineurs doivent calculer le hachage. Après l'avoir calculé, le mineur crée un nouveau bloc et reçoit une récompense de 12,5 BTC. La récompense pour la signature d'un nouveau bloc diminue tous les 4 ans. Au début du réseau Bitcoin, il s’agissait de 50 BTC.

Comment le système détermine-t-il le mineur qui a signé le nouveau bloc ?

Chaque mineur souhaitant créer un bloc travaille sur un problème informatique très complexe. Dont la complexité est sélectionnée par le réseau de telle sorte qu'en moyenne une solution soit trouvée toutes les 10 minutes. Si le nombre de mineurs augmente, la tâche devient plus difficile. Par conséquent, les chances que chaque participant résolve le problème en 10 minutes sont réduites. Plus un mineur dispose de puissance de calcul, plus ses chances de succès sont élevées. Le mineur qui résout le premier le problème et calcule le hachage signe le nouveau bloc et reçoit une récompense.

Alors qu'est-ce que nous avons?

L'algorithme Proof of Work offre une protection de haute qualité. Il n’y a jamais eu un seul cas de piratage du réseau Bitcoin. Cependant, cet algorithme présente un énorme inconvénient : le travail effectué nécessite de très grandes quantités d'électricité. La course aux nouveaux blocs a transformé l’industrie minière en un monstre énergétique insatiable. Et c’est pour résoudre ce problème que l’algorithme Proof of Stake a été développé.

Preuve de participation

La preuve de participation se traduit par une preuve de propriété. Il n'y a pas de mineurs dans cet algorithme. Les personnes qui confirment les transactions et créent de nouveaux blocs sont appelées validateurs.

Regardons un exemple hypothétique

Supposons qu'il y ait un bloc qui doit être signé et qu'il y ait 4 validateurs. Chaque validateur apporte ses fonds à la blockchain pour pouvoir signer un bloc.

Le premier validateur possède le plus de pièces et contribue à hauteur de 40 %. Le deuxième validateur contribue à hauteur de 25 %, le troisième à hauteur de 20 %, et enfin le dernier contribue à hauteur de 15 %. Avec l’algorithme Proof of Work, les chances de signer un bloc dépendent de la puissance de calcul dont vous disposez. Mais dans Proof of Stake, l’algorithme fonctionne différemment. Plus vous avez de pièces, plus vous avez de chances de signer un nouveau bloc.

Après des calculs aléatoires, le système sélectionne l'un des validateurs et il signe le bloc. Mais pour cette action, le validateur ne reçoit pas de nouvelles pièces, il reçoit toutes les commissions pour les transactions enregistrées dans ce bloc.

Avantages de la preuve de participation

L’algorithme Proof of Stake présente un certain nombre d’avantages évidents.

1. Aucune consommation d'énergie. Lors de l’utilisation de Proof of Stake, les ressources ne sont pas gaspillées. L'ordinateur, bien qu'il doive être allumé, n'effectue pas de calculs complexes et, par conséquent, ne consomme pas beaucoup d'électricité.

2. Il n’est pas nécessaire d’augmenter la puissance de calcul.

3. La nécessité de disposer d’une grande quantité de jetons en stock protège contre les attaques sur le réseau. Si un attaquant commence à acheter des pièces, leur valeur réagira immédiatement et commencera à croître activement. Et cela rendra l’achat ultérieur de jetons extrêmement peu rentable.

Si quelqu’un parvient à encaisser une fortune sur son bilan, l’attaquant risque de subir sa propre attaque, puisque la stabilité du système sera perturbée.

Vous savez désormais comment fonctionnent les algorithmes Proof of Work et Proof of Stake. Abonnez-vous à notre réseaux sociaux(liens en pied de page du site) pour ne pas manquer d'informations sur les nouveaux articles et projets.

Gagnez de l'argent et améliorez votre cerveau avec Business Biceps.

QUELLE EST LA DIFFÉRENCE ENTRE UNE MÉTHODE ET UN ALGORITHME ?

Méthode est un ensemble d'actions, et algorithme- une séquence d'actions spécifique.

1. L’algorithme est plus détaillé que la méthode. Une illustration d'un algorithme est un schéma fonctionnel, et une illustration d'une méthode est un dispositif dont les composants fonctionnent simultanément.

2. La même méthode peut être implémentée par plusieurs algorithmes. Et quoi méthode plus compliquée, plus il y a d'implémentations possibles sous forme d'algorithmes.

3. Vous pouvez comprendre la méthode à partir de la description de l'algorithme, mais la description de la méthode donnera une compréhension plus complète des idées mises en œuvre dans l'algorithme.

4. Il ne peut y avoir aucune erreur dans la méthode. Mais d’un autre côté, le choix de la méthode peut être erroné. En utilisant les mêmes données, une autre méthode peut toujours donner un meilleur résultat, dont l’avantage peut ne pas paraître évident à première vue. Le choix de l’algorithme peut également être erroné.

5. Différents algorithmes implémentant la même méthode peuvent donner des résultats complètement différents ! Montrons cela avec un exemple.

UN EXEMPLE MONTRANT L'INÉQUIVALENCE DES ALGORITHMES DE LA MÉTHODE

La méthode contient la procédure Z, qui fait pivoter une image bidimensionnelle d'un angle A donné et ajoute de la luminosité aux points de l'image d'une quantité B, en fonction de la distance à parcourir. point donné C : B=B(x-ho, y-oo) Le point « sélectionné » C peut se trouver aussi bien à l'intérieur qu'à l'extérieur des limites de l'image, cela ne change rien. En tournant, il reçoit de nouvelles coordonnées : x 0, y\.

Bien évidemment, deux algorithmes sont possibles : ■ d'abord faire pivoter selon un angle donné, puis ajouter de la luminosité ; » Ajoutez d'abord de la luminosité, puis développez.

Les résultats de ces deux algorithmes peuvent différer légèrement en raison de l'arrondi des résultats du calcul de distance : D=((x-xo) 2 + (y-Uo) 2) 1/2, a D, =((x, -x > o ) 2 +(y"-y"o) 2) 1/2 > et dans le cas général ces distances avant et après la rotation D et D" ne sont pas égales.

Lors de l'extraction racine carrée Des nombres irrationnels apparaissent, c'est-à-dire des fractions infinies. Ainsi, quelle que soit l’exactitude de l’arithmétique

ticks - 16 caractères ou 1024, tout de même, D et D" devront être arrondis après un certain caractère, en éliminant les caractères restants. L'augmentation de la précision ne fera qu'entraîner une diminution de la probabilité qu'après avoir arrondi D et D" soient inégal.

Si, sur la base du résultat de la procédure de rotation avec ajout de luminosité, un critère est calculé et l'une des plusieurs options est sélectionnée en fonction de sa valeur actions supplémentaires, alors les résultats des deux algorithmes peuvent différer non pas « juste un peu », mais *. dinal.

Par exemple, le critère a la forme T nouveau<3-T 0 i d ", где T 0 | d - суммарная яркость изображения до процедуры Z, a T new - после нее. И если в первом алгоритме Ты/Tnew = 0.3333 , а во втором 0.3334, то после проверки критерия выпол­нятся разные ветви алгоритма. Результат неэквивалентности алгоритмов будет хорошо заметен.

Même s’il n’y a pas de critère, l’erreur peut s’accumuler progressivement, à chaque étape d’un certain cycle.

Ainsi, deux algorithmes mettant en œuvre la même méthode peuvent parfois produire des résultats complètement différents.

Implémentation de l'algorithme - programme

Un programme est une implémentation, une « incarnation » d'un algorithme dans l'un des langages de programmation. Ainsi, le schéma général d'écriture d'un programme de compression (codec, c'est-à-dire compresseur et décompresseur), ainsi que de tout programme en général, est le suivant :

1) énoncé du problème ;

2) choix méthode;

3) création algorithme;

4) écrire programmes;

5) tests, optimisation et configuration.

Ce livre décrit exactement les méthodes, mais pour les illustrer, des algorithmes spécifiques à un processeur sont donnés, illustrés de textes en langage de programmation C.