문자열 집합에 대한 일반화접미사트리의 병행적 생성 알고리즘

나중채(Joong Chae Na) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.1

접미사트리 는 주어진 한 문자열의 모든 접미사를 표현하는 트리로, 문자열 처리, 압축 등 다양한 분야에서 활용된다. 접미사트리는 문자열 집합에 대한 자료구조로 확장될 수 있는데, 이를 일반화접미사트리 라 부른다. 본 논문에서는 일반화접미사트리를 병행적 으로 생성하는 문제를 다룬다. 기존의 알고리즘은 문자열들을 역방향으로 처리하면서 일반화접미사트리를 생성하는데, 접미사트리가 활용되는 대부분의 응용에서는 문자열을 정방향으로 처리하고 있어, 기존의 알고리즘은 활용 범위가 매우 제한된다. 본 논문에서는 문자열들을 정방향으로 처리하면서 일반화접미사트리를 병행적으로 생성하는 알고리즘을 제시함으로써 기존 알고리즘의 문제점을 극복한다. The suffix tree, a compacted trie representing all suffixes of a given string, is utilized in various applications such as string processing and data compression. The suffix tree can be extended to a data structure of a set of strings, called the generalized suffix tree. In this paper we consider the problem of constructing concurrently the generalized suffix tree. The previous algorithm constructs the generalized suffix tree by processing strings in backward direction. In most applications, strings are handled in forward direction, and thus the previous algorithm has some limits. We propose an algorithm for constructing concurrently the generalized suffix tree by processing strings in forward direction.

공간 노드들의 최단연결을 위한 3차원 유클리드 최소신장트리

김재각(Chae-Kak Kim),김인범(In-Bum Kim) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.1

일반적으로 유클리드 최소신장트리는 2차원 평면상에 존재하는 입력노드들이 최소 비용으로 연결된 것이다. 그러나 생성된 유클리드 최소신장트리는 3차원의 현실세계에 적용할 경우 그 연결비용은 최소비용이 아닐 수 있다. 본 논문에서는 3차원 공간상에 존재하는 입력노드를 최단 길이로 연결하는 3차원 유클리드 최소신장트리를 제안한다. 100%의 공간비율의 3차원 공간상에 존재하는 30,000개의 입력 노드에 대한 실험에서, 본 논문에서 제안된 방법에 생성된 트리는, Prim의 2차원 최소신장트리 알고리즘에 의해 생성된 유클리드 최소신장트리에 비해, 2차원 평면에서만 고려했을 때 251.2%의 연결 비용의 증가를 보이지만 이것은 3차원 실세계에서는 의미가 없다. 본 논문에서 제안된 방법에 의해 생성된 트리는 3차원 공간에서는 90.0%의 비용의 절감율을 보인다. 이는 제안된 방법이 3차원적 연결에 관한 많은 현실적인 문제에 잘 적용될 수 있음을 나타낸다. In general, Euclidean minimum spanning tree is a tree connecting input nodes with minimum connecting cost. But the tree may not be optimal when applied to real world problems of three dimension. In this paper, three dimension Euclidean minimum spanning tree is proposed, connecting all input nodes of 3-dimensional space with minimum cost. In experiments for 30,000 input nodes with 100% space ratio, the tree produced by the proposed method can reduce 90.0% connection cost tree, compared with the tree by two dimension Prim's minimum spanning tree. In two dimension plane, the proposed tree increases 251.2% connecting cost, which is pointless in 3-dimensional real world. Therefore, the proposed method can work well for many connecting problems in real world space of three dimensions.

들로네 삼각망과 최소신장트리를 결합한 효율적인 유클리드 스타이너 최소트리 생성

김인범(Inbum Kim) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.1

