조기은퇴제도를 위한 자금조달문제

이상운,Lee, Sang-Un 한국인터넷방송통신학회 2021 한국인터넷방송통신학회 논문지 Vol.21 No.3

본 논문은 조기퇴직자들의 퇴직금을 충당하는데 있어 최소의 초기 투자금만으로 최대의 재태크로 인한 수익금으로 충당하는 방법을 다룬다. 이 문제에 대해 Guéret et al.은 Mosel 프로그램을, Edvall은 해를 찾아가는 명확한 규칙없이 단지 CPLEX Branch-and-Cut MIP Solver 프로그램을 구현하여 해를 얻었다. 본 논문에서는 이 문제에 대해 만기도래기간이 긴 채권부터 역으로 채권 수를 결정하는 계산식을 제시하고, 채권 만기도래의 연속적 효과를 고려하여 채권 수 최적화를 수행하여 채권 수를 확정하였으며, 부족액은 역으로 1년만기 적금의 원금과 이자로 충당하는 계산식을 제시하였다. This paper deals with financing an early retirement scheme problem(FERSP) with minimum initial cash and filling up maximum financial interest. For this problem, Guéret et al. programming the Mosel, and Edvall merely realize the CPLEX Branch-and-Cut MIP Solver program to get the optimal solution. But there is no clear rule to finding the solution. This paper suggests calculation formula of bond number decision-making that the reverse from long arrival due date to short. Then we optimize and confirm the bonds number in accordance with continuative effect of the arrival due date. The shortage prepare with the principal and interest of one year deposit(saving) reversely calculation formula.

비대칭키 RSA의 ??(n) 해독을 위한 역 아기걸음- 2^k-ary 성인걸음법

이상운,Lee, Sang-Un 한국인터넷방송통신학회 2014 한국인터넷방송통신학회 논문지 Vol.14 No.6

When the public key e and the composite number n=pq are disclosed but not the private key d in an asymmetric-key RSA, message decryption is carried out by obtaining ${\phi}(n)=(p-1)(q-1)=n+1-(p+q)$ and subsequently computing $d=e^{-1}(mod{\phi}(n))$. The most commonly used decryption algorithm is integer factorization of n/p=q or $a^2{\equiv}b^2$(mod n), a=(p+q)/2, b=(q-p)/2. But many of the RSA numbers remain unfactorable. This paper therefore applies baby-step giant-step discrete logarithm and $2^k$-ary modular exponentiation to directly obtain ${\phi}(n)$. The proposed algorithm performs a reverse baby-step and $2^k$-ary adult-step. As a results, it reduces the execution time of basic adult-step to $1/2^k$ times and the memory $m={\lceil}\sqrt{n}{\rceil}$ to l, $a^l$ > n, hence obtaining ${\phi}(n)$ by executing within l times. 비대칭키 RSA의 공개키 e와 합성수 n=pq은 알고 있고 개인키 d를 모를 때, ${\phi}(n)=(p-1)(q-1)=n+1-(p+q)$을 구하여 $d=e^{-1}(mod{\phi}(n))$으로 개인키 d를 해독한다. 암호해독은 일반적으로 n/p=q 또는 $a^2{\equiv}b^2$(mod n), a=(p+q)/2,b=(q-p)/2를 구하는 소인수 분해법이 널리 적용되고 있다. 그러나 아직까지도 많은 RSA 수들이 해독되지 않고 있다. 본 논문은 ${\phi}(n)$을 직접 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 이산대수의 아기걸음-거인걸음법과 모듈러 지수연산의 $2^k$-ary법을 적용하였다. 이 알고리즘은 역-아기걸음과 $2^k$-ary 성인걸음법을 적용하여 기본적인 성인걸음법 수행횟수를 $1/2^k$로 줄이고, $m={\lfloor}\sqrt{n}{\rfloor}$의 저장 메모리 용량도 l, $a^l$ > n로 감소시켜 ${\phi}(n)$을 l회 이내로 구하였다.

최소 되먹임 간선 집합 문제 알고리즘

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

