Earticle

언플러그드 컴퓨터과학 활동은 카드, 실, 크래용 등 주변의 물건들을 사용하는 놀이와 퍼즐을 통하여 컴퓨터 과학에 대하여 학습하는 활동의 모음이다. 기존의 언플러그드 활동은 알고리즘을 소개하고 실생활에 적용하는 것에 편중되어 문제 해결을 위하여 알고리즘을 적용하기 전에 이루어져야 할 자료의 표현 방법에 대한 활동은 상대적으로 부족한 실정이다. 본 연구에서는 초등학생들에게 그래프 이론의 기본 개념과 실생활에 적용할 수 있는 그래프 알고리즘을 소개하는 언플러그드 수업을 설계하고 수업을 실시한 후에 설문조사를 통하여 수준의 적절성과 수업 효과에 대하여 평가하였다. 설문 응답을 분석한 결과 모든 응답자가 본 연구에서 제시한 수업 내용이 초등학생에게 적합하다고 응답하였고 수업의 효과와 적절성에 대하여 긍정적인 응답을 보였다.

Computer Science Unplugged is a collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around. In spite of the success of unplugged activities, the unplugged resources for experiencing the concepts of data structures is lacked. In this study, we design, implement and survey the 3 hour lessons of the core concepts of graph theory and the shortest path algorithm for the primary students using computer science unplugged activities. Our survey results showed that our lesson plan is adequate for primary school students and will have a positive effects for primary school students.

Transport with minimum time cost and distance remains to be an important research area in intelligent transport systems. Shortest path algorithms are primary methods to address simplified problems, which could not be well applied in high-dimensional real situations. We realized the minimum cost and maximum flow result via classical iterative algorithm based on graph theory, adjacency matrix is well applied to express the relationship between transport nodes, a topological sorting transport map is adopted to verify these approaches.

In this paper, we report the development of two DEM (digital elevation model) generation algorithms over urban areas from an IKONOS stereo pair. One ("EpiMatch") is originally developed for SPOT images and modified for IKONOS images. It uses epipolar geometry for accurate DEM generation. The other is based on graph-cut algorithm in 3D voxel space. This algorithm is believed to work better on height discontinuities than EpiMatch. An IKONOS image pair over Taejon city area was used for tests. Using ground control points obtained from differential GPS, camera model was set up and stereo matching applied. As a result, two DEMs over urban areas were produced. Within a DEM from EpiMatch small houses appear as small "cloudy" patches and large apartment and industrial buildings are visually identifiable. Within the DEM from graph-cut we could achieve better height information on building boundaries. The results show that both algorithms can generate DEMs from IKONOS images although more research is required on handling height discontinuities (for "EpiMatch") and on faster computation (for "Graph-cut").