스타이너 트리의 생성은 NP-Complete 영역에 속하므로, 이것을 위한 휴리스틱들은, 다수의 입력 노드에 대해서 많은 시간과 계산을 요구한다. 본 논문에서는 많은 입력노드에 대해, 들로네 삼각망과 Prim의 최소신장트리를 결합한 효과적인 유클리드 스타이너 최소트리 구성방법을 제안한다. 이 방법은 Prim의 최소신장트리와 최소신장트리기반 스타이너 트리와 각각 비교 분석되었다. 제안된 방법은 30,000개의 입력노드에 대해 최소신장트리에 비해 연결 길이는 2.1% 감소, 실행시간은 138.2% 증가하였고, 최소신장트리기반 스타이너최소트리에 비해 실행시간 18.9% 감소, 연결 길이 0.013% 감소의 실험결과를 보였다. 따라서 본 연구의 제안방법은 실행시간이 주요 요인이 되지 않는 환경에서 연결 길이를 단축해야 할 응용에 잘 적용될 수 있을 것이다. As Steiner minimum tree building belongs to NP-Complete problem domain, heuristics for the problem ask for immense amount execution time and computations in numerous inputs. In this paper, we propose an efficient mechanism of euclidean Steiner minimum tree construction for numerous inputs using combination of Delaunay triangulation and Prim's minimum spanning tree algorithm. Trees built by proposed mechanism are compared respectively with the Prim's minimum spanning tree and minimums spanning tree based Steiner minimum tree. For 30,000 input nodes, Steiner minimum tree by proposed mechanism shows about 2.1% tree length less and 138.2% execution time more than minimum spanning tree, and does about 0.013% tree length less and 18.9% execution time less than minimum spanning tree based Steiner minimum tree in experimental results. Therefore the proposed mechanism can work moderately well to many useful applications where execution time is not critical but reduction of tree length is a key factor.

팬데믹으로 인한 의료자원의 소진(消盡)시 치료의 우선순위(Triage)

안병하(Byungha Ahn) 한국비교사법학회 2022 비교사법 Vol.29 No.4

갑작스런 팬데믹으로 전세계가 어려움을 겪고있다. 특히 팬데믹 초기 대응과정에서의 극심한 혼란은 소위 선진국이라고 하는 나라조차도 피할 수 없는 것이었다. 이러한 경험들을 거치며 이번과 같은 예기치 못한 팬데믹 상황에서 필요한 의료자원의 수가 급증하는 환자의 수를 따르지 못할 때 어떠한 환자부터 치료해야 하는지에 관해 관심이 모아지게 되었고, 실제로 유럽의 몇몇 나라들에서는 의사단체 등에서 이와 관련한 지침을 발표하기도 하였다. 하지만 환자의 생명과 직결되는 이러한 선택의 문제는 민간에 맡겨놓을 성질의 것이 아니라 헌법적 가치에 입각하여 규범적으로 정당화되어야 할 문제이다. 이러한 인식을 기초로 하여 트리아지에 관해 고찰해 본 결과 본고에선 다음과 같은 결론에 이르게 되었다. 물론 트리아지 상황이 발생하지 않도록 대비하는 것이 가장 중요한 일임에는 변함이 없다. 1. 사전적 트리아지는 헌법적 가치에 반하지 않지만, 사후적 트리아지는 인간의 존엄에 반하며 예방적 트리아지는 생명권에 반한다. 2. 의학적 적응증(Indikation), 치료에 대한 환자의 동의, 치료의 긴급성은 트리아지의 전제조건이며 이들과 트리아지의 기준은 구별되어야 한다. 3. 허용되는 트리아지의 기준으로는 환자의 회복가능성이 가장 유력한 것이며, 그 외에 아주 예외적으로 환자의 구조자로서의 기능이나 단기체류 외국인인지 여부, 선착순 등이 엄격한 요건 하에 고려될 여지가 있다. 이에 반해 환자의 연령이나 사회적 지위, 트리아지 상황에 대한 책임, 제비뽑기 등은 올바른 기준이 될 수 없다. 4. 현재 국내의 상황과 같이 아직 트리아지에 관한 입법이 없는 상황에서 의사는 ‘정당한 사유’에 기한 진료의 거부, 의무의 충돌과 같은 법리에 의해 민법상 책임을 피할 수 있을 것이라 생각된다. Die ganze Welt leidet unter der plötzlich ausgebrochenen Corona-Pandemie. Sogar in den Industrieländern (Erste Welt Ländern) war zu Beginn der Pandemie eine medizinisch chaotische und angespannte Situation unvermeidlich. Diese Erfahrung brachte die Wichtigkeit der Triage während einer Pandemie ans Licht, sodass sogar ärzteverbände verschiedener Lnder dazu eigene Richtlinien veröffentlichten. Handlungsanweisungen bei Lebensnotstand sind in erster Linie jedoch eine normative Frage, die durch die Gesetzgeber geregelt werden muss. Aufgrund dieser Erkenntnis kommt die vorliegende Arbeit zu den folgenden Ergebnissen. 1. Während die ex-ante-Triage grundsätzlich nicht der Wertordnung der Verfassung widerspricht, sind die sog. präventive sowie ex-post-Triage nicht zulssig. Letzteres entspricht nicht der Würde des Menschen und die präventive Triage verletzt das Lebensrecht der nicht behandelten Patienten. 2. Eine medizinische Indikation, die Einwilligung des Patienten und die Dringlichkeit der Behandlung gehören zu den Voraussetzungen einer Triage, welche von ihren materiellen Kriterien wie der Erfolgsaussicht zu unterscheiden sind. 3. Als zulässiges Kriterium ist vor allem die Erfolgsaussicht zu nennen. Im Ausnahmefall können unter strengen Voraussetzungen folgende Kriterien bercksichtigt werden: ob der Patient für die Rettung anderer unersetzbar ist oder ob der Patient nicht ein Ausländer ist, der keinen Beitrag zur nationalen Gesundheitsversicherung leistet. Jedoch darf es keine Benachteiligung geben bezüglich Alter, sozialen Status oder Verschulden des Patienten. Los ist auch ein ungeeignetes Mittel, weil dadurch das Ziel der Triage nicht erreicht wird. 4. Es gibt noch kein Triage-Gesetz in Korea. In dieser Situation setzt sich der Arzt, der die Triage durchführt, in die straf- und zivilrechtliche Haftungsgefahr. Mit Hilfe der verschiedenen Rechtfertigungsgründe wie Pflichtenkollision oder berechtigten Behandlungsverweigerung kann er aber einer Haftung entgehen.

