Recursive Definition of the SymMerge Algorithm

Pok-Son Kim(김복선) 한국지능시스템학회 2016 한국지능시스템학회 학술발표 논문집 Vol.26 No.1

A New Complexity Analysis of Symmerge Algorithm

Pok-Son Kim(김복선),Arne Kutzner(쿠츠너 아네) 한국지능시스템학회 2015 한국지능시스템학회 학술발표 논문집 Vol.25 No.1

Concepts for Efficiently Merging on GPUs

Pok-Son Kim(김복선),Arne Kutzner 한국지능시스템학회 2010 한국지능시스템학회 학술발표 논문집 Vol.20 No.1

We introduce an algorithm for efficiently merging on contemporary GPUs that requires O(m log(n/m + 1)) element comparisons, where m and n are the sizes of the input sequences with m ≤ n. According to the lower bounds for merging our algorithm is asymptotically optimal. It uses a technique of repeated symmetric splittings for efficiently decomposing the merging problem into many equally sized subproblems. This decomposition strategy provides a high degree of parallelism that is necessary for efficiently solving the merging problem using GPGPU.

Proving Correctness of the RCPSV-Algorithm

Pok-Son Kim(김복선) 한국지능시스템학회 2013 한국지능시스템학회 학술발표 논문집 Vol.23 No.2

On a Simple and Stable Merging Algorithm

김복선(Pok-Son Kim),쿠츠너 아네(Arne Kutzner) 한국지능시스템학회 2010 한국지능시스템학회논문지 Vol.20 No.4

단순하고 스테이블한 머징알고리즘의 비교횟수와 관련된 worst case 복잡도를 분석한다. 복잡도 분석을 통해 소개되는 알고리즘이 m 과 n, m≤n 사이즈의 두 수열에 대해 O(mlog(n/m))의 비교횟수를 요구하는 사실을 증명한다. 그래서 병합에 있어서의 하계가 Ω(mlog(n/m))이라는 사실로부터 우리의 알고리즘이 비교횟수와 관련해 점근적 최적 알고리즘에 해당함을 추론가능하다. worst case 복잡도 증명을 위해 모든 입력수열로 구성된 정의구역을 두개의 서로소인 집합으로 나눈다. 그런 후 서로소인 각각의 집합으로 부터 특수한 subcase를 구별한 후 이들 subcase 각각에 대해 점근적 최적성을 증명한다. 이 증명을 바탕으로 나머지 모든 경우에 대한 최적성 또한 추론 또는 증명 가능함을 소개한다. 이로써 우리는 복잡도 분석이 까다로운 알고리즘에 대해 투명한 하나의 해를 제시한다. We investigate the worst case complexity regarding the number of comparisons for a simple and stable merging algorithm. The complexity analysis shows that the algorithm performs O(mlog(n/m)) comparisons for two sequences of sizes m and n m≤n. So, according to the lower bound for merging Ω(mlog(n/m)), the algorithm is asymptotically optimal regarding the number of comparisons. For proving the worst case complexity we divide the domain of all inputs into two disjoint cases. For either of these cases we will extract a special subcase and prove the asymptotic optimality for these two subcases. Using this knowledge for special cases we will prove the optimality for all remaining cases. By using this approach we give a transparent solution for the hardly tractable problem of delivering a clean complexity analysis for the algorithm.

효율적 In-Place Block Rotation 알고리즘과 복잡도 분석

김복선(Pok-Son Kim),쿠츠너 아네(Arne Kutzner) 한국지능시스템학회 2010 한국지능시스템학회논문지 Vol.20 No.3

