피라미드의 재귀원형군에 대한 임베딩

김숙연(Sook-Yeon Kim),설성욱(Sung-ook Sul),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.3

본 논문에서는 최근 제안된 상호연결망인 재귀원형군에 피라미드를 임베딩하는 방법을 제시하며, 그 임베딩이 여러가지 비용 척도 면에서 최적임을 증명한다. 우선, 최적 팽창률을 갖는 일대일 임베딩을 제시하고, 연장률 2, 밀집률 2임을 보인다. 이 일대일 임베딩을 바탕으로 보다 적은 노드를 갖는 재귀원형군에 대한 최적 부하율의 다대일 임베딩을 제시하고, 연장률이 2임을 보인다. 제시한 일대일 임베딩과 다대일 임베딩은 피라미드의 각 헤라벨에 있는 노드들을 재귀원형군에 균일하게 분포시키며, 이 경우 연장률 2는 최적임을 보인다. 본 논문에서 제안한 임베딩을 이용해 피라미드 구조에서 작동하는 병렬 알고리즘을 재귀원형군 구조의 병렬 컴퓨터에서 효과적으로 사용할 수 있다. In this paper, we present embeddings of the pyramid into the recursive circulant, an interconnection network recently proposed. We also show that the costs of the embeddings are optimal. First, we produce an one-to-one embedding with the expansion of optimum, the dilation of two and the congestion of two, Then we modify this one-to-one embedding to a many-to-one embedding with the load factor of optimum and the dilation of two, These embeddings uniformly distribute the nodes on the same level of the pyramid into the recursive circulant. We also show that the dilation of two is optimal if the embedding distributes the nodes on the same level uniformly, These embeddings can be applied to implement algorithms, designed for pyramids, on a parallel computer of recursive circulant structure.

완전 이진 트리의 재귀 원형군에 대한 Embedding

김숙연(Sook-Yeon Kim),박정흠(Jung-Heum Park),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

본 논문에서는 divide and conquer 알고리즘을 효율적으로 수행할 수 있는 병렬구조인 완전 이진 트리를 최근에 [4]에서 제안한 병렬 컴퓨터 구조 재귀 원형군(recursive circulant) 에 다대일 embedding하는 문제를 다룬다. 레벨 n인 완전 이진 트리 T_n을 재귀 원형군 G(2^m,4), 1 ≤m≤n-1,에 load factor 가 최적 일때, dilation 2, congestion 2로 embedding할 수 있고 load factor가 최적 load factor+1일때, dilation 1, congestion 2로 embedding할 수 있음을 보인다. 이 결과를 완전 이진 트리에 에지가 첨가된 X-트리나 full ringed 트리에 확장하면 그것들도 load factor 2, dilation 2로 embedding될 수 있다.

크기 2n×2m 인 메쉬의 꼬인 큐브에 대한 임베딩

김숙연 ( Sook Yeon Kim ) 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4

하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 2 × 2m인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 4× 2m인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m이 짝수일 경우엔 크기 2ⁿ × 2m인 메쉬가 꼬인 큐브에 연장율 1, 확장율 2n?1로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 2ⁿ로 임베딩됨을 보인다 (1≤n≤m). The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m , a mesh of size 2× 2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 4 × 2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2ⁿ × 2m can be embedded into a twisted cube with dilation 1 and expansion 2n?1 for even m and with dilation 1 and expansion 2n for odd m where 1≤ n ≤ m.

무선 센서 네트워크에서 위치 측정을 위한 중점 기법

김숙연(Sook-Yeon Kim),권오흠(Oh-Heum Kwon) 한국정보과학회 2005 정보과학회논문지 : 정보통신 Vol.32 No.5

