Главная Промышленная автоматика.

Хартманис, Льюис, Стирнз (Hartmanis J., Lewis P. М. II, Stearns R. E.)

[1965] Classification of computations by time and memory requirements, Proc. IFIP Congress 65, Spartan, N. Y., 31-35.

Хартманис, Стирнз (Hartmanis J., Stearns R. E.)

[1965] On computational complexity of algorithms, Trans. Amer. Math. Soc, 117, 285-306. (Русский перевод в Кибернетическом сборнике, нов. сер., вып. 4. М., Мир, 1967, стр. 57-85.)

Хартманис, Хопкрофт (Hartmanis J., Hopcroft J. E.)

[1971] An overview of the theory of computational complexity, J. Assoc Comput. Mach., 18, №3, 444-475. (Русский перевод в Кибернетическом сборнике, нов. сер., вып. И, М., Мир, 1974, стр. 131-176.)

Хейндел, Хоровиц (Heindel L. Е., Horowitz Е.)

[1971] On decreasing the computing time for modular arithmetic, IEEE 12th Annual Symposium on Switching and Automata Theory, 126-128.

Хект (Hecht M. S.)

[1973] Global data flow analysis of computer programs, Ph. D. Thesis, Dept. Electr. Engineering, Princeton University.

Хенни, Стирнз (Hennie F. C, Stearns R. E.)

[1966] Two tape simulation of multitape machines, J. Assoc. Comput. Mach.,

13, Я» 4, 533-546. (Русский перевод в сб. «Проблемы математической логики», М., Мир, 1970, стр. 194-211.)

Хиршберг (Hirschberg D. S.)

[1973] А linear space algorithm for computing maximal common subsequences, TR-138, Comput. Sci. Lab., Dept. Electr. Engineering, Princeton University, Princeton, N. J. См. также Comm. ACM, 18, № 6 (1975), 341-343.

Холл (Hall A. D.)

[1971] The ALTRAN system for rational manipulation-a survey. Comm. ACM,

14, №8, 517-521. XoH (Hohn F. E.)

[1958] Elementary matrix algebra, Macmillan, New York.

Xoop (Hoare C. A. R.)

[1962] Quicksort, Comput. J., 5, № I, 10-15.

Хопкрофт (Hopcroft J. E.)

[1971] An n log n algorithm for minimizing states in a finite automata, см. Кохави, Пац [1971], 189-196 (Русский перевод в Кибернетическом сборнике, нов. сер., вып. 11, М., Мир, 1974, стр. 177-184.)

Хопкрофт, Карп (Hopcroft J. Е., Karp R. М.)

[1971] An algorithm for testing the equivalence of finite automata, TR-71-114, Dept. Comput. Sci., Cornell University, Ithaca, N.Y.

Хопкрофт, Керр (Hopcroft J. E., Kerr L. R.)

[ 971] On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., 20, № 1, 30-36.

Хопкрофт, Мусински (Hopcroft J. E., Musinski J.)

[ 973] Duality in determining the complexity of noncommutative matrix multiplication, Proc. 5th Annual ACM Symposium on Theory of Computing, Austin, Texas, 73-87.

Хопкрофт, Тарьян (Hopcroft J. E., Tarjan R. E.)

[1973a] Efficient planarity testing, TR-73-165, Dept. Comput. Sci., Cornell University, Ithaca, N. Y. См. также Л Assoc. Comput. Mach. 21, №4 (1974). [19736] Dividing a graph into triconnected components, SIAM J. Comput., 2, №3, 135-157.

[1973b] Efficient algorithms for graph manipulation. Comm. ACM, 16, №6, 372-378.

Хопкрофт, Ульман (Hopcroft J. E., Ullman J. D.)

[ 969] Formal languages and their relation to automata, Addison-Wesley, Reading, Mass.

[1973] Set merging algorithms, SIAM J. Comput., 2, № 4, 294-303.



Хопкрофт, Уонг (Hopcroft J. Е., Wong J. К-)