μ와 υ를 두 인접수열 (consecutive sequence)이라고 했을 때 이때 “block rotation”이란 μυ를 υμ로 바꾸는 연산을 의미한다. 기존에 3개의 block rotation 알고리즘 즉 “BlockRotation”, “Juggling” 그리고 “Reversal 알고리즘”이 소개되었는데 최근 우리는 하나의 새로운, QuickRotation 이라고 명명한 block rotation 알고리즘을 소개했다. 우리는 이 논문에서 QuickRotation 알고리즘을 이들 기존의 알고리즘들과 비교해 보이고자 한다. 벤치마킹 뿐만 아니라 복잡도 분석을 통한 비교를 통해 QuickRotation 알고리즘의 우수성을 증명해 보이고자 한다. The notion “block rotation” denotes the operation of exchanging two consecutive sequences of elements μυ to υμ. There are three already well-known block rotation algorithms called BlockRotation, Juggling and Reversal algorithm. Recently we presented a novel block rotation algorithm called QuickRotation. In this paper we compare QuickRotation to these three known block rotation algorithms. This comparison covers a complexity analysis as well as benchmarking and shows that a switch to QuickRotation is almost always advantageous.

효율적 Block Rotation 알고리즘과 복잡도 분석

김복선(Pok-Son Kim),쿠츠너 아네(Arne Kutzner) 한국지능시스템학회 2010 한국지능시스템학회 학술발표 논문집 Vol.20 No.1

u와 u를 두 인접수열 (consecutive sequence)이라고 했을 때 이때 “block rotation"이 란 uv를 vu로 바꾸는 연산을 의미한다. 기존에 3개의 block rotation 알고리즘 즉 “BlockRotation", "Juggling" 그리고 "Reversal 알고리즘"이 소개되었는데 최근 우리는 하나의 새로운 QuickRotation 이라고 명명한 block rotation 알고리즘을 소개했다. 우리는 이 논문에서 QuickRotation 알고리즘을 이들 기존의 알고리즘들과 비교해 보이고자 한다. 벤치마킹 뿐만 아니라 복잡도 분석을 통한 비교를 통해 QuickRotation 알고리즘의 우수성을 증명해 보이고자 한다.

A New Complexity Analysis of the SymMerge Algorithm

Pok-Son Kim(김복선) 한국지능시스템학회 2015 한국지능시스템학회논문지 Vol.25 No.5

SymMerge 알고리즘은 두 입력수열 υ와 ν (?υ?=m, ?ν?=n, m ≤ n)에 대한 효율적 병합 알고리즘이다. SymMerge 알고리즘의 비교횟수와 관련한 복잡도 분석을 하고자 하며 지금까지의 복잡도 분석은 복잡도의 상계값을 찾으므로 점근적 계산방법을 통해 이루어졌다. 이 논문에서는 지금까지의 분석방법과는 달리 SymMerge 알고리즘의 대표적 두 special case에 해당하는 “Symmetric case”와 “Maximum spanning case”에 있어서 병합을 위해 요구되는 정확한 비교횟수를 즉 비교횟수의 최소상계 값을 계산해 보이고자 한다. “Symmetric case”의 경우 사이즈 m=2<SUP>κ</SUP>, n-2<SUP>ι</SUP>, ι≥κ인 임의의 입력수열에 대해 SymMerge 알고리즘이 필요로 하는 비교횟수는 정확하게 m ? n/m+4m-? m-3이고 “Maximum spanning case”의 경우 사이즈 m=2<SUP>κ</SUP>, n=2<SUP>m</SUP>-m인 임의의 입력수열에 대해 SymMerge 알고리즘이 필요로 하는 비교횟수는 정확하게 1/2m²+(m+1)? m-3/2m+2임을 계산해 보인다. 추가로 이들 두 special case에 있어서 요구되는 비교횟수가 재귀적 함수에 의해 정의될 수 있음을 보인다. The SymMerge algorithm is an efficient merging algorithm for input sequences υ and ν of sizes ?υ?=m and ?ν?=n, m ≤ n. We consider complexity analysis for SymMerge algorithm regarding to the required number of comparisons. The focus of the previous complexity analysis was on finding the values of upper bounds, i.e. showing the asymptotical optimality. In this paper, in a different way from the previous complexity analysis, we show that the overall required number of comparisons for two representative special cases “symmetric case” and “maximum spanning case” can be calculated exactly i.e. the least upper bounds regarding to the required number of comparisons are calculated. Symmerge requires exactly m ? n/m+4m-? m-3 comparisons for symmetric case of sizes m=2<SUP>κ</SUP>, n-2<SUP>ι</SUP>, ι≥κ of input sequences and exactly 1/2m²+(m+1)? m-3/2m+2 comparisons for maximum spanning case of sizes m=2<SUP>κ</SUP>, n=2<SUP>m</SUP>-m of input sequences. Additionally we show that the complexity of the Symmerge algorithm regarding to the overall required number of comparisons for these special cases can be defined by recurrence relations.

