http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
송명철(Myung-Chul Song),유관우(Kwan-Woo Ryu) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2
본 논문에서는 네트워크 모델 병렬 컴퓨터상에서 NC 최적인 알고리즘을 제시한다. 입력의 크기가 n 인 어떤 문제가 주어졌을 때, 그 문제를 해결하는 가장 좋은 순차 알고리즘의 수행시간을 Ta(n) 이라 하자 이 문제를 해결하는 병렬 알고리즘이 상수 k 에 대하여 O(log^kn) 개의 프로세서를 사용하여 O(T_s(n)/log^kn) 시간에 수행될 때 NC 최적이라고 한다. 본 논문에서 소개하는 모든 알고리즘은 p-프로세서 파이프라인 하이퍼큐브에서 O(n/p + log³p (loglogp)²) 시간에 수행되며, 약 하이퍼큐브 및 Shuffle exchange, Cube-connected cycles, Butterfly 모델상에서는 O(nlogp/p + log³p (loglogp)²) 시간에 수행된다. 또한 본 논문에선 고려한 문제들의 약 하이퍼큐브 및 bounded-degree 네트워크 상에서의 하한계를 보인다.