CC-GiST: 임의의 캐시 인식 검색 트리를 효율적으로 구현하기 위한 일반화된 프레임워크

노웅기,김원식,한욱신,Loh, Woong-Kee,Kim, Won-Sik,Han, Wook-Shin 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.1

최근 메인 메모리 가격이 하락하고 용량이 크게 증가함에 따라 메인 메모리 데이터베이스에 기반한 응용이 급격히 증가하고 있다. 캐시 미스 (cache miss)는 CPU에서 액세스하고자 하는 데이터가 캐시에 존재하지 않아 메모리로부터 읽어 들이는 과정이며, 메인 메모리 데이터베이스의 성능 감소의 중요한 원인이다. 메인 메모리 데이터베이스에서의 캐시 미스를 줄이고 캐시를 최대한 활용하기 위하여 여러 가지 캐시 인식 트리들(cache conscious trees)이 제안되었다. 이러한 캐시 인식 트리들은 각각 특성이 다르므로 하나의 응용에서 둘 이상의 캐시 인식 트리들이 동시에 관리될 수 있다. 또한, 만약 기존의 캐시 인식 트리가 응용에서의 요구를 만족시키지 못하면 새로운 캐시 인식 트리를 구현하여야 한다. 본 논문에서는 캐시 인식하는 일반화된 검색 트리(Cache-Conscious Generalized Search Tree, CC-GiST)를 제안한다. CC-GiST는 디스크 기반의 일반화된 검색 트리 (Generalized Search Tree, GiST) [HNP95]를 캐시 인식하도록 확장한 것이며, 포인터 압축(pointer compression)과 키 압축(key compression) 기법을 비롯하여 임의의 캐시 인식 트리의 공통적인 기능 및 알고리즘들을 동시에 제공한다. CC-GiST를 기반으로 특정 캐시 인식트리를 구현하려면 그 트리에 해당된 기능만을 구현하면 된다. 본 논문에서는 CC-GiST를 기반으로 기존의 대표적인 캐시 인식 트리인 CSB+-트리, pkB-트리, CR-트리를 구현하는 방법을 기술한다. CC-GiST를 이용함에 따라 메인 메모리 데이터베이스 응용에서 여러 개의 캐시 인식 트리를 관리하는 번거로움에서 벗어날 수 있고, 응용의 요구에 따른 새로운 캐시 인식 트리를 최소한의 노력으로 효율적으로 구현할 수 있다. According to recent rapid price drop and capacity growth of main memory, the number of applications on main memory databases is dramatically increasing. Cache miss, which means a phenomenon that the data required by CPU is not resident in cache and is accessed from main memory, is one of the major causes of performance degradation of main memory databases. Several cache-conscious trees have been proposed for reducing cache miss and making the most use of cache in main memory databases. Since each cache-conscious tree has its own unique features, more than one cache-conscious tree can be used in a single application depending on the application's requirement. Moreover, if there is no existing cache-conscious tree that satisfies the application's requirement, we should implement a new cache-conscious tree only for the application's sake. In this paper, we propose the cache-conscious generalized search tree (CC-GiST). The CC-GiST is an extension of the disk-based generalized search tree (GiST) [HNP95] to be tache-conscious, and provides the entire common features and algorithms in the existing cache-conscious trees including pointer compression and key compression techniques. For implementing a cache-conscious tree based on the CC-GiST proposed in this paper, one should implement only a few functions specific to the cache-conscious tree. We show how to implement the most representative cache-conscious trees such as the CSB+-tree, the pkB-tree, and the CR-tree based on the CC-GiST. The CC-GiST eliminates the troublesomeness caused by managing mire than one cache-conscious tree in an application, and provides a framework for efficiently implementing arbitrary cache-conscious trees with new features.

