Eine kurze Anmerkung zu Algorithmen für Computerprogramme

Was ist Computerprogrammierung?

Einfach ausgedrückt sagt es dem Computer, was er tun soll. Computer können viele Dinge tun, aber sie sind nicht sehr gut darin, selbst zu denken. Programmierer müssen ihm bestimmte Details mitteilen, beispielsweise das Füttern eines Kindes, und den Computer dazu bringen, den Sprachalgorithmus zu verstehen.

Algorithmus bezieht sich auf eine genaue und vollständige Beschreibung einer Problemlösung. Es handelt sich um eine Reihe klarer Anweisungen zur Lösung von Problemen. Mit anderen Worten: Es ist möglich, für bestimmte standardisierte Inputs innerhalb einer begrenzten Zeit den erforderlichen Output zu erhalten. Wenn ein Algorithmus fehlerhaft oder für ein Problem ungeeignet ist, wird die Ausführung des Algorithmus das Problem nicht lösen. Verschiedene Algorithmen können unterschiedliche Zeit, Raum oder Effizienz nutzen, um dieselbe Aufgabe zu erledigen. Die Qualität eines Algorithmus kann an seiner räumlichen und zeitlichen Komplexität gemessen werden.
Die Anweisungen im Algorithmus beschreiben eine Berechnung, die bei ihrer Ausführung von einem Anfangszustand und einer (möglicherweise leeren) Anfangseingabe ausgehen, eine begrenzte und klar definierte Reihe von Zuständen durchlaufen und schließlich eine Ausgabe erzeugen und bei dieser anhalten kann ein Endzustand. Der Übergang von einem Zustand in einen anderen ist nicht unbedingt deterministisch. Einige Algorithmen, einschließlich randomisierter Algorithmen, enthalten zufällige Eingaben.
Das Konzept der formalen Algorithmen entstand teilweise aus Versuchen, Hilberts Entscheidungsprobleme zu lösen, und nahm in späteren Versuchen, effiziente Berechenbarkeit oder effiziente Methoden zu definieren, Gestalt an. Zu diesen Versuchen gehörten die rekursiven Funktionen, die 1930, 1934 und 1935 von Kurt Gödel, Jacques Herbrand und Stephen Cole Crane vorgeschlagen wurden, der 1936 von Alonzo Church vorgeschlagene Lambda-Kalkül, die Formel 1 von Emil Leon Post aus dem Jahr 1936 und die Turing-Maschine von Alan Turing 1937. Auch heute noch gibt es oft Fälle, in denen intuitive Ideen schwer als formale Algorithmen zu definieren sind.

Eigenschaften

Ein Algorithmus sollte die folgenden fünf wichtigen Eigenschaften haben:
1. Endlichkeit
Die Endlichkeit eines Algorithmus bedeutet, dass der Algorithmus in der Lage sein muss, Terminate nach einer Endlichkeit auszuführen Anzahl der Schritte;
2. Eindeutigkeit
Jeder Schritt des Algorithmus muss klar definiert sein
3. Eingabe
Ein Algorithmus hat 0 oder mehr. Eine Eingabe wird verwendet, um die Ausgangssituation der Operation zu beschreiben Die sogenannte 0-Eingabe bedeutet, dass der Algorithmus selbst die Anfangsbedingungen festlegt.
4. Ausgabe (Ausgabe)
Ein Algorithmus verfügt über eine oder mehrere Ausgaben, um das Ergebnis nach der Datenverarbeitung wiederzugeben. Ein Algorithmus ohne Ausgabe ist bedeutungslos.
5. Durchführbarkeit (Effektivität)
Jeder im Algorithmus ausgeführte Berechnungsschritt kann in grundlegende ausführbare Operationsschritte zerlegt werden, d. h. jeder Berechnungsschritt kann innerhalb einer begrenzten Zeit abgeschlossen werden ( auch Wirksamkeit genannt).

Elemente

1. Operationen und Operationen von Datenobjekten: Die grundlegenden Operationen, die ein Computer ausführen kann, werden in Form von Anweisungen beschrieben. Der Satz aller Anweisungen, die ein Computersystem ausführen kann, wird zum Befehlssystem des Computersystems. Die grundlegenden Berechnungen und Operationen eines Computers sind wie folgt:
1. Arithmetische Operationen: Addition, Subtraktion, Multiplikation und Division usw.
2. Logische Operationen: Operationen wie ODER, UND, NICHT usw.
3. Relationale Operationen: größer als, Operationen wie kleiner als, gleich und ungleich
4. Datenübertragung: Eingabe, Ausgabe, Zuweisung und andere Operationen [1]
2. Kontrollstruktur von Der Algorithmus: Die funktionale Struktur eines Algorithmus hängt nicht nur von den ausgewählten Operationen ab, sondern auch von der Ausführungsreihenfolge zwischen den Operationen.

Klassifizierung

