컴퓨터 대수학

이 기사의 리드 섹션에는 기사의 다른 부분에 포함되지 않은 정보가 포함되어 있습니다. 만약 그 정보가 기사의 선두에 적합하다면, 이 정보는 기사 본문에도 포함되어야 합니다.(2020년 5월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학과 컴퓨터 ^[1]과학에서 기호 계산 또는 대수 계산이라고도 불리는 컴퓨터 대수는 수학적 표현과 다른 수학적 대상을 조작하기 위한 알고리즘과 소프트웨어의 연구와 개발을 의미하는 과학적 영역입니다.컴퓨터 대수는 과학적 컴퓨팅의 하위 분야로 여겨질 수 있지만, 과학적 컴퓨팅은 대개 대략적인 부동 소수점 숫자를 가진 수치 계산에 기초하기 때문에 일반적으로 별개의 분야로 여겨집니다.기호 계산은 주어진 값이 없고 기호로 조작되는 변수를 포함하는 표현으로 정확한 계산을 강조합니다.

기호 계산을 수행하는 소프트웨어 응용 프로그램은 컴퓨터 대수 시스템이라고 불리는데, 시스템이라는 용어는 적어도 컴퓨터에서 수학적 데이터를 표현하는 방법, (보통 구현에 사용되는 언어와는 다른) 사용자 프로그래밍 언어, 전용 언어를 포함하는 주요 응용 프로그램의 복잡성을 암시합니다.ed memory manager, 수학식의 입력/출력을 위한 사용자 인터페이스, 식의 단순화, 연쇄 규칙을 사용한 차별화, 다항식 인수분해, 부정적 적분 등과 같은 통상적인 연산을 수행하기 위한 많은 루틴 세트.

컴퓨터 대수학은 수학에서 실험을 하고 수치 프로그램에서 사용되는 공식을 설계하는 데 널리 사용됩니다.또한 공개 키 암호법에서와 같이 순수 수치적 방법이 실패하거나 일부 비선형 문제에 대해서도 완전한 과학적 계산에 사용됩니다.

용어.

어떤 저자들은 수학 공식을 가진 계산 이외의 다른 종류의 기호 계산을 지칭하기 위해 후자의 이름을 사용하여 컴퓨터 대수와 기호 계산을 구별합니다.어떤 저자들은 수학적인 ^[2]면에서 "컴퓨터 대수"와 같은 수학적인 면에서 상징적인 계산을 사용합니다.일부 언어에서 필드 이름은 영어 이름을 직접 번역하지 않습니다.일반적으로, 그것은 "형식적인 계산"을 의미하는 프랑스어로 Calcul formel이라고 불립니다.이 이름은 이 필드가 형식적 메서드와 갖는 관계를 나타냅니다.

기호연산은 과거에 기호조작, 대수조작, 기호처리, 기호수학, 기호대수 등으로 불리기도 하였으나, 비계산조작을 지칭하기도 하는 이 용어들은 컴퓨터 대수학에서 더 이상 사용되지 않습니다.

과학계

컴퓨터 대수학에 특화된 학문적 사회는 존재하지 않지만, SIGSAM(Symbolic and Agebric ^[3]Manipulation에 관한 특별 관심 그룹)이라는 컴퓨팅 기계 협회의 특별 관심 그룹이 이 함수를 상정하고 있습니다.

SIGSAM이 정기적으로 후원하는 ISSAC(^[4]International Symposium on Symbol and Agebric Computation)를 비롯하여 컴퓨터 대수에 관한 여러 연례 회의가 있습니다.

컴퓨터 대수학을 전문으로 하는 저널들이 여러 개 있는데, 가장 높은 저널은 1985년 Bruno Buchberger에 ^[5]의해 설립된 Journal of Symbol Computation입니다.컴퓨터 ^[6]대수학 논문을 정기적으로 발표하는 다른 저널도 몇 개 있습니다.

컴퓨터과학적 측면

이 절에서는 출처를 언급하지 않습니다. 신뢰할 수 있는 자료에 인용문을 추가하여 이 부분을 개선하는 데 도움을 주시기 바랍니다. 출처가 밝혀지지 않은 자료에 이의를 제기하여 제거할 수 있습니다.(2012년 11월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

자료표시

수치 소프트웨어는 대략적인 수치 계산에 매우 효율적이기 때문에, 컴퓨터 대수학에서는 정확하게 표현된 데이터로 정확한 계산을 강조하는 것이 일반적입니다.이러한 정확한 표현은 출력의 크기가 작은 경우에도 계산 중에 생성된 중간 데이터가 예측할 수 없는 방식으로 증가할 수 있음을 의미합니다.이 행동을 표현 스웰이라고 합니다.이러한 문제를 방지하기 위해 데이터의 표현뿐만 아니라 이를 조작하는 알고리즘에서도 다양한 방법이 사용됩니다.

수

수치 계산에 사용되는 일반적인 숫자 시스템은 고정된 경계 크기의 부동 소수점 숫자와 정수입니다.이 중 어떤 것도 표현이 ^[7]팽윤하기 때문에 컴퓨터 대수학에 편리하지 않습니다.

따라서 컴퓨터 대수학에서 사용되는 기본 숫자는 수학자의 정수이며, 일반적으로 기계어가 허용하는 가장 큰 밑수인 어떤 숫자의 무한한 부호가 있는 순서로 표현됩니다.이 정수들은 두 정수의 줄일 수 없는 분수인 유리수를 정의할 수 있습니다.

산술 연산의 효율적인 구현을 프로그래밍하는 것은 어려운 작업입니다.따라서 대부분의 무료 컴퓨터 대수 시스템과 Mathematica나 Maple 같은 일부 상용 대수 시스템은 GMP 라이브러리를 사용하며, 이는 사실상의 표준입니다.

표현.

숫자와 변수를 제외한 모든 수학식은 연산자 기호로 볼 수 있으며, 그 뒤에 일련의 피연산자가 뒤따릅니다.컴퓨터 대수 소프트웨어에서 표현은 보통 이런 식으로 표현됩니다.이 표현은 매우 유연하고, 언뜻 수학적 표현이 아닌 것처럼 보이는 많은 것들이 그렇게 표현되고 조작될 수 있습니다.예를 들어, 방정식은 "="를 연산자로 하는 식이고, 행렬은 "matrix"를 연산자로, 행은 피연산자로 하는 식으로 나타낼 수 있습니다.

심지어 프로그램들도 연산자 "절차"와 적어도 두 개의 피연산자들, 즉 파라미터들의 리스트와 본체, 그 자체가 연산자로서 "몸"과 명령들의 시퀀스를 피연산자로서 갖는 표현으로 간주되고 표현될 수 있습니다.반대로, 어떤 수학적 표현도 프로그램으로 볼 수 있습니다.예를 들어 식 a + b는 a와 b를 매개 변수로 하여 덧셈을 위한 프로그램으로 볼 수 있습니다.이 프로그램을 실행하는 것은 a와 b의 주어진 값에 대한 식을 평가하는 것입니다. 만약 그들에게 주어진 값이 없다면, 평가의 결과는 단순히 그것의 입력입니다.

평가가 지연되는 이 과정은 컴퓨터 대수학에서 기본적인 것입니다.예를 들어, 방정식의 연산자 "="는 또한 대부분의 컴퓨터 대수 시스템에서 등식 테스트의 프로그램 이름입니다: 일반적으로 등식의 평가는 방정식으로 귀결되지만, 등식 테스트가 필요한 경우 "부울로 평가" 명령을 통해 사용자가 명시적으로 요청하거나 자동으로 시작됩니다.프로그램 내부의 테스트의 경우, 부울 결과에 대한 평가가 실행됩니다.

식의 피연산자의 크기는 예측할 수 없고 작업 세션 중에 변경될 수 있으므로 피연산자의 시퀀스는 일반적으로 (Macsyma에서와 같이) 포인터의 시퀀스 또는 (Maple에서와 같이) 해시 테이블의 엔트리의 시퀀스로 표시됩니다.

단순화

${\displaystyle x^{}}$ ${\$ a$^{x$$}}$ $식$에 x에 대한 기본 미분 규칙을 원시적으로 적용하면 결과가 나타납니다.

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}}\right)}$

