Sorting and Searching
作者： Yoshiyasu Takefuji
DOI: 10.1007/978-1-4615-3642-0_9
关键词: Electronic circuit 、 Computer science 、 Binary logarithm 、 Computation 、 Sorting 、 Algorithm 、 Artificial neural network 、 String searching algorithm 、 Parallel algorithm 、 Parallel sorting
摘要: A new neural network parallel algorithm for sorting problems is introduced in this Chapter. The proposed using 0(n2) processors requires two and only steps, not depending on the problem size, while conventional O(n) by Leighton needs computation time 0(log n). similar solving string search problems.The uses 0(m×n) where n length of a text m pattern. It iteration steps to find pattern text, best existing O(loglog This Chapter based paper published IEEE Trans, Circuits Systems (Takefuji Lee 1990a) Journal Neural Network Computing 1990).
springer.com
sci-hub.st 参考文章(14)
Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin, Highly parallelizable problems Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 309- 319 ,(1989) , 10.1145/73007.73036
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
Zvi Galil*, Optimal parallel algorithms for string matching symposium on the theory of computing. pp. 240- 248 ,(1984) , 10.1145/800057.808687
N. Alon, Y. Azar, The average complexity of deterministic and randomized parallel comparison-sorting algorithms SIAM Journal on Computing. ,vol. 17, pp. 1178- 1192 ,(1988) , 10.1137/0217074
M. Hirata, H. Yamada, H. Nagai, K. Takahashi, A versatile data string-search VLSI IEEE Journal of Solid-state Circuits. ,vol. 23, pp. 329- 335 ,(1988) , 10.1109/4.992
Y. Takefuji, K.C. Lee, A super-parallel sorting algorithm based on neural networks IEEE Transactions on Circuits and Systems. ,vol. 37, pp. 1425- 1429 ,(1990) , 10.1109/31.62417
Ricardo A. Baeza-Yates, Improved string searching Software - Practice and Experience. ,vol. 19, pp. 257- 271 ,(1989) , 10.1002/SPE.4380190305
Foster, Kung, The Design of Special-Purpose VLSI Chips IEEE Computer. ,vol. 13, pp. 26- 40 ,(1980) , 10.1109/MC.1980.1653338
Tom Leighton, Tight bounds on the complexity of parallel sorting symposium on the theory of computing. pp. 71- 80 ,(1984) , 10.1145/800057.808667
G. De V. Smit, A comparison of three string matching algorithms Software: Practice and Experience. ,vol. 12, pp. 57- 66 ,(1982) , 10.1002/SPE.4380120106