Une brève note sur les algorithmes pour les programmes informatiques

Qu'est-ce que la programmation informatique ?

En termes simples, il indique à l'ordinateur quoi faire. Les ordinateurs peuvent faire beaucoup de choses, mais ils ne sont pas très doués pour penser par eux-mêmes. Les programmeurs doivent lui indiquer des détails spécifiques, comme nourrir un enfant, et lui faire comprendre l'algorithme du langage.

L'algorithme fait référence à une description précise et complète d'une solution de résolution de problèmes. Il s'agit d'une série d'instructions claires pour résoudre des problèmes. L'algorithme représente une méthode systématique pour décrire le mécanisme stratégique de résolution de problèmes. En d’autres termes, il est possible d’obtenir le résultat requis dans un temps limité pour certains intrants standardisés. Si un algorithme est défectueux ou inapproprié pour résoudre un problème, son exécution ne résoudra pas le problème. Différents algorithmes peuvent utiliser différents temps, espace ou efficacité pour accomplir la même tâche. La qualité d’un algorithme peut être mesurée par sa complexité spatiale et sa complexité temporelle.
Les instructions de l'algorithme décrivent un calcul qui, une fois exécuté, peut partir d'un état initial et d'une entrée initiale (éventuellement vide), passer par une série limitée et clairement définie d'états, et enfin produire une sortie et s'arrêter à un état final. Le passage d'un état à un autre n'est pas nécessairement déterministe. Certains algorithmes, notamment les algorithmes randomisés, contiennent des entrées aléatoires.
Le concept d'algorithmes formels est né en partie des tentatives visant à résoudre les problèmes de décision de Hilbert et a pris forme lors de tentatives ultérieures visant à définir une calculabilité efficace ou des méthodes efficaces. Ces tentatives comprenaient les fonctions récursives proposées par Kurt Gödel, Jacques Herbrand et Stephen Cole Crane respectivement en 1930, 1934 et 1935, le calcul lambda proposé par Alonzo Church en 1936, la Formulation 1 d'Emil Leon Post en 1936 et la Machine de Turing d'Alan Turing en 1936. 1937. Même aujourd’hui, il arrive souvent que des idées intuitives soient difficiles à définir comme des algorithmes formels.

Caractéristiques

Un algorithme doit avoir les cinq caractéristiques importantes suivantes :
1. Finitude
La finitude d'un algorithme signifie que l'algorithme doit être capable d'exécuter Terminate après un temps fini nombre d'étapes ;
2. Précision
Chaque étape de l'algorithme doit être clairement définie
3. Entrée
Un algorithme a 0 ou plus Une entrée est utilisée pour décrire la situation initiale de l'opération ; objet. L'entrée dite 0 signifie que l'algorithme lui-même définit les conditions initiales ;
4. Sortie (Sortie)
Un algorithme a une ou plusieurs sorties pour refléter le résultat après le traitement des données. Un algorithme sans résultat n'a aucun sens ;
5. Faisabilité (Efficacité)
Toute étape de calcul effectuée dans l'algorithme peut être décomposée en étapes d'opération exécutables de base, c'est-à-dire que chaque étape de calcul peut être complétée dans un temps limité ( également appelé efficacité).

Éléments

1. Opérations et opérations des objets de données : Les opérations de base qu'un ordinateur peut effectuer sont décrites sous forme d'instructions. L’ensemble de toutes les instructions qu’un système informatique peut exécuter devient le système d’instructions du système informatique. Les calculs et opérations de base d'un ordinateur sont les suivants :
1. Opérations arithmétiques : addition, soustraction, multiplication et division, etc.
2. Opérations logiques : opérations telles que OU, ET, NON, etc.
3. Opérations relationnelles : supérieur à, Opérations telles que inférieur, égal à et différent de
4. Transmission de données : entrée, sortie, affectation et autres opérations [1]
2. Structure de contrôle de l'algorithme : La structure fonctionnelle d'un algorithme dépend non seulement des opérations sélectionnées, mais également de l'ordre d'exécution entre les opérations.

Classification

