http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
장의덕(Eui-Deog Jang),방혜자(Hye-Ja Bang),전문석(Moon-Seog Jun),이철희(Chul-Hee Lee) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1
여러가지 제약 조건하의 문맥 자유 그래프 언어(CFGL) 상에서 우리는 연결성 문제의 복잡도를 분석한다. 문맥 자유 그래프를 일반 형식 언어 형태로 표현하고 이것을 다시 그래프로 유도하는 규칙들을 보이고 튜링 변환기를 통한 문맥 자유 그래프 언어의 연결성 결정 시간인 DEXPTIME을 DLOGTIME으로 줄일 수 있는 Mesh of tree상에서의 효율적인 병렬 알고리즘을 제안한다. 우리의 결과는 NETWORK,CAD,VLSI등의 공학 설계에 많은 도움을 줄 것이다.
문맥 자유 그래프 언어의 효과적인 연결성 문제의 복잡도 분석
장의덕(Eui-Deog Jang),방혜자(Hye-Ja Bang),전문석(Moon-Seog Jun),이철희(Chul-Hee Lee) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2
여러가지 제약 조건하의 문맥 자유 그래프 언어상에서 우리는 연결성 문제들의 간결한 그래프 표현과 그에 대한 복잡도를 분석한다. 문맥 자유 그래프 문법인 SNLC 문법을 정의하고 그래프 생성시 확장 과정에서 필요한 많은 공간을 줄일 수 있는 축약방법을 소개한다. 그래프상의 연결성 문제의 효과적 해결책의 방법을 예증하고 축약 병렬 알고리즘을 구현하고 복잡도를 분석한다. 우리의 결과는 NETWORK, CAD, VLSI등의 공학 설계에 많은 도움이 될것이다.
분산 네트워크에서 이중 연결 요소를 찾는 병렬 알고리즘
장의덕(Eui-Deog Jang),전문석(Moon-Seog Jun),이철희(Chul-Hee Lee) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2
본 논문에서는 n개의 프로세서와 m개의 간선을 가진 본산 네트워크에서 이중 연결 요소를 찾는 병렬 알고리즘을 제안한다. 우리는 이 알고리즘에서 메세지 복잡도 O(m+n)을 얻었으며 시간 복잡도 O(log n)을 얻었다. 이것은 비동기 또는 동기 시스템에 적용될 수 있으며 다른 APP 문제에 적용 가능할 것이다.
방향그래프에서 사이클을 찾기 위한 효율적인 병렬알고리즘
이정현(Jeong-Hyun Yi),장의덕(Eui-Deog Jang),전문석(Moon-Seog Jun),이철희(Chul-Hee Lee) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1
본 논문은 방향그래프에서 사이클을 찾는 알고리즘으로 Transitive Closure를 기본구조로 하고 있는 All Pairs Shortest Paths 알고리즘을 주로 사용하여 사이클을 찾을 수 있도록 변형하였다. 또한 이 알고리즘을 2차원 시스톨릭 배열에서 구현하면 O(N²)이지만, 본 논문에서는 매우 큰 크기의 방향그래프를 기존의 작은 용량(m)의 VLSI 구조에 맞추어 분할하여 3차원 Mesh of Tree에서 구현하여 속도를 향상시켰다. 이 분할 맵핑 방법을 사용하지 않고 3차원 Mesh of Tree에서 구현할 경우의 속도는 O(NlogN)이지만, 분할 맵핑 방법을 적응할 경우 그 속도는 O( (N/m)log(N/m)) 이 된다.