단순한 차수 제약 최소신장트리 알고리즘

이상운(Sang-Un Lee) 한국정보기술학회 2015 한국정보기술학회논문지 Vol.13 No.10

The degree-constrained minimum spanning tree(DCMST) is a special case of MST, which is also an important problem in network design. There has been unknown polynomial time algorithm for DCMST that is one of the NP-complete problem. Therefore metaheuristic method has been applied this problem to obtain approximated solution. This paper suggests an polynomial time heuristic algorithm to solve a DCMST with degree range d<SUB>L</SUB>≤d≤ d<SUB>H</SUB> . The d<SUB>H</SUB> DCMST is decided by minimum spanning tree. The 3≤d ≤d<SUB>H</SUB>-1DCMST is obtained by 1-opt edge swap method that has reduced one degree from MST step-by-step. Also, d<SUB>L</SUB>=2 Hamiltonian path DCMST can be obtain using k-opt (k=1,2,3) method. Empirical evaluation using eight benchmarking data of SHRD series, the proposed algorithm outperforms well-known optimal solution.

창의성 : 조직의 창의성 향상 방법, 여섯 색깔 모자 방법(회의 기법)과 기술 혁신 방법, 트리즈

이상운 ( Sang Woon Lee ),이경원 ( Kyeong Won Lee ),김원식 ( Won Sik Kim ) 한국지식경영학회 2005 지식경영 학술심포지움 Vol.14 No.-

위성 간 링크된 다중통신위성 일정계획 문제의 다항시간 알고리즘

이상운(Sang-Un Lee) 한국정보기술학회 2015 한국정보기술학회논문지 Vol.13 No.8

This paper deals with the time slot assignment problem (TSAP) that multi-satellite with intersatellite links (ISL) switches to traffic between 2n ground stations using on-board switching modes in SS/TDMA system. For this problem, there is only used to the linear programming (LP) or heuristic methods because there has been unknown the polynomial time algorithm to solve the optimal solution thus this problem has been classified as NP-hard. This paper suggests the algorithm with O(n)² time complexity to solve the optimal solution for this problem. Firstly, the proposed algorithm transforms the2n × 2n traffic matrix D into normalized D(ND) with all the rows and columns have the lower bound (LB) that is a maximum sum of traffic of rows or columns. Nextly, we select the maximum traffic of row and column in ISL first from ND matrix, then we select the other maximum traffic in nonoverlapping rows and columns. We decide the k th switch mode and the duration from the minimum traffic in the selected traffics. The proposed algorithm can be get the optimal solution for experimental data.

제곱-나눗셈 모듈러 지수연산법

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.4

암호학의 암호 생성과 해독, 소수판별법의 성능은 대부분 a<SUP>b</SUP> (mod m)의 모듈러 지수연산의 효율적 구현여부로 결정된다. 모듈러 지수연산법에는 제곱-곱셈 방식의 표준 이진법이 최선의 선택으로 알려져 있다. 그러나 큰 자리수의 b에 대해서는 사전처리를 하는 n-ary, (n≥2)이 보다 효율적으로 적용된다. 본 논문에서는 모듈러 지수 나눗셈 방법을 적용한 제곱-나눗셈법과 사전처리 없는 n-ary 제곱-나눗셈법을 제안하였다. 제곱-나눗셈법은 b가 2<SUP>k</SUP>+2<SUP>k-1</SUP>에 근접한 값 또는 2<SUP>k+1</SUP>에 근접한 경우 수행횟수 측면에서 가장 효율적임을 알 수 있었다. 나머지 값들에 대해서는 사전처리 없는 n-ary 제곱-나눗셈법을 적용하는 것이 사전처리를 하는 일반적인 n-ary법에 비해 수행횟수 측면에서 효율적임을 보였다. The performance and practicality of cryptosystem for encryption, decryption, and primality test are primarily determined by the implementation efficiency of the modular exponentiation of a<SUP>b</SUP> (mod m). To compute a<SUP>b</SUP> (mod m), the standard binary squaring (square-and-multiply) still seems to be the best choice. However, in large b bits, the preprocessed n-ary, (n≥2) method could be more efficient than binary squaring method. This paper proposes a square-and-divide and unpreprocessed n-ary square-and-divide modular exponentiation method. Results confirmed that the square-and-divide method is the most efficient of trial number in a case where the value of b is adjacent to 2<SUP>k</SUP>+2<SUP>k-1</SUP> or to 2<SUP>k+1</SUP>. It was also proved that for b out of the beforementioned range, the unpreprocessed n-ary square-and-divide method yields higher efficiency of trial number than the general preprocessed n-ary method.

