×

zbMATH — the first resource for mathematics

Parallel probabilistic searching and sorting algorithms. (English) Zbl 0727.68021
Kybernetika 26, Suppl. No. 1-6, 93 pp. (1990).
This is an exhaustive presentation of the author’s research in the complexity of probabilistic parallel search for large data bases. An introductory chapter is devoted to a presentation of the problem. The second chapter deals with the exact formulations connected with Turing machines and Church’s thesis, the third one presents the notions of probability theory used in the sequel. The fourth chapter deals with probabilistic search based on uniform probabilities for picking indices in a data base on \(N\) items, several levels of processors and reliable testing, showing a best time.
MSC:
68P10 Searching and sorting
68W15 Distributed algorithms
68P15 Database theory
Full Text: EuDML
References:
[1] M.A. Ajzerman: Logika, automaty, algoritmy (Logic, Automata, Aîgorithms - in Czech). Academia, Prague 1971.
[2] C Calude: Theories oí Computational Complexity. North Holland, Amsterdam 1988.
[3] M. Davis: Computability and Unsolvability. McGraw-Hill, New York 1958. · Zbl 0080.00902
[4] Z. Manna: Mathematical Theory of Computation. McGraw-Hill, New York 1974. Czech translation: SNTL, Prague 1981. · Zbl 0353.68066
[5] J. Mikloško, V. E. Kotov: Algorithms, Software and Hardware of Parallel Computers. Springer-Verlag, Berlin and Veda, Bratislava 1984. · Zbl 0594.68003
[6] H. Rogers: Theory oî Recursive Functions and Efïective Computability. McGraw-Hill, New York 1967. Russian translation: Mir, Moseow 1972.
[7] K. Wagner, G. Wechsung: Computational Complexity. VEB Deutscher Verlag der Wissenschaften, Berlin 1986. · Zbl 0584.68062
[8] V. Černý: Fyzikálne aspekty v matematickej informatike (Physical aspects in mathematical informatics - in SIovak). SOFSEM 1987, pp. 81-103.
[9] M. Davis: Computability and Unsolvability. McGraw-Hill, New York 1958. · Zbl 0080.00902
[10] W. Feller: Ап Iптгоdустіоп то РгоЬаЬШту Тнєогу апd ітд3 Аррlісатіопд3, I, II. J. Wiley and Sons, New York 1957 (vol.I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967.
[11] P. Halmos: Measure Theory. Van Nostrand, London, 1968.
[12] I. Kramosil: Paralelní pravděpodobnostní algoritmy jako prezentace nového paradigmatu ve znalostních systémech (Parallel probabilistic algorithms as presentation of new paradigma in knowledge systems - in Czech). Uplatnění expertníeh - znalostních systémů ve stavebnictví, Prague 1987, pp. 6 - 23.
[13] I. Kramosil: Extremum-searching hierarchicaí paralłel probabiíistic algorithms. Kybernetika (Prague) 24 (1988), 2, pp. 110-121.
[14] M. Loève: Probability Theory. Van Nostrand, Princeton, 1955. Russian translation: IIL, Moscow, 1962. · Zbl 0066.10903
[15] A. Rényi: Teorie pravděpodobnosti (Probability Theory - in Czech). Academia, Prague 1972.
[16] J. Štěpán: Teorie pravděpodobnosti - matematické základy (Probabilíty Theory - Mathematical Foundations - in Czech). Academia, Prague 1987.
[17] V. A. Uspenskij, A. L. Semenov: What are the gains of the theory of algorithms - basic development connected with the concept of aígorithm and with its application in mathematics. Algorithm in Modern Mathematics and its Appîications - Proceedings of the Symposium, Urgench 1979, pp. 100-234.
[18] I. Kramosil: Hierarchické paralelní pravděpodobnostní algorithmy (Hierarchical Paralle Probabilistic Algorithms - in Czech). Res. Rep. No. 1409, Institute of Information Theory and Automation 1986.
[19] I. Kramosil: Extremum-searching hierarchical parallel probabilistic algorithms. Kybernetika 24 (1988), 2, 110-121. · Zbl 0647.68061 · www.kybernetika.cz · eudml:28283
[20] W. Feller: An Introduction to Probability Theory and its Applications I, II. J. Wiley and Sons, New York, 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian transíation: Mir, Moscovv, 1964, 1967. · Zbl 0138.10207
[21] I. Kramosil: Statistical verification procedures for propositional caiculus. Computers and Artificial Intelligence 2, (1983), 3, 235-258. · Zbl 0529.68066
[22] I. Kramosil, J. Šindelář: Computational complexity of probabilistic searching algorithms over Herbrand universes. Computers and Artifìcial Intelligence 4 (1985), 2, 97-110. · Zbl 0561.68062
[23] W. Feller: An Introduction to Probability Theory and Its Applications I, II. J. Wiley and Sons, New York 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967. · Zbl 0138.10207
[24] A. V. Aho J. E. Hopcroft, J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading 1974. Russian translation: Mir, Moscow 1979. · Zbl 0326.68005
[25] H. Barringer: A Survey of Verification Techniques for Parallel Programs. (Lecture Notes in Computer Science 191.) Springer-Verlag, Berlin-Heidelberg-New York 1985. · Zbl 0566.68002 · doi:10.1007/3-540-15239-3_16
[26] W. Feller: An Introduction to Probability Theory and its Applications I., II. J. Wiley and Sons, New York 1957 (vol. I, 2nd edition), 1966 (vol. II). Russian translation: Mir, Moscow 1964, 1967. · Zbl 0138.10207
[27] I. Kramosil: Parallel probabilistic ordering algorithms with a simple conflict control strategy. Aplikace umele inteligence AI 88, Prague 1988, pp. 39-46.
[28] J. Miklosko, V. E. Kotov: Algorithms, Software and Hardware of Parallel Computers. Springer-Verlag, Berlin-Heidelberg-New York and Veda, Bratislava 1984. · Zbl 0594.68003
[29] J. H. Reif: On synchronous parallel computations with independent probabilistic choice. SIAM J. Comput. 13 (1984), 1, 46-56. · Zbl 0558.68038 · doi:10.1137/0213004
[30] R. Reischuk: A fast probabilistic parallel sorting algorithm. 22nd IEEE Symp. on Foundat. of Comp. Sci., Nashwille, Tennessee 1981.
[31] R. Reischuk: Probabilistic parallel algorithms for sorting and selection. SIAM J. Comput. 14 (1985), 2, 396-409. · Zbl 0578.68040 · doi:10.1137/0214030
[32] I. Kramosil: Hierarchies of parallel probabilistic searching algorithms with possible data access conflicts. Problems Control Inform. Theory 7^(1989), 6, 381 - 395. · Zbl 0796.68067
[33] I. Kramosil: A simulation of partial stochastic co-operation in parallel probabilistic searching algorithms. Artificial Intelligence and Information-Control Systems of Robots 89 - Proceedings of the conference held at Strbske Pleso, 6.- 10. 11. 1989 (I. Plander, North Holland, Amsterdam 1989, pp. 159-162.
[34] S. G. Akl: Parallel Sorting Algorithms. Academic Press, Orlando 1985. · Zbl 0657.68070
[35] Y. Azar, U. Vishkin: Tight comparison bounds on the complexity of parallel sorting. S.AM J. Comput. 16 (1987), 3, 458-464. · Zbl 0654.68070 · doi:10.1137/0216032
[36] P. Bachman, Phan-Mink-Dung: Nondeterministic computations - structure and axioms. Elektron. Informationsverarb. Kybernet. 22 (1986), 5-6, pp. 243-261.
[37] G. Bobrow, A. Collins (eds.): Representation and Understanding. Academic Press, New York 1975. · Zbl 0332.68007
[38] D. J. Boxma: A probabilistic analysis of multiprocessor list scheduling: the Erlang case. Comm. Statist. Stochastic Models 1 (1985), 2, 209-220. · Zbl 0605.68023 · doi:10.1080/15326348508807011
[39] M. Broy: On the Herbrand-Kleene universe for nondeterministic computations. Theoret. Comput. Sci. 36 (1985), 1, 1- 19. · Zbl 0567.68024 · doi:10.1016/0304-3975(85)90027-1
[40] M. Broy: A theory for nondeterminism, parallelism, communication, and concurrency. Theoret. Comput. Sci. 45 (1986), 1, 1-61. · Zbl 0601.68022 · doi:10.1016/0304-3975(86)90040-X
[41] C. L. Chang, R. T. C. Lee: Symbolic Logic and Mechanical Theorem Proving. Academic Press, New York-London 1974
[42] A. Church: Introduction to Mathematical Logic I. Princeton Univ. Press, Princeton, New Jersey 1956 · Zbl 0073.24301
[43] R. Davis, D. B. Lenat: Knowledge-Based Systems in Artificial Intelligence. McGraw-Hill, New York 1982. · Zbl 0479.68093
[44] J. Gill: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6 (1977), 4, 675-695. · Zbl 0366.02024 · doi:10.1137/0206049
[45] M. Karmarkar R. M. Karp G. S. Lueker, A. M. Odlyzko: Probabilistic analysis of optimum partitioning. J. Appl. Probab. 23 (1986), 3, 626-645. · Zbl 0611.60011 · doi:10.2307/3214002
[46] G. A. P. Kindervater, J. K. Lenstra: An introduction to parallelism in combinatorial optimization. Parallel Computers and Computations, CWI Syllabi 9, Math. Centrum Amsterdam, 1985, pp. 163-184. · Zbl 0593.90047
[47] L. Kronsjó: Computational Complexity of Sequential and Parallel Algorithms. J. Wiley and Sons, Chichester 1985. · Zbl 0625.68028
[48] L. Kučera: Kombinatorické algoritmy . (Combinatorial Algorithms - in Czech). SNTL, Prague 1983.
[49] M. Luby: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15 (1986), 4, 1036- 1053. · Zbl 0619.68058 · doi:10.1137/0215074
[50] Z. Manna, R. Waldinger: Special relations in automated deduction. J. Assoc. Comput. Mach. 33 (1986), 1, 1-59. · Zbl 0637.68103 · doi:10.1145/4904.4905
[51] A. N. Maslov: Verojatnostnyje mašiny Turinga i rekursivnyje funkcii. (Probabilistic Turing machines and recursive functions - in Russian). Dokl. Akad. Nauk SSSR 203 (1972), 5, 1018-1020.
[52] D. Mitra: Probabilistic models and asymptotic results for concurrent processing with exclusive and non-exclusive locks. SIAM J. Comput. 14 (1985), 4, 1030-1051. · Zbl 0582.68062 · doi:10.1137/0214072
[53] Parallelnaja obrabotka informacii, vol. 2. (Parallel Information Processing - a collection of papers - in Russian). Nauková dumka, Kijev 1985.
[54] Sborník: Expertní systémy - principy, realizace, využití. (Proceedings: Expert Systems - principles, realizations, applications, V. Zdráhal, V. Mařík. ČSVTS FEL ČVUT, Prague 1984.
[55] Sborník: Metody umělé inteligence a expertní systémy. (Proceedings: Methods of Artificial Intelligence and Expert Systems, Z. Zdráhal, V. Mařík. ČSVTS FEL ČVUT, Prague 1985.
[56] J. R. Shoenfield: Mathematical Logic. Addison-Wesley, Reading 1967 · Zbl 0155.01102
[57] J. R. Smith: Parallel algorithms for depth-first searches - planar graphs. SIAM J. Comput. 75 (1986), 3, 814-830. · Zbl 0612.68059 · doi:10.1137/0215058
[58] J. Sztrik: A probability model for priority processor-shared multiprogrammed computer systems. Acta Cybernet. 7 (1986), 3, 329-340. · Zbl 0587.68035
[59] Wang Hao: A Survey of Symbolic Logic. North-Holland, Amsterdam and China Press, Peking 1962.
[60] D. A. Watermann, L. Hayes-Roth (eds.): Pattern-Directed Interference Systems. Academic Press, New York 1978.
[61] G. Winskel: Category theory and models for parallel computations. Category Theory and Computer Programming (Lecture Notes in Comp. Sci. 240), Springer-Verlag, Berlin-Heidelberg-New York 1987, pp. 266-281.
[62] M. Zaionc: Nondeterministic programs definable in typed lambda-calculus. Fundam. Informaticae 8 (1985), 1, 63-72. · Zbl 0579.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.