이보다 더 간단한 표현이 일반적으로 바람직하며, 일반적인 표현을 사용할 때는 단순화가 필요합니다.

이러한 단순화는 일반적으로 다시 쓰기 ^[9]규칙을 통해 이루어집니다.몇 가지 클래스의 규칙 다시 쓰기를 고려해야 합니다.가장 간단한 것은 E - E → 0 또는 sin(0) → 0과 같이 항상 식의 크기를 줄이는 규칙입니다.그것들은 컴퓨터 대수 시스템에 체계적으로 적용됩니다.

덧셈과 곱셈과 같은 연관 연산에 어려움이 발생합니다.연관성을 다루는 표준적인 방법은 덧셈과 곱셈이 임의의 수의 피연산자를 갖는다는 것, 즉 a + b + c를 "+"(a, b, c)로 나타내는 것을 고려하는 것입니다.따라서 a + (b + c)와 (a + b) + c는 모두 a + b + c로 표시되는 "+"(a, b, c)로 단순화됩니다.a - b + c와 같은 표현의 경우, 가장 간단한 방법은 -E, E - F, E/F를 각각 (-1)⋅E, E + (-1)⋅F, E⋅F로 체계적으로 다시 쓰는 것입니다.즉, 표현의 내적 표현에서는 숫자의 표현 외에는 뺄셈도 나눗셈도 없고 단음의 마이너스도 없습니다.