Les algorithmes peuvent être grossièrement divisés en algorithmes de base, algorithmes de structure de données, algorithmes de théorie des nombres et algorithmes algébriques, algorithmes de géométrie computationnelle, algorithmes de théorie des graphes, programmation dynamique et analyse numérique, algorithmes de cryptage, tri algorithme, algorithme de récupération, algorithme de randomisation, algorithme parallèle, modèle de déformation hermitien, algorithme de forêt aléatoire.
Les algorithmes peuvent être globalement divisés en trois catégories :
1. Algorithmes limités et déterministes Ce type d'algorithme se termine dans une période de temps limitée. Ils peuvent prendre beaucoup de temps pour accomplir une tâche spécifiée, mais ils se termineront néanmoins dans un certain laps de temps. Les résultats de ces algorithmes dépendent souvent des valeurs d'entrée.
　　2. Algorithme fini et non déterministe Ce type d'algorithme se termine dans un temps limité. Cependant, pour une ou plusieurs valeurs données, le résultat de l’algorithme n’est ni unique ni certain.
　Trois algorithmes infinis sont les algorithmes qui ne se terminent pas parce que les conditions de définition de terminaison ne sont pas définies ou que les conditions définies ne peuvent pas être satisfaites par les données d'entrée. Souvent, des algorithmes infinis apparaissent en raison d’un échec dans la définition des conditions de terminaison.

Réserves de base de la théorie des nombres

Reste quadratique

Regardons d’abord la formule x2≡n(modp). Nous donnons maintenant n et demandons de trouver la valeur de x. Si on peut le trouver, n est le reste quadratique de mod p, qui est en fait le carré ultime de n au sens de mod p. Cipolla est un algorithme utilisé pour trouver x dans la formule ci-dessus.

Symbole Legendre

Le symbole Legendre est un outil puissant pour déterminer si un nombre est le reste quadratique de p doit être un nombre premier impair. (n,p) signifie que n est le symbole de Legendre par rapport à p. En fait, il s’agit de déterminer si n est le reste quadratique de p.

(np)=⎧⎩⎨1——p n'est pas un multiple de n, n est le reste quadratique de p−1——p n'est pas un multiple de n, n est le reste quadratique non-résidu de p (soit reste quadratique, soit non-résidu) 0——p est un multiple de n

Cela ressemble à beaucoup d'absurdités, Legendre est juste debout sur les épaules des géants Je viens de le résumer ci-dessus.
En fait, Legendre a également résumé certaines propriétés, mais généralement seul le critère d'Euler est utilisé, et cela peut être utile si le symbole de Legendre est une fonction produit.
Mais je ne sais toujours pas comment juger si n est le reste quadratique de p. Regardons le critère d'Euler

ll Legendre(ll a, ll p)
{
return qsm( a, (p-1)/2, p);
} 12341234

Critère d'Euler

Revoyons d'abord le théorème d'Euler xφ(p)≡1 (modp)
Parce que p ici est un nombre premier impair, donc xp−1≡1(modp)
Effectuez l'opération racine carrée sur xp−1, dans le champ des nombres imaginaires xp−12≡±1(modp ), s'il est égal à 1, il sera définitivement ouvert, et s'il est -1, il ne sera définitivement pas ouvert. Par conséquent, savoir si x est le reste quadratique de n utilise ce critère d'Euler.

if(qsm(n,(p-1)/2)==p-1){ printf("Pas de racine");
continuer
}12341234

-1 est p-1 au sens du mod p.

Flux d'algorithme

Étant donné n et p
Même si le signe de Legendre de n par rapport à p est 1, comment prend-on la racine carrée de n ?
Il est maintenant temps d’ouvrir votre esprit.

Trouver un nombre a

Nous attribuons au hasard un nombre a, puis effectuons l'opération racine carrée sur a2−n (c'est-à-dire calculons la valeur de son symbole Legendre) jusqu'à ce que leur symbole Legendre Jusqu'à -1 (c'est-à-dire jusqu'à ce que le carré ne puisse plus être ouvert).
Il s’agit de trouver un a qui satisfait (a2−n)p−12=−1
Ne vous inquiétez pas du pourquoi pour l’instant, nous en reparlerons plus tard, nous adorons maintenant en silence la grande imagination de Cipolla.

while(1){
a=rand()%p;
w=(a*a-n+p)%p; /2)==p-1)break;
}1234512345

Parce que nous recherchons un au hasard, est-ce que cela prendra beaucoup de temps pour le trouver ?
Réponse : Non !
∙Théorème 1 : Il y a p−12 n dans x2≡n(modp) pour que l'équation ait une solution
⇒Démontrer le théorème 1 : x2≡n(modp), s'il y a des nombres différents u, v , de sorte qu'après avoir introduit x, l'équation peut être résolue, alors il est évident que u2−v2|p est satisfait, donc (u+v)(u−v)|p est satisfait, car
u2− v2|p donc p ne peut pas être un multiple de (u-v), donc (u+v)|p, alors le nombre de telles paires de nombres existant dans p est p−12
D'après le théorème 1, l'attente de trouver aléatoirement a vaut 2.

