정보올림피아드와 정보과학 교육

장직현(Jik Hyun Chang) 한국정보과학회 2007 정보과학회지 Vol.25 No.7

(n, k)-스타 그래프상의 해밀토니안 임베딩

박천웅(Chonung Park),장직현(Jik-Hyun Chang) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.12

스타 그래프는 다중 처리기 상호 연결 네트워크로서 좋은 특성이 있지만, 노드 개수의 제한으로 실용적으로 구현하는데 어려움이 있다. n-스타 그래프의 경우 n!개의 노드를 가지는데 n!와 (n+l)! 사이에는 큰 차이가 있으므로, 원하는 노드 수보다 매우 작거나 매우 크게 된다. (n, k)-스타 그래프는 n!/(n-k)!개의 노드를 가지는 그래프로 스타 그래프가 갖는 여러 좋은 특성을 유지하면서 스타 그래프의 n!개 노드 개수의 제한을 n과 k 요소로 조절하여 적절한 노드 수의 그래프를 구성할 수 있다. (n, k)-스타 그래프의 이런 특성은 네트워크 위상을 설계하는데 있어서 보다 유연하다. 본 논문에서는 (n, k)-스타 그래프의 계층적 해밀토니안 싸이클을 재귀적으로 구성하는 방법을 제시한다. Although the star graph has many attractive properties as a multiprocessor interconnection network, a major practical difficulty with star graph is the restriction on the number of nodes. The n-star graph has n! nodes. Since there is a large gap between n! and (n+l)!, one may choose of either too few or too many available nodes. Thus, new topology, called (n, k)-star graph has been proposed. The (n, k)-star graph has n!/(n-k)! nodes and removes the restriction of number of nodes n! in the n-star graph, and preserves many attractive properties of the n-star graph such as node symmetry, hierarchical structure, maximal fault tolerance and simple shortest routing. The (n, k)-star graph's two parameters n and k can be tuned to make a suitable choice for the number of nodes in the interconnection network. This allows more flexibility in designing network topology than the star graph. In this paper, we introduce a recursive method which constructs a Hamiltonian cycle of (n, k)-star graph hierarchically.

재귀 대리 서명

김영설(Young-seol Kim),장직현(Jik-hyun Chang) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2C

대리서명은 원서명자의 서명 권한을 대리 서명자에게 위임하여 원서명자의 행위에 대해 서명할 수 있게 한 서명 방식이다. 이것은 일상생활에서 도장을 다른 사람에게 위임하는 것을 전자적으로 구현한 것이라 할 수 있다. 본 논문에서는 자기가 자신에게 서명 권한을 위임하는 방법을 통해 임시로 사용 할 수 있는 서명 키 쌍을 만들어내는 방법을 제안한다. 이 방법을 통해 원 서명 쌍을 보호할 수 있으며 동시에 여러쌍의 키들을 사용할 수 있으므로 작업들과 키 쌍들을 구분하여 관리할 수 있다. 또한 임시 서명 키 쌍의 폐기는 원 서명 키 쌍의 폐기보다 쉽기 때문에 제안하는 재귀 대리 서명은 실제적이라 할 수 있다.

Knapsack 문제에 대한 효율적인 병렬 알고리즘

김경환(Kyeong Hwan Kim),장직현(Jik Hyun Chang) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.4

본 논문에서는 knapsack 문제에 대한 기존의 two-list 알고리즘에 분할 정복 방법과 정렬행렬을 도입한 병렬 알고리즘을 제안한다. 이 알고리즘은 CREW SM SIMD 모델에서 시간 복잡도 T=O(2 ⁿ/4), 하드웨어 복잡도 H=O(2 ⁿ/4)를 갖는다. 또 이 알고리즘에서는 T≤2 ⁿ/4)인 범위에서 T · H=O(2 ⁿ/2))이고 T≥2 ⁿ/4 인 범위에서 T · H³=O(2ⁿ)인 상반관계가 성립함을 보인다. In this paper, we propose a parallel algorithm based on a previously known two-list algorithm incorporating the divide-and-conquer method and sorted matrix for the knapsack problem. This algorithm achieves time complexity T=O(2 ⁿ /4) and hardware complexity H=O(2 ⁿ /4) on the CREW SM SIMD model. And we prove that there exists a time-hardware tradeoff T · H=O(2 ⁿ /2) when T≤2 ⁿ /4 and T · H³=O(2ⁿ) when T≥(2 ⁿ /4).

스타그래프상에서의 새로운 인덱싱 기법과 효율적인 자료전달

이정인(Jung Ihn Lee),장직현(Jik Hyun Chang) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.4