무선 센서 네트워크에서 노드들의 위치를 측정하는 문제는 사건탐지, 라우팅, 정보추적 등의 중요한 네트워크 기능을 수행하기 위해 필수적으로 해결해야 한다. 위치측정 문제는 노드들 간의 연결성이 알려져 있을 때 네트워크의 모든 노드의 위치를 결정하는 문제이다. 본 논문에서는 분산 알고리즘인 중점기법을 중앙 집중적인 알고리즘으로 확장한다. 확장된 알고리즘은 단순하다는 중점 기법의 장점을 지니면서도 각 미지 노드가 세 개 이상의 고정 노드들의 중첩된 전송 범위에 속해야 한다는 단점을 갖지 않는다. 본 논문의 알고리즘은 위치 측정 문제가 일차원 행렬 방정식으로 정형화 될 수 있음을 보여준다. 이러한 일차원 행렬 방정식이 유일한 해를 가짐을 수학적으로 증명함으로써 모든 미지 노드들의 위치를 유일하게 결정할 수 있음을 보인다. Localization in wireless sensor networks is essential to important network functions such as event detection, geographic routing, and information tracking. Localization is to determine the locations of nodes when node connectivities are given. In this paper, centroid approach known as a distributed algorithm is extended to a centralized algorithm. The centralized algorithm has the advantage of simplicity, but does not have the disadvantage that each unknown node should be in transmission ranges of three fixed nodes at least. The algorithm shows that localization can be formulated to a linear system of equations. We mathematically show that the linear system have a unique solution. The unique solution indicates the locations of unknown nodes are capable of being uniquely determined.

다중 메쉬의 꼬인 큐브에 대한 임베딩

김숙연(Sook-Yeon Kim) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.2

꼬인 큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광받아 왔다. 본 논문에서는 크기 2ⁿ×2<SUP>m</SUP>인 메쉬의 복사본 2ⁿ?¹ 개가 꼬인 큐브에 노드 중복없이 연장율 1로 임베딩될 수 있음을 보인다(1≤n≤m). 여기서 확장율은 m이 짝수이면 1이고 홀수이면 2이다. The twisted cube has received great attention because it has several superior properties to the hypercube that is widely known as a versatile parallel processing system. In this paper, we show that node-disjoint 2ⁿ?¹ meshes of size 2ⁿ×2<SUP>m</SUP> can be embedded into a twisted cube with dilation 1 where 1≤n≤m. The expansion is 1 for even m and 2 for odd m.

트래픽 흐름의 분할 전송을 허용하는 통신망에서 경로 보호 메커니즘들에 대한 비교 분석

김숙연(Sook- Yeon Kim),정민영(Min Young Chung),양선희(Sunhee Yang),이유경(Yoo- Kyoung Lee) 한국통신학회 2000 한국통신학회 학술대회논문집 Vol.2000 No.11

완전이진트리의 교차큐브에 대한 임베딩

김숙연(Sook-Yeon Kim) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.3

교차큐브는 하이퍼큐브의 변형으로서 하이퍼큐브의 절반정도의 지름을 가지는 등의 개선된 망성질을 가진다. N-노드 완전이진트리는 (N+1)-노드 교차큐브의 부그래프임이 알려져 있으나 [P. Kulasinghe and S. Bettayeb, 1995] 완전이진트리의 노드 개수가 교차큐브의 노드 개수보다 더 큰 경우에 대한 효과적인 임베딩 방법은 알려져 있지 않다. 본 논문에서는 N-노드 완전이진트리를 M-노드 교차큐브에 연장율 1, 부하율 「N/M」로 임베딩할 수 있음을 보인다(N > M ≥ 2). 여기서 연장율과 부하율은 최적이다. 본 논문에서 제시하는 임베딩 방법은 같은 레벨의 트리 노드들을 교차큐브의 노드들에 골고루 분포시키는 특징도 가지고 있다. 이 특징은 트리 구조 알고리즘을 교차큐브에서 레벨 단위로 실행할 때 특히 유용하다. The crossed cube, a variation of the hypercube, possesses a better topological property than the hypercube in its diameter that is about half of that of the hypercube. It has been known that an N-node complete binary tree is a subgraph of an (N+1)-node crossed cube [P. Kulasinghe and S. Bettayeb, 1995]. However, efficient embedding methods have not been known for the case that the number of nodes of the complete binary tree is greater than that of the crossed cube. In this paper, we show that an N-node complete binary tree can be embedded into an M-node crossed cube with dilation 1 and load factor 「N/M」, N > M ≥ 2. The dilation and load factor is optimal. Our embedding has a property that the tree nodes on the same level are evenly distributed over the crossed cube nodes. The property is especially useful when tree-structured algorithms are processed on a crossed cube in a level-by-level way.

