http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 장직현(Jig Hyun Chang) (검색결과 2 건)
- 무료
- 기관 내 무료
- 유료
-
이정인(Jung Ihn Lee),장직현(Jig Hyun Chang) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.2
스타(star) 그래프는 하이퍼큐브가 갖는 여러 좋은 특성을 가지고 있으면서 경우에 따라서는 더 우수한 상호 연결 네트워크임이 알려져있다. 그러나 스타 그래프는 다중 처리기 상호 연결 네트워크로써 좋은 특성이 있지만 아직 그 특성을 효율적으로 이용한 알고리즘들이 많이 개발되지 않고 있다. 본 논문은 n¹개의 노드를 갖는 스타 그래프에 완전 이진트리를 임베딩히는 알고리즘을 제시한다. 결과로서 연장비율(dilation) l과 2의 임베딩에서 확장비율(expansion)은 n¹/(2ⁿ-1-1)과 n¹/(2^m-l)을 각각 얻었다. 단, m=n · [log n]-2 · 2^([log n])+3이다. 지금까지 완전 이진트리를 스타 그래프에 임베딩한 결과가 없으므로 완전 이진트리를 하이퍼큐브에 임베딩하고 이것을 다시 스타 그래프에 임베딩하여 얻은 결과와 비교하여서, 본 논문의 결과가 나음을 보인다. It has been shown that the star graph is an interconnection network which has many useful properties of the hypercube and is superior to the hypercube in some cases. Although the star graph has many attractive properties as a multiprocessor interconnection network, few algorithms exist to show its potential. In this paper two algorithms for embedding a complete binary tree in the star graph having n¹ nodes are described. Our algorithms give two embeddings with dilation 1 and expansion n¹/(2 ⁿ-1-1) and with dilation 2 and expansion n¹/(2^m-l), respectively, where m=n · [log n]-2 · 2^([log n])+3 No algorithm for embedding a complete binary tree in the star graph has been reported yet Our embedding results are better than the one obtained by embedding a complete binary tree in a hypercube and embedding the resulting hypercube in the star graph.
-
한 부류의 NP-Complete 문제에 대한 Systolic 트리 알고리즘 (pp.354-368)
이혜영(Hye Young Lee),장직현(Jig Hyun Chang) 한국정보과학회 1988 정보과학회논문지 Vol.15 No.5
본 논문에서는 한 부류의 NP-complete 문제에 대하여 완전 이진트리 배열을 사용한 systolic 시스템에 기초한 병렬 알고리즘을 연구한다. 모든 결과는 0/1 knapsack 문제에 대한 것이나 0/1 정수 프로그래밍(integer programming) 문제, 부분집합의 합(sum of subset) 문제, 집합 커버링(set covering) 문제 등과 같은 유형의 NP-complete 문제들을 유사한 방법으로 해결할 수 있다. 우리가 제시하는 병렬 알고리즘을 구성하는데 있어서 우선, n개의 수들의 집합의 모든 부분집합의 합을 계산하고 특정한 조건을 만족하는 합을 구하는 자료구조를 효율적으로 수행할 수 있는 완전 이진트리 구조를 갖는 systolic 트리 배열을 구현하고, 이 systolic 배열을 사용하여 0/1 knapsack 문제를 O(n) 시간 내에 O(2ⁿ)의 area complexity로 해결할 수 있음을 보이고, 또한 트리 배열의 area complexity를 1/2로 줄일 수 있음을 보였다. 트리 배열에서 계산된 부분합들로 heap을 구성하여 기존의 각각 O(2 ⁿ / ²), O(2 ⁿ / ⁴) area complexity를 갖고 O(2 ⁿ / ²) time complexity를 갖는 two-list 알고리즘과 four-table 알고리즘을 systolic 시스템에 구현하였다. 기존의 결과와는 달리 우리의 two-list 알고리즘의 systolic 시스템 구현은 time complexity에서 logarithmic factor를 무시하지 않은 결과를 얻었고, 또한 모든 구현에서 해와 관련된 부분집합의 0/1 해벡터를 complexity의 추가 부담 없이 쉽게 구할 수 있다. In this paper, we study the parallel algorithms for a class of NP-complete problems based on the systolic systems using complete binary tree arrays. We give the results all for 0/1 knapsack problem, but with simple modification, the NP-complete problems such as 0/1 integer programming, sum of subsets, set covering, etc. can be solved. To construct our parallel algorithms, first on a systolic tree array we consider the efficient implementations of a data structure which computes the sum of all subsets of the set of n numbers and then finds a sum satisfying a certain condition Using this systolic array, we show that 0/1 knapsack problem can be solved with O(n)time and 0(2ⁿ) area complexities, and then show that the area complexity can be reduced by 1/2. By constructing a heap with the partial sums computed on a tree array, we give the systolic implementations of two-list algorithm and four-table algorithm where both have O(2 ⁿ / ²) time complexity and each has O(2 ⁿ / ²), O(2 ⁿ / ⁴) area complexity, respectively.
연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
