Éléments de la théorie des algorithmes

Algorithme - un concept lié aux fondements fondamentaux de l'informatique. Il est apparu bien avant l'avènement des ordinateurs et est l'un des concepts de base des mathématiques.

Mot "algorithme" vient du nom d'un scientifique médiéval exceptionnel Mohamed ibn Moussa Al-Khorezmi(IX siècle après JC), en abrégé Al-Khorezmi... Dans la traduction latine de l'une des œuvres d'Al-Khorezmi, les règles d'exécution des actions ont commencé par les mots DIXIT ALGORIZMI (Algorizmi a dit), dans d'autres traductions latines l'auteur s'appelait ALGORITHME (Algorithme).

Avoir une idée "algorithme" pas clair, sans ambiguïté définitions au sens mathématique. Vous ne pouvez donner la description (clarification) de ce concept. Pour clarifier le concept "algorithme" la définition de "Exécuteur d'algorithmes" ... L'algorithme est formulé en vue d'un interprète spécifique.

Algorithme - un guide d'action pour l'interprète, donc le sens du mot « algorithme » est proche en sens du sens des mots « instruction » ou « prescription ».

Algorithme - clair et précis ordonnance(indication) l'exécutant pour effectuer une certaine séquence d'actions pour atteindre l'objectif spécifié ou résoudre la tâche.

Algorithme - une prescription exacte qui définit un processus de calcul, à partir d'une donnée initiale arbitraire à partir d'un certain ensemble de données possibles pour ce processus, visant à obtenir un résultat complètement déterminé par ces données initiales.

Il est clair que ce qui a été dit n'est pas une définition au sens mathématique du terme, mais reflète seulement la compréhension intuitive de l'algorithme (en mathématiques il n'y a pas de concept de "prescription", il n'est pas clair quelle doit être la précision, ce qui est « compréhensibilité », etc.).

Propriétés de base de l'algorithme

Caractère de masse.

L'algorithme a un certain nombre de valeurs d'entrée - arguments, définis avant le début de l'exécution. Le but de l'algorithme est d'obtenir un résultat (résultats) qui a une relation très précise avec les données d'origine. L'algorithme spécifie la séquence d'actions pour le traitement des données brutes en résultats. Pour l'algorithme, vous pouvez choisir différents ensembles de données d'entrée parmi l'ensemble de données admissibles pour ce processus, c'est-à-dire l'algorithme peut être utilisé pour résoudre toute une classe de problèmes du même type, différant par les données initiales. Cette propriété de l'algorithme est généralement appelée massivité ... Cependant, il existe des algorithmes qui ne s'appliquent qu'à un seul ensemble de données. On peut dire que pour chaque algorithme il y a sa propre classe d'objets qui sont admissibles comme données d'entrée. Puis la propriété caractère de masse signifie que l'algorithme est applicable à tous les objets de cette classe.

Compréhensibilité.

Pour que l'algorithme soit exécuté, il doit être clair pour l'exécuteur. Compréhensibilité de l'algorithme signifie la connaissance de l'interprète de ce qui doit être fait pour exécuter cet algorithme.

Discrétion.

L'algorithme est représenté comme une séquence finie d'étapes (l'algorithme a discret structure) et son exécution est divisée en étapes individuelles (l'exécution de l'étape suivante commence après l'achèvement de la précédente).

Membre.

L'exécution de l'algorithme se termine après l'exécution nombre fini d'étapes ... Lors de l'exécution de l'algorithme, certaines de ses étapes peuvent être répétées plusieurs fois. En mathématiques, il existe des procédures de calcul qui sont de nature algorithmique, mais ne pas posséder la propriété membres .

Certitude.

Chaque étape de l'algorithme doit être clairement et sans ambiguïté et ne doit pas permettre une interprétation arbitraire de la part de l'interprète. Par conséquent, l'algorithme est conçu pour conception purement mécanique . Exactement certitude l'algorithme permet d'instruire son exécution automate .

Efficacité.