황환원균과 3가철을 이용한 Trichloroethylene의 제거에 관한 연구

황기철,민지은,박인선,박재우,Hwang, Ki-Chul,Min, Jee-Eun,Park, In-Sun,Park, Jae-Woo 한국지하수토양환경학회 2008 지하수토양환경 Vol.13 No.1

혼합균에서 분리 배양한 황환원균에 의해 발생되는 황화수소가 염소계유기오염물질인 트리클로로에틸렌의 환원에 어떠한 영향을 미치는지, 또한 염소계유기오염물질에 대한 환원력이 있다고 알려진 2가철은 황화수소가 존재할 경우 트리클로로에틸렌의 환원과 어떠한 관계에 있는지를 알아보기 위하여 본 실험을 수행하였다. 황환원균에 독성을 나타내지 않는 수준의 트리클로로에틸렌의 농도에서 황화수소 발생 및 트리클로로에틸렌의 분해 실험을 수행한 결과 황산염의 환원으로 발생한 황화수소의 농도는 4.38 mM, 트리클로로에틸렌의 농도는 큰 변화가 없는 것으로 관찰되었으며 이를 통하여 황환원균에 의해 발생되는 황화수소의 농도가 트리클로로에틸렌을 환원시키기에는 부족하다는 것을 알 수 있었다. 그러나 황화수소의 농도가 위 실험에서 발생된 농도보다 100배 정도 높을 경우(438 mM)에는 트리클로로에틸렌에 대한 환원력이 있음을 확인하였다. 대표적인 산화철인 $Fe_2O_3$(3가철)를 첨가하였을 경우, 황환원균의 생장에 따라 황화수소, 2가철 및 트리클로로에틸렌의 농도변화를 관찰하였으며 이를 통하여 황환원균에 의해서 발생된 황화수소가 산화되면서 3가의 산화철을 2가철로 환원시키고 황화수소에 의하여 환원된 2가철이 트리클로로에틸렌을 분해하여 농도를 감소시키는 것을 확인하였다. 위의 실험결과를 바탕으로 낮은 농도의 황화수소는 트리클로로에틸렌의 환원에 영향을 미치지 못하며 다만, 황화수소에 의해 환원된 2가철이 트리클로로에틸렌을 분해시키는 주요한 요인임을 알 수 있었다. 또한 실제 해수중에서 황환원균과 $Fe_2O_3$가 공존할 경우의 트리클로로에틸렌의 제거 효과를 살펴보기 위한 실험을 한 결과 황환원균이 황화수소를 생성하여 트리클로로에틸렌의 제거에 영향을 줄 수 있는 반응들은 황환원균 생장에 필수적인 탄소원의 농도가 확보될 때 가능하다는 결론을 얻을 수 있었다. Sulfate reducing bacteria (SRB) is universally distributed in the sediment, especially in marine environment. SRB reduce sulfate as electron acceptor to hydrogen sulfide in anaerobic condition. Hydrogen sulfide is reducing agent enhancing the reduction of the organic and inorganic compounds. With SRB, therefore, the degradability of organic contaminants is expected to be enhanced. Ferrous iron reduced from the ferric iron which is mainly present in sediment also renders chlorinated organic compounds to be reduced state. The objectives of this study are: 1) to investigate the reduction of TCE by hydrogen sulfide generated by tht growth of SRB, 2) to estimate the reduction of TCE by ferrous iron generated due to oxidation of hydrogen sulfide, and 3) to illuminate the interaction between SRB and ferrous iron. Mixed bacteria was cultivated from the sludge of the sewage treatment plant. Increasing hydrogen sulfide and decreasing sulfate confirmed the existence of SRB in mixed culture. Although hydrogen sulfide lonely could reduce TCE, the concentration of hydrogen sulfide produced by SRB was not sufficient to reduce TCE directly. With hematite as ferric iron, hydrogen sulfide produced by SRB was consumed to reduce ferric ion to ferrous ion and ferrous iron produced by hydrogen sulfide oxidation decreased the concentration of TCE. Tests with seawater confirmed that the activity of SRB was dependent on the carbon source concentration.

