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

김숙연(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

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.

게이미피케이션을 기반으로 학습동기의 향상을 위한 UX 디자인 연구: 외국어 학습 애플리케이션에서 보상 사례를 중심으로

민재연(Jae Yeon Min),김숙연(Sook Yeon Kim) 한국HCI학회 2021 한국HCI학회 학술대회 Vol.2021 No.1

사회, 문화, 교육 등과 같은 여러 분야에서 발생하는 문제에 대해 게이미피케이션(Gamification)은 게임요소를 적용하여 문제를 해결하는 방법으로 사용되었다. 특히, 교육 분야에서는 학습자의 학습 동기를 유발하여 학습 성과의 향상을 위해 게이미피케이션을 활용하고 있다. 본고는 학습 애플리케이션에서 사용되는 게이미피케이션의 보상 요소가 학습 동기를 향상하기 위해 어떻게 활용되어야 하는지에 대한 UX 디자인 연구를 진행했다. 특히, ARCS 이론을 바탕으로 동기의 향상을 위해 사용되는 보상(Reward) 요인에 대한 사례 분석을 진행했다. 따라서, 본 연구는 학습 분야의 애플리케이션이 게이미피케이션을 활용하여 학습자의 동기를 향상하기 위한 UX 디자인에 대해 제언한다.

디자인 씽킹을 기반으로 저시력자를 고려한 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.

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

김숙연,Kim, Sook-Yeon 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.6

교차큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선 된 망 성질들을 가지므로 각광 받아 왔다. 크기가 $2{\times}2^m$이거나 $4{\times}2^m$인 메쉬를 연장율 1로 교차큐브에 임베딩하는 연구 결과는 이미 발표된바 있다. 그러나 양변의 길이가 모두 8 이상인 메쉬가 교차큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 크기 $2^n{\times}2^m$인 메쉬가 교차큐브에 연장율 1, 확장율 $2^{n-1}$로 임베딩될 수 있음을 보인다, $n{\geq}1$, $m{\geq}3$. The crossed cube has received great attention because it has equal or superior properties to the hypercube that is widely known as a versatile parallel processing system. It has been known that a mesh of size $2{\times}2^m$ can be embedded into a crossed cube with dilation 1 and expansion 1 and a mesh of size $4{\times}2^m$ with dilation 1 and expansion 2. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a crossed cube with dilation 1. In this paper, we show that a mesh of size $2^n{\times}2^m$ can be embedded into a crossed cube with dilation 1 and expansion $2^{n-1}$ where $n{\geq}1$ and $m{\geq}3$.

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

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

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{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size $4{\times}2^m$ 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^n{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion $2^{n-1}$ for even m and with dilation 1 and expansion $2^n$ for odd m where $1{\leq}n{\leq}m$. 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 $2{\times}2^m$인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 $4{\times}2^m$인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m 이 짝수일 경우엔 크기 $2^n{\times}2^m$인 메쉬가 꼬인 큐브에 연장율 1, 확장율 $2^{n-1}$ 로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 $2^n$로 임베딩됨을 보인다 ($1{\leq}n{\leq}m$).

무선 센서 네트워크에서 에지 가중치를 이용하여 위치를 측정하는 기법

김숙연,권오흠,Kim Sook-Yeon,Kwon Oh-Heum 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.10A

무선 센서 네트워크에서 위치측정 문제는 위치가 알려진 일부 고정 노드들을 기준으로 나머지 노드들의 위치를 결정하는 문제이다. 기존의 많은 위치 측정 기법들은 고정 노드들로부터의 거리나 각도의 측정값을 기반으로 multilateration 이나 삼각기법(triangulation)을 사용한다. 본 논문에서는 서로 전송 범위 내에 있는 노드 쌍에 대해서 가중치를 주어 미지 노드들의 위치를 계산하는 새로운 중앙 집중적 알고리즘을 제안한다. 본 기법은 단순하다는 장점을 지니며, 위치 측정 문제가 일차원 행렬 방정식으로 정형화 될 수 있음을 보여준다. 이러한 일차원 행렬방정식이 유일한 해를 가짐을 수학적으로 증명함으로써 모든 미지 노드들의 위치를 유일하게 결정할 수 있음도 보인다. 가중치는 다양하게 설정될 수 있으나 현실적으로 활용될 수 있을 만한 세 가지 가중치 설정 방법을 제시한 후 시뮬레이션을 통해 성능을 비교 분석한다. Localization in wireless sensor networks is to determine the positions of all nodes based on the Down positions of several nodes. Much previous work for localization use multilateration or triangulation based on measurement of angles or distances to the fixed nodes. In this paper, we propose a new centralized algorithm for localization using weights of adjacent nodes. The algorithm, having the advantage of simplicity, shows that the localization problem can be formulated to a linear matrix equalities. We mathematically show that the equalities have a unique solution. The unique solution indicates the locations of unknown nodes are capable of being uniquely determined. Three kinds of weights proposed for practical use are compared in simulation analysis.

에지 고장이 있는 Restricted Hypercube-Like 그래프의 해밀톤 경로

김숙연,전병태,Kim, Sook-Yeon,Chun, Byung-Tae 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.6

Restricted Hypercube-Like(RHL) 그래프는 교차큐브, 뫼비우스큐브, 엠큐브, 꼬인큐브, 지역꼬인큐브, 다중꼬인큐브, 일반꼬인큐브와 같이 유용한 상호연결망들을 광범위하게 포함하는 그래프군이다. 본 논문에서는 $m{\geq}4$ 인 m-차원 RHL 그래프 G에 대해서 임의의 에지 집합 $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, 가 고장일 때, 고장 에지들을 제거한 그래프 $G{\setminus}F$는 임의의 서로 다른 두 정점 s와 t에 대해서 dist(s, V(F))${\neq}1$ 이거나 dist(t, V(F))${\neq}1$이면 해밀톤 경로가 있음을 보인다. V(F)는 F에 속하는 에지들의 양 끝점들의 집합이고 dist(v, V(F))는 정점 v와 집합 V(F)의 정점들 간의 최소 거리이다. Restricted Hypercube-Like (RHL) graphs are a graph class that widely includes useful interconnection networks such as crossed cube, Mobius cube, Mcube, twisted cube, locally twisted cube, multiply twisted cube, and generalized twisted cube. In this paper, we show that for an m-dimensional RHL graph G, $m{\geq}4$, with an arbitrary faulty edge set $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, graph $G{\setminus}F$ has a hamiltonian path between any distinct two nodes s and t if dist(s, V(F))${\neq}1$ or dist(t, V(F))${\neq}1$. Graph $G{\setminus}F$ is the graph G whose faulty edges are removed. Set V(F) is the end vertex set of the edges in F and dist(v, V(F)) is the minimum distance between vertex v and the vertices in V(F).

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

김숙연(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.