Chaque étape de l'algorithme doit être effectuée avec précision et dans un temps fini. En ce sens, ils disent que l'algorithme doit être efficace , c'est à dire. les actions de l'exécuteur à chaque étape de l'exécution de l'algorithme doivent être suffisamment simples pour qu'elles puissent être exécutées avec précision et en un temps fini. Habituellement, les instructions individuelles à l'interprète contenues dans chaque étape de l'algorithme sont appelées équipes ... Ainsi, l'efficacité de l'algorithme est liée à la capacité à exécuter chaque commande en un temps fini. L'ensemble des commandes qui peuvent être exécutées par un exécuteur spécifique est appelé le système de commandement de l'exécuteur ... Par conséquent, l'algorithme doit être formulé pour contenir uniquement les commandes qui sont incluses dans le système de commandes de l'exécuteur. De plus, l'efficacité signifie que l'algorithme peut être exécuté non seulement dans un temps fini, mais dans un temps raisonnablement fini.

Les commentaires ci-dessus précisent concept d'algorithme intuitif , mais ce concept lui-même n'en devient pas plus clair et plus strict. Néanmoins, ce concept est utilisé en mathématiques depuis longtemps. Seulement avec l'identification de problèmes algorithmiquement insolubles, c'est-à-dire problèmes pour la solution desquels il est impossible de construire un algorithme, il est urgent de construire une définition formelle d'un algorithme correspondant à un concept intuitif bien connu. Le concept intuitif d'un algorithme, en raison de son incertitude, ne peut pas être un objet d'étude mathématique, par conséquent, pour prouver l'existence ou la non-existence d'un algorithme pour résoudre un problème, une définition formelle stricte de l'algorithme était nécessaire.

La construction d'une telle définition formelle a commencé avec la formalisation des objets (opérandes) de l'algorithme, car dans le concept intuitif de l'algorithme, ses objets peuvent être de nature arbitraire. Il peut s'agir, par exemple, de nombres, de relevés de capteurs fixant les paramètres du processus de production, de pièces et de positions d'échecs, etc. Cependant, en supposant que l'algorithme traite non pas des objets réels eux-mêmes, mais de leurs images, nous pouvons supposer que opérandes d'algorithme - des mots dans un alphabet arbitraire. Ensuite, il s'avère que l'algorithme convertit les mots d'un alphabet arbitraire en mots du même alphabet. Une formalisation plus poussée du concept d'algorithme est associée à la formalisation des actions sur les opérandes et à l'ordre de ces actions. L'une de ces formalisations a été proposée en 1936 par le mathématicien anglais A. Turing, qui a formellement décrit la construction d'une machine abstraite ( Machines de Turing ) en tant qu'exécuteur de l'algorithme et a exprimé la thèse principale selon laquelle tout algorithme peut être implémenté par la machine de Turing correspondante. Vers la même époque, le mathématicien américain E. Post a proposé un autre schéma algorithmique - Machine à courrier , et en 1954 le mathématicien soviétique A.A. Markov a développé la théorie des classes d'algorithmes nommées par lui algorithmes normaux , et a énoncé la thèse principale selon laquelle tout algorithme est normalisable.

Ces schémas algorithmiques sont équivalents en ce sens que des algorithmes décrits dans l'un des schémas peuvent également être décrits dans un autre. Récemment, ces théories d'algorithmes ont été regroupées sous le nom casse-tête .

Les théories logiques des algorithmes sont tout à fait adaptées pour résoudre des questions théoriques sur l'existence ou la non-existence d'un algorithme, mais elles n'aident en rien dans les cas où vous avez besoin d'un bon algorithme adapté à des applications pratiques. Le fait est que, du point de vue des théories logiques, les algorithmes destinés à des applications pratiques sont des algorithmes au sens intuitif. Par conséquent, lors de la résolution de problèmes liés à la création et à l'analyse de tels algorithmes, il faut souvent être guidé uniquement par l'intuition, et non par une théorie mathématique rigoureuse. Ainsi, la pratique s'est donné pour tâche de créer une théorie signifiante, dont le sujet serait les algorithmes, en tant que tels, et qui permettrait d'évaluer leur qualité, donnerait des méthodes pratiquement utilisables pour leur construction, transformation équivalente, preuve de correction, etc.