라벨 트리 데이터의 빈번하게 발생하는 정보 추출

백주련 ( Juryon Paik ),남정현 ( Junghyun Nam ),안성준 ( Sung-joon Ahn ),김응모 ( Ung Mo Kim ) 한국인터넷정보학회 2009 인터넷정보학회논문지 Vol.10 No.5

트리 데이터로부터 유용한 정보들을 추출하는 가장 일반적인 방식은 빈번하게 자주 발생하는 서브트리 패턴들을 얻는 것이다. XML 마이닝, 웹 사용 마이닝, 바이오인포매틱스, 네트워크 멀티캐스트 라우팅 등 빈번 트리 패턴 마이닝은 여러 다양한 영역에서 광범위하게 이용되고 있기 때문에, 해당 패턴들을 추출하기 위한 많은 알고리즘들이 제안되어 왔다. 하지만, 현재까지 제안된 대부분의 트리 마이닝 알고리즘들은 여러 가지 심각한 문제점들을 내포하고 있는데 이는 특히 대량의 트리 데이터집합을 대상으로 했을 때는 더 심각해 진다. 주요하게 발생하는 문제점들로는, (1) 계층적 트리 구조의 데이터 모델링, (2) 후보군 유지를 위한 고비용 계산, (3) 반복적인 입력 데이터 집합 스캔, (4) 높은 메모리 의존성이 대표적이다. 이런 문제점들을 발생하게 하는 주요 원인은, 대부분의 기존 알고리즘들이 apriori 방식에 근거하고 있다는 점과 후보군 생성과 빈발 횟수 집계에 anti-monotone 원리를 적용한다는 점에 기인한다. 언급한 문제들을 해결하기 위해, 본 저자들은 apriori 방식 대신pattern-growth 방식을 기반으로 하며, 빈번 서브트리 추출 대신 최대 빈번 서브트리 추출을 목적으로 한다. 이를 통해 제안된 방법은, 빈번하지 않은 서브트리들을 제거하는 과정 자체를 배제할 뿐만 아니라, 후보군 트리들을 생성하는 과정 또한 전혀 수행하지 않음으로써 전체 마이닝 과정을 상당히 개선한다. The most commonly adopted approach to find valuable information from tree data is to extract frequently occurring subtree patterns from them. Because mining frequent tree patterns has a wide range of applications such as xml mining, web usage mining, bioinformatics, and network multicast routing, many algorithms have been recently proposed to find the patterns. However, existing tree mining algorithms suffer from several serious pitfalls in finding frequent tree patterns from massive tree datasets. Some of the major problems are due to (1) modeling data as hierarchical tree structure, (2) the computationally high cost of the candidate maintenance, (3) the repetitious input dataset scans, and (4) the high memory dependency. These problems stem from that most of these algorithms are based on the well-known apriori algorithm and have used anti-monotone property for candidate generation and frequency counting in their algorithms. To solve the problems, we base a pattern-growth approach rather than the apriori approach, and choose to extract maximal frequent subtree patterns instead of frequent subtree patterns. The proposed method not only gets rid of the process for infrequent subtrees pruning, but also totally eliminates the problem of generating candidate subtrees. Hence, it significantly improves the whole mining process.