본 논문은 되먹임 집합 문제인 무방향 그래프의 정점과 간선, 방향 그래프의 노드와 호 문제들 중 간선 문제에 한정한 최소 원소개수 되먹임 간선 집합과 최소 가중치 되먹임 간선 집합 문제의 최적 해를 다항시간으로 얻는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프의 간선 집합은 최대신장트리 간선 집합과 최소 되먹임 간선집합의 합이 되는 특성을 적용하였다. 즉, 최소 되먹임 간선집합은 최대신장트리 간선 집합의 여집합인 특성이 있다. 제안된 알고리즘은 최소신장트리를 얻는 Kruskal 알고리즘을 변형시켜 간선들의 가중치를 내림차순으로 정렬시켜 사이클이 발생하지 않는 간선은 최대신장트리 간선 집합 MXST로, 사이클이 발생하는 간선은 되먹임 간선 집합 FES로 양분하는 방법으로 최적 해를 얻었다. 제안된 알고리즘은 그래프의 간선 수 만큼 수행하는 선형시간 복잡도를 갖는 특징이 있다. 간선 가중치가 없는 경우와 가중치가 있는 다양한 무방향 그래프에 제안된 알고리즘을 적용한 결과 100% 쉽게 최적 해를 얻는데 성공하였다. This paper presents a polynomial time algorithm to the minimum cardinality feedback edge set and minimum weight feedback edge set problems. The algorithm makes use of the property wherein the sum of the minimum spanning tree edge set and the minimum feedback edge set equals a given graph’s edge set. In other words, the minimum feedback edge set is inherently a complementary set of the former. The proposed algorithm, in pursuit of the optimal solution, modifies the minimum spanning tree finding Kruskal’s algorithm so as to arrange the weight of edges in a descending order and to assign cycle-deficient edges to the maximum spanning tree edge set MXST and cycle-containing edges to the feedback edge set FES. This algorithm runs with linear time complexity, whose execution time corresponds to the number of edges of the graph. When extensively tested on various undirected graphs both with and without the weighed edge, the proposed algorithm has obtained the optimal solutions with 100% success and accuracy.

최소신장트리를 이용한 무방향 그래프의 점대점 최단경로 탐색 알고리즘

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

본 논문은 실시간 GPS 항법시스템에서 최단경로 탐색에 일반적으로 적용되고 있는 Dijkstra 알고리즘을 양방향 통행로(무방향그래프)로만 구성된 도로에 적용하고 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 방향 그래프에서 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단경로를 결정하기 때문에 알고리즘 수행에 많은 메모리가 요구되어 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 무방향 그래프에 적합하도록 출발과 목적지 정점을 제외한 경로 정점들에 대해 최단경로를 설정하고, 출발 정점부터 시작하여 정점 유출 간선들에 대해 최단경로 설정 간선들과 일치하는 간선들을 모두 선택하는 방식으로 한 번에 다수의 정점들을 탐색하는 방법을 택하였다. 9개의 다양한 무방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 약 60%를 단축시키는 효과를 얻었으며, 알고리즘 수행에 필요한 메모리도 월등히 적게 요구되었다. This paper proposes a modified algorithm that improves on Dijkstra's algorithm by applying it to purely two-way traffic paths, given that a road where bi-directional traffic is made possible shall be considered as an undirected graph. Dijkstra's algorithm is the most generally utilized form of shortest-path search mechanism in GPS navigation system. However, it requires a large amount of memory for execution for it selects the shortest path by calculating distance between the starting node and every other node in a given directed graph. Dijkstra's algorithm, therefore, may occasionally fail to provide real-time information on the shortest path. To rectify the aforementioned shortcomings of Dijkstra's algorithm, the proposed algorithm creates conditions favorable to the undirected graph. It firstly selects the shortest path from all path vertices except for the starting and destination vertices. It later chooses all vertex-outgoing edges that coincide with the shortest path setting edges so as to simultaneously explore various vertices. When tested on 9 different undirected graphs, the proposed algorithm has not only successfully found the shortest path in all, but did so by reducing the time by 60% and requiring less memory.

요구사항 변경이 확정가 프로젝트 계획에 미치는 영향

이상운,Lee, Sang-Un 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.6

요구사항이 빈번히 변경되는 동적 비즈니스 시스템 프로젝트를 확정가로 개발할 경우, 개발과정에서 발생하는 요구사항의 변경에 따른 추가 소요 비용으로 인해 확정가 범위 이내로 개발을 완료하는 것은 거의 불가능하다. 확정가 범위 이내에서 성공적으로 프로젝트를 완료하기 위해서는 요구사항 변경 규모와 이에 기반하여 개발이 되지 않아도 되는 옵션 요구사항의 비율을 관리하여야 한다. 이에 대해 Bhagwat는 요구사항 변경이 구축단계에서만 발생한다고 한정하였다. 또한, 소프트웨어 개발비용, 구축단계 소요 비용과 요구사항 변경에 소요되는 추가 비용이 동일하다고 가정함으로써 요구사항 변경 비율과 옵션 요구사항의 비율 유도의 모순을 보였다. 본 논문은 요구사항 변경은 정련단계와 구축단계에서 발생한다고 가정하였다. 또한, 소프트웨어 개발비용, 구축단계 소요 비용과 요구사항 변경 비용간에는 차이가 발생한다고 가정하였다. 그 결과 확정가 대비 요구사항 변경에 따른 추가 소요 비용과 개발이 되지 않아도 되는 옵션 요구사항의 비율도 보다 현실성을 반영하는 결과를 얻을 수 있었다. To develop a dynamic system project in which the requirement changes frequently, it's impossible to finish the development within a fixed-cost due to additional budget occurring in need of requirement creep. To manage the successive project within a fixed-cost, it's better to manage the ratio of necessarily changed size of project and necessary optional requirement. According to Bhagwat, it is occurred in the construction phase. Also, he stated that the software development cost, construction phase cost and requirement cost are equal and it was wrong explanation in the ratio of requirement creep and optional requirement. This paper assumes the requirement creep to be happening in the phase of elaboration and construction. In addition, some differences were supposed to happen between software development cost, construction phase cost, and requirement creep cost. As a result, the reality was preferred rather than the ratio of optional requirement and the ratio of requirement creep.