Une théorie (analytique) significative des algorithmes n'est devenue possible que grâce aux travaux fondamentaux des mathématiciens dans le domaine des théories logiques des algorithmes. Le développement d'une telle théorie est associé à l'approfondissement et à l'expansion du concept formel d'algorithme, qui est trop restreint dans le cadre des théories logiques. Le caractère formel du concept permettra de lui appliquer des méthodes de recherche mathématique, et son ampleur devrait assurer la possibilité de couvrir tous les types d'algorithmes qui doivent être traités en pratique.

Sujet : Algorithme. propriétés de l'algorithme

Algorithme- il s'agit d'une prescription compréhensible et précise pour que l'interprète effectue la séquence finale d'étapes menant des données initiales au résultat souhaité

Propriétés de l'algorithme

q Discrétion (discontinuité) - l'algorithme doit être divisé en
séquence d'étapes à effectuer ;

q Certitude (déterminisme, précision) - algorithme
doit être mis en œuvre sans ambiguïté (avec précision) par l'interprète.

q Caractère de masse - l'algorithme compilé est applicable pour résoudre
problèmes similaires avec des données initiales différentes.

q Finitude (performance)- en un nombre fini d'étapes
le résultat doit être obtenu;

q Formalité - propriété signifiant que tout artiste interprète,
par exemple, un ordinateur agit formellement, c'est-à-dire strictement
suit les instructions fournies par le développeur
algorithme.

q Compréhensibilité – l'algorithme ne doit contenir que ces commandes
que l'interprète spécifique comprend.

Diagramme on appelle une image graphique de la structure logique d'un algorithme, dans laquelle chaque étape du processus de traitement de l'information est représentée sous forme de symboles géométriques (blocs) ayant une certaine configuration selon la nature des opérations effectuées.

Avec toute la variété des algorithmes pour résoudre des problèmes, on peut distinguer trois grands types de processus informatiques :

· Linéaire ;

· Branchement;

· Cyclique.

Linéaire est appelé un processus informatique dans lequel toutes les étapes de la résolution d'un problème sont effectuées dans l'ordre naturel d'écriture de ces étapes.

Branchement est appelé un processus de calcul dans lequel le choix de la direction du traitement de l'information dépend des données initiales ou intermédiaires (des résultats de la vérification de la réalisation de toute condition logique).

Cycle est appelée une partie répétitive des calculs. Un processus de calcul contenant un ou plusieurs cycles est appelé cyclique .

Répondez aux questions du test

1.Les principales propriétés de l'algorithme incluent ...

a) brièveté, certitude, fidélité, caractère de masse, formalité

b) discrétion, importance, efficacité, loyauté, formalité

c) fiabilité, discontinuité, efficacité, généralité, formalité

d) hiérarchisation, importance, efficacité, caractère de masse

2. Une description graphique de l'algorithme est une description utilisant ...

a) ... schémas

b) ... schémas fonctionnels

c) ... graphiques

d) ... toutes les méthodes ci-dessus

3. À quelle propriété de l'algorithme la définition fait-elle référence ?

L'interprète, ne comprenant pas le sens de l'algorithme et l'énoncé du problème, exécutant correctement chaque commande, peut obtenir le résultat correct.

a) caractère de masse

b) efficacité

c) formalité

d) fiabilité

4. La description d'algorithme en langage algorithmique est un outil pour écrire un algorithme..

a) ... sous forme théorique

b) ... sous forme de schémas

c) ... sous une forme analytique

d) ... sous une forme spéciale

5. La propriété de l'algorithme qui détermine la nature étape par étape de l'algorithme s'appelle ...

a) efficacité

b) sans ambiguïté

c) discrétion

d) masse

e) toutes les propriétés déterminent la nature étape par étape de l'algorithme

6. Un algorithme est dit linéaire si ...

