SymMerge 알고리즘이 갖는 성질들에 관한 연구 (A Study on Properties of the SymMerge Algorithm)

서지정보

· 발행기관 : 한국지능시스템학회
· 수록지 정보 : 한국지능시스템학회 논문지 / 30권 / 4호 / 297 ~ 302페이지
· 저자명 : 김복선

초록

SymMerge는 사이즈가 각각 과 인 배열된 두 입력수열을 대칭적 분할 및 로테이션 그리고 재귀적 계산과정을 거쳐 사이즈가 인 배열된 수열을 출력하는 병합알고리즘이다. 두 입력수열이SymMerge에 의해 병합이 되는 과정이 이진트리인 분할트리에 의해 묘사될 수 있는데 분할트리의각각의 정점은 SymMerge가 재귀적으로 적용이 될 때의 두 입력수열의 사이즈를 나타낸다. 우리는본 논문에서 사이즈가   인 두 입력수열에 대한 SymMerge의 분할트리가 재귀깊이  을 갖는 경우와 재귀깊이 를 갖는 대칭적 경우에 대해 분할트리의 각각의 정점의 두 입력수열의 사이즈가 정확한 수식에 의해 묘사 될 수 있음을 증명해 보이고자 한다. 뿐만아니라 이 두 경우에 대한 분할트리의 정점의 개수가  개에 해당한다는 사실을 비롯해SymMerge가 만족시키는 다양한 성질들을 보이고자 한다.

영어초록

SymMerge is a recursive algorithm that uses a symmetric comparison strategy and rotations for merging two sorted sequences of sizes  and  into one sequence of size  . The computational process of the SymMerge algorithm can be described by a binary tree called decomposition tree, where every node of this tree denotes a tuple comprising the sizes of two merged sequences. In this paper, we consider two special cases regarding the merging of sequences of sizes            : First, the case with maximum recursion depth    and, second, the symmetric case with recursion depth . For both cases, we show that the sizes of the two merged sequences of each node of the decomposition tree can be calculated by exact mathematical expressions. Further, we inspect several properties satisfied by SymMerge as e.g. that in both cases the number of nodes of the decomposition tree is   .

참고자료

· 없음