p-중앙 시설 위치선정 구성 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.6

본 논문은 n개의 행정구역으로 구성된 도시에 p개의 시설을 신규로 설치하는 경우, 비용이 최소가 되는 최적의 시설 위치를 선정하는 알고리즘을 제안하였다. 이 문제는 정확한 해를 찾는 다항시간 알고리즘이 제안되지 않아 NP-난제로 분류되어 있다. 제안된 방법은 p=[1,n-1]에 대해 먼저 노드들을 증가시키는 방법으로 p개를 선택하고, p번째 선택된 시설 위치를 교체하는 방법을 적용하여 기존의 Myopic 알고리즘의 단점을 개선하였다. 제안된 알고리즘은 n=5,7,10,55인 데이터에 적용한 결과 역-삭제 방법에 비해 최적 해에 가장 근사한 해를 구할 수 있었으며, 엑셀을 활용해 간단히 구현할 수 있는 장점도 있다. This paper proposes a location algorithm that locates newly built p-facilities in the optimal area with minimum cost in a city of n districts. This problem has been classified as NP-hard, to which no polynomial time algorithm exists. The proposed algorithm improves the shortcomings of existing Myopic algorithm by constructing until p-facilities and exchanging locations of p-th facility for p=[1,n-1]. When applied to experimental data of n=5,7,10,55 the proposed algorithm has obtained an approximate value nearest possible to the optimal solution take precedence of reverse-delete method. This algorithm is also simply executable using Excel.

경로설정과 파장 배정 문제의 독립집합 상자 채우기 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.1

본 논문은 광통신망에서 (s, t)에 대한 다중 패킷 통신 요구에 대해 최적의 광 경로를 설정하고, 최소 파장 수를 배정하는 경로설정과 파장 배정 문제 (RWAP)를 다룬다. RWAP는 지금까지 다항시간으로 최적 해를 구하는 알고리즘이 알려져 있지 않은 NP-완전으로 근사 해를 다항시간으로 구하고 있다. 본 논문은 주어진 망의 모든 (s, t)에 대해 최단 광 경로로 동일한 홉 수를 갖는 주경로와 대체경로를 사전에 결정하고, (s, t)에 대한 실제 특정 다중 패킷 통신이 요구될 때 이들 이중 경로를 이용하여 최대로 이용되는 간선의 이용횟수를 ?개로 줄이고, ?개의 파장 수 상자에 중복 간선 없이 담는 방법으로 O(kn) 계산 복잡도로 최적 해를 구할 수 있었다. 2개의 실험 데이터 망에 적용한 결과, 제안된 알고리즘은 기존에 알려진 최적 해를 얻을 수 있음을 보였다. This paper deals with the routing and wavelength assignment problem (RWAP) that decides the best lightpaths for multiple packet demands for (s, t) in optical communication and assigns the minimum number of wavelengths to given lightpaths. There has been unknown of polynomial-time algorithm to obtain the optimal solution for RWAP. Hence, the RWAP is classified as NP-complete problem and one can obtain the approximate solution in polynomial-time. This paper decides the shortest main and alternate lightpath with same hop count for all (s, t) for given network in advance. When the actual demands of communication for particular multiple packet for (s, t), we decrease the maximum utilized edge into b utilized number using these dual-paths. Then, we put these (s, t) into ?-wavelength bins without duplicated edge. This algorithm can be get the optimal solution within O(kn) computational complexity. For two experimental data, the proposed algorithm shows that can be obtain the known optimal solution.

가토 두개골 결손부 모델에서 테트라사이클린 함유 실크 파이브로인 차폐막의 골유도 재생 효과

이상운,박용태,김성곤,권해용,조유영,이희삼,Lee, Sang-Woon,Park, Yong-Tae,Kim, Seong-Gon,Kweon, HaeYong,Jo, You-Young,Lee, Heui Sam 대한악안면성형재건외과학회 2012 Maxillofacial Plastic Reconstructive Surgery Vol.34 No.5