n!개의 노드로 구성된 n-스타 그래프상에서 기존에 제시된 정렬알고리즘의 시간복잡도는 O(n³log n)이고 복사와 팩킹 알고리즘의 시간복잡도는 O(n²)이다. 위 알고리즘에서는 스타그래프의 노드들은 역방향 사전식 순서를 유지하고 있다. 본 논문에서는 스타그래프의 노드의 기능을 강화하여 각 노드는 여러개의 자료를 각기 다른 링크를 사용하여 동시에 전달할 수 있도록 하였고 이를 효율적으로 이용할 수 있는 새로운 인덱싱기법을 제시하여 임의의 두 서브스타들간에 순서를 유지하며 자료를 상수시간에 전달할 수 있는 자료전달방법을 제시하였다. 또한 새로운 인덱싱기법과 자료전달기법을 이용하여 정렬 알고리즘의 시간복잡도는 O(n²log³n)으로, 복사와 팩킹 알고리즘의 시간복잡도는 O(n)으로 낮출 수 있음을 보였다. The time complexity of sorting, copying, and packing algorithm which have already been presented are O(n³log n), O(n²), and O(n²) respectively on the star graph with n! nodes. In these algorithms, nodes in the star graph are ordered in reverse lexicographic order In this paper functions of each node in the star graph are extended to sending multiple data through different links simultaneously, and a new indexing scheme using the extended functions efficiently is presented. We show that data communication between two arbitrary substars in order-preserving way can be done in constant time. By using the new indexing scheme and data communication, we show that the time complexity of sorting algorithm, copying and packing can be lowered to O(n²log³n), O(n), and O(n), respectively.

Shuffle-Exchange 네트워크를 이용한 사전머신

박찬일(Park Chan Il),장직현(Chang Jik Hyun) 한국정보과학회 1988 정보과학회논문지 Vol.15 No.6

A dictionary machine is a data structure which allows operations such as search, delete, update, insert, extract-maximum, and extract-minimum, etc., on the set of items each of which consists of a record and a key. We consider the dictionary machines. suitable for VLSI design, on shuffle-exchange network which is known to be adequate to the general purpose parallel computing. In this paper, we propose an improvement of an existing batch processing dictionary machine and a new pipeline processing dictionary machine which has faster response time and higher throughput than those of batch processing dictionary machines. 사전머신은 레코드와 키의 쌍으로 구성된 정보 단위를 키에 따라 검색, 삭제, 갱신, 삽입및 최대, 최소의 키 값을 갖는 레코드와 키의 쌍을 검색하여 삭제하는 명령어를 실행하는 자료 구조이다. 우리는 일반목적의 병렬계산에 유용성이 이미 알려진 shuffle-exchange 네트워크을 이용하여 VLSI 디자인에 적합한 사전머신을 구현한다. 본 논문에서는 기존의 일괄처리 형식의 사전머신보다 효율적인 일괄처리 형식의 사전머신을 제안하였으며, 이러한 일괄처리 형식의 사전머신들보다 빠른 응답과 높은 throughput을 얻는 새로운 파이프라인처리 형식의 사전머신을 제안하였다.

두 직교경로간의 교차수에 대한 밀착상한

이종욱(Lee Jong Wook),장직현(Chang Jik Hyun) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.9

두 직교경로간의 교차수의 상한을 구하는 문제에 대하여 Kant는 두 직교경로 P,Q간의 교차수는 P가 맨해턴 경로, 즉 │P│=1로 제한될 경우 많아야 ┌4│Q│/3┐임을 보였고[3], Wang et al.은 │P│=2일 경우 교차수가 많아야 2│Q│+1임을 보였다[6]. 여기서 │P│와 │Q│는 각각 P와 Q를 구성하는 맨해턴 경로의 갯수이다. 그러나 경로의 길이에 제한이 없는 일반적인 경우에는 아직 밀착 상한(tight upper bound)이 발견되지 않았고, 최근의 결과로 Wang et al.은 두 직교경로 P,Q(│P│≤│Q│)간의 교차수는 │P│ │Q│+└│P│/2┘+┌│Q│ /3┐이하임을 증명하였다. 본 논문에서는 일반적인 경우에 대한 두 직교 경로간의 교차수가 │P│≥1이고 │Q│≥1일때 │P││Q│+1이하이고 또한 이 값이 밀착상한임을 보였다. 이때 │P│=4이거나 │Q│=4인 경우는 제외되며 이 경우의 상한은 │P││Q│+2이다. Kant showed that the upper bound on the number of intersections between two rectangular path P,Q is ┌│4│Q/3┐ when P is restricted to a Manhattan path, that is │P│=1, where │P│(respectively │Q│) is the number of Manhattan paths in P(respectively Q)[3]. Wang et al. showed that the upper bound is 2│Q│+1 when P is restricted to a path with length two, that is │P│=2[6]. The tight upper bound in general case, however, is not found yet. The recent result given by Wang et al is that the number of intersections between two rectangular paths P and Q is less than or equal to │P│ │Q│+└│P/2┘+┌Q/3┐, where │P│≤│Q│ is assumed. In this paper, we show that the tight upper bound on the number of intersections between two rectangular paths P,Q is │P││Q│+1 except either │P│=4 or │Q│=4. In case of │P│=4 or │Q│=4, the tight upper bound is │P││Q│+2.