a) il est composé de telle manière que sa mise en œuvre implique la répétition répétée des mêmes actions ;

b) la séquence d'exécution de ses commandes dépend de la véracité de certaines conditions ;

c) ses commandes sont exécutées dans l'ordre de leur succession naturelle les unes après les autres, quelles que soient les conditions ;

d) il comprend un algorithme auxiliaire ;

e) son enregistrement est présenté sur une seule ligne.

7.Ne s'applique pas aux propriétés principales de l'algorithme ...

a) l'exactitude ;

b) certitude

c) caractère de masse

d) efficacité

CONCEPT DE L'ALGORITHME. PROPRIÉTÉS DE L'ALGORITHME. TYPES D'ALGORITHMES. MÉTHODES DE DÉCRIPTION DES ALGORITHMES

Un algorithme est une instruction exacte et compréhensible à l'exécutant pour effectuer une séquence d'actions visant à résoudre la tâche. Le mot "algorithme" vient du nom du mathématicien Al Khorezmi, qui a formulé les règles pour effectuer des opérations arithmétiques. Initialement, un algorithme n'était compris que comme les règles permettant d'effectuer quatre opérations arithmétiques sur des nombres. À l'avenir, ce concept a commencé à être utilisé en général pour désigner une séquence d'actions menant à la solution de n'importe quelle tâche. En parlant de l'algorithme du processus de calcul, il est nécessaire de comprendre que les objets auxquels l'algorithme a été appliqué sont des données. L'algorithme pour résoudre un problème de calcul est un ensemble de règles pour transformer les données initiales en celles résultantes.

Le principal Propriétés algorithme sont :

1. déterminisme (certitude). Suppose l'obtention d'un résultat non ambigu du processus de calcul avec les données initiales données. En raison de cette propriété, le processus d'exécution de l'algorithme est de nature mécanique ;
2. efficacité. Indique la présence de telles données initiales pour lesquelles le processus de calcul mis en œuvre selon un algorithme donné doit s'arrêter après un nombre fini d'étapes et retourner le résultat souhaité ;
3. caractère de masse. Cette propriété suppose que l'algorithme doit être adapté pour résoudre tous les problèmes de ce type ;
4. discrétion. Cela signifie le démembrement du processus de calcul déterminé par l'algorithme en étapes distinctes, la possibilité dont l'exécuteur (ordinateur) peut effectuer ne fait aucun doute.

L'algorithme doit être formalisé selon certaines règles au moyen de moyens visuels spécifiques. Il s'agit notamment des méthodes d'écriture d'algorithmes suivantes : verbal, formule-verbal, graphique, langage de schéma d'opérateur, langage algorithmique.

En raison de sa clarté, la plus répandue est la méthode graphique (bloc-diagramme) d'écriture d'algorithmes.

Diagramme on appelle une image graphique de la structure logique d'un algorithme, dans laquelle chaque étape du processus de traitement de l'information est représentée sous forme de symboles géométriques (blocs) ayant une certaine configuration selon la nature des opérations effectuées. La liste des symboles, leur nom, les fonctions qu'ils affichent, leur forme et leur taille sont déterminés par les GOST.

Avec toute la variété des algorithmes de résolution de problèmes, on peut y distinguer trois principaux types de processus de calcul :

• linéaire;
• ramification;
• cyclique.

Linéaire est appelé un processus informatique dans lequel toutes les étapes de la résolution d'un problème sont effectuées dans l'ordre naturel d'écriture de ces étapes.

Branchement est appelé un processus de calcul dans lequel le choix de la direction du traitement de l'information dépend des données initiales ou intermédiaires (des résultats de la vérification de la réalisation de toute condition logique).

Un cycle est une section de calculs répétée à plusieurs reprises. Un processus de calcul contenant un ou plusieurs cycles est appelé cyclique ... Selon le nombre d'exécutions, les cycles sont divisés en cycles avec un certain nombre (prédéterminé) de répétitions et en cycles avec un nombre indéfini de répétitions. Le nombre de répétitions de ce dernier dépend du respect d'une certaine condition qui spécifie la nécessité d'effectuer le cycle. Dans ce cas, la condition peut être vérifiée au début du cycle - alors on parle d'un cycle avec une précondition, ou à la fin - alors c'est un cycle avec une postcondition.