접근제어 트리에 관한 연구: 공격 트리 적용

엄정호 보안공학연구지원센터(JSE) 2011 보안공학연구논문지 Vol.8 No.2

본 논문에서는 접근제어 모델의 구성요소와 공격 트리의 메커니즘을 활용하여 사용성과 확장성을 향상시킨 접근제어 트리를 설계하였다. 기존의 접근통제 모델은 역할, 직무, 상황을 매개체로 한 접근 제어 메커니즘을 이용하였다. 제안한 접근제어 트리는 접근제어 규칙을 트리 구조로 생성하기 때문에 사용성이 좋고 새로운 접근제어 요소를 추가할 때는 구성 변경이 없기 때문에 확장성이 우수하다. 사용자 인증, 접근권한, 작업기능 등의 요소를 활용하여 사용자에게 객체에 대한 작업모드 권한을 부여한다. 직무와 사용자 역할에 따라 접근권한을 할당하기 때문에 무분별한 객체에 대한 접근을 방지할 수 있고 객체의 중요도에 따라 접근제어 트리 구성요소에 보안속성을 적용함으로써 정보의 기밀성을 유지할 수 있다. In this paper, we designed the usable and scalable access control tree applied to attack tree mechanism and the components of access control model. The existing access control model used role, task, and context based access control mechanism. The proposed access control tree has a good usability as an access control rule is created with a tree structure. Also, it has a good scalability as the new access control components can be added without changing the configuration. It allows operation mode authorization to users, using factors such as user authentication, access right, and operation mode. It can prevent indiscriminate access because access authorization is assigned according to tasks and user roles. And it was possible to keep the confidentiality of information, applying the security properties to the components of access control tree according to the objects importance.

충돌 정보와 m-bit인식을 이용한 적응형 RFID 충돌 방지 기법

이제율 ( Je-yul Lee ),신종민 ( Jongmin Shin ),양동민 ( Dongmin Yang ) 한국인터넷정보학회 2013 인터넷정보학회논문지 Vol.14 No.5