Based on the geometric representation an efficient al-gorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes only O(n log n) time and O(n) space where n represents the number of vertices. The proposed se-quential algorithm can easily be implemented in parallel which takes O(log n) time and O(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.

본 논문에서는 고속도로 교통망의 연결성을 분석하고 중심이 되는 도시를 예측하기 위하여 그래프 이론을 이용하여 접근성 지표의 알고리즘을 제안한다. 먼저 그래프 이론을 이용하여 2025년 고속도로 교통망을 운송네트워크로 표현한다. 그리고 운송네트워크로부터 2025년 고속도로 교통망의 연결성을 효율적이고 정확하게 분석하고 예측하기 위한 접근성 지표의 알고리즘을 구현한다. 제안된 접근성 지표의 알고리즘을 통하여 얻은 2025년의 분석 결과를 활용하여 고속도로의 운송네트워크에서 교통의 중심도시를 찾을 수 있고, 상대적으로 교통의 접근성이 낮은 도시를 찾아, 향후 전국의 고속도로 교통망의 연결성을 개선시키는 정보로 활용한다.

In this paper, we propose the algorithms of accessibility indices using graph theory to analyze the connectivity of the highway traffic network and predict the central city. First, we find a transportation network that represents the highway traffic network in 2025 using graph theory. And we implement the algorithms of accessibility indices to efficiently and accurately analyze and predict the connectivity of the highway traffic network in 2025 from a given transportation network. Through the analysis results of 2025 obtained by using the proposed algorithm, we can find a city that is the center city of transportation in the highway transportation network, and it is used as information to improve the connectivity of the nationwide highway traffic network in the future.

그래프는 실세계의 많은 문제를 효과적으로 모델링하여 해를 구할 수 있는 강력한 방법을 제공하기 때문에 그래프의 표현 방법과 알고리즘 개발에 다양한 연구가 진행되어 왔다. 하지만, 대부분의 연구가 메인 메모리에 수용 가능한 크기를 갖는 그래프만을 고려하였기 때문에 큰 문제에 적용하기 위해서는 아직도 많은 어려움이 존재한다. 이를 극복하기 위하여 본 논문에서는 관계형 데이타베이스 이론에 기반하여 그래프를 표현하고 그래프 알고리즘을 정의할 수 있는 방법을 제안한다. 이 방법에서 그래프는 릴레이션으로 표현되며 그래프의 각 정점과 간선은 이 릴레이션의 튜플로서 저장된다. 이렇게 저장된 그래프에 대한 알고리즘은 추출, 선택, 죠인과 같은 관계대수 연산을 이용하여 정의되며 SQL과 같은 데이타베이스 언어를 사용하여 구현될 수 있다. 또한, 본 논문은 그래프의 저장 및 관리뿐만 아니라 다양한 응용프로그램 개발에도 사용될 수 있는 기본적인 그래프 함수들을 라이브러리화 하였다. 이와 같은 데이터베이스에 기반한 방법은 메모리에 수용되지 않는 크기의 그래프를 효과적으로 처리할 수 있는 방법을 제공할 뿐만 아니라 다양한 응용프로그램 개발을 용이하게 할 것이다. 또한, 데이타베이스가 제공하는 기본적인 기능인 다중사용자에 의한 동시공용 등과 같은 많은 장점을 가진다.

Graphs have provided a powerful methodology to solve a lot of real-world problems, and therefore there have been many proposals on the graph representations and algorithms. But, because most of them considered only memory-based graphs, there are still difficulties to apply them to large-scale problems. To cope with the difficulties, this paper proposes a graph representation and graph algorithms based on the well-developed relational database theory. Graphs are represented in the form of relations which can be visualized as relational tables. Each vertex and edge of a graph is represented as a tuple in the tables. Graph algorithms are also defined in terms of relational algebraic operations such as projection, selection, and join. They can be implemented with the database language such as SQL. We also developed a library of basic graph operations for the management of graphs and the development of graph applications. This database approach provides an efficient methodology to deal with very large- scale graphs, and the graph library supports the development of graph applications. Furthermore, it has many advantages such as the concurrent graph sharing among users by virtue of the capability of database.

본 논문에서는 자율 에이전트에 의해 미지의 공간을 탐사하는 실시간 그래프 탐색 알고리즘 DFS-RTA*와 DFS-PHA*를 제안하고 그 효율성을 비교한다. 두 알고리즘들은 모두 깊이-우선 탐색(DFS)을 기초로 하고 있으며, 직전 노드로의 빠른 후진(backtrack) 을 위해 각각 실시간 최단 경로 탐색 방법인 RTA*와 PHA*를 적용하는 것이 특징이다. 본 논문에서는 대표적인 3차원 온라인 게임 환경인 Unreal Tournament 게임과 지능형 캐릭터 에이전트인 KGBot를 이용한 실험을 통해 두 탐색 알고리즘의 완전성과 효율성을 분석해본다.

디지탈화된 지형 정보는 조망분석, 토목계획이나 설계, 또는 지리정보시스템등 여러 분야 에 필요한 요소가 된다. 또한 컴퓨터에 적절한 형식으로 입력된 지형정보는 모의 비행훈련이나 무인비행장치에서도 사용될 수 있다. 지형정보는 지도위에 등고선을 비롯한 여러가지 기호들로 표시되어 있어서 훈련된 요원에 의해 분석된다. 자동분석을 위해서는 컴퓨터에 입력되어야 하는 데 디지타이징 타블렛과 같은 장비를 사용하여 수동으로 입력하는 것은 많은 시간과 인력을 필요 로 한다. 본 논문에서는 이차원 지형도로부터 삼차원 지형정보를 자동적으로 추출하는 방법을 다 루고 있다. 등고선 조각연결 알고리즘을 포함하는 몇 가지 알고리즘들이 제안되었고 실제 지형도 를 사용하여 실험되었다.

Digitalized topographic information is necessary for many areas such as landscape analysis, civil engineering planning and design, and geographic information systems. It can also be used in flight simulator and automatic navigation of unmanned plane if it is stored in computer in relevant format. Topographic information is coded with various symbols including contour lines, and is analyzed by trained personnels. The information should be stored in computer for automatic analysis, but it requires a lot of time and manpower to enter the contours using manual input devices such as digitizing tablet. This paper deals with automatic extraction and reconstruction of 3D topographic information from 2D terrain map. Several algorithms were developed in this work including contour segment finding algorithm and contour segment linking algorithm. The algorithm were tested using real 2D terrain map.

In this paper we consider strongly polynomial variations of the auction algorithm for the single origin/all destinations shortest path problem. These variations are based on the idea of graph reduction, that is, deleting unnecessary arcs of the graph by using certain bounds naturally obtained in the course of the algorithm. We study the structure of the reduced graph and we exploit this structure to obtain algorithm with O(n min{m, nlogn}) and O(n$^{2}$) running time.

This paper proposes a path planning algorithm for mobile robot. To generate an optimal path and minimum time path for a mobile robot, we use the Genetic Algorithm(GA) and Visibility Graph. After finding a minimum-distance between start and goal point, the path is revised to find the minimum time path by path-smoothing algorithm. Simulation results show that the proposed algorithms are more effective.

This paper proposes a path planning algorithm for mobile robots. To generate a minimum-distance path for mobile robots, we use the Genetic Algorithm(GA) and Visibility Graph. After finding a minimum-distance path between a start and a goal point, the path is revised to find the smooth subminimum-distance path by a path-smoothing algorithm. Simulation results show that the proposed algorithms are effective.

객체지향 프로그래밍 방식으로 인해 프로그램의 재사용성이 증대되었다. 객체들을 재사용함으로서 프로그램을 수정 갱신하는 일이 더욱 많아져 점진적 데이터 흐름 분석 기법은 코드 최적화의 성능을 향상하는 중요한 방안이 되었다. 이에 본 논문에서는 데이터 흐름 분석을 위한 지배자연결그래프를 점진적으로 구성하는 알고리즘을 제안하고 이의 타당성과 성능을 실험을 통하여 제시하였다.

병렬 처리 시스템의 상호연결 네트워크로써 스타 그래프 구조간 그간 널리 사용되어 왔던 하이퍼규브에 비해 지름 및 차수 등의 특성에 우수한 성능을 보임으로 인해 최근 많은 연구자들의 관심을 받고 있다. 스타 그래프 네트워크에서 여러가지 통신문제들이 연구되어 지고 있는데 그러한 통신 문제 중 에 가장 기본이 될수있는 문제 중의 하나가 브로드캐스팅이다. 본 논문에서는 윕홀라우팅을 지원하는 스타 그래프 네트워크 시스템에서의 브로드캐스팅 문제를 다룬다. 윔홀라우팅을 사용하는 네트워크에서는 전송 노드간의 거리보다 전송 시 링크 충돌을 최소화하는 것이 전체 통신 시간을 줄이는 중요한 요소가 되는 데 본 논문에서는 스타 그래프 네트워크에서의 해밀 토니안 경로를 이용하여 링크 충돌이 없이 n 차원 스타 네트워크$([long_n n!]+1)$ 통신스텝이 전체 브로드캐스팅이 완료되는 알고리즘을 제시한다. 이는 이론 절 하한값 $([long_n n!]+1)$ 에 근접한 결과로 기존의 n-1 통신 스텝이 걸리는 알고리즘 보다 향상된 결과이다.

Recently star networks are considered as attractive alternatives to the widely used hypercube for interconnection networks in parallel processing systems by many researchers. One of the fundamental communication problems on star graph networks is broadcasing In this paper we consider the broadcasting problems in star graph networks using wormhole routing. In wormhole routed system minimizing link contention is more critical for the system performance than the distance between two communicating nodes. We use Hamiltonian paths in star graph to set up link-disjoint communication paths We present a broadcast algorithm in n-dimensional star graph of N(=n!) nodes such that the total completion time is no larger than $([long_n n!]+1)$ steps where $([long_n n!]+1)$ is the lower bound This result is significant improvement over the previous n-1 step broadcasting algorithm.