Purpose: The aim of this study was to evaluate the bone regeneration ability of 1% tetracycline (TC)-loaded silk fibroin membrane (SFM), in a rabbit calvarial defect model. Methods: Twenty New Zealand white rabbits were used for this study. Bilateral round defects were made on the rabbit parietal bone, using trephine bur with an 8 mm diameter. TC-loaded SFM or SFM was covered on the right parietal bone defect, and the left parietal bone defects were uncovered for the control. The animals were humanely sacrificed at 4 or 8 weeks postoperatively. A micro-computerized tomography (${\mu}$-CT) of each specimen was taken for analysis of bone regeneration. Hematoxylin and Eosin stain were done to observe histological findings. Results: From the ${\mu}$-CT results, regenerated bone volume ($mm^3$) of 1% TC-loaded SFM, SFM, and control were $7.80{\pm}5.87$, $8.79{\pm}3.44$, and $10.61{\pm}5.3$ at 4 weeks postoperatively, respectively (P>0.05). Regenerated bone volume ($mm^3$) of 1% TC-loaded SFM, SFM, and control were $36.56{\pm}8.50$, $25.86{\pm}8.17$, and $19.09{\pm}5.07$ at 8 weeks postoperatively, respectively (P<0.05). Conclusion: The 1% TC-loaded SFM showed more bone regeneration than the SFM and the uncovered control, in guided bone regeneration.

안정된 동숙자 문제의 최소 선호도 합 알고리즘

이상운(Sang-Un Lee) 한국정보기술학회 2015 한국정보기술학회논문지 Vol.13 No.9

Given n participants each of whom offered preference data over n-1 other participants in a stable roommates problem, this problem can be usually solved by the Irving algorithm with O(n<SUP>2</SUP>) complexity. The Irving algorithm get the initial solution S in first phase using Gale-Shapley algorithm with O(n<SUP>2</SUP>) complexity. In second phase, this algorithm change the set S using iterative rotation. This paper proposes a O(n) algorithm for this problem. In the preprocessing phase, the algorithm computes the sum preference sum<SUP>ij</SUP> - the sum of p<SUB>i</SUB>’s preference over p<SUB>i</SUB> and p<SUB>i</SUB>’s preference over p<SUB>i</SUB> - from an upper triangular matrix of an n-1 × n matrix. In Step 1, it selects the minimum sum preference min s<SUB>ij</SUB> and runs n/2 times the deletion of row and columns i,j . It then performs an alternation process of Step 2, given no stable roommates are attainable in the presence of a blocking pair. When tested on 10 roommates problems, the proposed algorithm has successfully obtained optimal solutions with complexity of O(n).

시뮬링크를 기반으로 한 파워 트렁크 리드 시스템의 동역학 모델링 및 제어기 설계

이상운(Sang-Woon Lee),이재천(Jae-Cheon Lee),류하오(Hao Liu),최영일(Young-Il Choi),정병대(Byoung-Dae Jung),윤근하(Gun-Ha Yoon) 한국자동차공학회 2011 한국자동차공학회 부문종합 학술대회 Vol.2011 No.5

Nowadays PTL(Power Trunk Lid) system is used to provide convenience to drivers and passengers by supplying additional power for existing trunk lid. In the paper the mathematical dynamical model of a PTL system is first constructed, and the simulation without control is performed to show the process of the trunk lid opening. Next in order to operate the trunk lid smoothly and safely, based on the above analytical dynamic model a PI controller is designed by using Matlab/Simulink. The simulation results indicate that the trunk lid is properly controled in the process of open, stop and close, which is closed to the set speed profile.

RSA의 오일러 함수 ϕ(n) 해독 2<SUP>k</SUP>β 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.7

대표적인 공개키 암호방식인 RSA에 사용되는 합성수 n=pq의 큰자리 소수 p,q를 소인수분해하여 구하는 것은 사실상 불가능하다. 공개키 e와 합성수 n은 알고 개인키 d를 모를 때, ?(n)=(p-1)(q-1)=n+1-(p+q)을 구하여 d=e^* There is to be virtually impossible to solve the very large digits of prime number p and q from composite number n=pq using integer factorization in typical public-key cryptosystems, RSA. When the public key e and the composite number n are known but the private key d remains unknown in an asymmetric-key RSA, message decryption is carried out by first obtaining ?(n)=(p-1)(q-1)=n+1-(p+q) and then using a reverse function of d=e^*