등식체계에서의 자동증명

위규범 한국수학사학회 1998 Journal for history of mathematics Vol.11 No.2

It is an undecidable problem to determine whether a given equation logically follows from a given set of equations. However, it is possible to give the answer to many instances of the problem, even though impossible to answer all the instances, by using rewrite systems and completion procedures. Rewrite systems and completion procedures can be implemented as computer programs. The new equations such a computer program generates are theorems that hold in the given equational theory. For example, a completion procedure applied on the group axioms generates simple theorems about groups. Mathematics students' teaming to know the existence and mechanisms of computer programs that prove simple theorems can be a significant help to promote the interests in abstract algebra and logic, and the motivation for studying.

셀룰러 오토마타 상에서 자기 복제

위규범 한국수학사학회 1999 Journal for history of mathematics Vol.12 No.1

We survey the researches on self-reproducing structures on cellular automata. Self-reproduction is the foremost characteristic of life, and cellular automata are ideal model for studying artificial life. From the early studies by Von Neumann to late results on computational models using self-reproducing structures and emergence of self-replication are covered. Also possible applications of self-replicating structures are listed.

Knuth-Bendix 완전화 절차에서의 규칙 분할과 공정성

위규범(Kyubum Wee) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.10

Knuth-Bendix 완전화 절차에서 방향을 줄 수 없는 등식을 두 개의 규칙으로 분할하는 것은 중요한 태크닉이다. 규칙분할은 많은 경우에 완전화 절차가 완전시스템을 생성하는데 도움을 주지만 어떤 경우에는 완전화 과정을 방해하기도 하며 완전화 절차가 종료하지 못하게 하기도 한다. 본 논문에서는 반복적인 규칙 분할이 어떻게 완전화 절차의 공정성을 붕괴시키는지 관찰하고, 공정성을 유지히는 방법을 제시한다. 또한 어떠한 조건하에서 반복적인 규칙분할이 일어나는지 조사한다. 이 결과들은 사용자 개입없이 완전한 rerwrite system을 생성함을 용이하게 한다. Splitting a non-orientable equation into two rules by introducing a new operator is an important technique in the Knuth-Bendix completion procedure. Splitting sometimes helps the Knuth-Bendix procedure generate a complete rewrite system, while other times it hinders the completion process or even leads to divergence. We show how the fairness of the Knuth-Bendix procedure can be disrupted by repeated splitting, and consider how to maintain the fairness. The causes of repeated splitting are also investigated. It is shown that how these results can be used to facilitate the automatic generation of complete rewrite systems.

최소 원형 스트링

위규범(Wee Kyun Bum),예흥진(Yeh Hong Jin) 한국정보처리학회 1998 정보처리학회논문지 Vol.5 No.9

We present a linear time algorithm for finding a lexicographically minimal circular string in a given string. The problem was motivated by an effort to implement state transition functions in isotropic cellular automata. A native algorithm for the problem would require quadratic time. The proposed algorithm runs in linear time by keeping the result of comparisons of substrings and reusing it afterwards when the same computation is needed.

정보과학 영재교육을 위한 학생선달과 교육내용

예홍진,위규범 한국영재학회 1999 영재교육연구 Vol.9 No.2

일반적으로 영재교육을 실시함에 있어서 가장 먼저 선행되어야 할 것은 영재아 판별기준을 정해 학생선발과정을 운영하는 것과 실제 가르칠 교육내용을 구체적으로 정의하여 교재를 개발하는 것이다. 특히, 최근에 각광받고 있는 정보과학 분야의 영재교육에 대한 연구는 이제 시작단계에 불과하여 서로 다른 이론적 근거와 주관적인 기준에 따라 전국의 과학연재교육센터들을 중심으로 다양한 논의가 활발하게 이루어지고 있다. 본 논문에서는 아주대학교 과학영재교육센터에서 초등학교 4학년부터 중학교 3학년까지의 학생들을 대상으로 운영되고 있는 정보과학 영재교육 프로그램을 자세히 소개함으로써, 앞으로 정보과학 분야의 영재교육을 위한 구체적인 영재판별기준과 학생선발절차는 물론 체계적인 교육과정 및 교과목의 개발을 위한 하나의 실례로써 소개하고자 한다.

유전자 알고리즘을 이용한 광상호 연결망에서 파장분할다중방식의 리스트 스케쥴링

