Merging Algorithm for Relaxed Min-Max Heaps Relaxed min-max 힙에 대한 병합 알고리즙

민용식,Min, Yong-Sik The Acoustical Society of Korea 1995 韓國音響學會誌 Vol.14 No.e1

본 논문은 relaxed min-max heap을 병합시키기 위하여 이용된 새로운 자료구조인 개선된 relaxed min-max-pair 힙으로서, 두개의 relaxed min-max 힙 즉, 크기가 n인 relaxed min-max nheap과 크기가 k인 relaxed min-max kheap으로 구성된 우선 순위 큐를 병합시키기 위한 순차적 알고리즘을 제시하고자 한다. 본 논문에서 제시된 방법은 [8]에 제시된 방법에서 relaxed min-max 힙을 병합시키기 위해서 이용된 blossomed tree와 lazying 방법을 제거하여도 병합이 되는 새로운 기법을 제시하였다. 결과적으로 본 논문에서 제세된 방법은 두개의 relaxed min-max 힙의 크기가 서로 다른 경우로서, 이때 크기 $k{\leq}{\lfloor}log(size(nheap)){\rfloor}$인 경우, 시간 복잡도가 O(log(log(n/k))*log(k)) 이고 공간복잡도가 O(n+k)임을 볼수가 있다. This paper presents a data structure that implements a mergeable double-ended priority queue ; namely, an improved relaxed min-max-pair heap. It suggests a sequential algorithm to merge priority queues organized in two relaxed min-max heaps : kheap and nheap of sizes k and n, respecrively. This new data sturuture eliminates the blossomed tree and the lazying method used to merge the relaxed min-max heaps in [8]. As a result, the suggested method in this paper requires the time complexity of O(log(log(n/k))*log(k)) and the space complexity of O(n+), assuming that $k{\leq}{\lfloor}log(size(nheap)){\rfloor}$ are in two heaps of different sizes.

Relaxed min-max 힘에 대한 병합 알고리즘

민용식(Yong sik Min) 호서대학교 중앙도서관 1994 호서대학교 논문집 Vol.2 No.-

This paper presents a data structure that implements a mergeable double-ended priority queue; namely, an improved relaxed min-max-pair heap. It suggests a sequential algorithm to merge priority queues organized in two relaxed min-max heaps: kheap and nheap of sizes k and n, respectively. This new data structure eliminates the blossomed tree and the lazying method used to merge the relaxed min-max heaps in [8]. As a result, the suggested method in this paper requires the time complexity of O(log(log(n/k))*log(k)) and the space complexity of O(n+k), assuming that k≤[log(size(nheap))] are in two heaps of different sizes.

Relaxed min-max 힙을 병합하는 병렬 알고리즘

민용식(Min Yong Sik) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.5

This paper presents a data structure that implements a mergable double-ended priority queue : namely an improved relaxed min-max-pair heap. By means of this new data structure, we suggest a parallel algorithm to merge priority queues organized in two relaxed heaps of different sizes, n and k, respectively. This new data-structure eliminates the blossomed tree and the lazying method used to merge the relaxed min-max heaps in [9]. As a result, employing max(2^i-1,[(m 1/4)]) processors, this algorithm requires O(log(log(n/k))?log(k)) time. Also, on the MarPar machine, this method achieves a 35.205-fold speedup with 64 processors to merge 8 million data items which consist of two relaxed min-max heaps of different sizes.

Parallel Sorting Algorithm by Median-Median

민용식,Min, Yong-Sik The Acoustical Society of Korea 1995 韓國音響學會誌 Vol.14 No.e1

