http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
안형찬 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.5
minimum terminal path decomposition of a tree is defined as a partition of the tree into edge-disjoint terminal-to-terminal paths that minimizes the weight of the longest path. In this paper, we present an -time algorithm to find a minimum terminal path decomposition of trees. The algorithm reduces the given optimization problem to the binary search using the corresponding decision problem, the problem to decide whether the cost of a minimum terminal path decomposition is at most . This decision problem is solved by dynamic programing in a single traversal of the tree. 최소단말경로분할이란 트리를 에지가 서로 소인 단말 노드 간 경로들로 분할하되, 가장 긴 경로의 길이를 최소화하는 문제이다. 본 논문에서는 트리의 최소단말경로분할을 시간에 구하는 알고리즘을 제시한다. 이 알고리즘은 주어진 최적화 문제를 이에 대응하는 결정 문제, 즉 최소단말경로분할의 비용이 이하인지를 결정하는 문제를 이용한 이진 탐색으로 환원한다. 결정 문제는 트리를 한 차례 순회하는 동안 동적 계획법에 의해 해결된다.
안형찬 전북대학교 문화융복합아카이빙연구소 2021 디지털문화아카이브지 Vol.4 No.1
In this paper, we propose to optimize the cost of data archiving via algorithmic planning. First, we present algorithmic methods to determine the distribution of data over multiple backup medias and sites. By formulating this distribution task as a concrete mathematical problem, we can apply approximation algorithms, heuristics, or exact algorithms for the problem. We then consider using data compression techniques to reduce the size of archived data. In particular, we focus on lossy compression algorithms and propose to establish a standard that enables a quality-time trade-off in multimedia data decoding. In light of the recent growth of graph data, we remark that graph sparsification and graph summarization algorithms can serve as lossy compression algorithms for graph data. 본 논문에서는 알고리즘을 활용한 계획으로 데이터 보존 비용을 최적화하는 기법을 제안한다. 먼저, 다수의 백업 미디어나 사이트에 데이터가 분산되는 방식을 알고리즘을 통해 결정하는 방안을 제시한다. 이 분산 작업을 잘 정의된 수학적 문제의 형태로 나타내고 나면, 이에 대해 근사 알고리즘이나 휴리스틱, 혹은 정확한 알고리즘을 적용할 수 있게 된다. 이어서, 데이터 압축 기법을 활용해 보존할 데이터의 양을 줄이는 방법을 고려한다. 특히, 손실 압축 알고리즘에 초점을 맞추어, 멀티미디어 데이터를 압축 해제함에 있어 질과 시간 사이의 교환을 가능하게 하는 표준을 정립할 것을 제안한다. 최근 그래프 데이터가 증가하고 있음을 감안할 때, 그래프 희소화나 그래프 요약 알고리즘이 그래프 데이터에 대한 손실 압축 알고리즘으로 기능할 수 있음에 주목하고자 한다.
안형찬(Hyung-Chan An) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.5·6
트리의 최소단말경로분할이란 트리를 에지가 서로 소인 단말 노드 간 경로들로 분할하되, 가장 긴 경로의 길이를 최소화하는 문제이다. 본 논문에서는 트리의 최소단말경로분할을 O(│V│²) 시간에 구하는 알고리즘을 제시한다. 이 알고리즘은 주어진 최적화 문제를 이에 대응하는 결정 문제, 즉 최소단말경로 분할의 비용이 ℓ 이하인지를 결정하는 문제를 이용한 이진 탐색으로 환원한다. 결정 문제는 트리를 한 차례 순회하는 동안 동적 계획법에 의해 해결된다. A minimum terminal path decomposition of a tree is defined as a partition of the tree into edge-disjoint terminal-to-terminal paths that minimizes the weight of the longest path. In this paper, we present an O(│V│²)-time algorithm to find a minimum terminal path decomposition of trees. The algorithm reduces the given optimization problem to the binary search using the corresponding decision problem, the problem to decide whether the cost of a minimum terminal path decomposition is at most ℓ. This decision problem is solved by dynamic programing in a single traversal of the tree.
윤인섭,안형찬 한국정보과학회 2022 정보과학회 컴퓨팅의 실제 논문지 Vol.28 No.12
In this paper, we propose a new heuristic that optimizes implementations of graph coloring algorithms on GPGPUs by selecting efficient graph representations depending on the input graphs. Previously, Alabandi et al. gave a graph coloring algorithm suitable for GPGPU implementation; however, limitations due to its monolithic use of a single data structure restricted using the full power of GPGPUs. We adopted multiple graph representations that work better with GPGPUs and experimentally measured the resulting performance improvements. These experiments were conducted on RTX 2060 and GTX 1050Ti using graphs from public repositories as the benchmark set. Based on the results, we devised a heuristic that considers the input graph's properties, such as its degree, to automatically select the most suitable graph representation. This led to an average improvement of 8.01% (RTX 2060) - 10.43% (GTX 1050Ti) in running time compared to the previous algorithm. Lastly, we investigated individual cases for which the heuristic showed little improvement. 본 논문에서는 그래프 채색 알고리즘의 GPGPU상 구현을 최적화하는 새로운 기법으로서, 입력에 따라 최적의 그래프 표현방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 본 논문에서는 GPGPU에 알맞은 복수의 자료 구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 2060과 GTX 1050Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 기존 대비 평균 8.01%(RTX 2060)~10.43%(GTX 1050Ti)의 수행 속도 개선 효과를 나타내었다. 끝으로, 휴리스틱의 효과가 저조한 경우에 대한 개별 분석을 수행하였다.
시스템 활성화 오버헤드를 고려한 멀티코어 시스템의 에너지 최적화
이국렬,안형찬 한국정보과학회 2024 정보과학회논문지 Vol.51 No.1
This paper presents heuristics to optimize the energy consumption of multicore systems with wake-up overhead. A multicore system can optimize its energy consumption by strategically (de)activating itself. Given the task information of the system, OSPAL algorithm was previously known to find a schedule that maximizes the common idle time. However, this schedule does not necessarily minimize energy consumption because of the wake-up overhead associated with the storage of memory footprint to non-volatile memory. Previous research proposed to address this issue by modifying their algorithm so that it does not keep common idle times shorter than a threshold. We observe that their choice of threshold is not optimal and propose a randomized heuristic to improve the energy consumption. We also present a dynamic-programming-based postprocessing heuristic to adjust common idle times. We conducted computational experiments to measure the performance of the proposed heuristics, which indicated an average improvement of 37.69% in energy consumption compared to the previous algorithm.