네트워크 보안을 위한 정책 기반 망 관리에 대한 핵심 정책 정보 모델 적용

김숙연(Sook-Yeon Kim),김건량(Geon-Lyang Kim),김명은(Myung-Eun Kim),방효찬(Hyo-Chan Bang),김기영(Ki-Young Kim),장종수(Jong-Su Jang) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

본 논문에서는 네트워크 기반의 침입 탐지 및 대응을 위한 정책 기반 망 관리 (NS-PBNM : Network Security Policy Based Network Management)에 핵심 정책 정보 모델(PCIM :Policy Core Information Model) 을 적용하는 시스템 구현 방안을 제시한다. 이 시스템은 여러 장치를 유연성 있게 통합적으로 관리한다는 정책 기반 망 관리의 목적뿐만 아니라, 정책을 표현, 관리, 공유 및 재사용하는데 있어 호환성 및 확장성을 확보한다는 PCIM의 목적을 동시에 달성한다. 먼저 NS-PBNM의 구조를 제시하고 이 구조를 기반으로 PCIM을 적용하는 방안을 제시한다. PCIM은 네트워크 침입 탐지 및 대응이라는 기능을 수행하는 있어 네트워크 보안 정책 정보 모델로 확장된 후, 정책 서버의 정책 관리 도구와 정책 저장소의 구조를 결정한다.

다중 메쉬의 교차큐브에 대한 임베딩

김숙연(Sook-Yeon Kim) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.5

교차큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광 받아 왔다. 크기 4 × 2<SUP>m</SUP>인 메쉬의 복사본 두 개, 혹은 크기 8 × 2<SUP>m</SUP>인 메쉬의 복사본 네 개가 교차큐브에 연장율 1, 확장율 1로 임베딩 될 수 있음이 알려져 있다[Dong, Yang, Zhao, and Tang, 2008]. 그러나 양변의 길이가 모두 8 보다 큰 메쉬 다수 개가 교차큐브에 연장율 1, 확장율 1로 임베딩될 수 있는지는 알려진 바가 없다. 이 논문에서는 크기 2<SUP>n</SUP> × 2<SUP>m</SUP>인 메쉬의 복사본 2<SUP>n-1</SUP> 개가 교차큐브에 연장율 1, 확장율 1로 임베딩될 수 있음을 보인다, n≥ 1, m ≥ 3. 이 연구 결과는 연장율과 확장율이라는 주요 임베딩 측정 척도에서 최적이다. 또한 이 연구결과는 메쉬 구조를 가지는 다수 개의 작업을 교차큐브 구조를 가지는 병렬 컴퓨터에 할당하는데 효과적으로 활용될 수 있다. The crossed cube has received great attention because it has equal or superior properties compared to the hypercube that is widely known as a versatile parallel processing system. It has been known that disjoint two copies of a mesh of size 4 × 2<SUP>m</SUP> or disjoint four copies of a mesh of size 8 × 2<SUP>m</SUP> can be embedded into a crossed cube with dilation 1 and expansion 1 [Dong, Yang, Zhao, and Tang, 2008]. However, it is not known that disjoint multiple copies of a mesh with more than eight rows and columns can be embedded into a crossed cube with dilation 1 and expansion 1. In this paper, we show that disjoint 2<SUP>n-1</SUP> copies of a mesh of size 2<SUP>n</SUP> × 2<SUP>m</SUP> can be embedded into a crossed cube with dilation 1 and expansion 1 where n ≥ 1 and m ≥ 3. Our result is optimal in terms of dilation and expansion that are important measures of graph embedding. In addition, our result is practically usable in allocating multiple jobs of mesh structure on a parallel computer of crossed cube structure.