This paper presents a parallel sorting algorithm suitable for the SIMD multiprocessor. The algorithm finds pivots for partitioning the data into ordered subsets. The data can be evenly distributed to be sorted since it uses the probability theory. For n data elements to be sorted on p processors, when $n{\geq}p^2$, the algorithm is shown to be asymptotically optimal. In practice, sorting 8 million data items on 64 processors achieved a 48.43-fold speedup, while the PSRS required a 44.4-fold speedup. On a variety of shared and distributed memory machines, the algorithm achieved better than half-linear speedups. 본 논문은 SIMD 병렬 처리 컴퓨터에 적합한 병렬 분류 알고리즘을 제시키 위해서, 다음과 같이 수행이 된다. 첫째, 비순서화된 데이타 집합을 p개의 프로세서로 할당시킨후에 순차적 quicksort로 분류한다. 그 다음으로, 분류된 각 프로세서의 중위수값을 구한다음 이 값에 위해서 각 프로세서에 데이타 값을 할당시킨다. 각 프로세서에 할당된 데이타가 정확하게 분배가 되도록 중위수와 중위수 값을 구해서 각 프로세서에 적합한 데이타를 다시 할당 시키게 된다. 이때 각 프로세서가 지닌 데이타의 수는 확률이론을 이 용하였다. 마지막으로, 각 프로세서에 할당된 데이타를 순차적 quicksort로 분류하면 된다. 여기서 분류될 데이타 n가 $n{\geq}p^2$일때 본 알고리즘은 최적이 되게됨을 볼수가 있다. 실제적 구현에 있어서, 64개 프로세서를 이용해서 8백만개의 데이타를 분류할때 PSRS 방법의 speedup은 44.4인 반면에 본 알고리즘은 48.43이 된다. 즉, 다양한 공용과 분산 기억장치 기계에 관해서, 본 알고리즘의 speedup은 거의 절반 이상의 선형시간으로서 성취가 됨을 볼 수가 있다.

PDOCM : Fast Text Compression on MasPar Machine

민용식,Min, Yong-Sik The Acoustical Society of Korea 1995 韓國音響學會誌 Vol.14 No.1

본 논문은 redundancy를 제거함으로 해서 데이타의 축약을 할 수 있는 새로운 방법론 즉, 병렬 컴퓨터인 MasPar 머쉰에 적합한 새로운 데이타 구조를 제시하고자 하는데 그 주된 목적이 있다. 이것을 실제로 구현한 결과, 본 논문에 제시된 방법인 PDOCM (Parallel Dynamic Octal Compact Mapping)은 기존의 방법중 가장 효율이 좋은 것으로 나타난 Huffman 코드와 비교할때는 평균적으로 $30\%$정도, bit-mapping방법과 비교할때는 평균적으로 $40\%$ 정도의 우수성을 보였다. 그리고 10 백만개의 영문자를 이용해서 MasPar 기계에서 64개의 프로세서를 이용하여 구현시킨 결과 54.188의 가속화율을 얻으므로서 우수한 방법임을 알 수가 있었다. Due to rapid progress in data communications, we are able to acquire the information we need with ease. One means of achieving this is a parallel machine such as the MasPar. Although the parallel machine makes it possible to receive/transmit enormous quantities of data, because of the increasing volume of information that must be processed, it is necessary to transmit only a minimal amount of data bits. This paper suggests a new coding method for the parallel machine, which compresses the data by reducing redundancy. Parallel Dynamic Octal Compact Mapping (PDOCM) compresses at least 1 byte per word, compared with other coding techniques, and achieves a 54.188-fold speedup with 64 processors to transmit 10 million characters.

기능성 게임콘텐츠의 음향 청취방법이 뇌 활성화지수에 미치는 효과

민용식,유회종,Min, Yong-Sik,Yoo, Hunter 한국음향학회 2010 韓國音響學會誌 Vol.29 No.4