Créer un champ pluriel

On dit qu'il est créé, mais en fait, il n'est pas du tout nécessaire de le programmer. On dit que c'est un champ pluriel juste pour la commodité de. compréhension.
Dans le domaine des nombres complexes communément appris, il existe un i qui satisfait i2=−1.
Nous créons également un domaine similaire, car nous devons prendre la racine carrée de a2−n, et a2−n a un reste quadratique qui n'est pas p, nous définissons donc ω=a2−n−−−−−√ . Alors le courant ω, comme i, satisfait ω2=a2−n, nous définissons donc un nouveau domaine.

struct CN{
ll x,y;
Opérateur ami CN *(CN x,CN y){
CN z;
z.x=(x.x*y.x%p+ x.y *y.y%p*w%p)%p;
z.y=(x.x*y.y%p+x.y*y.x%p)%p;


Nous définissons les opérateurs comme opérations normales sur les nombres complexes. Vous pouvez trouver ce z. La représentation dans ce domaine est similaire à un nombre complexe normal : a+bω

La réponse est

Nous demandons x2≡n(modp), la valeur de x

Nous sachez maintenant Après avoir connu a et ω, vous pouvez obtenir la réponse.

Réponse = (a+ω)p+12
Vraiment ? réel! Mais cette réponse ne consiste-t-elle pas en des nombres réels et imaginaires ?
Selon le théorème de Lagrange, on peut conclure que le coefficient du nombre imaginaire doit être 0.

CN Cqsm(CN x,ll y){\puissance rapide des nombres complexes CN z;z.x=1,z.y=0;\note initialisation while(y){ if(y&1)z=z*x;
x=x*x;
y/=2;
} return z;
}123456789123456789
w=(a*a-n+p)%p;
u.x=a , u.y=1;//Pourquoi u.y vaut 1 - utilisez simplement des coefficients statistiques dans les statistiques de nombres complexes
u=Cqsm(u,(p+1)/2);
ll yi=u.x, er=p-u. x; if(yi>er)swap(yi,er); if(yi==er){ printf("%lldn",yi);
} else{ printf("%lld %lldn ",yi, euh);
}12345678910111234567891011

Pourquoi y a-t-il deux réponses, telles que 4√=±2, x2≡(p−x)2(modp)Évidemment, car Diviser la partie arrière en x2≡x2−2px+p2(modp) et supprimez tous les p, donc x2≡(p−x)2(modp).

Démontrez le principe

Et puis proposez quelques théorèmes pour une explication facile.

Théorème

∙Théorème 2 : (a+b)p≡ap+bp(modp)
⇒Démontrer le théorème 2 : D'après le théorème du binôme :
(a+ b )p≡∑pi=0Cipap−ibi(modp)
≡∑pi=0p!(p−i)!i!ap−ibi(modp)
On peut trouver que seulement lorsque i=0 ou i = Lorsque p, la formule n'a pas p facteurs, donc tous les facteurs avec p au milieu peuvent être omis, donc (a+b)p≡ap+bp(modp)
∙Théorème 3 : ωp≡−ω( modp)
⇒ Démontrer le théorème 3 : ωp
=ωp−1∗ω
=(ω2)p−12∗ω
=(a2−n)p−12∗ω—car ω2= a2− n
=−ω——Parce que (a2−n)p−12=−1
∙Théorème 4 : ap≡a(modp)
⇒Démontrer le théorème 3 : ap selon le petit théorème de Fermat
≡ap−1≡1(modp)
Donc ap≡a∗ap−1≡a(modp)

Dérivation

Problème : x2≡n(modp) résoudre pour x
Cipolla : Le nombre réel de x≡(a+ω)p+12(modp)
Convertir directement la formule :
(a+ω)p+12(modp)
≡ ((a +ω)p+1)12(modp)
≡((a+ω)p(a+ω))12(modp)
≡((ap+ωp)(a+ω) )12( modp) D'après le théorème 2
≡((a−ω)(a+ω))12(modp) D'après le théorème 3 et le théorème 4
≡(a2−ω2)12(modp) D'après le théorème 3 et le théorème 4
≡(a2−ω2)12(modp) D'après au Théorème 3 et Théorème 4
≡(a2−(a2−n))12(modp) satisfait ω2=a2−n
≡n12(modp)
Donc (a+ω)p+12≡ n12≡n√(modp )

C'est tellement imaginatif ! ! ! ! ! ! ! ! ! ! ! ! ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!