뉴로-퍼지 소프트웨어 신뢰성 예측

이상운(Sang-Un Lee) 한국정보과학회 2000 정보과학회논문지 : 소프트웨어 및 응용 Vol.27 No.4

본 논문은 주어진 고장 데이타로부터 소프트웨어의 신뢰성 예측력 향상을 위해 뉴로-퍼지 시스템 연구를 수행하였다. 다른 소프트웨어로부터 수집된 10개의 고장 수 데이타와 4개의 고장시간 데이타에 대해 규칙의 수를 변경시키면서 다음 단계 예측을 실험하였다. 뉴로-퍼지 시스템의 예측력을 보이기 위해 다음 단계 예측에 대해 비교하였다. 실험 결과 뉴로-퍼지 시스템은 다양한 소프트웨어에 잘 적용되었다. 또한 널리 사용되고 있는 신경망과 통계적 소프트웨어 신뢰성 성장 모델의 예측력과 견줄 정도의 좋은 결과를 얻었다. This paper explores neuro-fuzzy system in order to improve the software reliability predictability from failure data. We perform numerical simulations for actual 10 failure count and 4 failure time data sets from different software projects with the various number of rules. Comparative results for next-step prediction problem is presented to show the prediction ability of the neuro-fuzzy system. Experimental results show that neuro-fuzzy system is adapt well across different software projects. Also, performance of neuro-fuzzy system is favorably with the other well-known neural networks and statistical SRGMs.

4-색 알고리즘

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

본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 O(n)선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 G=(V₁,E₁)의 정점 집합 V를 최대 독립집합 C₁와 최소 정점 피복 집합 C₁으로 정확히 양분하는 기법을 적용하여 C₁에 첫 번째 색을 배정하고, C₁ 집합의 정점들로 축소된 연결 그래프 G=(V₂,E₂)를 대상으로 C₂와 C₂로 양분하여 C₂에 두 번째 색을 지정하였다. C₂ 집합의 정점들로 축소된 연결 그래프 G=(V₃,E₃)를 대상으로 C₃와 C₃로 양분하여 C₃에 세 번째 색을 지정하였다. 마지막으로C₃를 C₄로 하여 4번째 색을 배정하였다. 2개의 실제 지도 그래프와 2개의 평면 그래프를 대상으로 제안된 알고리즘을 적용한 결과 모든 그래프에서 채색수 χ(G)=4를 찾는데 성공하였다. 결국, 제안된 "4-색 알고리즘"은 평면 그래프의 4-색을 결정하는 일반적인 알고리즘으로 적용할 수 있을 것이다. This paper proposes an algorithm that proves an NP-complete 4-color theorem by employing a linear time complexity where O(n). The proposed algorithm accurately halves the vertex set V of the graph G=(V₁,E₁) into the Maximum Independent Set (MIS) C₁ and the Minimum Vertex Cover Set C₁. It then assigns the first color to C₁ and the second to C₂, which, along with C₂, is halved from the connected graph G=(V₂,E₂), a reduced set of the remaining vertices. Subsequently, the third color is assigned to C₃, which, along with C₃, is halved from the connected graph G=(V₃,E₃), a further reduced set of the remaining vertices. Lastly, denoting C₃ as C₄, the algorithm assigns the forth color to C₄. The algorithm has successfully obtained the chromatic number χ(G)=4 with 100% probability, when applied to two actual map and two planar graphs. The proposed "four color algorithm", therefore, could be employed as a general algorithm to determine four-color for planar graphs.

작업자 배정 문제의 다항시간 알고리즘

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

The linear assignment problem (LAP) and linear bottleneck assignment problem (LBAP) has been unknown the algorithm to solve the optimal solution within polynomial-time. These problems are classified by NP-hard. Therefore, we can be apply metaheuristic methods or linear programming (LP) software package or Hungarian algorithm (HA) with O(m⁴) computational complexity. This paper suggests polynomial time algorithm with O(mn)=O(m²),m=n time complexity to LAP and LBAP. The select-delete method is simply applied to LAP, and the delete-select method is used to LBAP. For the experimental data without the unique algorithm can be apply to whole data, the proposed algorithm can be obtain the optimal solutions for whole data.