Sens du mot algorithme très semblable au sens des mots Recette,instruction... Cependant, tout algorithme, à la différence d'une recette ou d'une méthode, a nécessairement les propriétés suivantes.

1. L'exécution de l'algorithme est divisée en une séquence d'actions-étapes terminées. Ce n'est qu'après avoir terminé une action (commande) que vous pouvez passer à la suivante. Cette propriété de l'algorithme est appelée discrétion... Une instruction spéciale dans l'enregistrement d'algorithme (commande) prescrit à l'interprète d'effectuer chaque action individuelle.

2. Compréhensibilité- l'algorithme ne doit pas contenir d'instructions dont le sens peut être perçu de manière ambiguë par l'interprète, c'est-à-dire l'enregistrement de l'algorithme doit être si clair et complet que l'interprète n'a pas besoin de prendre de décisions indépendantes. L'algorithme est toujours conçu pour l'exécution d'un interprète « non-pensant »... L'algorithme est composé des commandes incluses dans le SKI.

Considérons un exemple bien connu d'algorithme « de tous les jours » - un algorithme de traversée de rue : « Regardez vers la gauche. S'il n'y a pas de voitures, marchez jusqu'au milieu de la rue. S'il y en a, attendez qu'ils passent, etc. ». Imaginez une situation : il y a une voiture à gauche, mais elle ne va pas - sa roue est changée. Si vous pensez que l'exécuteur de l'algorithme doit attendre, alors vous avez compris cet algorithme. Si vous décidez que vous pouvez traverser la rue, compte tenu de l'algorithme corrigé en raison de circonstances imprévues (à votre avis!), alors vous n'avez pas appris le concept d'un algorithme.

3. Déterminisme (certitude et sans ambiguïté). Chaque commande de l'algorithme définit une action sans ambiguïté de l'exécuteur, et il doit être déterminé sans ambiguïté quelle commande est exécutée ensuite. C'est-à-dire que si un algorithme est appliqué de manière répétée au même ensemble de données initiales, il reçoit à la sortie le même résultat à chaque fois.

4. Efficacité- l'exécution de l'algorithme doit être achevée en un nombre fini d'étapes, et le résultat de la résolution du problème doit être obtenu. L'un des résultats possibles peut être l'établissement du fait que le problème n'a pas de solutions.

La propriété de performance contient la propriété membres- la réalisation de l'algorithme en un nombre fini d'étapes.

5. Caractère de masse- l'algorithme est adapté pour résoudre n'importe quel problème d'une certaine classe de problèmes, c'est-à-dire l'algorithme fonctionne correctement sur un certain ensemble de données initiales, appelé domaine d'applicabilité de l'algorithme.

La propriété du caractère de masse détermine plutôt la qualité de l'algorithme, et ne fait pas référence à des propriétés obligatoires (telles que la discrétion, la compréhensibilité, etc.). Il existe des algorithmes dont la portée est limitée par un seul ensemble de données d'entrée ou même son absence (par exemple, obtenir un nombre fixe de chiffres corrects du nombre p). Il est plus correct de dire que l'algorithme devrait être applicable à toutes les données de son domaine de définition, et le mot massivité n'est pas toujours adapté pour décrire une telle propriété.

Notion d'algorithme

En résumant ce qui précède, nous formulons ce qui suit concept algorithme.

Algorithme - une prescription compréhensible et précise pour l'interprète pour effectuer la séquence finale d'actions menant des données initiales au résultat souhaité.

La définition donnée n'est pas une définition au sens mathématique du terme, c'est-à-dire ce n'est pas une définition formelle (pour une définition formelle de l'algorithme, voir l'article " Théorie des algorithmes”).