덧셈과 곱셈의 교환성과 관련하여 또 다른 어려움이 발생합니다.문제는 비슷한 용어들을 빨리 인식해서 조합하거나 취소하는 것입니다.모든 항을 검정하는 것은 매우 긴 합과 곱으로 인해 비용이 많이 듭니다.이를 해결하기 위해 맥시마는 합과 곱의 피연산자를 같은 용어를 연속된 위치에 배치하는 순서로 정렬하여 쉽게 탐지할 수 있습니다.Maple에서 해시 함수는 유사한 용어가 입력되면 충돌을 생성하도록 설계되어 소개되자마자 결합할 수 있습니다.이를 통해 계산에서 여러 번 나타나는 하위 표현식을 즉시 인식하고 한 번만 저장할 수 있습니다.이를 통해 동일한 표현식에 동일한 연산이 반복되지 않도록 하여 메모리를 절약하고 연산 속도를 높입니다.

일부 다시 쓰기 규칙은 적용되는 식의 크기를 증가시키거나 감소시키는 경우도 있습니다.이것은 분포도 또는 삼각형의 동일성의 경우입니다.예를 들어, 분배 법칙은 (${\displaystyle x}$ ${\displaystyle +}$ ${\displaystyle 1{}^{}}$) ${\displaystyle 4^{}}$→ ${\displaystyle 4^{}}$ + ${\displaystyle {}^{}}$ x ${\displaystyle 3^{}}$+ ${\displaystyle 6}$ ${\displaystyle x^{}}$2 + ${\displaystyle 4}$ ${\displaystyle \mathrm{x}}$+ 1$${\$displaystyle (x+1)^{4$$}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$$$및 (${\displaystyle x}$-${\displaystyle 1}$) (${\displaystyle x^{}}$4 + ${\displaystyle 3^{}}$ + ${\displaystyle x^{}}$2 +${\displaystyle x}$ +${\displaystyle 1}$ )${\displaystyle }$$→$ ${\displaystyle x^{}}$5 - $.$ ${\displaystyle$ ($x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow$x^{$5}-1.$ 이러한 다시 쓰기 규칙을 적용하거나 적용하지 않는 일반적인 선택을 할 수 없으므로 이러한 다시 쓰기는 사용자가 명시적으로 호출한 경우에만 수행됩니다.분산성의 경우 이 다시 쓰기 규칙을 적용하는 컴퓨터 기능을 일반적으로 "확장"이라고 합니다."인자"라고 불리는 역방향 재작성 규칙은 중요하지 않은 알고리즘을 필요로 하며, 따라서 컴퓨터 대수 시스템의 핵심 함수입니다(다항식 인자화 참조).

수학적 측면

컴퓨터에서 수학적 표현을 조작하고 싶을 때 몇 가지 근본적인 수학적 질문이 나타납니다.우리는 주로 다변량 유리 분수의 경우를 고려합니다.식에 나타나는 비합리적인 함수가 단순화되는 순간 보통 새로운 불확정자로 간주되기 때문에 이는 실질적인 제약이 아닙니다.예를들면,

${\displaystyle(\sin(x+y)^{2}+\log(z^{2}-5)^{3}}$

sin ⁡ (${\displaystyle x}$ +${\displaystyle y}$ )$${\$displaystyle \sin (x+y)}$ ${\displaystyle 및}$ log ⁡ ( ${\displaystyle z^{}}$ 2${\displaystyle {}^{}}$-${\displaystyle 5}$ )$${\$displaystyle \log (z^{2}$ - $5)}$에서 다항식으로 봅니다.

이퀄리티

수학적 표현에는 두 가지 평등 개념이 있습니다.통사적 평등이란 컴퓨터에서 표현하는 그들의 동등함입니다.이것은 프로그램에서 테스트하기 쉽습니다.의미적 동등성은 두 표현이 같은 수학적 대상을 나타낼 때 입니다.

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

표현식에 지수와 로그가 허용되는 경우, 숫자를 나타내는 두 표현식이 의미론적으로 동일한지 여부를 결정하는 알고리즘이 존재하지 않을 수 있다는 것은 리처드슨의 정리로부터 알려져 있습니다.따라서 다항식 및 유리 분수와 같은 일부 클래스의 식에서만 (의미적) 동등성을 검정할 수 있습니다.

두 표현식의 동일성을 검증하기 위해서는 특정 알고리즘을 설계하는 대신 어떤 표준 형식으로 표현식을 넣거나 그 차이를 정규 형식으로 넣고 결과의 구문적 동일성을 검증하는 것이 일반적입니다.

컴퓨터 대수학에서 "정규 형식"과 "정규 형식"은 ^[10]동의어가 아닙니다.표준 형식은 표준 형식의 두 표현식이 구문적으로 동일한 경우에만 의미론적으로 동일한 것이고, 표준 형식은 일반 형식의 표현식이 구문적으로 0인 경우에만 의미론적으로 0인 것입니다.즉, 0은 정규 형태의 표현으로서 고유한 표현을 가지고 있습니다.

일반적으로 컴퓨터 대수학에서는 몇 가지 이유로 일반적인 형태가 선호됩니다.첫째, 표준 양식은 일반 양식보다 계산 비용이 더 많이 들 수 있습니다.예를 들어, 다항식을 표준 형태로 놓으려면, 모든 곱을 분배율을 통해 확장해야 하지만, 정규 형태로는 필요하지 않습니다(아래 참조).두 번째로, 라디칼을 포함하는 표현의 경우와 마찬가지로 표준 형태가 존재하는 경우 임의의 선택에 의존하며 독립적으로 계산된 두 표현식에 대해 이러한 선택이 다를 수 있습니다.이로 인해 표준 양식을 사용할 수 없게 될 수 있습니다.

역사

컴퓨터 대수학이 시작된 1970년경, 오래 전에 알려진 알고리즘들이 컴퓨터에 처음 적용되었을 때,^[11] 그것들은 매우 비효율적인 것으로 밝혀졌습니다.따라서, 이 분야의 연구자들은 고전 대수학을 재검토하여 이를 효과적으로 만들고 이 효과를 구현하기 위한 효율적인 알고리즘을 발견하는 것에 많은 비중을 차지했습니다.이러한 종류의 작업의 대표적인 예는 분수를 단순화하는 데 필요한 다항식 최대 공약수의 계산입니다.놀랍게도, 고전적인 유클리드의 알고리즘은 무한장 이상의 다항식에 비효율적인 것으로 밝혀졌고, 따라서 새로운 알고리즘이 개발될 필요가 있었습니다.선형대수학의 고전적 알고리즘 역시 마찬가지였습니다.

참고 항목

• 자동정리 속담
• 컴퓨터 보조 증명
• 계산 대수기하학
• 컴퓨터 대수 체계
• 증명 검사기
• 모델 체커
• 기호-숫자 계산
• 심볼릭 시뮬레이션
• 상징 인공지능

참고문헌

추가열람

주제에 대한 자세한 정의는 다음과 같습니다.

• Buchberger, Bruno (1985). "Symbolic Computation (An Editorial)" (PDF). Journal of Symbolic Computation. 1 (1): 1–6. doi:10.1016/S0747-7171(85)80025-0.

해당 주제에 대한 교과서의 경우:

• Davenport, James H.; Siret, Yvon; Tournier, Èvelyne (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation. Translated from the French by A. Davenport and J. H. Davenport. Academic Press. ISBN 978-0-12-204230-0.
• von zur Gathen, Joachim; Gerhard, Jürgen (2003). Modern computer algebra (2nd ed.). Cambridge University Press. ISBN 0-521-82646-2.
• Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992). Algorithms for Computer Algebra. Bibcode:1992afca.book.....G. doi:10.1007/b102438. ISBN 978-0-7923-9259-0.
• Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf, eds. (1983). Computer Algebra: Symbolic and Algebraic Computation. Computing Supplementa. Vol. 4. doi:10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6. S2CID 5221892.