Previous |  Up |  Next


computer science and automata
In this paper several methods for constructing tables without repetition of items are studied from the probabilstic point of view. Formulae for expected values of the number of examinations of the kind "is $x$ placed in cell $T_i$ in a table $T$?" are given. The situation when a table $T$ is placed on a backing store of a computer and segmented is also considered. Described methods are very useful in many systems of information processing.
[1] Г. M. Аделъсон-Велъский E. M. Ландис: Один алгоритм организации информации. ДАН 146, № 2, (1962). Zbl 1226.30001
[2] А. П. Ершов Г. И. Кожухин И. В. Поттосин: Обзор особенностей альфа-транслятора. Альфа система автоматизации программирования под редакцией А. П. Ершова, Новосибирск 1965 (the English translation of this paper is in J. of ACM, Jan. 1966). Zbl 1225.00032
[3] W. W. Peterson: Adressing for random-access storage. IBM J. Res. and Devel. 4, No 4, (1957). MR 0085633
[4] 3. К. Иванова: О выборе функции расстоновки для организации табличных просмотров. Отчет ВЦ СО АН СССР, Новосибирск 1961. Zbl 1160.68305
[5] К. И. Курбаков: Способ адресации, использующий сжатые коды слов в качестве адресов памяти. ДАН 163, № 4, 841-844 (1965). Zbl 1099.01519
[6] Shay G., Raver N.: A method for key-to-address transformation. IBM J. Res. and Devel. 7, 121-132, No 2, (1963).
[7] Л. А. Хиздер: Некоторые свойства диадических деревев. Ж. В. M. M. Ф. 6, 389-394, № 2 (1956). Zbl 0995.90522
[8] W. Feller: An Introduction to Probability Theory and its Applications. Vol. 1, J. Willey, New York 1950. Zbl 0039.13201
[9] R. Morris: Scatter storage techniques. Comm. of ACM 11, 38-44, No. 1, (1968). DOI 10.1145/362851.362882
Partner of
EuDML logo