[ 974] А linear time algorithm for isomorphism of planar graphs, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 172-

Хорват (Horvath E. C.)

[1974] Some efficient stable sorting algorithms, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 194-215.

Хоровиц (Horowitz E.)

[1972] A fast method for interpolation using preconditioning. Inform. Process. Lett., I, №4, 157-163.

Xy (Hu T. C.)

[1968] A decomposition algorithm for shortest paths in a network., Operat.

Res., 16, 91-102. Xy, Таккер (Hu T. C, Tucker A. C.)

[1971] Optimum binary search trees, SIAM J. AppL Math., 21, № 4, 514-532. Хэдиан, Соубел (Hadian A., Sobel M.)

[1969] Selecting the rth largest using binary errorless comparisons. Tech. Rept.

121, Dept. of Statistics, University of Minnesota, Minneapolis. Цейтин Г. С.

°[1968l О сложности вывода в исчислении высказываний. Записки научн. семинаров Ленингр. отд. Матем. ин-та АН СССР, т. 8, 234-259. Шёнхаге (Schonhage А.)

[1971] Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform., 1, 139-144.

Шёнхаге, Штрассен (Schonhage A., Strassen V.)

[1971] Schnelle Multiplikation grosser Zahlen, Computing, 7, №3-4, 281-292.

(Русский перевод в Кибернетическом сборнике, нов. сер., вып. 10, М., Мир,

1973, стр. 87-98.) Шепердсон, Стерджис (Shepherdson J. С, Sturgis Н. Е.)

[ 963] Computability of recursive functions, J. Assoc. Comput. Mach., 10, № 2,

217-255. Штрассен (Strassen V.)

[1969] Gaussian elimination is not optimal, Numer. Math., 13, №4, 354-356.

(Русский перевод в Кибернетическом сборнике, нов. сер., вып. 7, М., Мир,

1970, стр. 67-70.)

°[1973] Vermeidung von Divisionen, J. Reine Angew. Math., 264, 184-202. [1974J Polynomials with rational coefficients which are hard to compute, SIAM J. Comput., 3, №2, 128-149.

"[1976] Computational complexity over finite fields, SIAM J. Comput. 5, № 2, 234-331.

Элгот, Робинсон (Elgot С. С, Robinson A.)

[1964] Random access stored program machines, J. Assoc. Comput. Mach., II, №4, 365-399.

Эренфойхт, Цайгер (Ehrenfeucht A., Zeiger H. P.)

[1974] Complexity measures for regular expressions, Proc. 6th Annual ACM Symposium on Theory of Computing, Seattle, Washington, 75-79.

Янгер (Younger D. H.)

[1967] Recognition of context-free languages in time я. Inform, and Contr., 10, № 2, 189-208. (Русский переводе сб. «Проблемы математической логики», М., Мир, 1970, стр. 344-362.)



ГЛОССАРИЙ

- сложить (команда сложения)

- и (конъюнкция)

begin

- начало

- сокращение от blank - пустой (символ, обозначаю-

щий пустую клетку ленты)

CHOICE

- выбор

comment

- комментарий

- сокращение от divide - разделить (команда деле-

ния)

-делать

else

- иначе, в противном случае

- конец

exclusive or -

false for goto HALT if ... then in

JGTZ

JUMP JZERO

LOAD MULT

otherwise

исключающее или (разделительная дизъюнкция, или сложение по модулю два) ложь, ложный для

то же, что go to-перейти к остановиться (команда остановки) если ... то в

сокращение от jump on greater than zero-перейти (к указанной команде), если (содержимое сумматора) больше нуля, -перейти (безусловный переход) сокращение от jump on zero (разъясняется аналогично JGTZ, но переход при равенстве содержимого сумматора нулю)

сокращение от left-влево (сдвиг головки влево) загрузить (вызов в сумматор) сокращение от multiply-умножить (команда умножения)

•не (отрицание)

•в противном случае





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 [167] 168 169 170 171 172 173 174

0.0039