Algorithmen können grob in grundlegende Algorithmen, Datenstrukturalgorithmen, Zahlentheorie und algebraische Algorithmen, rechnerische Geometriealgorithmen, Graphentheoriealgorithmen, dynamische Programmierung und numerische Analyse, Verschlüsselungsalgorithmen und Sortierung unterteilt werden Algorithmus, Abrufalgorithmus, Randomisierungsalgorithmus, Parallelalgorithmus, hermitisches Deformationsmodell, Random-Forest-Algorithmus.
Algorithmen können grob in drei Kategorien unterteilt werden:
1. Begrenzte, deterministische Algorithmen Diese Art von Algorithmus endet innerhalb eines begrenzten Zeitraums. Die Ausführung einer bestimmten Aufgabe kann lange dauern, wird aber dennoch innerhalb einer bestimmten Zeitspanne beendet. Die Ergebnisse solcher Algorithmen hängen oft von den Eingabewerten ab.
　　2. Endlicher, nicht deterministischer Algorithmus Dieser Algorithmustyp endet in einer begrenzten Zeit. Für einen bestimmten Wert (oder mehrere Werte) ist das Ergebnis des Algorithmus jedoch nicht eindeutig oder sicher.
　Drei unendliche Algorithmen sind solche Algorithmen, die nicht terminieren, weil die Terminierungsdefinitionsbedingungen nicht definiert sind oder die definierten Bedingungen durch die Eingabedaten nicht erfüllt werden können. Oftmals entstehen unendliche Algorithmen, weil die Beendigungsbedingungen nicht definiert wurden.

Grundlegende Reserven der Zahlentheorie

Quadratischer Rest

Schauen wir uns zunächst die Formel x2≡n(modp) an. Wir geben nun n an und bitten darum, den Wert von x zu ermitteln. Wenn es gefunden werden kann, ist n der quadratische Rest von mod p, der tatsächlich das ultimative Quadrat von n im Sinne von mod p ist. Cipolla ist ein Algorithmus, der verwendet wird, um x in der obigen Formel zu finden.

Legendre-Symbol

Das Legendre-Symbol ist ein leistungsstarkes Werkzeug, um zu bestimmen, ob eine Zahl der quadratische Rest von p sein muss. (n,p) bedeutet, dass n das Legendre-Symbol in Bezug auf p ist. Tatsächlich geht es darum, zu bestimmen, ob n der quadratische Rest von p ist.

(np)=⎧⎩⎨1——p ist kein Vielfaches von n, n ist der quadratische Rest von p−1——p ist kein Vielfaches von n, n ist das Quadrat Nicht-Rest von p (entweder quadratischer Rest oder Nicht-Rest) 0——p ist ein Vielfaches von n

Es scheint eine Menge Unsinn zu sein, Legendre steht einfach da auf den Schultern von Giganten Habe es oben gerade zusammengefasst.
Tatsächlich hat Legendre auch einige Eigenschaften zusammengefasst, aber im Allgemeinen wird nur das Euler-Kriterium verwendet, und es kann nützlich sein, wenn das Legendre-Symbol eine Produktfunktion ist.
Aber ich weiß immer noch nicht, wie ich beurteilen soll, ob n der quadratische Rest von p ist. Schauen wir uns das Euler-Kriterium an

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

Eulers Kriterium

Betrachten wir zunächst den Satz von Euler xφ(p)≡1 (modp)
Da p hier eine ungerade Primzahl ist, also xp−1≡1(modp)
Führe die Quadratwurzeloperation für xp−1 im imaginären Zahlenfeld xp−12≡±1(modp aus ), wenn es gleich 1 ist, wird es definitiv geöffnet, und wenn es -1 ist, wird es definitiv nicht geöffnet. Daher wird für die Frage, ob x der quadratische Rest von n ist, dieses Euler-Kriterium verwendet.

if(qsm(n,(p-1)/2)==p-1){
continue
}12341234

-1 ist p-1 im Sinne von mod p.

Algorithmusablauf

Gegeben n und p
Auch wenn das Legendre-Zeichen von n in Bezug auf p 1 ist, wie ziehen wir die Quadratwurzel von n?
Jetzt ist es an der Zeit, Ihren Geist zu öffnen.

Finden Sie eine Zahl a

Wir weisen zufällig eine Zahl a zu und führen dann die Quadratwurzeloperation für a2−n durch (d. h. berechnen den Wert ihres Legendre-Symbols), bis ihr Legendre-Symbol vorliegt Bis es -1 ist (d. h. bis das Quadrat nicht geöffnet werden kann).
Es geht darum, ein a zu finden, das (a2−n)p−12=−1 erfüllt.
Mach dir vorerst keine Sorgen darüber, warum, wir werden später darüber reden, wir werden Cipolla jetzt im Stillen verehren.

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

