| [ Guru ] in KIDS 글 쓴 이(By): guest (SKKIM) 날 짜 (Date): 1996년01월22일(월) 13시32분42초 KST 제 목(Title): 수학 잘하시는 분께 질문 하나! 안녕하세요? 수학, 특히 선형대수를 잘 하시는 분께 질문이 있어요. 컴파일러쪽에서 어떤 연구 주제를 다루다가 다음과 같은 문제에 맞닥뜨리고 말았는데요, 아시는 분은 도움을 주시기를 간곡히 부탁드립니다. <문제> m개의 정수형 변수가 선형적으로 결합된 일차다항식이 n개 있습니다. 이때, 각 다항식의 값을 F로 나타낸다면, 다음과 같겠죠. 즉, F1 = A11*X1 + A12*X2 + ... + A1m*Xm F2 = A21*X1 + A22*X2 + ... + A2m*Xm : : Fn = An1*X1 + An2*X2 + ... + Anm*Xm 과 같이 주어졌다고 합시다. 여기서 Aij는 정수형 상수입니다. 또, 각 정수형 변수 Xi (1 <= i <= m)에 대해서는 다음과 같이 범위가 주어져 있답니다. 즉, MINi <= Xi <= MAXi 와 같이 말이죠. 그러면, 문제를 드리지요. F1,...,Fn 이 취할 수 있는 값의 집합을 각각 V1,...,Vn 이라고 할 때, V1,...,Vn 모두에 대한 합집합 원소의 갯수, 즉 n(V1 U V2 U ... U Vn) 이 얼마일까하는 것이 문제입니다. 전 이를 풀기 위해 먼저 교집합들의 원소의 갯수를 구해보았는데요, 계산과정이 너무 복잡하고 알고리즘의 복잡도가 2의 지수승으로 나타나더군요. 다른 뭐 좋은 방법이 없을까요? 해법이 아니더라도 어느 책이나 논문을 보면 도움을 받을 수 있다는 등의 조언이라도 해 주신다면 정말 정말 고마울 겁니다. 부탁합니다. 제 e-mail 주소는 skkim@archi.snu.ac.kr 입니다. 어디로든 보내 주세요. 그럼, 안녕히... |