RFID(Radio Frequency Identification)시스템은 하나의 RFDI리더, 다수의 RFID태그 장치들로 이루어진 비접촉방식의 근거리 무선 인식 기술이다. RFID태그는 자체적인 연산 수행이 가능한 능동형 태그와 이에 비해 성능은 떨어지지만 저렴한 가격으로 물류 유통에 적합한 수동형 태그로 나눌 수 있다. 데이터 처리 장치는 리더와 연결되어 리더가 전송받은 정보를 처리한다. RFID 시스템은 무선주파수를 이용해 다수의 태그를 빠른 시간에 인식할 수 있다. RFID시스템은 유통, 물류, 운송, 물품관리, 출입 통제, 금융 등 다양한 분야에서 응용되고 있다. 하지만 RFID시스템을 더욱 확산시키기 위해서는 가격, 크기, 전력소모, 보안 등 해결할 문제가 많다. 그 문제들 중에서 본 논문에서는 다수의 수동형 태그를 인식할 때 발생하는 충돌 문제를 해결하기 위한 알고리즘을 제안한다. RFID 시스템에서 다수의 태그를 인식하기 위한 충돌 방지 기법에는 확률적인 방식과 결정적인 방식 그리고 이를 혼합한 하이브리드 방식이 있다. 본 논문에서는 우선 기존에 있던 확률적 방식의 충돌방지기법인 알로하 기반 프로토콜과 결정적 방식의 충돌방지기법인 트리 기반 프로토콜에 대해 소개한다. 알로하 기반 프로토콜은 시간을 슬롯 단위로 나누고 태그들이 각자 임의로 슬롯을 선택하여 자신의 ID를 전송하는 방식이다. 하지만 알로하 기반 프로토콜은 태그가 슬롯을 선택하는 것이 확률적이기 때문에 모든 태그를 인식하는 것을 보장하지 못한다. 반면, 트리 기반의 프로토콜은 리더의 전송 범위 내에 있는 모든 태그를 인식하는 것을 보장한다. 트리 기반의 프로토콜은 리더가 태그에게 질의 하면 태그가 리더에게 응답하는 방식으로 태그를 인식한다. 리더가 질의 할 때, 두 개 이상의 태그가 응답 한다면 충돌이라고 한다. 충돌이 발생하면 리더는 새로운 질의를 만들어 태그에게 전송한다. 즉, 충돌이 자주 발생하면 새로운 질의를 자주 생성해야하기 때문에 속도가 저하된다. 그렇기 때문에 다수의 태그를 빠르게 인식하기 위해서는 충돌을 줄일 수 있는 효율적인 알고리즘이 필요하다. 모든 RFID태그는 96비트의 EPC(Electronic Product Code)의 태그ID를 가진다. 이렇게 제작된 다수의 태그들은 회사 또는 제조업체에 따라 동일한 프리픽스를 가진 유사한 태그ID를 가지게 된다. 이 경우 쿼리 트리 프로토콜을 이용하여 다수의 태그를 인식 하는 경우 충돌이 자주 일어나게 된다. 그 결과 질의-응답 수는 증가하고 유휴 노드가 발생하여 식별 효율 및 속도에 큰 영향을 미치게 된다. 이 문제를 해결하기 위해 충돌 트리 프로토콜과 M-ary 쿼리 트리 프로토콜이 제안되었다. 하지만 충돌 트리 프로토콜은 쿼리 트리 프로토콜과 마찬가지로 한번에 1비트씩 밖에 인식을 못한다는 단점이 있다. 그리고 유사한 태그ID들이 다수 존재할 경우, M-ary 쿼리 트리 프로토콜을 이용해 인식 하면, 불필요한 질의-응답이 증가한다. 본 논문에서는 이러한 문제를 해결하고자 M-ary 쿼리 트리 프로토콜의 매핑 함수를 이용한 m-비트 인식, 맨체스터 코딩을 이용한 태그 ID의 충돌정보, M-ary 쿼리 트리의 깊이를 하나 감소시킬 수 있는 예측 기법을 이용하여 성능을 향상시킨 적응형 M-ary 쿼리트리 프로토콜을 제안한다. 본 논문에서는 기존의 트리기반의 프로토콜과 제안하는 기법을 동일한 조건으로 실험하여 비교 분석 하였다. 그 결과 제안하는 기법은 식별시간, 식별효율 등에서 다른 기법들보다 성능이 우수하다. RFID(Radio Frequency Identification) system is non-contact identification technology. A basic RFID system consists of a reader, and a set of tags. RFID tags can be divided into active and passive tags. Active tags with power source allows their own operation execution and passive tags are small and low-cost. So passive tags are more suitable for distribution industry than active tags. A reader processes the information receiving from tags. RFID system achieves a fast identification of multiple tags using radio frequency. RFID systems has been applied into a variety of fields such as distribution, logistics, transportation, inventory management, access control, finance and etc. To encourage the introduction of RFID systems, several problems (price, size, power consumption, security) should be resolved. In this paper, we proposed an algorithm to significantly alleviate the collision problem caused by simultaneous responses of multiple tags. In the RFID systems, in anti-collision schemes, there are three methods: probabilistic, deterministic, and hybrid. In this paper, we introduce ALOHA-based protocol as a probabilistic method, and Tree-based protocol as a deterministic one. In Aloha-based protocols, time is divided into multiple slots. Tags randomly select their own IDs and transmit it. But Aloha-based protocol cannot guarantee that all tags are identified because they are probabilistic methods. In contrast, Tree-based protocols guarantee that a reader identifies all tags within the transmission range of the reader. In Tree-based protocols, a reader sends a query, and tags respond it with their own IDs. When a reader sends a query and two or more tags respond, a collision occurs. Then the reader makes and sends a new query. Frequent collisions make the identification performance degrade. Therefore, to identify tags quickly, it is necessary to reduce collisions efficiently. Each RFID tag has an ID of 96bit EPC(Electronic Product Code). The tags in a company or manufacturer have similar tag IDs with the same prefix. Unnecessary collisions occur while identifying multiple tags using Query Tree protocol. It results in growth of query-responses and idle time, which the identification time significantly increases. To solve this problem, Collision Tree protocol and M-ary Query Tree protocol have been proposed. However, in Collision Tree protocol and Query Tree protocol, only one bit is identified during one query-response. And, when similar tag IDs exist, M-ary Query Tree Protocol generates unnecessary query-responses. In this paper, we propose Adaptive M-ary Query Tree protocol that improves the identification performance using m-bit recognition, collision information of tag IDs, and prediction technique. We compare our proposed scheme with other Tree-based protocols under the same conditions. We show that our proposed scheme outperforms others in terms of identification time and identification efficiency.