최대 매칭 문제의 최소차수 정점 간 간선 선택 알고리즘

이상운,Lee, Sang-Un 한국인터넷방송통신학회 2022 한국인터넷방송통신학회 논문지 Vol.22 No.5

This paper deals with the maximum cardinality matching(MCM) problem. The augmenting path technique is well known in MCM. MCM is obtained by $O({\sqrt{n}}m)$ time complexity augmenting path algorithm for the general graph, and O(m log n) algorithm for the bipartite graph. On the other hand, this paper suggests O(n) linear time algorithm. The proposed algorithm based on the basic principle of as possible as largest selected inter-vertex edges in order to obtain the MCM. This paper simply selects edge {u,𝜐} that the minimum degree vertex u and minimum degree vertex 𝜐 in N_G(u) 𝜈(G)=k times iteration. For various general and bipartite graphs experimental data, this algorithm can be get the 𝜈(G) exactly.

도메틱 수 문제에 관한 최대차수 정점 지배집합 알고리즘

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

최대 지배집합의 수인 도메틱 수 문제 (DNP)는 정확한 해를 다항시간으로 구하는 알고리즘이 존재하지 않아 NP-완전 문제로 알려져 있다. 본 논문은 DNP의 해를 다항시간으로 구하는 알고리즘을 제안하였다. 그래프의 최대 차수 Δ(G) 정점 vi를 Di, i = 1,2,?,k의 지배집합의 원소로 선택하는 방법을 적용하고, Vi+1 = Vi?Di의 축소된 그래프에 대해 Di+1을 구하였다. 또한 V?Di = NG(Di)가 지배집합으로 되는지 여부를 검증하였다. 제안된 알고리즘을 15개의 다양한 그래프에 적용한 결과 정확한 해를 다항시간 복잡도 O(kn)으로 구하는데 성공하였다. 결국, 제안된 알고리즘은 도메틱 수 문제가 P-문제임을 보였다. In the absence of a polynomial time algorithm capable of obtaining the exact solutions to it, the domatic number problem (DNP) of dominating set (DS) has been regarded as NP-complete. This paper suggests polynomial-time complexity algorithm about DNP. In this paper, I select a vertex vi of the maximum degree Δ(G) as an element of a dominating set Di, i = 1,2,?,k, compute Di+1 from a simplified graph of Vi+1 = Vi?Di, and verify that Di is indeed a dominating set through  V?Di = NG(Di). When applied to 15 various graphs, the proposed algorithm has succeeded in bringing about exact solutions with polynomial-time complexity O(kn). Therefore, the proposed domatic number algorithm shows that the domatic number problem is in fact a P-problem.

그룹 고장 데이터의 소프트웨어 신뢰성 예측에 관한 신경망 모델

이상운,박영목,박수진,박재흥,Lee, Sang-Un,Park, Yeong-Mok,Park, Soo-Jin,Park, Jae-Heung 한국정보처리학회 2000 정보처리논문지 Vol.7 No.12