화랑 문제의 최소 정점 경비원 수 알고리즘

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

본 논문은 화랑 문제의 최소 정점 경비원 수를 구하는 알고리즘을 제안하였다. n개의 사각형 방으로 구성된 화랑의 최소 경비원수는 정확한 해를 구하는 공식이 제안되었다. 그러나 단순하거나 장애물이 있는 다각형 또는 직각 다각형에 대해 최대 경비원수를 구하는 공식만이 제안되었으며, 최소 경비원수를 구하는 근사 알고리즘만이 제안되고 있다. n개의 정점으로 구성된 다각형 P에 대한 최대 정점 경비원 수를 구하는 방법은 Fisk가 다음과 같이 제안하였다. 첫 번째로, n-2개의 삼각형으로 구성된 삼각분할을 수행한다. 두 번째로 3색-정점색칠을 한다. 세 번째로 최소 원소를 가진 채색수를 정점 경비원의 위치로 결정한다. 본 논문에서는 지배집합으로 최소 정점 경비원 수를 구한다. 첫 번째로, 가능한 모든 가시적인 정점들 간에 간선을 그린 가시성 그래프를 얻는다. 두 번째로, 가시성그래프로부터 직접 지배집합을 얻는 방법과 가시성 행렬로부터 지배집합을 얻는 방법을 적용하였다. 다양한 화랑 문제에 적용한 결과 제안된 알고리즘은 단순하면서도 최소 정점 경비원 수를 얻을 수 있었다. This paper suggests the minimum number of vertex guards algorithm. Given n rooms, the exact number of minimum vertex guards is proposed. However, only approximation algorithms are presented about the maximum number of vertex guards for polygon and orthogonal polygon without or with holes. Fisk suggests the maximum number of vertex guards for polygon with n vertices as follows. Firstly, you can triangulate with n-2 triangles. Secondly, 3-chromatic vertex coloring of every triangulation of a polygon. Thirdly, place guards at the vertices which have the minority color. This paper presents the minimum number of vertex guards using dominating set. Firstly, you can obtain the visibility graph which is connected all edges if two vertices can be visible each other. Secondly, you can obtain dominating set from visibility graph or visibility matrix. This algorithm applies various art galley problems. As a results, the proposed algorithm is simple and can be obtain the minimum number of vertex guards.

프로젝트 인도율 그룹 분할 방법을 이용한 소프트웨어 개발노력 추정

이상운,노명옥,이부권,Lee, Sang-Un,No, Myeong-Ok,Lee, Bu-Gwon 한국정보처리학회 2002 정보처리학회논문지D Vol.9 No.2

소프트웨어 개발시 중요하게 제기되는 문제점으로 소프트웨어 생명주기의 초기단계에서 개발에 투입될 노력과 비용을 추정하는 능력이다. 측정된 소프트웨어 규모인 기능점수 (FP, Function Point)로부터 프로젝트 개발에 소요되는 노력과 비용을 추정하는 회귀모델들이 제안되었다. 그러나 이들 제안된 모델들은 사용한 표본의 크기가 작고, 과거에 개발된 프로젝트를 대상으로 하고 있다. 1990년대에 개발된 789개 소프트웨어 개발 프로젝트들에 투입된 개발노력에 이들 모델을 적용한 결과 결정계수 $R^2$가 0.53 이하로 데이터의 변동을 설명하였다. 본 논문은 프로젝트 인도율(PDR)을 이용하여 동질성을 갖는 그룹으로 분류하여 개발노력을 추정하는 모델을 제안하였다. 제안된 모델은 랜덤한 잔차 분포를 갖고 있고, 대부분의 PDR 범위에서 0.99이상의 결정계수로 데이터의 변동을 설명하였다. The main issue in software development is the ability of software project effort and cost estimation in the early phase of software life cycle. The regression models for project effort and cost estimation are presented by function point that is a software sire. The data sets used to conduct previous studies are of ten small and not too recent. Applying these models to 789 project data developed from 1990 ; the models only explain fewer than 0.53 $R^2$(Coefficient of determination) of the data variation. Homogeneous group in accordance with project delivery rate (PDR) divides the data sets. Then this paper presents general effort estimation models using project delivery rate. The presented model has a random distribution of residuals and explains more than 0.93 $R^2$ of data variation in most of PDR ranges.

지배집합 알고리즘

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

본 논문은 아직까지 정확한 해를 다항시간으로 구하는 알고리즘이 존재하지 않아 NP-완전 문제로 알려진 지배집합 (DS) 문제의 정확한 해를 선형시간으로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프의 간선이 존재하지 않을 때까지 최소차수 Δ(G)를 가진 정점 u의 인접정점들 중 최대차수 Δ(G)를 가진 정점 v를 최소 독립지배집합(MIDS)의 원소로 포함시키고 v의 부속 간선을 삭제하는 방법을 반복적으로 수행하여 구하였다. MIDS로부터 최소 지배집합 (MDS)으로 변환시키고, MDS로부터 최소연결 DS (MCDS)로 변환시키는 방법으로 DS 관련 모든 문제의 정확한 해를 구할 수 있었다. 제안된 알고리즘을 10개의 다양한 그래프에 적용한 결과 정확한 해를 선형 시간복잡도 O(n)으로 구하는데 성공하였다. 결국, 제안된 지배집합 알고리즘은 지배집합 문제가 P-문제임을 증명하였다. This paper proposes a linear-time algorithm that has been designed to obtain an accurate solution for Dominating Set (DS) problem, which is known to be NP-complete due to the deficiency of polynomial-time algorithms that successfully derive an accurate solution to it. The proposed algorithm does so by repeatedly assigning vertex v with maximum degree Δ(G)among vertices adjacent to the vertex v with minimum degree Δ(G) to Minimum Independent DS (MIDS) as its element and removing all the incident edges until no edges remain in the graph. This algorithm finally transforms MIDS into Minimum DS (MDS) and again into Minimum Connected DS (MCDS) so as to obtain the accurate solution to all DS-related problems. When applied to ten different graphs, it has successfully obtained accurate solutions with linear time complexity O(n). It has therefore proven that Dominating Set problem is rather a P-problem.

비대칭키 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 한국인터넷방송통신학회 2024 한국인터넷방송통신학회 논문지 Vol.24 No.4

수레바퀴 중심축(허브, 정점)이 요구하는 살(간선)을 교차없이 연결하여 모든 중심축이 연결된 망을 형성하는 수레바퀴 살 퍼즐 문제는 연구의 불모지라 할 수 있다. 이 문제에 대해서는 지수시간이 소요되는 전수 탐색법이나 분기 한정 법조차도 제시된 알고리즘이 없는 실정이다. 본 논문은 주어진 SP에 대해 m×n의 교차 대각선을 가진 격자 그래프를 작도하고, 잉여 간선을 전정(삭제)하는 알고리즘을 제안하였다. 제안된 알고리즘은 간선 수가 허브 요구량과 일치하는 허브의 간선을 선택하고 이와 교차하는 간선을 삭제하는 단순한 방법이다. 만약 허브 요구량을 충족하는 간선을 가진 허브가 존재하지 않으면 여유 량이 최대인 허브의 간선을 우선하여 삭제(전정)하는 전략을 채택하였다. 제안된 알고리즘을 20개의 벤치마킹 실험 데이터에 적용한 결과 모든 문제에 대해 시행착오 회수를 최소로 하는 해를 구할 수 있음을 보였다. The problem of the spokes puzzle(SP), which connects the spokes(edges) required by the wheel axis (hub, vertex) without intersection to form a network in which all the hubs are connected, can be said to be a wasteland of research. For this problem, there is no algorithm that presents a brute-force search or branch-and-bound method that takes exponential time. This paper proposes an algorithm to plot a lattice graph with cross-diagonal lines of m×n for a given SP and to pruning(delete) the surplus edges(spokes). The proposed algorithm is a simple way to select an edge of a hub whose number of edges matches the hub requirement and delete the edge crossing it. If there is no hub with an edge that meets the hub requirement, a strategy was adopted to preferentially delete(pruning) the edge of the hub with the maximum amount of spare. As a result of applying the proposed algorithm to 20 benchmarking experimental data, it was shown that a solution that minimizes the number of trials and errors can be obtained for all problems.

최소-최대 교대 전략을 적용한 k-CPP 알고리즘

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