한 부류의 NP - complete 문제에 대한 Systolic 트리 알고리즘 (pp.673-676)

이혜영(Hye Young Lee),장직현(Jik Hyun Chang) 한국정보과학회 1987 한국정보과학회 학술발표논문집 Vol.14 No.2

본 논문에서는 NP-complete 문제의 하나인 knapsack problem을 트리 구조의 systolic array를 이용한 병렬 처리에 의하여 그 해를 구할 수 있는 여러가지 알고리즘을 제시한다. n-1 레벨의 완전 이진 트리 구조를 이용한 병렬 알고리즘은 O(2ⁿ)의 area complexity를 갖고 O(n) time 내에 knapsack problem의 해를 찾을 수 있다. 또한 이러한 모형을 이용하여 two-list 알고리즘과 four-table 알고리즘을 병렬 처리 할 수 있도록 구현 했으며, 이 알고리즘은 각각 O(2ⁿ/²)과 O(2ⁿ/⁴)의 area complexity를 가지고 O(2ⁿ/²) time complexity를 갖는다. 이러한 알고리즘을 약간 변형하여 같은 유형의 다른 NP-complete 문제를 유사한 방법으로 쉽게 해결 할 수 있다.

RSA 서명에 기반한 효율적인 공정한 예약과 교환 프로토콜

성인제(In-Jeu Sung),장직현(Jik Hyun Chang) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

우리는 RSA 서명에 기반한 효율적인 공정한 예약과 교환 프로토콜을 위해 검증 가능한 암호화를 일반화한 부분적인 검증 가능한 암호화를 제안한다. 부분적인 검증 가능한 암호화를 이용해서 서명에 대한 공정한 교환과 더불어 전자 계약 시 사전 계약이나 비행기 티켓에 대한 예약을 할 수 있도록 프로토콜을 확장했다. 또한 예약과 교환 시에 공정성을 보장하도록 했다. 이로써 우리는 공정한 교환 프로토콜의 교환 단계에서 발생하는 계산 양과 전송 양을 예약과 교환 단계로 분산시키는 효과를 얻었다. 그리고 마지막으로 Ateniese가 제안한 RSA 서명에 기반한 공정한 교환 프로토콜과 성능 비교를 하였다.

CRAP에서 O(1) 시간 오일러-투어 알고리즘과 응용

김영학(Young Hak Kim),장직현(Jik Hyun Chang) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.2

본 논문에서 n 개의 장점을 갖는 루트가 지정되지 않은 트리 T 가 주어질 때, 2차원 n x (n-1) CRAP에서 T의 오일러 투어를 생성하는 O(1) 시간 알고리즘을 제안한다. 다음에 임의의 정점 r 이 주어질 때, 2차원 (2n-1) x(2n-1) CRAP을 사용하여 정점 r 에서 시작하는 T의 오일러 투어의 정점들을 O(1) 시간에 순서적으로 나열한다. T의 정돈된 오일러 투어의 정점들을 사용하여 각 정점의 부모와 전위/후위 순회 번호, 각 정점을 루트로 하는 서브트리에서 정점들의 수, 그리고 각 정점의 레벨을 계산하는 기본적인 O(1) 시간 알고리즘들을 제안한다. 또한 포리스트를 이진트리로 변환하는 문제와 가장 근접한 공통 조상을 찾는 문제를 해결하기 위한 O(1) 시간 알고리즘을 설명한다. In this paper, given an unrooted tree T with n vertices, we propose an O(1) time algorithm for creating the Euler tour of T on a two-dimensional n x (n-1) CRAP. Then, given an arbitrary vertex r , we list in O(1) time the vertices of the Euler tour of T starting a vertex r on a two-dimensional (2n-1) x (2n-1) CRAP. Using the vertices of the ordered Euler tour of T, several basic O(1) time algorithms which compute the parent and the preorder/postorder number of each vertex, the number of vertices in the subtree rooted at each vertex, and the level of each vertex are proposed. Also, we present O(1) time algorithms which solve the problem of transforming a forest into a binary tree and the problem of finding lowest common ancestors.