Notez que pour chaque interprète l'ensemble des actions autorisées (SKI) est toujours limité - il ne peut pas y avoir d'artiste pour lequel une action est autorisée. Le raisonnement paraphrasé de I. Kant justifie la déclaration formulée comme suit : « Si un tel interprète existait, alors parmi ses actions permises figurerait la création d'une telle pierre qu'il ne peut pas soulever. Mais cela contredit la licéité de l'action "Raise any stone".

Il est intéressant de noter qu'il existe des problèmes qu'une personne, de manière générale, est capable de résoudre sans connaître l'algorithme pour le résoudre. Par exemple, il y a des photos de chats et de chiens devant une personne. La tâche consiste à déterminer si un chat ou un chien est représenté sur une photo particulière. Une personne résout ce problème, mais il est extrêmement difficile d'écrire un algorithme pour résoudre ce problème.

D'autre part, il existe des problèmes pour lesquels il est généralement impossible de construire une procédure de résolution. De plus, ce fait peut être rigoureusement prouvé. Vous pouvez lire à ce sujet dans l'article " Problèmes algorithmiquement insolubles” 2.

Résout le problème de trouver le débit maximum dans le réseau de transport. L'algorithme n'est pas un cas particulier de l'algorithme de Ford Fulkerson. Mis en œuvre sans améliorations particulières, l'algorithme s'exécute dans le temps. Quelques améliorations plus ... Wikipedia

Les algorithmes de recherche locale sont un groupe d'algorithmes dans lesquels la recherche est effectuée uniquement sur la base de l'état actuel, et les états précédemment passés ne sont pas pris en compte et ne sont pas mémorisés. Le but principal de la recherche n'est pas de trouver le chemin optimal vers ... ... Wikipedia

Ce terme a d'autres significations, voir Mars (homonymie). MARS Création : 1998 Publication : 1998 Taille clé ... Wikipedia

Ce terme a d'autres significations, voir Mars (homonymie). MARS Création : 1998 ... Wikipédia

Ce terme a d'autres significations, voir Algorithme (significations). Pour améliorer cet article, est-ce souhaitable ? : Repenser le design en respectant les règles... Wikipédia

Cet article incorpore du matériel de cette version de l'article correspondant de Wikipédia en anglais. La transformation opérationnelle (OP) est une technologie permettant de prendre en charge une gamme de fonctionnalités de collaboration dans des systèmes avancés ... ... Wikipedia

Algorithmes de recherche sur les graphiques A * B * Algorithme de Bellman Ford Recherche bidirectionnelle Algorithme de Dijkstra Algorithme de Johnson Recherche en largeur d'abord Recherche en profondeur d'abord Recherche en premier Algorithme de Floyd Warshall Recherche ... ... Wikipedia

Il s'agit d'un algorithme permettant de classer les éléments dans une liste. Lorsqu'un élément de liste comporte plusieurs champs, le champ qui sert de critère de classement est appelé clé de tri. En pratique, un nombre est souvent utilisé comme clé, et dans d'autres domaines ... ... Wikipedia

Fonction de hachage cryptographique BMW (eng. BMW Blue Midnight Wish) (хф) avec sortie en n bits, où n = 224,256, 384 ou 512. Les fonctions de hachage sont conçues pour créer des « empreintes digitales » ou des « condensés » de messages de longueur de bits arbitraire. ... ... Wikipédia

Cet article devrait être wiki. Veuillez le remplir selon les règles de mise en forme des articles. Ce terme a d'autres significations, voir TEA (significations) ... Wikipedia

Livres

• Logiques et nombres premiers de Lukasiewicz, A. S. Karpenko, Pour la première fois dans la littérature mondiale, une étude monographique établit un lien direct entre la logique et les nombres premiers. Bien que les logiques ambiguës de Lukasiewicz soient le résultat d'une réfutation... Catégorie : Logique Editeur : Librokom,
• Logique dans les questions et réponses. Tutoriel, Kobzar Vladimir Ivanovich, Le tutoriel est écrit conformément au programme du cours de logique formelle traditionnelle (générale, philosophique). Il examine les principales formes et méthodes d'activité mentale, leur ... Catégorie: