고분자 과학기술은 한국인에 유리하다

심정섭,Sim, Jeong-Seop 한국과학기술단체총연합회 1998 과학과 기술 Vol.31 No.8

고분자 과학은 골격이 1940년대에 확립되어 이제 회갑을 맞는 활기찬 학문이다. 오랜전통을 갖는 서구과학의 타 학문에 비해 6.25동란등으로 10년 정도의 학문적 공백기를 감안하더라도 근소한 핸디캡으로 출발하였으므로 고분자 과학과 기술의 성취에는 한국인의 입장이 유리할 것이다.

문자열의 근사커버 찾기

심정섭,박근수,김성렬,이지수,Sim, Jeong-Seop,Park, Kun-Soo,Kim, Sung-Ryul,Lee, Jee-Soo 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.1

반복적인 문자열에 대한 연구는 최근 들어 여러 분야에서 활발히 진행되어 왔다. 특히, DNA 염기서열의 분석 등 분자생물학에서 그 필용성이 대두되어 있다. 주기 커버, 시드 시퀘어 등이 반복적인 문자열의 대표적인 예들이다. 근사문자열 매칭 분야에서도 근사주기, 근사스퀘어 등 반복적인 문자열에 관 한 연구가 진행되고 있다. 본 논문에서는 근사커버의 개념을 제시한다. 길이가 각각 m, n 인 두 문자열 P. T가 주어졌을 때, P가 T의 근사커버가 되는 최소의 편집거리를 O(mn) 시간, 최소의 가중편집거리를 $O(mn^2)$시간에 찾는 알 고리즘을 제시한다. 또한 문자열 T만 주어졌을 때. T의 최소 근사커버 거리를 갖는 문자열 P를 찾는 문제가 NP-완전 결과임을 증명한다. Repetitive strings have been studied in such diverse fields as molecular biology data compression etc. Some important regularities that have been studied are perods, covers seeds and squares. A natural extension of the repetition problems is to allow errors. Among the four notions above aproximate squares and approximate periodes have been studied. In this paper, we introduce the notion of approximate covers which is an approximate version of covers. Given two strings P(|P|=m) and T(|T|=n) we propose and algorithm with finds the minimum distance t such that P is a t-approximate cover of T. The algorithm take O(m,n) time for the edit distance and $O(mn^2)$ time of finding a string which is an approximate cover of T is minimum distance is NP-complete.

A String Reconstruction Algorithm and Its Application to Exponentiation Problems

심정섭,이문규,김동규,Sim, Jeong-Seop,Lee, Mun-Kyu,Kim, Dong-Kyue Korean Institute of Information Scientists and Eng 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.9

Most string problems and their solutions are relevant to diverse applications such as pattern matching, data compression, recently bioinformatics, and so on. However, there have been few works on the relations between string problems and cryptographic problems. In this paper, we consider the following string reconstruction problems and show how these problems can be applied to cryptography. Given a string x of length n over a constant-sized alphabet ${\sum}$ and a set W of strings of lengths at most an integer $k({\leq}n)$, the first problem is to find the sequence of strings in W that reconstruct x by the minimum number of concatenations. We propose an O(kn+L)-time algorithm for this problem, where L is the sum of all lengths of strings in a given set, using suffix trees and a shortest path algorithm for directed acyclic graphs. The other is a dynamic version of the first problem and we propose an $O(k^3n+L)$-time algorithm. Finally, we show that exponentiation problems that arise in cryptography can be successfully reduced to these problems and propose a new solution for exponentiation. 대부분의 문자열 문제들과 이들에 대한 알고리즘들은 패턴 매칭, 데이타 압축, 생물정보학 등의 분야에 응용되어 왔다. 그러나 문자열 문제와 암호화 문제의 관련성에 대한 연구는 거의 진행되지 않았다. 본 논문에서는 다음과 같은 문자열 재구성 문제들에 대해 연구하고 이 결과들이 암호학에 응용될 수 있음을 보인다. 유한 알파벳으로 구성된 길이 n인 문자열 x와, 길이 $k({\leq}n)$ 이내의 문자열의 집합 W가 주어졌을 때, 첫 번째 문제는 내의 문자열들 중 일부 문자열들을 최소의 회수로 연결하여 x를 재구성할 수 있는 연결 순서를 찾는 문제이다. 이 문제에 대해 O(kn+L)-시간 알고리즘을 제시한다. 이때, L은 W 내의 모든 문자열들의 길이의 합을 표시한다. 두 번째 문제는 첫 번째 문제의 동적 버전이며 이에 대해 $O(k^3n+L)$시간 알고리즘을 제시한다. 마지막으로 암호학과 관련된 멱승문제와 위에 제시된 재구성 문제들과의 관련성을 보이고 멱승문제를 해결하는 새로운 알고리즘을 제시한다.

문자열의 근사커버 찾기

심정섭(Jeong Seop Sim),박근수(Kunsoo Park),김성렬(Sung-Ryul Kim),이지수(Jee-Soo Lee) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.1·2

반복적인 문자열에 대한 연구는 최근 들어 여러 분야에서 활발히 진행되어 왔다. 특히 DNA 염기서열의 분석 등 분자생물학에서 그 필요성이 대두되고 있다. 주기, 커버, 시드, 스퀘어 등이 반복적인 문자열의 대표적인 예들이다. 근사문자열 매칭 분야에서도 근사주기, 근사스퀘어 등 반복적인 문자열에 관한 연구가 진행되고 있다. 본 논문에서는 근사커버의 개념을 제시한다. 길이가 각각 m, n 인 두 문자열 P, T 가 주어졌을 때, P 가 T 의 근사커버가 되는 최소의 편집거리를 O (mn) 시간, 최소의 가중편집거리를 O (mn²) 시간에 찾는 알고리즘을 제시한다. 또한, 문자열 T 만 주어졌을 때, T 의 최소 근사커버 거리를 갖는 문자열 P 를 찾는 문제가 NP-완전 결과임을 증명한다. Repetitive strings have been studied in such diverse fields as molecular biology, data compression, etc. Some important regularities that have been studied are periods, covers, seeds and squares. A natural extension of the repetition problems is to allow errors. Among the four notions above, approximate squares and approximate periods have been studied. In this paper, we introduce the notion of approximate covers which is an approximate version of covers. Given two strings P ( P = m) and T ( T = n) , we propose an algorithm which finds the minimum distance t such that P is a t -approximate cover of T . The algorithm takes O (mn) time for the edit distance and O (mn²) time for a weighted edit distance. Furthermore, when only T is given, we show that the problem of finding a string which is an approximate cover of T with the minimum distance is NP-complete.

A String Reconstruction Algorithm and Its Application to Exponentiation Problems

심정섭(Jeong Seop Sim),이문규(Mun-Kyu Lee),김동규(Dong Kyue Kim) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.9·10

대부분의 문자열 문제들과 이들에 대한 알고리즘들은 패턴 매칭, 데이타 압축, 생물정보학 등의 분야에 응용되어 왔다. 그러나 문자열 문제와 암호화 문제의 관련성에 대한 연구는 거의 진행되지 않았다. 본 논문에서는 다음과 같은 문자열 재구성 문제들에 대해 연구하고 이 결과들이 암호학에 응용될 수 있음을 보인다. 유한 알파벳으로 구성된 길이 n 인 문자열 x 와, 길이 k (≤ n) 이내의 문자열의 집합 W가 주어졌을 때, 첫 번째 문제는 W내의 문자열들 중 일부 문자열들을 최소의 회수로 연결하여 x 를 재구성할 수 있는 연결 순서를 찾는 문제이다. 이 문제에 대해 O(kn+L) -시간 알고리즘을 제시한다. 이때, L은 W내의 모든 문자열들의 길이의 합을 표시한다. 두 번째 문제는 첫 번째 문제의 동적 버전이며 이에 대해 O(k³n+L)-시간 알고리즘을 제시한다. 마지막으로 암호학과 관련된 멱승문제와 위에 제시된 재구성 문제들과의 관련성을 보이고 멱승문제를 해결하는 새로운 알고리즘을 제시한다. Most string problems and their solutions are relevant to diverse applications such as pattern matching, data compression, recently bioinformatics, and so on. However, there have been few works on the relations between string problems and cryptographic problems. In this paper, we consider the following string reconstruction problems and show how these problems can be applied to cryptography. Given a string χ of length n over a constant-sized alphabet ∑ and a set W of strings of lengths at most an integer к (≤ n), the first problem is to find the sequence of strings in W that reconstruct χ by the minimum number ofoncatenations. We propose an О(kn+L)-time algorithm for this problem, where ? is the sum of all lengths of strings in a given set, using suffix trees and a shortest path algorithm for directed acyclic graphs. The other is a dynamic version of the first problem and we propose an О(k³n+L)-time algorithm. Finally, we show that exponentiation problems that arise in cryptography can be successfully reduced to these problems and propose a new solution for exponentiation.

정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘

김영호,심정섭,Kim, Youngho,Sim, Jeong Seop 한국정보과학회 2017 정보과학회논문지 Vol.44 No.8

반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 ${\delta}$-근사주기와 최소 ${\gamma}$-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 $O(n^2)$ 시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 $O(n^2)$개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 ${\delta}$-근사주기를 계산하는데 약 19.7배, 최소 ${\gamma}$-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다. Repetitive strings have been studied in diverse fields such as data compression, bioinformatics and so on. Recently, two problems of approximate periods of strings over integer alphabets were introduced, finding minimum ${\delta}-approximate$ periods and finding minimum ${\gamma}-approximate$ periods. Both problems can be solved in $O(n^2)$ time when n is the length of the string. In this paper, we present two parallel algorithms for solving the above two problems in O(n) time using $O(n^2)$ threads, respectively. The experimental results show that our parallel algorithms for finding minimum ${\delta}-approximate$ (resp. ${\gamma}-approximate$) periods run approximately 19.7 (resp. 40.08) times faster than the sequential algorithms when n = 10,000.

정수 문자집합상의 접미사트리 구축을 위한 새로운 합병 알고리즘

김동규,심정섭,박근수,Kim, Dong-Kyu,Sim, Jeong-Seop,Park, Kun-Soo 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.2

주어진 스트링 S의 접미사트리 $T_s$를 구축하기 위하여 , 먼저 홀수위치들에 대한 접미사트리 $ T_0$를 제귀적으로 구축하고 짝수위치들에 대한 접비사트리 $T_e$를 $ T_o$/로 부터 구축한 다음 $ T_o$와 $T_e$를 합병하여 $T_s$를 구축하는 새로운 방식이 사용되고 있다. 인덱스자료구조에 관련된 문제들 중 정수 문자집합상의 접미사트리를 선형시간에 구축하는 문제는 오랫동안 미해결문제로 남아 있었다. Farach은 이 방식을 적용하여 처음으로 성형시간이 소요되는 알고리즘을 제시하였다. 이 알고리즘은 중 가장 어려운 곳은 합병하는 부분이다. 본 논문에서는 BFS(breadth-first search)에 기반하는 새로운 합병알고리즘을 제안한다. 제안된 합병알고리즘은 Farach의 DFS(depth-first search) 방식보다 개념적으로 단순하게 동작하므로 다른 응용의로 쉽게 확장될수 있다. A new approach of constructing a suffix tree $T_s$for the given string S is to construct recursively a suffix tree $ T_0$ for odd positions construct a suffix tree $T_e$ for even positions from $ T_o$ and then merge $ T_o$ and $T_e$ into $T_s$ To construct suffix trees for integer alphabets in linear time had been a major open problem on index data structures. Farach used this approach and gave the first linear-time algorithm for integer alphabets The hardest part of Farachs algorithm is the merging step. In this paper we present a new and simpler merging algorithm based on a coupled BFS (breadth-first search) Our merging algorithm is more intuitive than Farachs coupled DFS (depth-first search ) merging and thus it can be easily extended to other applications.

Chlorobenzene 常壓氣 相接觸 加水分解에 依한 石炭酸의 合成

성좌경,심정섭,Seong Jwa Gyeong,Sim Jeong Seop 대한화학회 1952 대한화학회지 Vol.2 No.1

접미사 배열을 이용한 시간과 공간 효율적인 검색

최용욱(Yong Wook Choi),심정섭(Jeong Seop Sim),박근수(Kunsoo Park) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.5·6

길이가 n 인 알파벳 Σ 상의 텍스트 T 에서 패턴 P 를 효율적으로 검색하기 위해 접미사 트리와 접미사 배열이 널리 쓰이고 있다. 접미사 배열이 접미사 트리보다 더 적은 공간을 사용하기 때문에 텍스트의 길이가 긴 경우에는 접미사 배열이 더 선호되고 있다. 최근에는 접미사 배열을 이용한 O( P · Σ ) 시간과 O( · log ) 시간 검색 알고리즘들이 개발되었다. 본 논문에서는 접미사 배열을 이용한 시간과 공간 효율적인 알고리즘들을 제시한다. 하나의 알고리즘은 O( ) 비트 공간을 사용하여 O( ) 시간에 수행되고, 다른 하나는 O( n · log · n log log n/ log n)비트 공간을 사용하여 O( ·log ) 시간에 수행되는데, 두 번째 알고리즘은 보다 효율적인 공간을 사용하면서 여전히 빠른 알고리즘이다. 본 논문이 제시하는 알고리즘들이 시간과 공간에 있어 기존의 알고리즘들보다 더 효율적인 알고리즘들임을 실험을 통해 보여주고 있다. To search efficiently a text T of length n for a pattern P over an alphabet Σ, suffix trees and suffix arrays are widely used. In case of a large text, suffix arrays are preferred to suffix trees because suffix arrays take less space than suffix trees. Recently, O( )-time and O( )-time search algorithms in suffix arrays were developed. In this paper we present time and space efficient search algorithms in suffix arrays. One algorithm runs in O( ) time using O( n · )-bits space, and the other runs in O( ) time using O( n log · n log log n/ log n)-bits space, which is more space efficient and still fast. Experiments show that our algorithms are efficient in both time and space when compared to previous algorithms.

문자열의 최소 δ-근사주기와 최소 γ-근사주기 찾기

김영호(Youngho Kim),심정섭(Jeong Seop Sim) 한국정보과학회 2015 한국정보과학회 학술발표논문집 Vol.2015 No.12