정혜진,위규범,예홍진,홍만표,변광준,Jung, Hea-Jin,Wee, Kyu-Bum,Yeh, Hong-Jin,Hong, Man-Pyo,Byeon, Kwang-June 한국정보처리학회 1998 정보처리논문지 Vol.5 No.9

파장분할다중방식의 패킷 전송을 하는 광상호연결망에서 노드들 사이에 송수신하는 패킷의 수가 임의로 주어지는 일반적인 교통량의 스케쥴링은 NP-complete 문제이며, 이 경우에 대하여 리스트 스케쥴링이 좋은 성능을 보임이 알려져 있다. 리스트 스케쥴링은 각 시간 단위에 배치할 송신자를 고려하는 순서에 따라서 스케쥴 결과가 달라질 수 있다. 본 논문에서는 송신자를 고려하는 순서를 다양하게 시도하여 효율적인 스케쥴을 구하는 방법을 제시한다. 다양한 순서를 탐색하는 방법으로서 유전자 알고리즘을 이용한다. The problem of scheduling general packet traffic on WDM optical interconnection networks is NP-complete, It is known that the list scheduling is a good approximation algurithm fur this problem, The resulting list schedules vary depending on the order of transmitters considered to be placed on each time slot We propose an improvement of the list scheduling that tries different orders of transmitters to obtain shorter schedule lengths, Genetic algorithms are used to explore various orders of transmitters.

Passive Star형 광상호연결망에서 광/전 변환을 고려한 최적의 전송 스케쥴링

이상수,위규범,홍만표,예홍진,Lee, Sang-Su,Wi, Gyu-Beom,Hong, Man-Pyo,Ye, Hong-Jin 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.7

본 논문은 N개의 노드로 구성된 파장분할다중화(Wavelength Division Multiplexing) 방식의 Passive Star형 광상호연결망에서 K개의 파장이 사용가능 할 때 패킷 전송 스케쥴링 문제를 다루고 있다. 모든 노드는 파장조율이 가능한 송신기와 특정 파장에 고정된 수신기를 각각 한 개씩 가지고 있으며, 하나의 패킷이 송신기로부터 수신기까지 전송되는 데에 걸리는 시간은 항상 일정하다고 가정한다. 최적의 패킷 전송 스케쥴이란 송신노드 입장에서 임의의 파장에서 다른 파장으로 송신기를 조율하는 데에 따른 지연시간(turning delay)을 고려하여 같은 시간에 최대한 많은 서로 다른 파장을 사용하도록 함과 동시에, 수신노드의 입장에서 수신된 패킷들의 광/전 변환에 따른 지연시간(conversion delay)을 고려하여 패킷의 수신간격을 일정하게 유지함으로써 모든 패킷이 최소시간 내에 전송될 수 있도록 언제 어떤 파장을 사용하여 패킷들을 전송할 것인지 결정하는 것을 말한다. 본 논문에서는 파장조율에 따른 지연시간을 $\delta$로 나타낼 때 모든 노드가 자기 자신을 제외한 다른 모든 노드에 주기적으로 전방송(all-to-all broadcast)을 반복하는 경우에 임의로 주어진 N, K, $\delta$의 값에 대하여 최적의 패킷 전송 스케쥴을 구할 수 있는 알고리즘을 제안하고 있다. 또한, N이 K로 나누어 떨어지면 최적의 전방송 주기는 [NK($\delta$+1)/{$N_2$-N-NK+K$^2$+K}](N-1)임을 증명하였다.

침입탐지를 위한 유한상태기계의 생성 기법

임영환,위규범,Lim, Young-Hwan,Wee, Kyu-Bum 한국정보처리학회 2003 정보처리학회논문지 C : 정보통신,정보보안 Vol.10 No.2

침입 탐지 기법에 있어서 유한상태기계(finite automata)를 통해 정상 행위를 프로파일링 하는 연구들이 많이 진행되어 왔으나, 자동으로 간결한 형태의 오토마타를 생성하는 것이 매우 어려웠다. 이전 연구에서는 프로세스를 오토마타로 프로파일링 하기 위해 빈번한 시스템 콜 서열(system call sequence)을 매크로(macro)로 치환하고, 이러한 서열을 인식하는 오토마타를 수작업으로 생성하였다. 본 논문에서는 이러한 오토마타를 자동적으로 생성할 수 있도록, 서열 정합(sequence alignment)을 수행하고 스트링으로부터 반복되는 패턴들을 찾아내어 프로세스들로부터 매크로를 추출하고 오토마타를 생성해내는 방법을 제안한다. 생성된 오토마타가 침입탐지에 효과적으로 이용될 수 있음을 실험을 통하여 보였다. Although there have been many studies on using finite automata for intrusion detection, it has been a difficult problem to generate compact finite automata automatically. In a previous research an approach to profile normal behaviors using finite automata was proposed. They divided the system call sequence of each process into three parts prefix, main portion, and suffix, and then substituted macros for frequently occurring substrings. However, the procedure was not automatic. In this paper we present algorithms to automatically generate intrusion detection automata from the sequence of system calls resulting from the normal runs of the programs. We also show the effectiveness of the proposed method through experiments.