Complexity of the Symmerge Algorithm

Pok-Son Kim(김복선) 한국지능시스템학회 2008 한국지능시스템학회논문지 Vol.18 No.2

m≤n을 만족하는 m과 n을 두 입력수열이라고 했을 때 Symmerge는 비교횟수와 관련해 복잡도 O(mlog n/m)를 필요로 하는 stable minimum storage 머징 알고리즘이다. 그러므로 비교횟수와 관련된 머징의 점근적 하계 Ω(mlog n/m)에 의해 Symmerge 알고리즘은 최적 알고리즘에 해당함을 알 수 있다. Symmerge는 두 입력수열의 분할 (partition)과 로테이션 (rotation)을 통해 얻어지는 수열들에 알고리즘의 재귀적 콜 (recursive call)이 적용되는 divide 와 conquer 기술을 이용한다. 이로 인해 수열들이 반복해서 분할과 로테이션 되는데 특히 재귀의 깊이가 m-1 가 되는 경우에 있어서 두 입력수열의 길이의 관계를 알아보고자 한다. Symmerge is a stable minimum storage merging algorithm that needs O(mlog n/m) element comparisons, where m and n are the sizes of the input sequences with m≤n. Hence, according to the lower bound for merging, the algorithm is asymptotically optimal regarding the number of comparisons. The Symmerge algorithm is based on the standard recursive technique of "divide and conquer". The objective of this paper is to consider the relationship between m and n for the degenerated case where the recursion depth reaches m-1.

SymMerge 알고리즘의 재귀적 정의

김복선(Pok-Son Kim) 한국지능시스템학회 2017 한국지능시스템학회논문지 Vol.27 No.5

병합 알고리즘은 원소의 개수가 과 인 두 개의 배열된 인접수열을 원소의 개수가 인 배열된 하나의 수열로 만드는 알고리즘이다. 우리는 SymMerge라고 명명한 스테이블하고, 비트의 메모리를 추가적으로 필요로 하는 병합알고리즘을 소개하였고 비교횟수 그리고 덮어쓰기 (assignment)와 관련해 최악의 경우에 대한 복잡도 분석을 소개했다. 그리고 기존의 논문에서 우리는 SymMerge 알고리즘의 정의를 유사부호 (Pseudocode)를 이용해 묘사하였다. 이 논문에서 우리는 -재귀함수를 이용해 SymMerge 알고리즘이 정의 될 수 있음을 보이고자 한다. 추가로 이러한 재귀적 정의를 바탕으로 원소의 개수가 과 인 두 개의 입력수열을 병합하기 위해 요구되는 비교횟수가 재귀 함수에 의해 계산될 수 있음을 보인다. Merging denotes the operation of rearranging the elements of two adjacent sorted sequences of sizes and, so that the result forms one sorted sequence of elements. We presented a stable minimum storage merging algorithm called SymMerge and investigated its worst case complexity regarding the number of comparisons as wlle as assignments. In former publications we delivered a definition of the SymMerge algorithm by means of Pseudocode. Here we will give a definition of the same algorithm by using -recursive functions. Additionally, using the -recursive definition we will develop a recursive function for precisely calculating the number of comparisons required fro merging two sequences of sizes and