Weil wir nach dem Zufallsprinzip suchen, wird es lange dauern, es zu finden?
Antwort: Nein!
∙Satz 1: Es gibt p−12 n in x2≡n(modp), so dass die Gleichung eine Lösung hat
⇒Beweisen Sie Satz 1: x2≡n(modp), wenn es verschiedene Zahlen u, v gibt , so dass Nachdem sie x eingebracht haben, kann die Gleichung gelöst werden, dann ist es offensichtlich, dass u2−v2|p erfüllt ist, also ist (u+v)(u−v)|p erfüllt, weil
u2− v2|p also p kann nicht sein Ein Vielfaches von (u-v), also (u+v)|p, dann ist die Anzahl solcher in p vorhandenen Zahlenpaare p−12
Gemäß Satz 1 ist die Erwartung, zufällig zu finden a ist 2.

Erstellen Sie ein Pluralfeld

Es soll erstellt werden, aber tatsächlich besteht überhaupt keine Notwendigkeit, es zu programmieren. Es wird nur aus Bequemlichkeitsgründen als Pluralfeld bezeichnet Verständnis.
Im allgemein erlernten Bereich komplexer Zahlen gibt es ein i, das i2=−1 erfüllt.
Wir erstellen auch einen ähnlichen Bereich, weil wir die Quadratwurzel von a2−n ziehen wollen und a2−n einen quadratischen Rest hat, der nicht p ist, also definieren wir ω=a2−n−−−−−√ . Dann erfüllt das aktuelle ω, wie i, ω2=a2−n, also definieren wir einen neuen Bereich.

struct CN{
ll x,y;
CN Friend Operator *(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


Wir definieren Operatoren wie folgt normale komplexe Zahlenoperationen. Das findet man z. Die Darstellung in diesem Bereich ähnelt einer normalen komplexen Zahl: a+bω

Die Antwort ist

Wir fragen nach x2≡n(modp), dem Wert von x

We Jetzt wissen Nachdem Sie a und ω kennen, können Sie die Antwort erhalten.

Antwort = (a+ω)p+12
Wirklich? real! Aber besteht diese Antwort nicht aus realen und imaginären Zahlen?
Nach dem Satz von Lagrange kann man schlussfolgern, dass der Koeffizient der imaginären Zahl 0 sein muss.

CN Cqsm(CN x,ll y){\schnelle Potenz komplexer Zahlen CN z;z.x=1,z.y=0;\note initialization 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;//Warum u.y 1 ist – verwenden Sie einfach statistische Koeffizienten in der Statistik komplexer Zahlen
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, er);
}12345678910111234567891011

Warum gibt es zwei Antworten, wie zum Beispiel 4√=±2, x2≡(p−x)2(modp)Offensichtlich, weil Teilen Sie den hinteren Teil in x2≡x2−2px+p2(modp) und entferne alle p, also x2≡(p−x)2(modp).

Beweisen Sie das Prinzip

Und überlegen Sie sich dann einige Theoreme zur einfachen Erklärung.

Satz

∙Satz 2: (a+b)p≡ap+bp(modp)
⇒Beweisen Sie Satz 2: Nach dem Binomialsatz:
(a+ b )p≡∑pi=0Cipap−ibi(modp)
≡∑pi=0p!(p−i)!i!ap−ibi(modp)
Es kann nur gefunden werden, wenn i=0 oder i = Wenn p, hat die Formel keine p Faktoren, daher können alle Faktoren mit p in der Mitte weggelassen werden, also (a+b)p≡ap+bp(modp)
∙Theorem 3: ωp≡−ω( modp)
⇒ Beweisen Sie Satz 3: ωp
=ωp−1∗ω
=(ω2)p−12∗ω
=(a2−n)p−12∗ω – denn ω2= a2− n
=−ω——Weil (a2−n)p−12=−1
∙Satz 4: ap≡a(modp)
⇒Beweisen Sie Satz 3: ap gemäß dem kleinen Satz von Fermat
≡ap−1≡1(modp)
Also ap≡a∗ap−1≡a(modp)

Ableitung

Problem: x2≡n(modp) lösen für x
Cipolla: Die reelle Zahl von x≡(a+ω)p+12(modp)
Konvertieren Sie die Formel direkt:
(a+ω)p+12(modp)
≡ ((a +ω)p+1)12(modp)
≡((a+ω)p(a+ω))12(modp)
≡((ap+ωp)(a+ω) )12( modp) Gemäß Satz 2
≡((a−ω)(a+ω))12(modp) Gemäß Satz 3 und Satz 4
≡(a2−ω2)12(modp) Gemäß zu Satz 3 und Satz 4
≡(a2−(a2−n))12(modp) erfüllt ω2=a2−n
≡n12(modp)
Also (a+ω)p+12≡ n12≡n√(modp )
Das ist so einfallsreich! ! ! ! ! ! ! ! ! ! ! ! ! !

Das obige ist der detaillierte Inhalt vonEine kurze Anmerkung zu Algorithmen für Computerprogramme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!