많은 소프트웨어 프로젝트는 시험이나 운영단계에서 고장 시간이나 고장 수 데이타 보다는 그룹 고장 데이타 (여러 고장 간격에서 또는 가변적인 시간 간격에서의 고장 들)가 수집된다. 본 논문은 그룹 고장 데이타에 대해 가변적인 미래의 시간에서 누적 고장 수를 예측할 수 있는 신경망 모델을 제시한다. 신경망의 입-출력으로 무엇을 선택하고 어떤 순서로 훈련을 수행하느냐에 따라 신경망의 예측력에 영향을 미친다. 따라서, 신경망의 입-출력에 대한 11개의 훈련제도가 고려되었으며, 모델의 성능을 평가하기 위해 다음 단계 평균 상대 예측 오차 (AE)와 정규화된 AE (NAE) 측도에 의해 최적의 훈련제도가 선택되고, 다른 잘 알려진 신경망 모델과 통계적 소프트웨어 신뢰성 성장 모델과 비교되었다. 실험 결과, 가변적인 미래의 시간 간격에서 누적 고장 수를 예측하기 위해서는 신경망 모델에 가변 시간간격 정보가 필요함을 보였다. Many software projects collect grouped failure data (failures in some failure interval or in variable time interval) rather than individual failure times or failure count data during the testing or operational phase. This paper presents the neural network (NN) modeling that is dble to predict cumulative failures in the variable future time for grouped failure data. ANN's predictive ability can be affected by what it learns and in its ledming sequence. Eleven training regimes that represents the input-output of NN are considered. The best training regimes dre selected rJdsed on the next' step dvemge reldtive prediction error (AE) and normalized AE (NAE). The suggested NN models are compared with other well-known KN models and statistical software reliability growth models (SHGlvls) in order to evaluate performance, Experimental results show that the NN model with variable time interval information is necessary in order to predict cumulative failures in the variable future time interval.

소프트웨어 시험 노력 추정 시그모이드 모델

이상운,Lee, Sang-Un 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.4

소프트웨어 시험단계에 투입되는 노력의 분포를 추정하는 대표적인 모델로 Weibull 분포(Rayleigh와 지수분포 포함)가 있다. 이 모델은 시험 시작시점에서 실제로 많은 노력이 투입되는 점을 표현하지 못한다. 또한 다양한 형태를 갖고 있는 실제 시험 노력의 분포를 적절히 표현하지 못하고 있다. 이러한 문제점을 해결하기 위해 본 논문은 시그모이드 모델을 제안하였다. 신경망 분야에서 적용되고 있는 시그모이드 함수로부터 소프트웨어 시험 노력을 적절히 표현할 수 있도록 함수 형태를 변형시켰다 제안된 모델은 다양한 분포 형태를 보이고 있는 실제 수행된 소프트웨어 프로젝트로부터 얻어진 6개의 시험 노력 데이터에 적용하여 적합성을 검증하였다. 제안된 시그모이드 모델은 기존의 Weibull 모델보다 성능이 우수하여 소프트웨어 시험노력을 추정하는데 있어 와이블 모델의 대안으로 채택될 수 있을 것이다. Weibull distribution Iincluding Rayleigh and Exponential distribution is a typical model to estimate the effort distribution which is committed to the software testing phase. This model does not represent standpoint that many efforts are committed actually at the test beginning point. Moreover, it does not properly represent the various distribution form of actual test effort. To solve these problems, this paper proposes the Sigmoid model. The sigmoid function to be applicable in neural network transformed into the function which properly represents the test effort of software in the model. The model was verified to the six test effort data which were got from actual software projects which have various distribution form and verified the suitability. The Sigmoid model nay be selected by the alternative of Weibull model to estimate software test effort because it is superior than the Weibull model.

라운드-로빈 홈 앤드 어웨이 스포츠 리그 대진표 작성 정규형 라틴 방진 알고리즘

이상운,Lee, Sang-Un 한국인터넷방송통신학회 2018 한국인터넷방송통신학회 논문지 Vol.18 No.4

The home-and-way round-robin sports leagues scheduling problem with minimum brake is very hard to solve in polynomial time. This problem is NP-hard, the complexity status is not yet determined. This paper suggests round-robin sports leagues scheduling algorithm not computer-aided program but by hand with O(n) time complexity for arbitrary number of teams n with always same pattern. The algorithm makes a list of mathes using $n{\times}n$ canonical latin square for n=even teams. Then trying to get home(H) and away(A) with n-2 minimum number of brakes. Also, we get the n=odd scheduling with none brakes delete a team own maximum number of brakes from n=even scheduling. 최소 제동 수를 갖는 홈 앤드 어웨이 라운드-로빈 경기일정 대진표를 작성하는 문제는 매우 어려워 NP-난제로 알려져 있다. 본 논문에서는 임의의 팀 수 n에 대해서도 항상 동일한 패턴으로 경기일정 대진표를 O(n) 수행 복잡도로 컴퓨터 프로그램 도움 없이 직접 손으로 작성할 수 있는 알고리즘을 제안하였다. 제안된 알고리즘은 n=even 팀에 대해 $n{\times}n$ 정규형 라틴 방진을 작성하여 대진표를 작성하고, 최소 제동 수가 n-2 가 되도록 홈-어웨이를 배정하였다. 또한, n=odd에 대해서는 n=even 결과에서 최대 제동 수를 갖는 n번째 팀을 삭제하는 방법으로 제동이 전혀 없는 대진표를 작성하였다.