컴퓨터 프로그램의 알고리즘에 관한 참고 사항

컴퓨터 프로그래밍이란 무엇인가요?

　 간단히 말해서 컴퓨터에게 무엇을 해야 할지 알려줍니다. 컴퓨터는 많은 일을 할 수 있지만 스스로 생각하는 데에는 능숙하지 않습니다. 프로그래머는 아이에게 먹이를 주는 것과 같은 구체적인 세부 사항을 알려주고 컴퓨터가 언어 알고리즘을 이해하도록 해야 합니다.

　알고리즘은 문제 해결 솔루션에 대한 정확하고 완전한 설명을 의미합니다. 문제 해결을 위한 일련의 명확한 지침입니다. 알고리즘은 문제 해결을 위한 전략적 메커니즘을 설명하는 체계적인 방법을 나타냅니다. 즉, 특정 입력 사양에 대해 제한된 시간 내에 필요한 출력을 얻는 것이 가능합니다. 알고리즘에 결함이 있거나 문제에 적합하지 않은 경우 알고리즘을 실행해도 문제가 해결되지 않습니다. 서로 다른 알고리즘은 동일한 작업을 완료하기 위해 서로 다른 시간, 공간 또는 효율성을 사용할 수 있습니다. 알고리즘의 품질은 공간 복잡도와 시간 복잡도로 측정할 수 있습니다.
　알고리즘의 지침은 실행 시 초기 상태와 (비어 있을 수도 있는) 초기 입력에서 시작하여 제한적이고 명확하게 정의된 일련의 상태를 거쳐 최종적으로 출력을 생성하고 최종에서 중지할 수 있는 계산을 설명합니다. 상태. . 한 상태에서 다른 상태로의 전환이 반드시 결정적일 필요는 없습니다. 무작위 알고리즘을 포함한 일부 알고리즘에는 무작위 입력이 포함되어 있습니다.
　형식 알고리즘의 개념은 부분적으로 힐베르트의 결정 문제를 해결하려는 시도에서 유래했으며 효율적인 계산 가능성 또는 효율적인 방법을 정의하려는 후속 시도에서 구체화되었습니다. 이러한 시도에는 각각 1930년, 1934년, 1935년에 Kurt Gödel, Jacques Herbrand 및 Stephen Cole Crane이 제안한 재귀 함수, 1936년 Alonzo Church가 제안한 람다 미적분학, 1936년 Emil Leon Post의 공식 1 및 Alan Turing의 Turing Machine이 포함되었습니다. 1937. 오늘날에도 직관적인 아이디어를 형식적인 알고리즘으로 정의하기 어려운 경우가 종종 있습니다.

특징

　알고리즘은 다음과 같은 다섯 가지 중요한 특성을 가져야 합니다:
　1. 유한성
　알고리즘의 유한성은 알고리즘이 제한된 수의 단계를 실행한 후에 종료될 수 있어야 함을 의미합니다.
　2. 정확성(정확성)
알고리즘의 각 단계에는 정확한 정의가 있어야 합니다;
　3. 입력(Input)
　알고리즘에는 작업 개체의 초기 상황을 설명하기 위한 0개 이상의 입력이 있습니다. 소위 0개의 입력은 알고리즘 자체의 정의를 나타냅니다. 4. 출력(Output) 알고리즘은 입력 데이터를 처리한 결과를 반영하기 위해 하나 이상의 출력을 갖습니다. 출력이 없는 알고리즘은 의미가 없습니다. 5. 타당성(효과성) 알고리즘에서 수행되는 모든 계산 단계는 실행 가능한 기본 작업 단계로 분해될 수 있습니다. 즉, 각 계산 단계는 제한된 시간 내에 수행될 수 있습니다. 내부 완료(타당성이라고도 함).

Elements

　 1. 데이터 객체의 작동 및 작동: 컴퓨터가 수행할 수 있는 기본 작업이 명령어 형식으로 설명됩니다. 컴퓨터 시스템이 실행할 수 있는 모든 명령의 집합이 컴퓨터 시스템의 명령 시스템이 됩니다. 컴퓨터의 기본 계산 및 연산은 다음과 같습니다. 1. 산술 연산: 덧셈, 뺄셈, 곱셈, 나눗셈 등 2. 논리 연산: OR, AND, NOT 등의 연산 3. 관계 연산: 보다 큼 , 작음, 같음, 같지 않음 4. 데이터 전송: 입력, 출력, 할당 및 기타 작업 [1] 2. 알고리즘 제어 구조: 알고리즘의 기능적 구조는 선택한 작업에 따라 달라질 뿐만 아니라 작업 간의 실행 순서와 관련됩니다.

분류