대학 컴퓨터 실습 교양과목에서의 학업성취 요인에 대한 연구

김완섭 한국정보교육학회 2013 정보교육학회논문지 Vol.17 No.4

본 연구는 실습 중심의 컴퓨터 교양과목에서의 학생들의 학업성취에 영향을 미치는 요인을 발견하기 위한 것이 다. 교과목 운영을 통한 교육성과 즉 학생들의 학업성취도를 향상시키기 위해서는 학업성취도에 영향을 미치는 요 인들을 분석하고 그 결과를 교육에 반영하여 개선하는 순환 과정이 필요하다. 특히 컴퓨터 실습을 중심으로 하는 실용 교과목은 이론 중심의 과목들과 특성이 다르므로 그 요인에 대한 연구가 요구된다. 본 연구에서는 요인을 발 견하기 위한 분석으로 로지스틱 회귀분석과 데이터마이닝 분야의 결정트리 분석을 수행하였다. 실험을 위한 데이 터로는 서울소재 S대학의 교양필수과목에서 시행된 MOS 자격증 시험결과를 사용하였다. 로지스틱 회귀분석을 통 해서는 담당교수, 수강인원, 수업시간, 그룹(강의기간) 순으로 중요성을 파악할 수 있었다. 데이터마이닝의 의사결 정트리 분석을 통해서는 그 외에 학번, 재수강 여부, 강의실 환경의 추가 요인을 발견할 수 있었고, 특히 다양한 요 인들이 학업성취에 복합적으로 영향을 미치는 것을 트리 모형을 통해 파악할 수 있었다. 분석 결과의 트리모형을 결과로 제시하였으며, 수식을 제안하여 여러 개의 트리 모형으로부터 요인의 중요도를 수치화하여 제시하였다. The purpose of this study is to find out the factors of the students' achievement on the computer training courses which are based on computer practice. In order to improve the academic achievement of the students, it is necessary to analyze the factors affecting academic achievement and apply the results of the analysis to education. In particular, it is necessary to study for finding out factors of the academic achievement in practical computer training courses, because these courses are different from other courses focusing on the theory. In this study, in order to find out the factors, the logistic regression analysis and the decision tree analysis which is the field of data mining were peformed. For the experimental data, the test results of the MOS certification of the S university in seoul were used. Through logistic regression analysis it is found that the factors of the professors, class size, lecture time, group(lecture period) are important in order. Through decision tree analysis of data mining, it is found that there are some additional factors ; entrance year, whether the course is retaken, and the classroom environment. and these various factors effect the academic achievement compositively as identified through the model tree. The tree model was presented as a result of the analysis, and the importance of the factors is expressed numerically from multiple tree models by using the proposed mathematical formula.