디자인 씽킹을 기반으로 저시력자를 고려한 UX 디자인 프로세스의 역할에 관한 고찰 -외국어 학습 애플리케이션에서 가독성 사례를 중심으로-

민재연(Min, Jae Yeon),김숙연(Kim, Sook Yeon) 한국전시산업융합연구원 2020 한국과학예술융합학회 Vol.38 No.5

디지털 시대를 맞아 4차 산업혁명의 등장으로 현대사회가 변화하고 있다. 유통, 공공사업, 교육 등 다양한 분야에서 디지털과 물리적 세계의 융합이 이뤄질 전망이다. 특히 교육현장은 기술을 접목해 디지털 혁명을 통한 다양한 디지털 교육 응용프로그램을 출시하고 있다. 그러나 저시력자는 웹과 모바일과 같은 디지털 환경의 주요 사용자로 간주되지 않는다. 그래서 모바일 환경에서 콘텐츠나 텍스트를 인식하기 어려워 디지털 격차가 발생한다. 본 연구는 모바일 애플리케이션에서 제공되는 UX 디자인이 저시력 사용자를 배제한다는 문제를 제기하며 UX 디자인 프로세스의 역할에 대해 논의하는 것으로 시작됐다. 본 연구의 목적은 인문학적 관점에서 디자인 씽킹을 바탕으로 저시력자의 가독성을 고려한 UX 디자인 프로세스의 역할을 논하는 것이다. 따라서 본 논문은 기존의 웹 접근성과 선행 연구를 통해 학습 애플리케이션을 분석하고 문제점을 도출한 후, 디자인 씽킹을 바탕으로 보완된 UX 디자인 프로세스의 역할에 대한 검토를 제안하고자 시도하였다. 연구 결과 및 내용은 다음과 같다. 첫째, 본 논문은 인문학적 관점에서 본 디자인 씽킹을 바탕으로 모바일 환경에서 저시력자를 이해할 수 있는 범위와 가능성을 확대했다. 둘째, 과학기술정보통신부의 응용 사례와 보고 사례비교 분석을 통해 저시력자가 경험한 문제를 도출했다. 셋째, 디자인 씽킹과 UX 디자인 프로세스의 융합은 인문학적 관점을 통해 UX 프로세스에 저시력 사용자가 포함될 수 있다는 가능성을 시사했다. 이러한 연구를 바탕으로 다양한 분야의 애플리케이션에서 융합적 접근 방식을 통해 저시력자의 가독성을 고려해 UX 디자인 프로세스가 확대될 것으로 기대된다. In the face of digital era, modern society is changing with the emergence of the Fourth Industrial Revolution. It is predicted that convergence of digital and physical worlds will take place in various fields such as distribution, public works, and education. In particular, the field of education is releasing a variety of digital educational applications through a digital revolution by combining technology. However, people with low vision are not considered as major users of digital environments such as the web and mobile. So, they have a hard time recognizing contents or texts in their mobile environment, thus resulting in digital gaps. This study began with discussing the role of the UX design process, raising the issue that the UX design offered in mobile applications excludes users with low vision. The purpose of this study is to discuss the role of the UX design process, which takes into account the readability of people with low vision, based on design thinking from humanistic perspective. Hence, this paper tried to analyze the learning application and draw up problems through existing web accessibility and prior studies, and then to propose a review on the role of the complemented UX design process based on design thinking. The results and content of the study are as follows: First, based on the design thinking from the humanistic perspective, this paper expanded the scope and the possibility of understanding people with low vision in the mobile environment. Second, through comparative analysis of cases of applications and reports by the Ministry of Science and ICT, the problems experienced by low vision people were derived. Third, the convergence of design thinking and UX design processes suggested the possibility that the UX process could include users with low vision through the humanistic perspective. Based on these studies, it is expected that the UX design process expands by considering the readability of people with low vision through a converged approach in applications in various fields.