알고리즘은 크게 기본 알고리즘, 자료 구조 알고리즘, 정수론 및 대수학 알고리즘, 계산 기하학 알고리즘, 그래프 이론 알고리즘, 동적 프로그래밍 및 수치 분석, 암호화 알고리즘, 정렬 알고리즘, 검색 알고리즘, 무작위화 알고리즘으로 나눌 수 있습니다. , 병렬 알고리즘, Hermitian 변형 모델, Random Forest 알고리즘.
　 알고리즘은 크게 세 가지 범주로 나눌 수 있습니다.
　 1. 제한적이고 결정적인 알고리즘 이 유형의 알고리즘은 제한된 기간 내에 종료됩니다. 지정된 작업을 수행하는 데 오랜 시간이 걸릴 수 있지만 여전히 특정 시간 내에 종료됩니다. 이러한 알고리즘의 결과는 입력 값에 따라 달라지는 경우가 많습니다.
　　2. 유한, 비결정적 알고리즘 이 유형의 알고리즘은 제한된 시간 내에 종료됩니다. 그러나 주어진 값(또는 값들)에 대해 알고리즘의 결과는 고유하거나 확실하지 않습니다.
　　셋, 무한 알고리즘은 종료 정의 조건이 정의되지 않았거나 정의된 조건을 입력 데이터가 만족할 수 없어 종료되지 않는 알고리즘입니다. 종료 조건을 정의하지 못하여 무한 알고리즘이 발생하는 경우가 많습니다.

기본 정수론 예비

2차 나머지

먼저 x2=n(modp) 공식을 살펴보겠습니다. 이제 n을 제공하고 x의 값을 구하도록 요청합니다. 만약 찾을 수 있다면, n은 mod p의 2차 나머지이고, 이는 실제로 mod p의 의미에서 n의 최종 제곱입니다. Cipolla는 위 방정식에서 x를 찾는 데 사용되는 알고리즘입니다.

Legendre 기호

Legendre 기호는 숫자가 p의 2차 나머지인지 확인하는 강력한 도구입니다. p는 홀수 소수여야 합니다. (n,p)는 n이 p에 대한 르장드르 기호임을 의미합니다. 실제로 n이 p의 2차 나머지인지 여부를 확인하는 것입니다.

(np)=⎧⎩⎨1——p는 n의 배수가 아니며, n은 p−1의 2차 나머지입니다.——p는 n의 배수가 아니며, n은 p의 2차 비잔차입니다( 2차 나머지 또는 비잔차) 0——p는 n

의 배수입니다. 말도 안되는 소리가 많은 것 같습니다. Legendre는 거인의 어깨 위에 서서 이를 요약했습니다.
사실 르장드르에서도 일부 속성을 정리했지만 일반적으로 오일러 기준만 사용하며, 르장드르 기호가 제품 기능인 경우 유용할 수 있습니다.
하지만 n이 p의 2차 나머지인지 어떻게 판단할지 모르겠습니다. 아래 오일러의 기준을 살펴보겠습니다.

ll Legendre(ll a, ll p)
{
                                                                                                  p)
} 12341234

Euler's; criterion

먼저 오일러의 정리를 복습해 봅시다. 허수장, xp−12ל±1 (modp), 1과 같으면 제곱근은 확실히 풀리고, -1이면 절대 풀리지 않습니다. 따라서 x가 n의 2차 나머지인지 여부는 이 오일러 기준을 사용합니다.

if(qsm(n,(p-1)/2)==p-1){ printf("No rootn");

continue;

}12341234


-1은 모드 의미에서 p-입니다. p 1.

알고리즘 흐름

n과 p가 주어졌을 때

p에 대한 n의 르장드르 부호가 1인 경우에도 n의 제곱근은 어떻게 구할 수 있나요?

이제 마음을 열어야 할 때입니다.

숫자 a 찾기

숫자 a를 무작위로 선택한 다음 르장드르 기호가 -1이 될 때까지 a2−n에 대한 제곱근 연산을 수행합니다(즉, 르장드르 기호의 값을 계산합니다). 해결) 현재까지).

(a2−n)p−12=−1을 만족하는 a를 찾으세요.

왜 지금은 걱정하지 마세요. 이에 대해서는 나중에 이야기하고 지금은 조용히 Cipolla를 숭배하겠습니다.

while(1){

a=rand()%p;

w=(a*a-n+p)%p; if(qsm(w,(p-1)/2)==p-1 )break;
}1234512345


랜덤으로 찾기 때문에 검색하는데 시간이 오래 걸리나요?

답변: 아니요!