본 연구는 기능성 게임 콘텐츠의 교육효과를 위해 음향청취방법을 달리하여, 인간의 뇌파 지수로 분석한 유사 실험을 한 연구이다. 실험결과 무음으로 처리한 대조군에 비해 스피커 방식의 청취방법이 높은 뇌 활성화 반응도를 보였으며, 다음으로 헤드폰 방식 이였다. 본 연구에서는 기능성 게임 콘텐츠의 음향청취방법에 따라 인지반응에 미치는 정도를 뇌파 지수 분석을 통하여 정량적으로 분석한 것에 큰 의미가 있다. To do an experimental analysis in this paper, we divided two non-equivalent control groups, such as pre and post test groups for difference listening types by serious game contents. From these test groups, we can achieve the most ability of its activity quotient (ACQ) effect is a phonic type and the next one is an aural type. The purpose of this paper is focused on the quantitative analysis of the human's brain quotient (BQ) derived from serious educational game contents.

A Parallel Algorithm for Merging Heaps on MasPar Machine

민용식,Min, Yong-Sik 한국정보처리학회 1995 정보처리논문지 Vol.2 No.4

본 논문은 크기가 n와 k인 nheap과 kheap을 병합시키기 위한 병렬 알고리즘을 제 시함과 동시에 그들을 MasPar상에 실제로 구현하고자 하는데 그 주된 목적이 있다. 이때, EREW-PRAM(Exclusive-Read Exclusive-Write Parallel Random Acess Machin)상에 서 max(2$^{-1}$, $\ulcorner$(m+1)/4$\lrcorner$개의 프로세서를 이용해서 본 논문에 제시된 알고리즘 의 시간 복잡도가 O(log(n/k)*log(n))임을 제시하였다. 여기서 i는 heap의 height를 뜻하며, m은 크기 n과 k의 합으로 구성된 것이다. 또한 이것을 MasPar 컴퓨터에 적용 을 시켰을 때, 테이타의 양이 8백만개이고, 64개의 프로세서를 이용한 경우의 speedup 을 33.934를 얻었다. 이때 적용된 데이타의 형태는 불완전 힙상에서 크기가 k〈n를 지 니는 경우의 처리이다. 그리고 이같이 제시된 알고리즘의 EPU(Effective Processor Utilization)을 계산하면 1인 최적의 speedup율을 나타냄을 알 수가 있다. In this paper, we suggest a parallel algorithm to merge priority queues organized in two heaps, kheap and nheap of sizes k and n, correspondingly. Employing max(2$^{-1}$, $\ulcorner$(m+1)/4$\lrcorner$'s processors, this algorithm requires O(log(n/k)*log(n)) on an EREW-PRAM, where i is the height of the heap and m is the summation of sizes n and k. Also, when we run it on the MasPar machine, this method achieves a 33.934-fold speedup with 64 processors to merge 8 million data items which consist of two heaps of different sizes. So our parallel algorithm's EPU is close to 1, which is considered as an optimal speedup ratio.eedup ratio.

최적 윈도우를 이용한 클리핑 알고리즘

민용식(Yong sik Min) 호서대학교 중앙도서관 1994 호서대학교 논문집 Vol.2 No.-

The most attention-getting object in Computer Graphic is the clipping on Window, for it can make the shape of window a new shape and controllable environment. To utilize the functions of clipping for utmost conditions ,three methods can be considered : the first is to utilize the chracteristics of hardware, the second is to utilize those of the software and the third is the utilizing those hardware and software. This study suggests the way of solving the clipping problem by adapting the second method, that is, software using the optimal dynamic window, which is included the edges inside the new window. And to prove the effectivness of the algorithm already mentioned, I acted up it on IBM-PC with C-language . As a result of practice, the effectiveness of algorithm was prove to be much more excellent than the prsent methods.

국내 미디어산업의 파급효과 분석

민용식(Yong-Sik Min),임응순(Eung-Soon Lim),정군오(Kun-Oh Jung) 한국콘텐츠학회 2010 한국콘텐츠학회논문지 Vol.10 No.1

전 세계적으로 미디어산업의 중요성이 증대되고 있으며, 이에 따라서 미디어산업의 전반적인 변혁이 일어나고 있다. 따라서 미디어산업에 대한 국민경제적 파급효과 분석이 필요한 시기라 할 수 있다. 본 연구에서는 산업연관분석을 통한 미디어산업을 분석하였는데, 먼저 수요유도형 모형을 이용하여 생산유발효과, 부가가치 유발효과, 취업유발효과를 구하였고, 공급유도형 모형을 이용하여 공급지장효과를 구하였고, 레온티에프 가격모형을 이용하여 물가파급효과를 분석하였다. 분석결과는 미디어산업의 1원의 생산에 대하여 경제 전체에 생산유발효과는 0.5461원, 부가가치 유발효과는 0.3143원 유발하였으며, 10억원당 취업유발은 5.0459명, 미디어산업에 1원의 공급지장이 생기면 국민경제전에 미치는 공급지장효과는 0.7353원으로 나타났으며, 10%의 가격상승에 의한 물가파급효과는 0.2389%로 분석되었다. The media industry is becoming more important around the world and there are changes over this industry. Therefore this is the time that the economic impacts is needed about media industry. This study attempts to examine the economic impacts of the media industry using an inter-industry analysis. Specifically, the study investigates production-inducing effect, value added inducing effect and employ-inducing effect of the media industry based on demand-driven model and the study deals with supply shortage effect and sectoral price effect of the media industry by using supply-driven model and Leontief price model. The results of this analyses are presented; 0.5461 won in production-inducing effect, 0.3143 won in value added inducing effect when 1 won is produced by media industry, 5.0459 persons in employ-inducing effect when 1 billion won is produced, 1 won of supply shortage in this industry results 0.7353 won in supply shortage effect which affect the other industries. Sectoral price effect is 0.2389% due to the 10% increase of price.

산업연관분석을 이용한 일본 방송산업의 국민경제적 파급효과 분석

민용식(Yong Sik Min),임응순(Eung Soon Lim),곽소윤(So Yoon Kwak) 한국아시아학회 2008 아시아연구 Vol.10 No.3

본 논문에서는 산업연관분석을 이용하여 일본 방송산업의 국민경제적 파급효과를 분석하고자 한다. 먼저 수요유도형 모형을 이용하여 생산유발효과, 부가가치 유발효과를 살펴본다. 아울러 공급유도형 모형 및 레온티에프 가격모형을 적용하여 방송산업의 공급지장효과 및 물가파급효과를 살펴본다. 이러한 분석은 모두 방송산업을 내생부문이 아닌 외생부문으로 다룸으로써 방송산업을 중심으로 이루어지게 된다. 주요 분석결과를 요약하면 다음과 같다. 방송산업의 1엔 생산은 타 산업의 생산을 0.9653엔 만큼 유발하며, 타 산업의 부가가치를 0.5323엔 만큼 유발한다. 한편 방송산업에서 1엔의 공급이 이루어지지 못할 때, 타 산업에서는 1.7383엔의 생산차질이 발생한다. 마지막으로 방송산업 산출물의 가격이 10% 상승했을 때, 국민경제 전체에 미치는 물가파급효과는 0.5596%로 분석되었다. This study attempts to examine the economic impacts of broadcasting industry in Japan using an inter-industry analysis. Specifically, the study investigates production-inducing effect and value added inducing effect of the broadcasting industry in Japan based on demand-driven model. Moreover, the study deals with supply shortage effect and sectoral price effect by using supply-driven model and Leontief price model, respectively, which have been rarely used. These analyses pay particular and close attention to the broadcasting industry of Japan by taking it as exogenous rather than endogenous. Some interesting findings emerge from the study. First, the production of 1.0 yen in the broadcasting industry in Japan induces the production of 0.9653 yen and the value-added of 0.5323 yen in other industries. Second, the supply shortage of 1.0 yen in the broadcasting industry in Japan disables other industries to produce 1.7383 yen. Finally, an increase of 10% in price level of the broadcasting industry in Japan raises the overall price level by 0.5596%.