중국 자동차 번호판 인식

안영준,위규범,홍만표,Ahn, Young-Joon,Wee, Kyu-Bum,Hong, Man-Pyo 한국정보처리학회 2007 정보처리학회논문지B Vol.14 No.2

도난차량 추적과 주차 관리 시스템 및 과속 차량 탐지 등에 광범위하게 사용되는 차량 번호판 인식 시스템을 구현하였다. 인식 시스템은 번호판을 추출하는 부분과 추출된 번호판을 인식하는 단계로 나뉘어진다. 번호판 추출 단계에서는 영상의 기울기를 측정하기 위해 수평 성분만을 추출하는 필터를 사용하여 차창과 번호판을 포함한 차량 전면부의 수평 성분만을 검출한 후 이것의 기울기를 측정하는 방법으로 번호판의 기울기를 구한다. 세그먼트 추출 과정에서는 신경화소 또는 배경화소가 연속하여 나타나는 블록의 계수의 변화를 감지하여 각 문자 또는 숫자를 추출한다. 각 문자 또는 숫자의 인식 단계에서는 잡음의 영향을 덜 받으며 높은 정확도를 보이는 비교템플렛 방법을 제안한다. 기존의 원형정합 방법과 히스토그램 방법과의 비교 실험을 통하여 제안한 방법의 인식 성능이 우수함을 보인다. We implement automobile license plates recognition system. These days automobile license plate recognition systems are widely used for tracing stolen cars. managing parking facilities, ticketing speeding cars, and so on. Recognition systems largely consist of three parts plates extraction, segments extraction, and segment recognition. For plates extraction, we measure the degree of inclination of plate. We use filters that extract only the horizontal components of the front of an automobile to measure the degree of inclination. For segment extraction, we trace the change of the number of blocks that consist solely of foreground pixels or background pixels as the horizontal scanning line moves along upward. For recognition of each individual letter or digit, we devise a variant of template matching method, called comparative template matching. Through experiments, we show that comparative template matching is less prone misled by noises and exhibits higher performance compared to the traditional method of template matching or histogram based recognition.

정보과학 영재교육을 위한 학생선발과 교육내용

예홍진,위규범 한국영재학회 1999 영재교육연구 Vol.9 No.2

일반적으로 영재교육을 실시함에 있어서 가장 먼저 선행되어야 할 것은 영재아 판별기준을 정해 학생선발과정을 운영하는 것과 실제 가르칠 교육내용을 구체적으로 정의하여 교재를 개발하는 것이다. 특히, 최근에 각광받고 있는 정보과학 분야의 영재교육에 대한 연구는 이제 시작단계에 불과하여 서로 다른 이론적 근거와 주관적인 기준에 따라 전국의 과학연재교육센터들을 중심으로 다양한 논의가 활발하게 이루어지고 있다. 본 논문에서는 아주대학교 과학영재교육센터에서 초등학교 4학년부터 중학교 3학년까지의 학생들을 대상으로 운영되고 있는 정보과학 영재교육 프로그램을 자세히 소개함으로써, 앞으로 정보과학 분야의 영재교육을 위한 구체적인 영재판별기준과 학생선발절차는 물론 체계적인 교육과정 및 교과목의 개발을 위한 하나의 실례로써 소개하고자 한다. There are two things that should precede others in practicing gifted education. One is to establish criteria on selecting pupils, and the other is to develop curriculum by defining specific contents to teach. In particular, gifted education in the area of information science is in such an early stage that several gifted education centers are hotly discussing those matters based on various theoretical foundations and subjective standards. In this paper, we introduce in detail the gifted education programs in information science for the students ranging from the elementary school fourth grade to the middle school third grade that is being administered at the Center for Gifted Education at Ajou University. It will serve as a case study of systematic curriculum development as well as criteria and procedure of selecting pupils for gifted education in information science.