∙정리 1: x2=n(modp)에는 p−12 n이 있으므로 방정식에 해가 있습니다.
⇒정리 1: x2=n(modp)을 증명하고, 서로 다른 숫자 u, v가 있으면 이를 로 가져옵니다. x 마지막으로 방정식을 풀 수 있습니다. 그러면 u2−v2|p가 만족된다는 것이 명백하므로 (u+v)(u−v)|p가 만족됩니다. 왜냐하면
u2−v2|p이므로 p는 a가 될 수 없기 때문입니다. (u-v)의 배수이므로 (u+v)|p이므로 p에 존재하는 이러한 숫자 쌍의 수는 p−12입니다.
정리 1에 따르면 무작위로 a를 찾을 것으로 예상되는 값은 2입니다.

복수 필드 만들기

생성된다고는 하지만 실제로는 이해의 편의를 위해 전혀 프로그래밍할 필요가 없다고 합니다.

우리가 흔히 학습하는 복소수 필드에는 i2=−1을 만족하는 i가 있습니다.

또한 a2−n의 제곱근을 구해야 하고 a2−n에는 p가 아닌 2차 나머지가 있으므로 비슷한 정의역을 만듭니다. 따라서 Ω=a2−n−−−−−−√를 정의합니다. 그러면 이제 i와 마찬가지로 Ω도 Ω2=a2−n을 만족하므로 새로운 도메인을 정의합니다.

struct CN{

ll x,y;

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;             return z; z를 찾을 수 있습니다. 이 영역의 표현은 일반 복소수와 유사합니다. a+bΩ

답을 구하세요

우리에게 필요한 것은 x의 값인 x2=n(modp)입니다.
이제 a와 Ω를 알았으니 다음을 얻을 수 있습니다. 대답은 다음과 같습니다.

답변 = (a+Ω)p+12

정말요? 진짜! 그런데 이 답은 실수와 허수로 구성되어 있지 않나요?

라그랑주의 정리에 따르면 허수의 계수는 0이어야 한다는 결론을 내릴 수 있습니다.

(CN CQSM (CN X, LL Y) {\ 보라색 고속 전력 CN Z; z.x = 1, z.y = 0; \ while (y) {if (y & 1) z*x;

x 초기화에 주의하세요 = x* x;
y/=2;
} return z;
}123456789123456789
w=(a*a-n+p)%p;
u.x=a,u.y=1;//u.y가 1인 이유— —복소수 통계에서는 통계 계수를 사용하세요
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

왜 답이 2개인가요? 예를 들어, 4√=±2, x2=(p-x)2(modp)는 x2=x2-2px+p2(modp)가 분리되고 모든 p가 제거되므로 x2=(p-x)가 분명합니다. 2(모드).

원리를 증명

하고 쉽게 설명할 수 있는 정리를 생각해 보세요.

정리

∙정리 2: (a+b)p=ap+bp(modp)

⇒증명 정리 2: 이항 정리에 따르면:
(a+b)p=∑pi=0Cipap−ibi(modp )
∑pi=0p!(p−i)!i!ap−ibi(modp)
i=0 또는 i=p인 경우에만 공식에 p의 인수가 없다는 것을 알 수 있습니다. 중간에 있는 p의 인수는 생략될 수 있으므로 (a+b)p=ap+bp(modp)
∙정리 3: Ωp=−Ω(modp)
⇒증명 정리 3: wop
=Ωp−1 ****Ω
=(Ω2) p−12*Ω
=(a2−n)p−12*Ω——왜냐하면 Ω2=a2−n
=−Ω——(a2−n)p−12=를 만족하기 때문입니다 −1
∙정리 4: ap ña(modp)
⇒ 정리 3 증명: 페르마의 작은 정리에 따른 ap
=ap−1=1(modp)
그래서 ap=a*ap−1=a(modp)

Derivation

문제: x2=n(modp)는 x를 구합니다.

Cipolla: x=(a+ω)p+12(modp)의 실수
공식을 직접 변환:
(a+Ω)p+12 (modp)
EMA((a+Ω)p+1)12(modp)
EMA((a+Ω)p(a+Ω))12(modp)
EMA((ap+Ωp)(a+Ω ))12(modp) 정리 2에 따름
zzo((a−Ω)(a+ω))12(modp)정리 3 및 정리 4에 따름
ל(a2−Ω2)12(modp)정리 3에 따름 정리 4
=(a2−(a2−n) )12(modp)는 Ω2=a2−n
=n12(modp)
그래서 (a+Ω)p+12=n12=n√(modp)
This를 충족합니다. 상상력이 너무 과하다! ! ! ! ! ! ! ! ! ! ! ! ! !

위 내용은 컴퓨터 프로그램의 알고리즘에 관한 참고 사항의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!