#4-6-1 The Art of Computer Programming - 준수치적 알고리즘

4-6에서는 다항식의 산술에 대해 배운다.

다항식은 알고리즘 문제 풀이에도 많이 응용된다.

 

모닉다항식 : 차수가 n이고 선행 계수가 1일 때를 일컬음.

 

4-6-1절의 내용은 다항식의 나눗셈에 대한 내용이다.

산술들을 하나의 field에 관한 다항식들에 대해 수행한다면, 

한 다항식을 다른 다항식으로 나누는 연산을 다중 정밀도 정수 나눗셈과 동일한 방식으로 수행이 가능하다.

이게 무슨 말일까..

 

기약 다항식 : 하나의 유일 인수분해 정역에 관한 다항식들은 하나의 유일 인수분해 정역을 형성하는데, 이 정의역 안에서 소수인 다항식을 말함.

????? 그렇단다...

그 뒤에 예를 들어놓은 내용이 있는데, 하나의 정수에 대해 여러 가지 형태로 다항식을 표현할 수 있지만 인수분해는 유일하다는 의미이다. 그러니까 좀 이해가 되는 듯.

 

서로소 : 유일한 인수분해 정역의 원소 모두의 약수인 소수가 존재하지 않을 때, 그러한 유일 인수분해 정역의 원소들을 의미

원시 다항식 : 한 유일 인수분해 정역에 관한 다항식의 계수들이 서로 소일 때 그러한 다항식을 가리킴

 

그 이후에는 GCD, LCM에 대한 논의와 하위 종결식 알고리즘에 대한 설명이 있다.